Advertisement
Guest User

Untitled

a guest
Apr 3rd, 2020
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6.  
  7. struct Node{
  8.     int key;
  9.     double d;
  10.     char c;
  11.     Node *nextNodes[10];
  12.     Node(int, double, char);
  13. };
  14.  
  15. class SkipList{
  16.     int listMaximumLevel;
  17.     Node* header;
  18.  
  19.     public:
  20.     SkipList(int, float);
  21.     float P;
  22.     void displayList();
  23.     bool InsertNode(int);
  24.     void RemoveNode(int);
  25.     void InsertNodesBulk(int);
  26.     Node* SearchForNode(int);
  27.     int RandomLevel();
  28.     string PrintListOfNodes(int, int);
  29.     int AmountOfNodes(int);
  30. };
  31.  
  32. int SkipList::AmountOfNodes(int level){
  33.     Node* currentNode = header;
  34.     int amount =0;
  35.     while(currentNode->nextNodes[level]!=nullptr){
  36.         currentNode = currentNode->nextNodes[level];
  37.         amount++;
  38.     }
  39.     return amount;
  40. }
  41. string SkipList::PrintListOfNodes(int minimumLevel, int n){
  42.         Node* currentNode = header;
  43.         string output = "";
  44.         for(int i=0;i<n;i++){
  45.                 if(currentNode->nextNodes[minimumLevel]!=nullptr){
  46.                 currentNode = currentNode->nextNodes[minimumLevel];
  47.                 output+=to_string(currentNode->key)+" ";
  48.                 }
  49.         }
  50.         cout << output;
  51.           return output;
  52. }
  53.  
  54. void SkipList::RemoveNode(int key){
  55.  
  56.     Node *currentNode = header;
  57.     Node *update[listMaximumLevel];
  58.  
  59.     for(int i=listMaximumLevel;i>=0;i--){
  60.         while (currentNode->nextNodes[i] != nullptr && currentNode->nextNodes[i]->key < key){
  61.             currentNode = currentNode->nextNodes[i];
  62.         }
  63.         cout << to_string(currentNode->key)<< endl;
  64.         update[i] = currentNode;
  65.     }
  66.     if(update[0]->nextNodes[0]->key != key){
  67.         throw runtime_error("Remove: Node not found");
  68.     }
  69.     currentNode = update[0]->nextNodes[0];
  70.     for(int i=0;i<=listMaximumLevel;i++){
  71.             if(update[i]->nextNodes[i] != nullptr && update[i]->nextNodes[i]->key == key){
  72.                     if(update[i]->nextNodes[i]->nextNodes[i]!=nullptr){
  73.                            update[i]->nextNodes[i] = update[i]->nextNodes[i]->nextNodes[i];
  74.                            }else{
  75.                                update[i]->nextNodes[i] = nullptr;
  76.                            }
  77.             }
  78.             else{
  79.                 return;
  80.                 update[i]->nextNodes[i] == nullptr;
  81.         }
  82.     }
  83.     delete currentNode;
  84. }
  85.  
  86. Node* SkipList::SearchForNode(int key){
  87.     Node* currentNode = header;
  88.         for(int i=listMaximumLevel;i>=0;i--){
  89.             while (currentNode->nextNodes[i] != nullptr && currentNode->nextNodes[i]->key <= key){
  90.                 currentNode = currentNode->nextNodes[i];
  91.                 if(currentNode->key == key){
  92.                     return currentNode;
  93.                 }
  94.             }
  95.         }
  96.     throw runtime_error("Search: Node not found");
  97. }
  98.  
  99. SkipList::SkipList(int maxLevel, float p){
  100.     this->listMaximumLevel = maxLevel;
  101.     this->P = p;
  102.     header = new Node(0,0,'a');
  103.     for(int i=0;i<maxLevel;i++){
  104.         header->nextNodes[i] == nullptr;
  105.     }
  106. }
  107.  
  108. Node::Node(int key, double value, char c){
  109.     this->key = key;
  110.     this->d = value;
  111.     this->c = c;
  112. };
  113.  
  114. int SkipList::RandomLevel(){
  115.     int level = 0;
  116.     while(rand()%100 < P*100 && level < listMaximumLevel){
  117.         level++;
  118.     }
  119.     return level;
  120. }
  121. bool SkipList::InsertNode(int key){
  122.     Node *currentNode = header;
  123.     Node *update[listMaximumLevel];
  124.     for(int i=listMaximumLevel;i>=0;i--){
  125.         while (currentNode->nextNodes[i] != nullptr && currentNode->nextNodes[i]->key <= key){
  126.             currentNode = currentNode->nextNodes[i];
  127.             if(currentNode->key == key){
  128.                 currentNode->c = 'D';
  129.                 return false; //w liscie znajduje sie juz wezel z danym kluczem
  130.             }
  131.         }
  132.         update[i] = currentNode;
  133.     }
  134.     Node *nodeToInsert = new Node(key, rand(), 'T');
  135.  
  136.     int nodeLevel = RandomLevel();
  137.     for(int i=0;i<=nodeLevel;i++){
  138.         nodeToInsert->nextNodes[i] = update[i]->nextNodes[i];
  139.         update[i]->nextNodes[i] = nodeToInsert;
  140.     }
  141.     return true;
  142. }
  143. void SkipList::displayList()
  144. {
  145.     cout<<"\n*****Skip List *****"<<"\n";
  146.     for (int i=listMaximumLevel;i>=0;i--)
  147.     {
  148.         Node *node = header->nextNodes[i];
  149.         cout << "Level " << i << ": ";
  150.         while (node != nullptr)
  151.         {
  152.             cout << node->key<<" ";
  153.             node = node->nextNodes[i];
  154.         }
  155.         cout << "\n";
  156.     }
  157. };
  158.  
  159.  
  160. void SkipList::InsertNodesBulk(int n){
  161.     int insertedCounter = 0;
  162.     while(insertedCounter < n){
  163.         bool isNodeUnique = InsertNode((rand()%10000)+99);
  164.         if(isNodeUnique == true){
  165.             insertedCounter++;
  166.         }else{
  167.         insertedCounter--;
  168.         }
  169.     }
  170. }
  171.  
  172. // Driver to test above code
  173. int main()
  174. {
  175.     srand((unsigned)time(0));
  176.  
  177.         clock_t begin, end;
  178.     double time_spent;
  179.     begin = clock();
  180.  
  181.  
  182.     int N;
  183.     int LMAX;
  184.     int k1;
  185.     int k2;
  186.     int k3;
  187.     int k4;
  188.     int k5;
  189.     FILE* fp = fopen("inlab02.txt", "r");
  190.     if (fp == NULL)
  191.         return -1;
  192.     fscanf (fp, "%d %d %d %d %d %d %d", &N, &LMAX, &k1, &k2, &k3, &k4, &k5);
  193.     fclose(fp);
  194.  
  195.    SkipList* sList = new SkipList(LMAX, 0.5);
  196.     try{
  197.  
  198.     sList->SearchForNode(k1);
  199.        }
  200.         catch(runtime_error e){
  201.         cout << e.what() << endl;
  202.     }
  203.     sList->InsertNodesBulk(N);
  204.     for(int i=0;i<LMAX;i++){
  205.         cout << to_string(sList->AmountOfNodes(i)) << endl;
  206.     }
  207.     for(int i=0;i<LMAX;i++){
  208.         cout << sList->PrintListOfNodes(i,20);
  209.     }
  210.     sList->InsertNode(k2);
  211.      cout << sList->PrintListOfNodes(0,20);
  212.     sList->InsertNode(k3);
  213.      cout << sList->PrintListOfNodes(0,20);
  214.     sList->InsertNode(k4);
  215.      cout << sList->PrintListOfNodes(0,20);
  216.     sList->InsertNode(k5);
  217.      cout << sList->PrintListOfNodes(0,20);
  218.     for(int i=0;i<LMAX;i++){
  219.         cout << to_string(sList->AmountOfNodes(i)) << endl;
  220.     }
  221.   for(int i=0;i<LMAX;i++){
  222.         cout << sList->PrintListOfNodes(i,20);
  223.     }
  224.     sList->RemoveNode(k3);
  225.     sList->RemoveNode(k2);
  226.     sList->RemoveNode(k5);
  227.        for(int i=0;i<LMAX;i++){
  228.         cout << to_string(sList->AmountOfNodes(i)) << endl;
  229.     }
  230.       for(int i=0;i<LMAX;i++){
  231.         cout << sList->PrintListOfNodes(i,20);
  232.     }
  233.  
  234.     //sList->displayList();
  235.  
  236.     end = clock();
  237.     time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  238.  
  239.     cout << to_string(time_spent);
  240.  
  241.  
  242.  
  243.    return 0;
  244. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement