also also here s header fle

head tail listen 16 next len values next len values 1 9 next len values 2 10 12 next len values 4 2 5 4 2 8 0 1 null 5 2 7 0 -1 2 Each chunk contains a fixed size Tarray (in the above example T is an int), an int to track how full the chunk is, and a pointer to the next chunk The type T should be defined by the template as shown in the examples given in class There should be a constant ARRAY_SIZE = 8 that defines the fixed size of the array of each chunk. Elements should be added to the array 8 starting at its index o listen shows the length of the entire length len shows the length of a node. . . An empty Chunklist should be implemented as null head and tail pointers. Your Chunklist should allocate chunks only when actually needed and delete them when no longer needed. Unit Test Dependencies - IMPORTANT Many of the tests depend on certain functions to work in order for the tests to pass successfully. Here is a table of the dependencies. Unit test Dependencies Constructor Test Constructors. Append. Contains, GetLength Append_Remove_Test Append. Remove. Contains LoadFactor Index Test Append, Remove. GetIndex Iterator Test Append. Remove, Resetiterator, GetNextitem For example, the Constructor_Test requires Append. GetLength and contains to work for the test to work properly, Recommended Implementation Order The following is a recommended order to implement the functions. This is not mandatory, but you may find it helpful to follow this order. 1. Chunklist() 2. GetLength) 3. LoadFactor) 4. Append() T 5. Contains() 6. Remove(1) 7. Chunklistar, arrien) , 8. GetIndex(int) 9. ResetIterator(). Setiextiten) Function Description Each section below describes how each function should behave. Be sure to read the descriptions carefully Chunklist() The default constructor should create an empty Chunklist. An empty Chunklist should be implemented as null head and tail pointers You . should also initialize the variables related to the iterator, Chunklist(T[] arr, arrlen) This constructs a Chunklist using the values from arr. It should append all the values from ar to the list. The parameter arrlen is the length of arr. If arten is an invalid array length, you should throw a InvalidirayLength . You should initialize the iterator to start at the beginning of the list HINT: You should use the Append function here. -Chunklist(); This is the deconstructor for the list. It will remove all the nodes in the list. In this particular case, it will actually be the same code as we used in other implementations of linked lists we cover in class. Note that while this function is not graded you should probably implementit int GetLength() GetLength should return the length of the entire list. It does not return the number of nodes/chunks. For example, in this example GetLength function should retum 16. head tail listten 16 - next len values next len values 1 9 next len values 2 10 12 next len values 8 8 4 2 5 4 2 null 5 2 7 0 2 0 1 HINT: You should update the length any time you add/remove items double LoadFactor() The load factor is the following value tells us what percentage of the Chunklist is actually storing items. It is calculated using the following: Ioad factor - listten/ (total number of spots in the Chunklist) This function should throw an EmptyList() error if the list is empty. Example: The load factor of the the following Chunktist is load factor - 16/(04) - 0.5 This means that only 50% of the Chunklist space is being used to store items. The other 50% is empty head tail listLen 16 next len values 8 4 next len values 1 9 next len values 2 10 12 next len values null 5 2 7 0 2 5 4 2 - 1 2 bool Contains (T value) This function returns true if value exists in the Chunklist. To do this, you need to check the array of each node until you find value or you reach the end of the list without finding value. This function should throw an EmptyList() error if the list is empty and you attempt to find an item. Here is a rough algorithm while(current mode has not reached the end of the list) for (each Index in the current node) if values[Index) of the current node is the value you are looking for return true > return false void Append(T value) This function appends value to the end of the list. This function should do the following Attempt to add the value to the last position of the last node If the last node is full when you try to add valve, then a new node should be created and placed at he end of the list. valve can then be added to this new last node Be sure to update any bookkeeping variable! Example: Suppose we add the value 7 to the following list Before adding head tail listten 15 next len values next len values 2 10 12 next len values B 4 2 2 5 4 4 2 null 8 2 7 7 0 -1 2 4 5 6 0 Since the last node is full we need to make a new node and add it to the end. The 7 would then be placed at the first position of the new node After adding 7 head tail listLen 16 4 2 - 1 2 bool Contains (T value) This function returns true if value exists in the Chunklist. To do this, you need to check the array of each node until you find value or you reach the end of the list without finding value. This function should throw an EmptyList() error if the list is empty and you attempt to find an item. Here is a rough algorithm while(current mode has not reached the end of the list) for (each Index in the current node) if values[Index) of the current node is the value you are looking for return true > return false void Append(T value) This function appends value to the end of the list. This function should do the following Attempt to add the value to the last position of the last node If the last node is full when you try to add valve, then a new node should be created and placed at he end of the list. valve can then be added to this new last node Be sure to update any bookkeeping variable! Example: Suppose we add the value 7 to the following list Before adding head tail listten 15 next len values next len values 2 10 12 next len values B 4 2 2 5 4 4 2 null 8 2 7 7 0 -1 2 4 5 6 0 Since the last node is full we need to make a new node and add it to the end. The 7 would then be placed at the first position of the new node After adding 7 head tail listLen 16 . next len values next len values next len next len 2 10 12 null 1 7 values values 8 4 2 5 4 2 8 0 1 8 2 7 0 -1 2 4 5 6 void Remove(T value) This function should find the first instance of value and remove it from the list. When it removes the element, it should preserve the order of the list. In other words, the order of the other elements of the list should not be changed. You will need to shift elements in the node in order to accomplish this. This function should throw an aptylist() error if the list is empty and you attempt to remove an item. Below we show several scenarios your remove function should be able to handle NOTE THESE EXAMPLES DO NOT COVER ALL THE CASES YOUR REMOVE SHOULD BE ABLE TO HANDLE Example: Removing from a node Suppose we remove from the following list Before removal bend Ben 10 net net 10 val 2 7 O -1 3 5 After removal bead tail isten no next len val values 7 2 10 12 S Example: Removing the last element in a node Suppose we remove from the following list Before removal head tail listen 16 next len values next len values 1 9 next len values 2 10 12 next len values null 8 2 7 0 8 4 2 5 4 2 8 0 1 2 2 3 3 5 6 Removing 9 would make the node empty. This means you would remove the node. After removal head tail listten 15 . next len values 8 4 next len values 2 10 12 next len values 2 5 4 2 8 0 1 null 5 2 7 0 -1 2 Example: Removing last element in the head Suppose we remove from the following list Before removal head tail listen 8 . next len values 1 9 next len values 2 10 12 next len values null 8 2 7 0 -1 2 3 5 6 Removing 9 would make the head empty. If this happens, then you should delete the old head and update the head pointer After removal head tail . listien 7 next len next len null 8 2 will be within the first node since I curr->lon In this case we return curr-> values). Example: Suppose we call Get Index(7) head tail listien 16 next next len values len 1 9 9 next len values next len values 2 10 12 values null 5 2 2 7 0 8 14 12 5 4 2 8 0 11 - 1 2 1 will be within the first node since I curren Example: Suppose we call BetIndex(9) Ultimately, this should return the oth element of the 3rd node, which is the value 10. Let's apply the algorithm. Drawing a picture for , a yourself is highly recommended. head listen 16 next len values next len values . 1 9 next len values 2 10 12 next | len values 8 4 2 5 4 2 2 8 0 1 1 null 5 2 7 0 -1 2 will NOT be within the first node is NOT less than curren in this case Since we know we are not in the first node, we will need move cure to the next node. Before we move to the next node, we update 1 1. Curran I would now have the value 1 After updating 1, we update cure be the next node and check 1 c currle Note that curr->lon is now 1 This is because the second node only has 1 element in the array fie cure is now the node with single 9 in it). will NOT be within the curr node since 1 is NOT less than curren - curren in this case We update 1 - cure So now I now has the value 0. After updating we move come to the next node. is within the curr node since I currlen We return the value cure values which is 10 #ifndef CHUNKLIST_CHUNKLIST_H adefine CHUNKLIST_CHUNKLIST_M #include 1 using namespace std; const int ARRAY_SIZE = 8; 1 14 16 1/ These error classes are done. No modifications are required. Il See Chunklist_demo.cpp for an example of how they are used. class InvalidArrayLength public: string Msgot return "Invalid array length used for constructor."; 3 10 1 22 class IndexOutOfBounds public: string Msg return "Index is out of bounds"; > 20 29 30 31 class IteratorOutOfBounds { public: string Msg() { return "Iterator is out of bounds. Nothing left to iterate over."; 3 33 35 30 3 class Emptylist public: string Msg() { return "List is empty": 3 1/ Put your pre/post conditions here. template class Chunklist ( public: 1/ Constructors Chunklist(); Chunklist(T arr[], int arrlen); 5 5 52 53 // Deconstructor -Chunklist(); 5 56 57 58 59 1/ Add/remove elements void Append(T value); void Remove(T value); // Stuff to find out about the Chunktist int GetLength(); double LoadFactor(); bool Contains (T value); 62 65 1/ Accessing elements T GetIndex(int i); void ResetIterator(); T GetNextItem(); 68 bool IsEmpty(); private: 72 74 75 1/ Note we did not need to make this a template 11 since this struct is part of a template class. struct Node Node* next; int len; I values[ARRAY_SIZE] 76 SE 81 Node" head; Node" tail; 82 8 // iterator Node* iterNode; int arrPos; // What node are were currently on? 1/ Within the node, what element are we looking at? BE BE int listLen; int numChunks; // Total elements // Total chunksodes 93 #include "Chunklist.cpp" Pendif //CHUNKLIST_CHUNKLIST H head tail listen 16 next len values next len values 1 9 next len values 2 10 12 next len values 4 2 5 4 2 8 0 1 null 5 2 7 0 -1 2 Each chunk contains a fixed size Tarray (in the above example T is an int), an int to track how full the chunk is, and a pointer to the next chunk The type T should be defined by the template as shown in the examples given in class There should be a constant ARRAY_SIZE = 8 that defines the fixed size of the array of each chunk. Elements should be added to the array 8 starting at its index o listen shows the length of the entire length len shows the length of a node. . . An empty Chunklist should be implemented as null head and tail pointers. Your Chunklist should allocate chunks only when actually needed and delete them when no longer needed. Unit Test Dependencies - IMPORTANT Many of the tests depend on certain functions to work in order for the tests to pass successfully. Here is a table of the dependencies. Unit test Dependencies Constructor Test Constructors. Append. Contains, GetLength Append_Remove_Test Append. Remove. Contains LoadFactor Index Test Append, Remove. GetIndex Iterator Test Append. Remove, Resetiterator, GetNextitem For example, the Constructor_Test requires Append. GetLength and contains to work for the test to work properly, Recommended Implementation Order The following is a recommended order to implement the functions. This is not mandatory, but you may find it helpful to follow this order. 1. Chunklist() 2. GetLength) 3. LoadFactor) 4. Append() T 5. Contains() 6. Remove(1) 7. Chunklistar, arrien) , 8. GetIndex(int) 9. ResetIterator(). Setiextiten) Function Description Each section below describes how each function should behave. Be sure to read the descriptions carefully Chunklist() The default constructor should create an empty Chunklist. An empty Chunklist should be implemented as null head and tail pointers You . should also initialize the variables related to the iterator, Chunklist(T[] arr, arrlen) This constructs a Chunklist using the values from arr. It should append all the values from ar to the list. The parameter arrlen is the length of arr. If arten is an invalid array length, you should throw a InvalidirayLength . You should initialize the iterator to start at the beginning of the list HINT: You should use the Append function here. -Chunklist(); This is the deconstructor for the list. It will remove all the nodes in the list. In this particular case, it will actually be the same code as we used in other implementations of linked lists we cover in class. Note that while this function is not graded you should probably implementit int GetLength() GetLength should return the length of the entire list. It does not return the number of nodes/chunks. For example, in this example GetLength function should retum 16. head tail listten 16 - next len values next len values 1 9 next len values 2 10 12 next len values 8 8 4 2 5 4 2 null 5 2 7 0 2 0 1 HINT: You should update the length any time you add/remove items double LoadFactor() The load factor is the following value tells us what percentage of the Chunklist is actually storing items. It is calculated using the following: Ioad factor - listten/ (total number of spots in the Chunklist) This function should throw an EmptyList() error if the list is empty. Example: The load factor of the the following Chunktist is load factor - 16/(04) - 0.5 This means that only 50% of the Chunklist space is being used to store items. The other 50% is empty head tail listLen 16 next len values 8 4 next len values 1 9 next len values 2 10 12 next len values null 5 2 7 0 2 5 4 2 - 1 2 bool Contains (T value) This function returns true if value exists in the Chunklist. To do this, you need to check the array of each node until you find value or you reach the end of the list without finding value. This function should throw an EmptyList() error if the list is empty and you attempt to find an item. Here is a rough algorithm while(current mode has not reached the end of the list) for (each Index in the current node) if values[Index) of the current node is the value you are looking for return true > return false void Append(T value) This function appends value to the end of the list. This function should do the following Attempt to add the value to the last position of the last node If the last node is full when you try to add valve, then a new node should be created and placed at he end of the list. valve can then be added to this new last node Be sure to update any bookkeeping variable! Example: Suppose we add the value 7 to the following list Before adding head tail listten 15 next len values next len values 2 10 12 next len values B 4 2 2 5 4 4 2 null 8 2 7 7 0 -1 2 4 5 6 0 Since the last node is full we need to make a new node and add it to the end. The 7 would then be placed at the first position of the new node After adding 7 head tail listLen 16 4 2 - 1 2 bool Contains (T value) This function returns true if value exists in the Chunklist. To do this, you need to check the array of each node until you find value or you reach the end of the list without finding value. This function should throw an EmptyList() error if the list is empty and you attempt to find an item. Here is a rough algorithm while(current mode has not reached the end of the list) for (each Index in the current node) if values[Index) of the current node is the value you are looking for return true > return false void Append(T value) This function appends value to the end of the list. This function should do the following Attempt to add the value to the last position of the last node If the last node is full when you try to add valve, then a new node should be created and placed at he end of the list. valve can then be added to this new last node Be sure to update any bookkeeping variable! Example: Suppose we add the value 7 to the following list Before adding head tail listten 15 next len values next len values 2 10 12 next len values B 4 2 2 5 4 4 2 null 8 2 7 7 0 -1 2 4 5 6 0 Since the last node is full we need to make a new node and add it to the end. The 7 would then be placed at the first position of the new node After adding 7 head tail listLen 16 . next len values next len values next len next len 2 10 12 null 1 7 values values 8 4 2 5 4 2 8 0 1 8 2 7 0 -1 2 4 5 6 void Remove(T value) This function should find the first instance of value and remove it from the list. When it removes the element, it should preserve the order of the list. In other words, the order of the other elements of the list should not be changed. You will need to shift elements in the node in order to accomplish this. This function should throw an aptylist() error if the list is empty and you attempt to remove an item. Below we show several scenarios your remove function should be able to handle NOTE THESE EXAMPLES DO NOT COVER ALL THE CASES YOUR REMOVE SHOULD BE ABLE TO HANDLE Example: Removing from a node Suppose we remove from the following list Before removal bend Ben 10 net net 10 val 2 7 O -1 3 5 After removal bead tail isten no next len val values 7 2 10 12 S Example: Removing the last element in a node Suppose we remove from the following list Before removal head tail listen 16 next len values next len values 1 9 next len values 2 10 12 next len values null 8 2 7 0 8 4 2 5 4 2 8 0 1 2 2 3 3 5 6 Removing 9 would make the node empty. This means you would remove the node. After removal head tail listten 15 . next len values 8 4 next len values 2 10 12 next len values 2 5 4 2 8 0 1 null 5 2 7 0 -1 2 Example: Removing last element in the head Suppose we remove from the following list Before removal head tail listen 8 . next len values 1 9 next len values 2 10 12 next len values null 8 2 7 0 -1 2 3 5 6 Removing 9 would make the head empty. If this happens, then you should delete the old head and update the head pointer After removal head tail . listien 7 next len next len null 8 2 will be within the first node since I curr->lon In this case we return curr-> values). Example: Suppose we call Get Index(7) head tail listien 16 next next len values len 1 9 9 next len values next len values 2 10 12 values null 5 2 2 7 0 8 14 12 5 4 2 8 0 11 - 1 2 1 will be within the first node since I curren Example: Suppose we call BetIndex(9) Ultimately, this should return the oth element of the 3rd node, which is the value 10. Let's apply the algorithm. Drawing a picture for , a yourself is highly recommended. head listen 16 next len values next len values . 1 9 next len values 2 10 12 next | len values 8 4 2 5 4 2 2 8 0 1 1 null 5 2 7 0 -1 2 will NOT be within the first node is NOT less than curren in this case Since we know we are not in the first node, we will need move cure to the next node. Before we move to the next node, we update 1 1. Curran I would now have the value 1 After updating 1, we update cure be the next node and check 1 c currle Note that curr->lon is now 1 This is because the second node only has 1 element in the array fie cure is now the node with single 9 in it). will NOT be within the curr node since 1 is NOT less than curren - curren in this case We update 1 - cure So now I now has the value 0. After updating we move come to the next node. is within the curr node since I currlen We return the value cure values which is 10 #ifndef CHUNKLIST_CHUNKLIST_H adefine CHUNKLIST_CHUNKLIST_M #include 1 using namespace std; const int ARRAY_SIZE = 8; 1 14 16 1/ These error classes are done. No modifications are required. Il See Chunklist_demo.cpp for an example of how they are used. class InvalidArrayLength public: string Msgot return "Invalid array length used for constructor."; 3 10 1 22 class IndexOutOfBounds public: string Msg return "Index is out of bounds"; > 20 29 30 31 class IteratorOutOfBounds { public: string Msg() { return "Iterator is out of bounds. Nothing left to iterate over."; 3 33 35 30 3 class Emptylist public: string Msg() { return "List is empty": 3 1/ Put your pre/post conditions here. template class Chunklist ( public: 1/ Constructors Chunklist(); Chunklist(T arr[], int arrlen); 5 5 52 53 // Deconstructor -Chunklist(); 5 56 57 58 59 1/ Add/remove elements void Append(T value); void Remove(T value); // Stuff to find out about the Chunktist int GetLength(); double LoadFactor(); bool Contains (T value); 62 65 1/ Accessing elements T GetIndex(int i); void ResetIterator(); T GetNextItem(); 68 bool IsEmpty(); private: 72 74 75 1/ Note we did not need to make this a template 11 since this struct is part of a template class. struct Node Node* next; int len; I values[ARRAY_SIZE] 76 SE 81 Node" head; Node" tail; 82 8 // iterator Node* iterNode; int arrPos; // What node are were currently on? 1/ Within the node, what element are we looking at? BE BE int listLen; int numChunks; // Total elements // Total chunksodes 93 #include "Chunklist.cpp" Pendif //CHUNKLIST_CHUNKLIST H