Modify Nodes for dynamic memory

- Change the nexts array to be a pointer to ListNode* (ListNode**)

- Given the number of nexts passed in from the List, generate a new dynamic array of ListNode* size of num of nexts.

- Add functionality to return underlying address stored in the nexts array (overload array operator)

- If you are unable to figure this part out. Modify your original list function to add the nodes properly.

- Create a destructor to clean up memory.

Add Traversal

- Add functionality to print out the skiplist at every level. (ie: print(5) will print the skipList at the x+1th index level)

 #ifndef SKIPLIST_H_ #define SKIPLIST_H_ #include "ListNode.h" #include  #include  template  class SkipList { public: SkipList() { head = new ListNode*[100]; } /** * @brief Destroy the Linked List object * */ ~SkipList() { clearList(); delete[] head; } /** * @brief Get the Head object * * @return ListNode */ ListNode *getHead(int level) { return head[level]; } void add(T payload); void remove(T target); std::ostream &print(std::ostream &strm) const; void testNumNexts(); private: int numNexts(double probability = -1); ListNode* findLocation(T target, ListNode* start, int level); int numNodes = 0; void clearList(); ListNode **head = nullptr; }; /** * @brief This function adds a new node to the list at the head * * @note Modified 1/29 to change to ordered list. * * @tparam T * @param payload */ template  void SkipList::add(T payload) { int level = numNexts()-1; ListNode *newNode = new ListNode(payload, level); while(level >= 0) { ListNode* prevNode = findLocation(payload, head[level], level); if (prevNode == nullptr) { if(head[level] != nullptr) newNode->setNext(head[level], level); head[level] = newNode; } else { newNode->setNext(prevNode->getNext(level), level); prevNode->setNext(newNode, level); } level--; } numNodes++; } /** * @brief This function searches for a location in a linked list and returns the previous node. * * @tparam T * @param target the value to be looking for * @param start the node to start the search * @return the node that comes before the target in the list */ template  ListNode* SkipList::findLocation(T target, ListNode* start, int level){ ListNode* curr = start; ListNode* prev = nullptr; while(curr != nullptr && curr->getPayload() != target){ prev = curr; curr = curr->getNext(level); } return prev; } /** * @brief This function searches and removes a value from the list * * @tparam T * @param target */ /* Not Currently Updating as not asked for. template  void SkipList::remove(T target) { ListNode *current = head[0]; ListNode *previous = nullptr; while (current != nullptr && current->getPayload() != target) { if (current != head) previous = current; current = current->getNext(); } if (current != nullptr) { int numLevels = current->getNumLevels(); if (previous) previous->setNext(current->getNext()); else head = nullptr; delete current; numNodes--; } } */ /** * @brief Deletes all elements in the list * * @tparam T */ template  void SkipList::clearList() { ListNode *current = head[0]; while (current != nullptr) { head[0] = current->getNext(); delete current; current = head[0]; } numNodes = 0; } /** * @brief Print the entire list as well as the structure * * @tparam T * @param strm * @return std::ostream& */ template  std::ostream &SkipList::print(std::ostream &strm) const { ListNode *current = head[0]; while (current != nullptr) { current->printNodeStructure(strm); current = current->getNext(); /* Old print code. Updated quickly to output structure. strm << *current << " -> ( "; current = current->getNext(); if (current == nullptr) strm << "/ )" << std::endl; else strm << *current << " )" << std::endl; */ } return strm; } /** * @brief Overloaded stream insertion operator * * @tparam T * @param strm * @param list * @return std::ostream& */ template  std::ostream &operator<<(std::ostream &strm, const SkipList &list) { return list.print(strm); } /** * @brief Calculate number of nexts a node should have. * * @return int referencing the number of nexts */ template  int SkipList::numNexts(double probability) { // Generate random number between 0 and 1 if(probability < 0) probability = ((double)rand()/(double)RAND_MAX); // Since we know the distribution is probability = 1 + 0.5^numLevels // We can solve using logarithms int numNexts = (1 + floor(log(probability)/log(0.5))); int maxNexts = numNodes > 1 ? floor(log2(numNodes)) : 1; if(numNexts > maxNexts) numNexts = maxNexts; return numNexts; } template  void SkipList::testNumNexts(){ int distribution[20] {10000}; int maxNexts = (numNodes > 1 ? floor(log2(numNodes)) : 1); for(int i = 0; i < distribution[0]; i++) distribution[numNexts((double)rand()/(double)RAND_MAX)]++; std::cout << "Our maxNexts: " << maxNexts << std::endl; std::cout << "Our generated distribution: " << std::endl; for(int i = 0; i < maxNexts; i++) std::cout << (i+1) << ": " << distribution[i] << std::endl; } #endif