CS3021 Program Assignment 3

Preparation" Review the materials up to and including OOP, template, and binary search trees. The primary focus of this assignment is the creation of an abstract data type OrderedList using the C++ template feature and the binary search tree. The implementation is based on the sample class BST. Problem Statement" An ordered list is a linear sequence of ordered (sorted) items. When you insert a new item into the ordered list, the item is inserted into a position to maintain the order. Here's an example using integer elements. Suppose the ordered list is (in abstract notation; not the actual C++ statement)! ! ! L = ( 2, 34, 55, 89, 100, 230, 334, 989 ) then L.insert(94) (or L-insert(94) depending on how you declared L) will result in ! ! L = ( 2, 34, 55, 89, 94, 100, 230, 334, 989 ) Your task for this assignment is to implement the OrderedList class that supports update, query, and scanning operations.! ! Specification" Here’s the declaration of the OrderedList class.! ! template <class T class! OrderedList { public! : OrderedList(); ! ~OrderedList(); //--------- Update Operations ----------------------------// void insert(T* item); !! void remove(T* item); //--------- Access Operations ----------------------------// T* first( ); T* last( ); T* next( ); ! T* prev( ); T* at(int idx); ! T* search(T* item); ! vector<T* scan( ); //----------------- Queries ----------------------------// int size( ); bool isEmpty( ); ! private: //include private data members and functions of your design }; Operations" Please read the specification for each function very, very carefully. ! Function Specification void insert(T* item) Insert an item into the ordered list in the correct position so the ascending order is maintained after the insertion. For simplicity, assume the item is not a duplicate of any existing items in the ordered list. The current node becomes undefined after a successful insertion; see the section titled Notion of Current. void remove(T* item) Delete the designated item from the ordered list. If the designated item is not found, do nothing. If the item is an object, then you only need to pass an item with the key field value specified. The current node becomes undefined after a successful deletion; see the section titled Notion of Current. T* search(T* item) Search for and return the designated item in the ordered list. If the item is not found, return NULL. If the item to search is an object, then you only need to pass an item with the key field value specified. See the provided sample main on how the search is done with a Pet object. T* first( ) Return the first item in ascending order. Return NULL if the ordered list is empty. T* last( ) Return the last item in ascending order. Return NULL if the ordered list is empty. Function Specification T* next( ) Return the next item in ascending order. When there is no next item, then return NULL. To retrieve the first three items in the tree, for example, you can call first(), next(), and next(). The the section Notion of Current provides the detail of the next and prev operations. T* prev( ) The inverse operation of next. The section Notion of Current provides the detail of the next and prev operations. T* at(int idx) Return the item at the idx’s position in ascending order. The first item is at position 0, and the last item at position size()-1. Return NULL for any invalid index position. vector<T* scan( ) Return the items in the ordered list as a vector. The items are returned in ascending order. If the tree is empty, then return an empty vector, i.e., a vector with no elements, not a NULL. int size( ) Return the number of items in the ordered list. bool isEmpty( ) Return true if the ordered list is empty; otherwise, return false. Notion of Current" In order to implement the access operations first, last, next, and prev, we need to support the notion of the current node. Include a data member in the class to keep track of the current node. Initially, the current node is undefined (NULL). When you call the first or the next function, the first node (in ascending order) becomes the current node. Similarly, when the current node is undefined, and you call the last or the prev function, the last node becomes the current node. After the current node is set, calling the next and prev function updates the current node to the next or previous node (in ascending order). If the current node is the last node, then calling the next function returns NULL, and the current node is not changed. That is, it points to the last node. It does not become NULL. If the current node is the first node, then calling the prev function returns NULL, and the current node is not changed.! The current node gets undefined (NULL) after a successful insert or delete operation. So, for example, if you execute first(), next(), next(), insert(x), next(), you will get the first node back after the last next() call. Notice the current node changes to NULL only after a successful update operation. If the update operation is not successful, then there is no structural change in the ordered list. Thus, the current node needs to be the same as before the (unsuccessful) update operation.! Member Object" To be able to organize and manage objects in the structure, the concrete type (primitives like int and classes like Pet) that replaces the template type T of the OrderedList class must support the comparison operations < and == and the stream output operation <<. The OrderedList class implementation should not assume any more than these three operations.! ! Requirements" 1. All functions must have good performance. For example, you should not implement the at function by first calling the scan function and returning the i’th data in the vector. You should implement the at function without scanning the complete tree. Likewise, make sure your other access functions first, last, next, and prev perform well. ! 2. There should be absolutely NO input and output statements in the functions. You may place temporary I/O statements in a function for testing/debugging purposes during the development, but you must remove them before the submission.! 3. DO NOT CHANGE the public member functions defined in the file OrderedList.h. The instructor's test program will import functions from your module so it is critical that the function signatures are not changed. ! 4. DO NOT ADD any new public member functions to the OrderedList class. But, you may add as many private data members and private helper functions as you wish.! 5. Functions you define in the program should not access any global variables, those define outside of the class. Use of the global symbolic constants is fine.! 6. Because you are submitting only a single source file, be sure to include a header comment in the file to record your name, the course number, the assignment number, and any detailed explanation of your functions as appropriate.! 7. Format the program in a clean manner. Group statements into logical groups and include a descriptive comment for each group. Group comments do not have to be verbose. One sentence would suffice if the statements in a group are written correctly and precisely. Include enough blank lines between logical groups.! 8. Insert one or more blank lines between statements as necessary to make the code more readable and easier to follow. Do not pack statements too densely (e.g., 20 statements with no blank lines between them).! 9. Use comments judiciously. Do not include redundant and meaningless comments.! Starter Code" The following source files are provided to you.! Filename Description orderedlist.h The source file for the template class OrderedList. Do not make any changes to the public segment of the class declaration. The private segment, however, is under your complete control. pet.h and pet.cpp The Pet class header and implementation files. See the example in the main program on how to create and manipulate an ordered list of Pet objects. prog3tester.cpp This sample main program illustrates a basic interaction with an ordered list. Review the code here to confirm your understanding of the expected behavior of an ordered list is correct. ! ! ! Starter code is provided in two format.! 1. Eclipse project named Prog3. You can import this project using the menu option Import... and select the option General-Existing Projects into Workspace. The project is provided in the zip format Prog3.zip.! 2. Plain source files orderedlist.h, pet.h, pet.cpp, and progetester.cpp. You can create an empty C++ project and then import these files into the project.! There’s also a single text file sampleoutput.txt that contains an output from running the provided prog3tester.cpp. This is the output you expect to receive when your OrderedList implementation is correct and complete.! Development Ideas" Review the BST class implementation. This class is the model you follow to complete this assignment. Many of the functions in the OrderedList class are identical to those in the BST class (disregarding the obvious naming differences, e.g., find vs. search, BST vs. OrderedList, etc.). You can reuse the BSTNode class in this assignment.! First, implement the functions that have counterparts in the BST class. Many of these can be implemented with copy-and-paste.! Next, implement the access functions. Implement the first and the last functions. Then, implement the prev and the next functions. Finally, implement the at function. The at function is similar to the inorder traversal of the binary search tree, but in the at function, you must keep track of the order of the node visits. You can implement the at function with a recursive or norecursive helper function. A non-recursive version requires a stack.! Incremental Development" Here’s the suggested order of development (assuming you’re starting with the provided OrderedList.h). ! 1. Implement insert! 2. Implement scan! 3. Implement search! 4. Implement first and last! 5. Implement next and prev! 6. Implement remove! 7. Implement at! 8. Implement the destructor! ! Testing the Functions" As was the case with the previous assignments, create an adequate number of test data and carry out exhaustive tests. Make sure you carry out adequate number of tests after each step and integral tests at several points in the development (e.g., after Step 3, test three functions collectively with a large data set). Coming up with a good set of tests is the best way to construct bug-free code. You need to think very carefully in formulating test routines.! Submission" Submit the source file orderedlist.h, that fully implements the OrderedList class, via the Sakai course website’s Program Assignment 3 page. You are only required to submit this source file. On the submission due date, you will be asked to make modifications to the orderedlist.h file and submit the modified version also.!