Node file code below #ifndef NODE_H #define NODE_H #include using namespace std; // the node class Node{
Question:
Node file code below
#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
vector
Node(int val, int level){
value = val;
next = vector
prev = vector
};
};
#endif
SKIPLIST.H FILE CODE BELOW
#include
#include
#include
#include
#include
#include
#include "Node.h"
#ifndef SKIPLIST_H
#define SKIPLIST_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);
tail = new Node(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
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){
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];
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
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];
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
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";
}
}
}
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;
Node *tail;
int priority;
int maxlevel;
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) {
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";
}
}
}
};
#endif
in my priorityq file 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
Expert Answer:
