Node file code below#ifndef NODE_H#define NODE_H#include .pdf

Node file code below#ifndef NODE_H#define NODE_H#include .pdf

• 1.
  Node file codebelow #ifndef NODE_H #define NODE_H #include using namespace std; // the node class Node{ public: int value; // Array of pointers to the next nodes (which may be located at various levels) // next[i] is the next link for level i // the size of this vector determines the number of levels that the current node is part of vector next; vector prev; // previous links for each level the node is part of Node(int val, int level){ value = val; next = vector(level+1, nullptr); // initialize array of pointers to nulls prev = vector(level+1, nullptr); // initialize array of pointers to nulls }; }; #endif SKIPLIST.H FILE CODE BELOW #include #include #include #include #include
• 2.
  #include #include "Node.h" #ifndef SKIPLIST_H #defineSKIPLIST_H using namespace std; class SkipList{ public: // Maximum allowed level index int MAXIMUM_ALLOWED_LEVEL_INDEX; // current maximum level amongst the inserted nodes int currentHighestLevelIndex; // the head node's next links are connected to the first node at every level Node *head; Node* tail; // last node at every level SkipList(int maxLevels){ MAXIMUM_ALLOWED_LEVEL_INDEX = maxLevels; // initially we have the bottom-most level only currentHighestLevelIndex = 0; // create the header node, value is irrelevant (as long as it doesn't match an inserted value - NO REPEATS), number of next links is important (initially this node is the first node at every level) head = new Node(INT_MIN, MAXIMUM_ALLOWED_LEVEL_INDEX);
• 3.
  tail = newNode(INT_MAX, MAXIMUM_ALLOWED_LEVEL_INDEX); // last nodes at each level // connect head to tail at every level for(int i = 0; i <= MAXIMUM_ALLOWED_LEVEL_INDEX; i++){ head->next[i] = tail; // head's prev is null tail->prev[i] = head; // tail's next is null } } int RandomLevel(){ float probablity = (float)rand()/RAND_MAX; // flip a coin int lvl = 0; while (probablity < 0.5 && lvl < MAXIMUM_ALLOWED_LEVEL_INDEX){ lvl++; // landed heads so increase level by 1 probablity = (float)rand()/RAND_MAX; // flip a coin again } return lvl; } Node* CreateNode(int value, int level){ // create a new node with next links for every level that this node will be part of // it will use these links to connect to the next node at each level return new Node(value, level); } void InsertElement(int value){ Node *current = head; // start at head node vector update(MAXIMUM_ALLOWED_LEVEL_INDEX+1, nullptr); // this will hold the nodes that need updating at every level after the insert takes place for (int i = currentHighestLevelIndex; i >= 0; i--){ // start at the highest level and move down so that more nodes may be skipped // for level i, if value is to be inserted here then find out where (i.e. after which node) while (current->next[i] != nullptr && current->next[i]->value < value){
• 4.
  current = current->next[i]; } //found the node after which the value is to be placed at level i update[i] = current; // move down a level, if possible } // at level 0, where current is pointing to by the end of the preceding loop, move over one node to the right where the value is to be inserted to see if the value already exists there (NO REPEATS allowed) current = current->next[0]; if (current == nullptr || current->value != value){ int ranLevel = RandomLevel(); // choose a random level upto where the new node will be placed (starting from level 0) if (ranLevel > currentHighestLevelIndex){ // if random level for current node is higher than the current maximum level for existing nodes; then set head as the node after which the new value is to be inserted for each level over current maximum to the level chosen for new value to be inserted (update currently contains nulls for these level(s)). for (int i = currentHighestLevelIndex+1; i <= ranLevel; i++){ update[i] = head; } // also change the current maximum level for the existing nodes currentHighestLevelIndex = ranLevel; } // create new node with next links for every level from ranLevel to zero Node* n = CreateNode(value, ranLevel); // placing new node in the correct place at every level for (int i = 0; i<=ranLevel; i++){ // n connects as a new node between update[i] and update[i]->next[i] n->next[i] = update[i]->next[i];
• 5.
  n->prev[i] = update[i]; //update[i] connects to n (update[i] is the node before n) update[i]->next[i] = n; // n->next[i] (this was originally update[i]->next[i], the node that should be after n) connects back to n n->next[i]->prev[i] = n; } } } void Delete(int value){ // remove value from skip list (all levels) if it exists (output a message if it does not exist) Node *current = head; // start at head node vector update(MAXIMUM_ALLOWED_LEVEL_INDEX+1, nullptr); // this will hold the nodes that need updating at every level after the delete takes place for (int i = currentHighestLevelIndex; i >= 0; i--){ // start at the highest level and move down so that more nodes may be skipped // for level i, if value is to be deleted from here then find out where from (i.e. after which node could it be) while (current->next[i] != nullptr && current->next[i]->value < value){ current = current->next[i]; // moving right on level i } if(current->next[i] != nullptr && current->next[i]->value == value){ // found the node after which exists the target node (node that is to be deleted from level i) update[i] = current; } // move down a level, if possible } // at level 0, where current is pointing to by the end of the preceding loop, move over one node to the right to see value exists there before we try to delete it current = current->next[0];
• 6.
  if (current !=nullptr && current->value == value){ // value exists at level 0, so delete it from all levels where it is located. for (int i = 0; i <= currentHighestLevelIndex; i++){ if(update[i]){ // first we ensure that value exists at level i (otherwise update[i] will be null) // update[i] connects to the node after current (current->next[i]) update[i]->next[i] = current->next[i]; // current->next[i] (the node that should be after update[i]) connects back to update[i] current->next[i]->prev[i] = update[i]; // disconnect current from level i - are these necessary? current->next[i] = nullptr; current->prev[i] = nullptr; } } // delete current delete current; // update currentHighestLevelIndex if necessary while (currentHighestLevelIndex >= 0 && head->next[currentHighestLevelIndex] == tail){ currentHighestLevelIndex--; } } else{ // if update[0] is nullptr then preceding loop was unable to find value at level 0 cout << "Value " << value << " does not exist in the skip list.n"; } } bool Search(int value){ // TO BE COMPLETED // search for value in skip list and return true if it exists; false otherwise
• 7.
  Node *current =head; // start at head node for (int i = currentHighestLevelIndex; i >= 0; i--){ // start at the highest level and move down so that more nodes may be skipped // for level i, keep moving right while values are less than what we are looking for (and if it is possible to move any further right while (current->next[i] != nullptr && current->next[i]->value < value){ current = current->next[i]; // moving right } if(current->next[i] != nullptr && current->next[i]->value == value){ return true; // found the value at level i } // move down a level, if possible } return false; // value not found, we are at level 0 and to the farthest right at level 0 (value always exists at level 0 if in the list) } void ShowForward(){ cout << "Showing forward:n"; for (int i = currentHighestLevelIndex; i >= 0;i--){ Node *node = head->next[i]; cout << "Level " << i << ": "; while (node != nullptr && node->next[i] != tail){ cout << node->value << " -> "; node = node->next[i]; } if(node){ cout << node->value << " .n"; } else{ cout << " .n"; } } }
• 8.
  void ShowBackward(){ cout <<"Showing backward:n"; for (int i = currentHighestLevelIndex; i >= 0;i--){ Node *node = tail->prev[i]; cout << "Level " << i << ": "; while (node != nullptr && node->prev[i] != head){ cout << node->value << " -> "; node = node->prev[i]; } if(node){ cout << node->value << " .n"; } else{ cout << " .n"; } } } }; #endif PRIORITYQ file code below #ifndef PRIORITYQ_H #define PRIORITYQ_H #include #include #include #include #include "Skiplist.h" using namespace std; class PriorityQ{ public: Node *head;
• 9.
  Node *tail; int priority; intmaxlevel; PriorityQ(int Level){ srand(time(0)); //priority = rand() % (Level-1); maxlevel = Level-1; head = new Node(INT_MIN, Level-1); tail = new Node(INT_MAX, Level-1); } bool isEmpty() { return head->next[0] == tail; } void enqueue(int data) { priority = rand() % (maxlevel + 1); //cout << "priority " << priority << endl; Node *curr = head; for (int i = maxlevel; i >= 0; i--) { curr = head; while (curr->next[i] != nullptr && curr->next[i]->value < data) { curr = curr->next[i]; } if (i <= priority) { Node *newNode = new Node(data, i); newNode->next[i] = curr->next[i]; curr->next[i] = newNode; } } } void dequeue(int value, int level) { for (int i = level; i >= 0; i--) { Node *curr = head->next[i]; while (curr->next[i] != nullptr && curr->value < value) {
• 10.
  if(curr->value == value){ Node*temp = curr; curr->prev[i]->next[i] = curr->next[i]; curr->next[i]->prev[i]=curr->prev[i]; curr = curr->next[i]; delete temp; } curr = curr->next[i]; } } } void process() { for (int i = maxlevel; i >= 0; i--) { Node *curr = head; cout << "Process " << i << ": "; while (curr->next[i] != tail) { cout << curr->next[i]->value << ", "; dequeue(curr->next[i]->value, i); curr = curr->next[i]; } } } void show(){ for (int i = maxlevel; i >= 0;i--){ Node *node = head->next[i]; cout << "Level " << i << ": "; while (node != nullptr && node->next[i] != tail){ cout << node->value << " -> "; node = node->next[i]; } if(node){ cout << node->value << " .n"; } else{ cout << " .n";
• 11.
  } } } }; #endif in my priorityqfile code my process method is not working correctly, its outputting the below Level 2: 5 -> 55 -> . Level 1: 5 -> 10 -> 55 -> 1000 -> . Level 0: 2 -> 5 -> 10 -> 22 -> 55 -> 700 -> 1000 -> . Process 2: 5, 55, WHEN l should be getting Level 2: 5 -> 55 -> . Level 1: 5 -> 10 -> 55 -> 1000 -> . Level 0: 2 -> 5 -> 10 -> 22 -> 55 -> 700 -> 1000 -> . Process 2: 5, 55, Process 1: 10,1000 Process 0 2,22,700 please fix my process and dequeue code if you see the problem