CSCI 235 Fall 2023 Term Project
Algorithmic Adventures II: Exponential Creature Odyssey
Project 7 - Binary Skill Tree
While our Creatures know how to fight, our wizard boss wants to know how their skills may progress over time. To do this, we will implement a Binary Skill Tree that will allow us to track the skills of our Creatures!
The link to accept the GitHub Classroom assignment can be found on Blackboard
You are given the BinaryNode and BinarySearchTree classses. You will implement the SkillTree class as a subclass of BinarySearchTree that stores Skills.
Implementation
Work through the tasks sequentially (implement and test). Only move on to a task when you are positive that the previous one has been completed correctly. Remember that the names of classes and methods must exactly match those in this specification (FUNCTION NAMES, PARAMETER TYPES, RETURNS, PRE AND POST CONDITIONS MUST MATCH EXACTLY).
Remember, you must thoroughly document your code!!!
Task 1: Implement the Skill struct
The Skill struct must be defined in SkillTree.hpp but outside the SkillTree class definition, and holds the following public members:
Data members
- int id_ // A unique identifier for the Skill- string name_ // The name of the Skill- string description_ // The description of the Skill- bool leveled_ // Whether or not the Skill is leveled up
Constructors
// Default constructor// Parameterized constructor/*** @param id: The unique identifier for the Skill* @param name: The name of the Skill* @param description: The description of the Skill* @param leveled: Whether or not the Skill is leveled up*/
Methods
/*** @param: A const reference to Skill* @return: True if the id_ of the Skill is equal to that of the argument, false otherwise*/operator==/*** @param: A const reference to Skill* @return: True if the id_ of the Skill is less than that of the argument, false otherwise*/operator</*** @param: A const reference to Skill* @return: True if the id_ of the Skill is greater than that of the argument, false otherwise*/operator>
Task 2: Implement the SkillTree class as a subclass of BinarySearchTree that stores Skills
####
The SkillTree class must define the following public members.
Constructors
/*** Default Constructor*//*** @param: A const reference to string: the name of a csv file* @post: The SkillTree is populated with Skills from the csv file* The file format is as follows:* id,name,description,leveled* Ignore the first line. Each subsequent line represents a Skill to be added to the SkillTree.*/
Methods
/*** @param: A const reference to int representing the id of the Skill to be found* @return: A pointer to the node containing the Skill with the given id, or nullptr if the Skill is not found*/findSkill/*** @param: A const reference to Skill* @post: The Skill is added to the tree (in BST order as implemented in the base class) only if it was not already in the tree. Note that all comparisons are id-based as implemented by the Skill comparison operators.* @return: True if the Skill is successfully added to the SkillTree, false otherwise*/addSkill/*** @param: A const reference to string: the name of a Skill* @return: True if the Skill is successfully removed from the SkillTree, false otherwise*/removeSkill/*** @post: Clears the tree*/clear/*** @param: A const reference to int representing the id of a Skill* Note: For a Skill to be leveled up, its parent Skill must also be leveled up, thus the Skill points are the number of Skills that must be leveled up before and including the Skill with the given id.* @return: an integer: the number of skill points needed to level up the Skill with the given id, starting from the root (i.e. the number of nodes from root to the given Skill).* Include the Skill with the given id in the count. For example, if the tree contains the following Skills (represented by their ids):* 5* / \* 1 8* and the function parameter queries for id 8, the function should return 2.* Disregard the leveled_ field of the existing Skills in the tree.* If the Skill with the given id is not found, return -1.*/calculateSkillPoints/*** @post: Balances the tree. Recall the definition of a balanced tree:* A tree is balanced if for any node, its left and right subtrees differ in height by no more than 1. * All paths from root of subtrees to leaf differ in length by at most 1* Hint: You may sort the elements and build the tree recursively using a divide and conquer approach*/balance/*** @post: prints the tree in preorder, in the format:[id_] [name_]\n[description_]\n[leveled_]*/preorderDisplay()
Testing
How to compile with your Makefile:
In terminal, in the same directory as your Makefile and your source files, use the following command
make rebuild
This assumes you did not rename the Makefile and that it is the only one in the current directory.
You must always implement and test your programs INCREMENTALLY!!! What does this mean? Implement and TEST one method at a time. For each class:
Implement one function/method and test it thoroughly (write a main file with multiple test cases + edge cases if applicable).
Only when you are certain that function works correctly and matches the specification, move on to the next.
Implement the next function/method and test in the same fashion. How do you do this? Write your own
main()function to test your classes. Choose the order in which you implement your methods so that you can test incrementally: i.e. implement constructors then accessor functions, then mutator functions. Thoroughly test with valid and invalid input to check that your function behaves as expected in each case. Pay special attention to edge cases. Sometimes functions depend on one another. If you need to use a function you have not yet implemented, you can use stubs: a dummy implementation that always returns a single value for testing. Don’t forget to go back and implement the stub!!! If you put the word STUB in a comment, some editors will make it more visible.
Grading Rubric
Correctness 100% (distributed across unit testing of your submission)
No style and documentation points for this last project.
Important: You must start working on the projects as soon as they are assigned to detect any problems with submitting your code and to address them with us well before the deadline so that we have time to get back to you before the deadline.
There will be no negotiation about project grades after the submission deadline.
Submission:
We will grade the following :
SkillTree.hpp
SkillTree.cpp
Although Gradescope allows multiple submissions, it is not a platform for testing and/or debugging and it should not be used for that. You MUST test and debug your program locally. To help you not rely too much on Gradescope for testing, we will only allow 5 submissions per day. Before submitting to Gradescope you MUST ensure that your program compiles using the provided Makefile and runs correctly on the Linux machines in the labs at Hunter (see detailed instructions on how to upload, compile and run your files in the “Programming Guidelines” document). That is your baseline, if it runs correctly there it will run correctly on Gradescope, and if it does not, you will have the necessary feedback (compiler error messages, debugger or program output) to guide you in debugging, which you don’t have through Gradescope. “But it ran on my machine!” is not a valid argument for a submission that does not compile. Once you have done all the above you submit it to Gradescope.
Due date:
This project is due on May 14 No late submissions will be accepted.
Important
You must start working on the projects as soon as they are assigned to detect any problems and to address them with us well before the deadline so that we have time to get back to you before the deadline. There will be no extensions and no negotiation about project grades after the submission deadline.
Help
Help is available via drop-in tutoring in Lab 1001B (see website for schedule). You will be able to get help if you start early and go to the lab early. We only have 3 UTAs in the lab, the days leading up to the due date will be crowded and you will not be able to get much help then.**
Authors: Georgina Woo, Tiziana Ligorio