Advertisement
pavelperc

removeNext_working

Nov 2nd, 2018
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.03 KB | None | 0 0
  1.  
  2. // Version from Polina, hope it works..
  3.  
  4. template <class Value, class Key, int numLevels>
  5. void SkipList<Value, Key, numLevels>::removeNext(SkipList::Node* node)
  6. {
  7.     using namespace std;
  8.     if (node == nullptr || node->next == nullptr || node->next == Base::_preHead)
  9.         throw std::invalid_argument("You can't remove next node!");
  10.     Node* toDelete = node->next;
  11.  
  12.     Node* currNode = Base::_preHead;
  13.     int level = currNode->levelHighest;
  14.     while (level >= 0)
  15.     {
  16.         Node* right = currNode->nextJump[level];
  17.         //равенство ключей - но ссылки могут быть не равны!
  18.         //случай, когда ключи повторяются
  19.         if (right->key == toDelete->key)
  20.         {
  21.             //отец предполагаемого удаляемого (равного по ссылке)
  22.             Node* amongEqual = currNode;
  23.             while (amongEqual->nextJump[level] != Base::_preHead && amongEqual->nextJump[level]->key == toDelete->key)
  24.             {
  25.                 if (amongEqual->nextJump[level] == toDelete)
  26.                 {
  27.                     cout << "delete in equal" << endl;
  28.                     //переставляем ссылку
  29.                     amongEqual->nextJump[level] = amongEqual->nextJump[level]->nextJump[level];
  30.                     //едем вправо
  31.                     currNode = amongEqual;
  32.                     break;
  33.                 }
  34.                 cout << "in equal: right" << endl;
  35.                 amongEqual = amongEqual->nextJump[level];
  36.             }
  37.             cout << "down =" << endl;
  38.             level--;
  39.         }
  40.         else if (right == Base::_preHead || right->key > toDelete->key)
  41.         {
  42.             cout << "down >" << endl;
  43.             //едем вниз
  44.             level--;
  45.         }
  46.         else
  47.         {
  48.             cout << "right" << endl;
  49.             //едем вправо
  50.             currNode = right;
  51.         }
  52.     }
  53.     node->next = node->next->next;
  54.     delete toDelete;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement