Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- using namespace std;
- struct Node{
- int key;
- double d;
- char c;
- Node *nextNodes[10];
- Node(int, double, char);
- };
- class SkipList{
- int listMaximumLevel;
- Node* header;
- public:
- SkipList(int, float);
- float P;
- void displayList();
- bool InsertNode(int);
- void RemoveNode(int);
- void InsertNodesBulk(int);
- Node* SearchForNode(int);
- int RandomLevel();
- string PrintListOfNodes(int, int);
- int AmountOfNodes(int);
- };
- int SkipList::AmountOfNodes(int level){
- Node* currentNode = header;
- int amount =0;
- while(currentNode->nextNodes[level]!=nullptr){
- currentNode = currentNode->nextNodes[level];
- amount++;
- }
- return amount;
- }
- string SkipList::PrintListOfNodes(int minimumLevel, int n){
- Node* currentNode = header;
- string output = "";
- for(int i=0;i<n;i++){
- if(currentNode->nextNodes[minimumLevel]!=nullptr){
- currentNode = currentNode->nextNodes[minimumLevel];
- output+=to_string(currentNode->key)+" ";
- }
- }
- cout << output;
- return output;
- }
- void SkipList::RemoveNode(int key){
- Node *currentNode = header;
- Node *update[listMaximumLevel];
- for(int i=listMaximumLevel;i>=0;i--){
- while (currentNode->nextNodes[i] != nullptr && currentNode->nextNodes[i]->key < key){
- currentNode = currentNode->nextNodes[i];
- }
- cout << to_string(currentNode->key)<< endl;
- update[i] = currentNode;
- }
- if(update[0]->nextNodes[0]->key != key){
- throw runtime_error("Remove: Node not found");
- }
- currentNode = update[0]->nextNodes[0];
- for(int i=0;i<=listMaximumLevel;i++){
- if(update[i]->nextNodes[i] != nullptr && update[i]->nextNodes[i]->key == key){
- if(update[i]->nextNodes[i]->nextNodes[i]!=nullptr){
- update[i]->nextNodes[i] = update[i]->nextNodes[i]->nextNodes[i];
- }else{
- update[i]->nextNodes[i] = nullptr;
- }
- }
- else{
- return;
- update[i]->nextNodes[i] == nullptr;
- }
- }
- delete currentNode;
- }
- Node* SkipList::SearchForNode(int key){
- Node* currentNode = header;
- for(int i=listMaximumLevel;i>=0;i--){
- while (currentNode->nextNodes[i] != nullptr && currentNode->nextNodes[i]->key <= key){
- currentNode = currentNode->nextNodes[i];
- if(currentNode->key == key){
- return currentNode;
- }
- }
- }
- throw runtime_error("Search: Node not found");
- }
- SkipList::SkipList(int maxLevel, float p){
- this->listMaximumLevel = maxLevel;
- this->P = p;
- header = new Node(0,0,'a');
- for(int i=0;i<maxLevel;i++){
- header->nextNodes[i] == nullptr;
- }
- }
- Node::Node(int key, double value, char c){
- this->key = key;
- this->d = value;
- this->c = c;
- };
- int SkipList::RandomLevel(){
- int level = 0;
- while(rand()%100 < P*100 && level < listMaximumLevel){
- level++;
- }
- return level;
- }
- bool SkipList::InsertNode(int key){
- Node *currentNode = header;
- Node *update[listMaximumLevel];
- for(int i=listMaximumLevel;i>=0;i--){
- while (currentNode->nextNodes[i] != nullptr && currentNode->nextNodes[i]->key <= key){
- currentNode = currentNode->nextNodes[i];
- if(currentNode->key == key){
- currentNode->c = 'D';
- return false; //w liscie znajduje sie juz wezel z danym kluczem
- }
- }
- update[i] = currentNode;
- }
- Node *nodeToInsert = new Node(key, rand(), 'T');
- int nodeLevel = RandomLevel();
- for(int i=0;i<=nodeLevel;i++){
- nodeToInsert->nextNodes[i] = update[i]->nextNodes[i];
- update[i]->nextNodes[i] = nodeToInsert;
- }
- return true;
- }
- void SkipList::displayList()
- {
- cout<<"\n*****Skip List *****"<<"\n";
- for (int i=listMaximumLevel;i>=0;i--)
- {
- Node *node = header->nextNodes[i];
- cout << "Level " << i << ": ";
- while (node != nullptr)
- {
- cout << node->key<<" ";
- node = node->nextNodes[i];
- }
- cout << "\n";
- }
- };
- void SkipList::InsertNodesBulk(int n){
- int insertedCounter = 0;
- while(insertedCounter < n){
- bool isNodeUnique = InsertNode((rand()%10000)+99);
- if(isNodeUnique == true){
- insertedCounter++;
- }else{
- insertedCounter--;
- }
- }
- }
- // Driver to test above code
- int main()
- {
- srand((unsigned)time(0));
- clock_t begin, end;
- double time_spent;
- begin = clock();
- int N;
- int LMAX;
- int k1;
- int k2;
- int k3;
- int k4;
- int k5;
- FILE* fp = fopen("inlab02.txt", "r");
- if (fp == NULL)
- return -1;
- fscanf (fp, "%d %d %d %d %d %d %d", &N, &LMAX, &k1, &k2, &k3, &k4, &k5);
- fclose(fp);
- SkipList* sList = new SkipList(LMAX, 0.5);
- try{
- sList->SearchForNode(k1);
- }
- catch(runtime_error e){
- cout << e.what() << endl;
- }
- sList->InsertNodesBulk(N);
- for(int i=0;i<LMAX;i++){
- cout << to_string(sList->AmountOfNodes(i)) << endl;
- }
- for(int i=0;i<LMAX;i++){
- cout << sList->PrintListOfNodes(i,20);
- }
- sList->InsertNode(k2);
- cout << sList->PrintListOfNodes(0,20);
- sList->InsertNode(k3);
- cout << sList->PrintListOfNodes(0,20);
- sList->InsertNode(k4);
- cout << sList->PrintListOfNodes(0,20);
- sList->InsertNode(k5);
- cout << sList->PrintListOfNodes(0,20);
- for(int i=0;i<LMAX;i++){
- cout << to_string(sList->AmountOfNodes(i)) << endl;
- }
- for(int i=0;i<LMAX;i++){
- cout << sList->PrintListOfNodes(i,20);
- }
- sList->RemoveNode(k3);
- sList->RemoveNode(k2);
- sList->RemoveNode(k5);
- for(int i=0;i<LMAX;i++){
- cout << to_string(sList->AmountOfNodes(i)) << endl;
- }
- for(int i=0;i<LMAX;i++){
- cout << sList->PrintListOfNodes(i,20);
- }
- //sList->displayList();
- end = clock();
- time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
- cout << to_string(time_spent);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement