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)

#SkipList.h

#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

main.cpp

#include  #include "SkipList.h" #include  int main() { srand(42); SkipList intList; for (int i = 0; i < 10; i++) intList.add(i); std::cout << "Int List" << std::endl; std::cout << intList; SkipList charList; for (int i = 0; i < 26; i++) { std::cout << "Character: " << static_cast(i + 'a') << std::endl; charList.add('a' + i); } std::cout << "Char List" << std::endl; std::cout << charList; charList.testNumNexts(); return 0; }

#ListNode.h

#ifndef LISTNODE_H_ #define LISTNODE_H_ #include  template  class ListNode { public: /** * @brief Construct a new List Node object * * @param payload */ ListNode(T payload, int levels) : payload{payload}, numLevels{levels} { for(int i = 0; i < 100; i++) { next[i] = nullptr; } } /** * @brief Remove default constructor * */ ListNode() = delete; /** * @brief Set the Next object * * @param newNext * @param level the level of next to modify */ void setNext(ListNode *newNext, int level = 0) { if(level > numLevels) throw std::out_of_range("Node doesn't contain that many levels"); else next[level] = newNext; } /** * @brief Get the Next object * * @param level the level of next to return * * @return ListNode* */ ListNode *getNext(int level = 0) { if(level > numLevels) throw std::out_of_range("Node doesn't contain that many levels"); else return next[level]; } /** * @brief Print payload of Node object. * * @param strm * @return std::ostream& */ std::ostream &print(std::ostream &strm) const { return strm << payload; } /** * @brief Get the Payload object * * @return const T& */ const T &getPayload() { return payload; } int getNumLevels() const { return numLevels; } std::ostream& printNodeStructure(std::ostream &strm) const { strm << payload << "\t" << numLevels + 1 << std::endl; for(int i = numLevels; i >= 0; i--) { strm << "\t[" << i << "] -> ( "; if(next[i] == nullptr) strm << "---"; else strm << next[i]->payload; strm << " )" << std::endl; } return strm; } private: const T payload; ListNode *next[100]; int numLevels = 0; }; /** * @brief * * @tparam T * @param strm * @param node * @return std::ostream& */ template  std::ostream &operator<<(std::ostream &strm, const ListNode &node) { return node.print(strm); } #endif