Skip Lists Final Project¶
Why Skip Lists¶
I was at first intriqued by skiplists by reading the chapter but I was still left with a lot of questions and a little bit of confusion on how the jumping or skipping would work. I watched some youtube videos further explaining the data structures I have included the notes from those videos below, under video notes. First step will be mapping out my timeline and steps to the Project
Steps¶
Watch Videos and Take notes
Compare Notes to the textbook and finalize a completed note sheet
Research Ideas for how to use a skip lists in a cool Project
Create the basic management system of the Skip List Data structure
Create a point system for the explorer game
Implement the search list into the explorer game
Video Notes¶
Searching¶
In this example you are searching for 50. You start at the most upper left node and begin by searching down. Throughout the search you see a stair step search process form until you reach your target
skipSearch(50):
node = start
while node.getBelow()! null
node = node.getBelow()
while node.getNext.getKey() <= 50
node = node.getNext()
return node
When searching for something that doesn’t exist it will return the largest node <= the data you are searching for
Insertion¶
In this example we are inserting the key of 42
Search for the largest key <= 42 (which will then be returned by the search method)
Insert the new node
Manipulate the refrences for the new inserted node
Keep inserting the node on the tower until the coin flip returns tails
Deletion¶
Search for the node you want to delete
Remove the node
Manipulate the horizontal refrences
Project Implementation¶
Leaderboard system
- Features:
Add player score
Update score
store the data on the hardrive (search for ideas on how best to store)
Implement into the last project
Skip List Code¶
Attention
This is just the skip list management system. You can see how the insert, search and delete functions work.
#include <stdio.h>
#include <queue>
#include <sstream>
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
using namespace std;
class Node
{
public:
int key;
int value;
int height;
vector<Node*> next;
Node(int k, int v, int h)
{
key = k;
value = v;
height = h;
next.resize(h + 1, nullptr);
}
};
class SkipList
{
public:
int top_level;
int max_level;
Node* front;
SkipList(int maxLevel)
{
max_level = maxLevel;
top_level = 0;
front = new Node(-1,-1,maxLevel);
}
int search(int target)
{
Node* current = front; //starts with the current node at the front of the topmost list
int level = top_level;
/*Two nested WHILE loops handle the traversal. The inner loop iterates through
the current linked list until it hits the end of the list (current.next[level] == null)
or a node with a key larger than or equal to target (current.next[level].key >= target).
The outer loop drops down a single level each
iteration until we hit the bottom of the list */
while(level >= 0)
{
while(current->next[level] != nullptr && current->next[level]->key < target)
{
current = current->next[level];
}
level = level - 1;
}
/* check that that node both exists and has the correct key */
Node* result = current->next[0];
/*When the search loop terminates, we are guaranteed to be at the last node in the list with a key
less than the target. The target is either the next node in the list or does not exist.*/
if (result != nullptr && result->key == target)
{
return result->value;
}
else
{
return -1;
}
}
int randomLevel() //random number generator will need for insert
{
int level = 0;
while(rand() % 2 && level < max_level)
{
level++;
}
return level;
}
void insert(int key, int value)
{
int level = top_level;
Node* current = front; //We update last for each level each time we drop down from that level
vector<Node*> last(max_level + 1, nullptr); //We update last for each level each time we drop down from that level
/*The outer WHILE loop iterates through the list’s levels, saving the last node
seen at each level and then dropping down to the next level. The inner WHILE loop
traverses the skip list, moving forward whenever another node along this level has
a key less than our target.*/
while(level >= 0)
{
while(current->next[level] != nullptr && current->next[level]->key < key)
{
current = current->next[level];
}
last[level] = current; //We update last for each level each time we drop down from that level
level--;
}
Node* result = current->next[0];
if(result != nullptr && result->key == key) // If we happen to find a matching key while traversing the skip list, we simply update the data for that key
{
result->value = value;
return;
}
int new_level = randomLevel(); //calling the random number generator
if(new_level > top_level) //We check whether the selected level represents a new top level for the list and, if so, update
{
top_level = new_level;
}
Node* new_node = new Node(key, value, new_level);
for(int j = 0; j <= new_level; j++) //fixing pointers
{
if(last[j] == nullptr)
{
last[j] = front;
}
new_node->next[j] = last[j]->next[j];
last[j]->next[j] = new_node;
}
}
void erase(int target)
{
int level = top_level;
Node* current = front; //starts with the current node at the front of the topmost list
vector<Node*> last(max_level + 1);
while (level >= 0)
{ /*A pair of nested WHILE loops searches across each level until we hit a node with a
key greater than or equal to target or the end of the list (null).*/
while(current->next[level] != nullptr && current->next[level]->key < target)
{
current = current->next[level];
}
last[level] = current;
level--;
}
Node* result = current->next[0]; //At the end of the search, we check that we’ve found a node whose key matches target
if(result == nullptr || result->key != target)
{
return;
}
level = result->height;
//link the next pointers for each node in the skip list’s last to point past the current node
for(int j = 0; j <= level; j++)
{
last[j]->next[j] = result->next[j];
result->next[j] = nullptr;
}
if(level == top_level) // check whether the skip list’s top level is still valid
{
int top = top_level;
while(top > 0 && front->next[top] == nullptr)
{
top--;
}
top_level = top;
}
}
};
int main()
{
cout <<"Testing the skip list suite" << endl;
cout <<"Searching the list" << endl;
SkipList list(5);
list.insert(10, 100);
list.insert(20, 200);
list.insert(15, 150);
cout << "Search 15 = " << list.search(15) << endl;
cout << "Search 99 = " << list.search(99) << endl;
list.erase(15);
cout << "Search 15 after erase = " << list.search(15) << endl;
}
Original game¶
Attention
This is a game that I made for the first project. This game is about exploring regions. I will be implementing a point system and using the skip lists as a leaderboard for the players scores.
#include <stdio.h>
#include <queue>
#include <sstream>
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
using namespace std;
// writting a program that uses a node that points to 4 other nodes and 1 mode
// the mode points to a node and mode(itsself)
// also use a stack in the program
//think creativly and correctly use the data structures
// i choose to initilize Mode but either Mode or Node have to be initilizied since they both point to eachother.
class Mode;
//node
class Node{
public:
string name;
Node* north;
Node* south;
Node* east;
Node* west;
Mode* mode;
bool visited;
Node(string n) : name(n), north(nullptr), south(nullptr), east(nullptr), west(nullptr){}
void connect(Node* n,Node* s,Node* e,Node* w)
{
this->north = n;
this->south = s;
this->east = e;
this->west = w;
}
void assignMode(Mode* m)
{
this->mode = m;
}
string getName()
{
return name;
}
Mode* getMode()
{
return mode;
}
vector<Node*> getNeighbors();
void displayInfo()
{
cout << "Node Name: " << name << endl;
cout <<"Mode: " << this->mode << endl;
cout << "Neighbors are " << north->name << ", " << south->name << ", " << east->name << ", " << west->name << endl;
}
};
vector<Node*> Node::getNeighbors()
{
vector<Node*> result;
if (north) result.push_back(north);
if (east) result.push_back(east);
if (south) result.push_back(south);
if (west) result.push_back(west);
return result;
}
class Mode{
public:
string modeName;
Mode* self;
Mode* nextMode;
Node* linkedNode;
Mode(string name)
{
modeName = name;
self = this;
nextMode = nullptr;
linkedNode = nullptr;
}
void setNextMode(Mode* m)
{
nextMode = m;
}
void connectToNode(Node* n)
{
linkedNode = n;
}
string getName()
{
return modeName;
}
Mode* getNextMode()
{
return nextMode;
}
void displayInfo()
{
cout << " Mode: " << modeName << endl;
cout << "Linked to Node: " << linkedNode->name << endl;
cout << "Next mode: " << nextMode->modeName << endl;
cout << "Self points to: " << modeName << endl;
}
};
class Explorer
{
private:
queue<Node*> q;
unordered_set<Node*> visited;
int points = 0;
public:
Explorer(){}
void explore(Node* start);
void visit(Node* n);
void addPoints(int p)
{
points += p;
cout << " -> You earned " << p << " points! (Total: " << points << ")" << endl;
}
int getPoints() const
{
return points;
}
};
void Explorer::explore(Node* start)
{
q.push(start);
visited.insert(start);
while(!q.empty())
{
Node* current = q.front();
q.pop();
visit(current);
vector<Node*> neighbors = current->getNeighbors();
for(Node* neighbor : neighbors)
{
if(neighbor && visited.find(neighbor) == visited.end())
{
q.push(neighbor);
visited.insert(neighbor);
}
}
}
}
void Explorer::visit(Node* n)
{
cout << "Exploring region: " << n->getName() << endl;
// Check if this node was visited before
if (visited.find(n) != visited.end())
{
cout << " You’ve already been here before!" << endl;
}
else
{
cout << " New area discovered!" << endl;
visited.insert(n);
addPoints(10);
}
Mode* current = n->getMode();
cout << " Current mode: " << current->getName() << endl;
if (current->getName() == "Idle")
{
// scanning
addPoints(5); // Scanning gives points
}
else if (current->getName() == "Scanning")
{
// analyzing
addPoints(20); // Analyzing gives more points
}
if (current->getNextMode() != nullptr)
{
n->assignMode(current->getNextMode());
cout << " Transitioned to next mode: " << n->getMode()->getName() << endl;
} else
{
cout << " Already in final mode." << endl;
}
cout << endl;
}
int main()
{
Node* root = new Node("Central Hub");
/*Asking the user for the terrians and creating said nodes, I could have just chosen the terrians
but i wanted it to be more interactive*/
cout <<"What terrian would you like to explore?"<<endl;
string terrainOne;
cin >> terrainOne;
Node* north = new Node(terrainOne);
cout <<"What terrian would you like to explore?"<<endl;
string terrainTwo;
cin >> terrainTwo;
Node* south = new Node(terrainTwo);
cout <<"What terrian would you like to explore?"<<endl;
string terrainThree;
cin >> terrainThree;
Node* east = new Node(terrainThree);
cout <<"What terrian would you like to explore?"<<endl;
string terrainFour;
cin >> terrainFour;
Node* west = new Node(terrainFour);
/************************************************* */
//attaches all of the "sub nodes (the regions) to the root main node"
root->north = north;
root->east = east;
root->south = south;
root->west = west;
//root->displayInfo();
//creates all of the modes for the game
Mode* idle = new Mode("Idle");
Mode* scanning = new Mode("Scanning");
Mode * analyzing = new Mode("Analyzing");
//connects the modes
idle->setNextMode(scanning);
scanning->setNextMode(analyzing);
//sets the mode for the nodes
north->assignMode(idle);
south->assignMode(idle);
east->assignMode(idle);
west->assignMode(idle);
root->assignMode(idle);
//scanning->displayInfo();
Explorer e;
//e.explore(root);
Node* current = root;
while(true)
{
cout <<"-----------------------------------------------" << endl;
cout <<endl;
cout << "You are at " << current->getName() << endl;
cout << "You are " << current-> getMode()->getName() << endl;
cout << endl;
cout << "Where do you want to go?" << endl;
cout << "1. North" << endl;
cout << "2. South" << endl;
cout << "3. East" << endl;
cout << "4. West" << endl;
cout << "5. Scan current area" << endl;
cout << "6. Analyze Current area"<< endl;
cout << "7. Exit exploration"<< endl;
cout << "> ";
int choice;
cin >> choice;
cout << endl;
cout << endl;
if (choice == 1 && root->north)
{
current = root->north;
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 2 && root->south)
{
current = root->south;
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 3 && root->east)
{
current = root->east;
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 4 && root->west)
{
current = root->west;
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 5)
{
e.visit(current); // reuse your visit() method
cout << "Points: " << e.getPoints() << endl;
}
else if(choice == 6 && current->getMode()->getName() == "Scanning")
{
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 7)
{
cout << "Exiting exploration. Goodbye!" << endl;
cout << "Points: " << e.getPoints() << endl;
break;
}
else
{
cout << "Invalid move. There’s no path that way!" << endl;
}
cout <<"-----------------------------------------------" << endl;
cout << endl;
cout << endl;
}
}
Final Project¶
Attention
There are 3 files for the final version. This includes the skiplist.cpp file which houses all the logic for the skiplist, the Skiplist.h which houses the method declarations for the skiplist so that I can include it into the game, and finally main.cpp which is the orignal game with the addition of the point system.
Skiplist.h¶
#pragma once
#include <stdio.h>
#include <queue>
#include <sstream>
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <string>
using namespace std;
class Node
{
public:
string key;
int value;
int height;
vector<Node*> next;
Node(string k, int v, int h);
};
class SkipList
{
public:
int top_level;
int max_level;
Node* front;
SkipList(int maxLevel);
string search(string target);
int randomLevel();
void insert(string key, int value);
void erase(string target);
void saveToFile(const string& filename);
void loadFromFile(const string& filename);
void print();
};
skiplist.cpp¶
#include "Skiplist.h" //takes all the methods defined in Skiplist.h and adds the guts here
Node::Node(string k, int v, int h)
{
key = k;
value = v;
height = h;
next.resize(h + 1, nullptr);
}
SkipList::SkipList(int maxLevel)
{
max_level = maxLevel;
top_level = 0;
front = new Node("", -1, maxLevel);
}
string SkipList::search(string target)
{
Node* current = front;
int level = top_level;
while (level >= 0)
{
while (current->next[level] != nullptr && current->next[level]->key < target)
{
current = current->next[level];
}
level = level - 1;
}
Node* result = current->next[0];
if (result != nullptr && result->key == target)
{
return result->key;
}
else
{
return "";
}
}
int SkipList::randomLevel()
{
int level = 0;
while (rand() % 2 && level < max_level)
{
level++;
}
return level;
}
void SkipList::insert(string key, int value)
{
int level = top_level;
Node* current = front;
vector<Node*> last(max_level + 1, nullptr);
while (level >= 0)
{
while (current->next[level] != nullptr && current->next[level]->key < key)
{
current = current->next[level];
}
last[level] = current;
level--;
}
Node* result = current->next[0];
if (result != nullptr && result->key == key)
{
result->value = value;
return;
}
int new_level = randomLevel();
if (new_level > top_level)
{
top_level = new_level;
}
Node* new_node = new Node(key, value, new_level);
for (int j = 0; j <= new_level; j++)
{
if (last[j] == nullptr)
{
last[j] = front;
}
new_node->next[j] = last[j]->next[j];
last[j]->next[j] = new_node;
}
}
void SkipList::erase(string target)
{
int level = top_level;
Node* current = front;
vector<Node*> last(max_level + 1);
while (level >= 0)
{
while (current->next[level] != nullptr && current->next[level]->key < target)
{
current = current->next[level];
}
last[level] = current;
level--;
}
Node* result = current->next[0];
if (result == nullptr || result->key != target)
{
return;
}
level = result->height;
for (int j = 0; j <= level; j++)
{
last[j]->next[j] = result->next[j];
result->next[j] = nullptr;
}
if (level == top_level)
{
int top = top_level;
while (top > 0 && front->next[top] == nullptr)
{
top--;
}
top_level = top;
}
}
void SkipList::saveToFile(const string& filename)
{
ofstream out(filename);
if (!out.is_open()) return;
Node* current = front->next[0];
while (current)
{
out << current->key << " " << current->value << "\n";
current = current->next[0];
}
}
void SkipList::loadFromFile(const string& filename)
{
ifstream in(filename);
if (!in.is_open()) return;
int score;
string name;
while (in >> name >> score)
{
insert(name, score);
}
}
void SkipList::print()
{
cout << endl;
cout << "Leaderboard" << endl;
cout << "---------------------" << endl;
vector<Node*> nodes;
Node* current = front->next[0];
while (current)
{
nodes.push_back(current);
current = current->next[0];
}
sort(nodes.begin(), nodes.end(), [](Node* a, Node* b)
{
return a->value > b->value;
});
for (auto n : nodes)
{
cout << n->key << " : " << n->value << endl;
}
cout << endl;
}
Main¶
#include "Skiplist.h" //this includes the entire skiplist structure (all the methods)
using namespace std;
//compiling and running intructions
// g++ main.cpp skiplist.cpp -o leaderboard
//./leaderboard
//This file is a copy of the original game just with the Skiplist.h included
// writting a program that uses a node that points to 4 other nodes and 1 mode
// the mode points to a node and mode(itsself)
// also use a stack in the program
//think creativly and correctly use the data structures
// i choose to initilize Mode but either Mode or Node have to be initilizied since they both point to eachother.
class Mode;
//GameNode used find and replace to change from Node to GameNode because I also have a Node for the SkipList
class GameNode{
public:
string name;
GameNode* north;
GameNode* south;
GameNode* east;
GameNode* west;
Mode* mode;
bool visited;
GameNode(string n) : name(n), north(nullptr), south(nullptr), east(nullptr), west(nullptr){}
void connect(GameNode* n,GameNode* s,GameNode* e,GameNode* w)
{
this->north = n;
this->south = s;
this->east = e;
this->west = w;
}
void assignMode(Mode* m)
{
this->mode = m;
}
string getName()
{
return name;
}
Mode* getMode()
{
return mode;
}
vector<GameNode*> getNeighbors();
void displayInfo()
{
cout << "GameNode Name: " << name << endl;
cout <<"Mode: " << this->mode << endl;
cout << "Neighbors are " << north->name << ", " << south->name << ", " << east->name << ", " << west->name << endl;
}
};
vector<GameNode*> GameNode::getNeighbors()
{
vector<GameNode*> result;
if (north) result.push_back(north);
if (east) result.push_back(east);
if (south) result.push_back(south);
if (west) result.push_back(west);
return result;
}
class Mode{
public:
string modeName;
Mode* self;
Mode* nextMode;
GameNode* linkedNode;
Mode(string name)
{
modeName = name;
self = this;
nextMode = nullptr;
linkedNode = nullptr;
}
void setNextMode(Mode* m)
{
nextMode = m;
}
void connectToNode(GameNode* n)
{
linkedNode = n;
}
string getName()
{
return modeName;
}
Mode* getNextMode()
{
return nextMode;
}
void displayInfo()
{
cout << " Mode: " << modeName << endl;
cout << "Linked to Node: " << linkedNode->name << endl;
cout << "Next mode: " << nextMode->modeName << endl;
cout << "Self points to: " << modeName << endl;
}
};
class Explorer
{
private:
queue<GameNode*> q;
unordered_set<GameNode*> visited;
int points = 0;
public:
Explorer(){}
void explore(GameNode* start);
void visit(GameNode* n);
void addPoints(int p)
{
points += p;
cout << " -> You earned " << p << " points! (Total: " << points << ")" << endl;
}
int getPoints() const
{
return points;
}
};
void Explorer::explore(GameNode* start)
{
q.push(start);
visited.insert(start);
while(!q.empty())
{
GameNode* current = q.front();
q.pop();
visit(current);
vector<GameNode*> neighbors = current->getNeighbors();
for(GameNode* neighbor : neighbors)
{
if(neighbor && visited.find(neighbor) == visited.end())
{
q.push(neighbor);
visited.insert(neighbor);
}
}
}
}
void Explorer::visit(GameNode* n)
{
cout << "Exploring region: " << n->getName() << endl;
// Check if this node was visited before
if (visited.find(n) != visited.end())
{
cout << " You’ve already been here before!" << endl;
}
else
{
cout << " New area discovered!" << endl;
visited.insert(n);
addPoints(10);
}
Mode* current = n->getMode();
cout << " Current mode: " << current->getName() << endl;
if (current->getName() == "Scanning")
{
addPoints(5); //Scanning gives points
}
else if (current->getName() == "Scanning")
{
// analyzing
addPoints(20); //Analyzing gives more points
}
if (current->getNextMode() != nullptr)
{
n->assignMode(current->getNextMode());
cout << " Transitioned to next mode: " << n->getMode()->getName() << endl;
} else
{
cout << " Already in final mode." << endl;
}
cout << endl;
}
int main()
{
GameNode* root = new GameNode("Central Hub");
/*Asking the user for the terrians and creating said nodes, I could have just chosen the terrians
but i wanted it to be more interactive*/
cout <<"What terrian would you like to explore?"<<endl;
string terrainOne;
cin >> terrainOne;
GameNode* north = new GameNode(terrainOne);
cout <<"What terrian would you like to explore?"<<endl;
string terrainTwo;
cin >> terrainTwo;
GameNode* south = new GameNode(terrainTwo);
cout <<"What terrian would you like to explore?"<<endl;
string terrainThree;
cin >> terrainThree;
GameNode* east = new GameNode(terrainThree);
cout <<"What terrian would you like to explore?"<<endl;
string terrainFour;
cin >> terrainFour;
GameNode* west = new GameNode(terrainFour);
/************************************************* */
//attaches all of the "sub nodes (the regions) to the root main node"
root->north = north;
root->east = east;
root->south = south;
root->west = west;
//root->displayInfo();
//creates all of the modes for the game
Mode* idle = new Mode("Idle");
Mode* scanning = new Mode("Scanning");
Mode * analyzing = new Mode("Analyzing");
//connects the modes
idle->setNextMode(scanning);
scanning->setNextMode(analyzing);
//sets the mode for the nodes
north->assignMode(idle);
south->assignMode(idle);
east->assignMode(idle);
west->assignMode(idle);
root->assignMode(idle);
//scanning->displayInfo();
/*Game "Starts" here, User enters terrains, user chooses where to go and what to do when they visit to earn points*/
Explorer e;
GameNode* current = root;
while(true)
{
cout <<"-----------------------------------------------" << endl;
cout <<endl;
cout << "You are at " << current->getName() << endl;
cout << "You are " << current-> getMode()->getName() << endl;
cout << endl;
cout << "Where do you want to go?" << endl;
cout << "1. North" << endl;
cout << "2. South" << endl;
cout << "3. East" << endl;
cout << "4. West" << endl;
cout << "5. Scan current area" << endl;
cout << "6. Analyze Current area"<< endl;
cout << "7. Exit exploration"<< endl;
cout << "> ";
int choice;
cin >> choice;
cout << endl;
cout << endl;
if (choice == 1 && root->north)
{
current = root->north;
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 2 && root->south)
{
current = root->south;
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 3 && root->east)
{
current = root->east;
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 4 && root->west)
{
current = root->west;
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 5)
{
e.visit(current); // reuse your visit() method
cout << "Points: " << e.getPoints() << endl;
}
else if(choice == 6 && current->getMode()->getName() == "Scanning")
{
e.visit(current);
cout << "Points: " << e.getPoints() << endl;
}
else if (choice == 7)
{
cout << "Exiting exploration. Goodbye!" << endl;
cout << "Points: " << e.getPoints() << endl;
cout << "Enter your name to save your score to the leaderboard :" << endl;
string name;
cin >> name;
SkipList board(10);
board.loadFromFile("leaderboard.txt"); //loads previous leaderboard
board.insert(name, e.getPoints());
board.saveToFile("leaderboard.txt"); //saves new leaderboard
board.print();
break;
}
else
{
cout << "Invalid move. There’s no path that way!" << endl;
}
cout <<"-----------------------------------------------" << endl;
cout << endl;
cout << endl;
}
}
Leaderboard¶
Attention
This is what the leaderboard text file looks like which drives the system by being able to store data over time
Brayden 50
Larry 50
Terry 80