handle.cpp

   1
   2 /***************************************************************************
   3  *   Copyright (C) 2006 by Wolfgang Gerlach   *
   4  *   No object matches key 'wgerlach'.   *
   5  *                                                                         *
   6  *   This program is free software; you can redistribute it and/or modify  *
   7  *   it under the terms of the GNU General Public License as published by  *
   8  *   the Free Software Foundation; either version 2 of the License, or     *
   9  *   (at your option) any later version.                                   *
  10  *                                                                         *
  11  *   This program is distributed in the hope that it will be useful,       *
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  14  *   GNU General Public License for more details.                          *
  15  *                                                                         *
  16  *   You should have received a copy of the GNU General Public License     *
  17  *   along with this program; if not, write to the                         *
  18  *   Free Software Foundation, Inc.,                                       *
  19  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
  20  ***************************************************************************/
  21
  22 #include <iostream>
  23 #include <cstdlib>
  24
  25 #include "handle.h"
  26
  27 using std::cerr;
  28 using std::cout;
  29 using std::endl;
  30
  31 ulong Handle::getPos(ulong key){
  32         HandleNode *n = getKey(key);
  33         if (n==0) return 0;
  34
  35         PosNode *p = n->posNode;
  36
  37         #ifndef NDEBUG
  38         if (p==pos->getNil()) {
  39                 cerr << "error: Handle::getPos: no PosNode found." << endl;
  40                 exit(EXIT_FAILURE);
  41         }
  42         #endif
  43         return (this->pos->getPos(p));
  44 }
  45
  46 ulong* Handle::getEndPositions(){
  47         ulong num = getSize();
  48         ulong i = 0;
  49
  50         if (this->root == getNil()) return 0;
  51
  52         ulong *positions= new ulong[num];
  53
  54
  55         HandleNode *n = (HandleNode*) treeMinimum(root);
  56         while (n != getNil()) {
  57
  58                 //printf("node: %d", n);
  59             positions[i] = this->pos->getPos(n->posNode);
  60             i++;
  61                 n = (HandleNode*) treeSuccessor((RBNode*) n);
  62         }
  63         return positions;
  64 }
  65
  66
  67 ulong* Handle::getKeys(){
  68         ulong num = getSize();
  69         ulong i = 0;
  70
  71         if (this->root == getNil()) return 0;
  72
  73         ulong *keys= new ulong[num];
  74
  75
  76         HandleNode *n = (HandleNode*) treeMinimum(root);
  77         #ifndef NDEBUG
  78         HandleNode *oldn;
  79         #endif
  80         while (n != getNil()) {
  81
  82                 //printf("node: %d", n);
  83                 keys[i] = n->key;
  84                 i++;
  85                 #ifndef NDEBUG
  86                 oldn = n;
  87                 #endif
  88                 n = (HandleNode*) treeSuccessor((RBNode*) n);
  89                 #ifndef NDEBUG
  90                 if (n == oldn) {
  91                                 cerr << "old!" << endl;
  92                                 exit(EXIT_FAILURE);
  93                                 }
  94                 #endif
  95         }
  96         #ifndef NDEBUG
  97         if (num != i) {
  98                 cerr << "num: " << num << endl;
  99                 cerr << "i: " << i << endl;
 100                 cerr << "error: Handle::getKeys: key number was not correct." << endl;
 101                 exit(EXIT_FAILURE);
 102         }
 103         #endif
 104         return keys;
 105 }
 106
 107 void Handle::deleteKey(ulong key){
 108
 109         HandleNode *n = getKey(key);
 110         this->pos->deletePosNode(n->posNode);
 111
 112         rbDelete( n, callHandleUpdateCountersOnPathToRoot);
 113         delete n;
 114 }
 115
 116
 117
 118
 119 HandleNode* Handle::getKey(ulong key){
 120         HandleNode *n= getRoot();
 121         while (n != getNil()) {
 122                 if (n->key == key) return n;
 123                 if (n->getLeft() != getNil()) {
 124                         if (key <= n->getLeft()->maxkey) n=n->getLeft();
 125                         else n=n->getRight();
 126                 }
 127                 else n=n->getRight();
 128         }
 129
 130
 131         return 0;
 132 }
 133
 134 void Handle::updateCountersOnPathToRoot(HandleNode *n) {
 135         while (n != getNil()) {
 136                 updateCounters(n);
 137
 138                 n = n->getParent();
 139         }
 140 }
 141
 142
 143 void Handle::updateCounters(HandleNode *n) {
 144         #ifndef NDEBUG
 145         if (n == getNil()) {
 146                 cerr << "error: Handle::updateCounters" << endl;
 147                 exit(EXIT_FAILURE);
 148         }
 149         #endif
 150         n->subtreeSize=1;
 151
 152
 153         n->subtreeSize += n->getLeft()->subtreeSize;
 154
 155
 156         if ( n->getRight() != getNil()) {
 157                 n->subtreeSize += n->getRight()->subtreeSize;
 158                 n->maxkey=n->getRight()->maxkey;
 159         } else n->maxkey=n->key;
 160
 161 }
 162
 163
 164 HandleNode* Handle::getNewKey(){
 165         HandleNode *n= getRoot();
 166
 167         if (n == getNil()) {
 168                 //tree is empty
 169                 HandleNode *newLeaf= new HandleNode(getNil(),1); // 1=smallest key, 0 = error
 170                 setRoot(newLeaf);
 171                 ((RBNode*)newLeaf)->color=BLACK;
 172
 173                 return newLeaf;
 174         }
 175
 176         if (n->maxkey == n->subtreeSize) {
 177                 // tree is full
 178                 HandleNode *last = (HandleNode*) treeMaximum(n);
 179
 180
 181                 HandleNode *newLeaf= new HandleNode(getNil(), n->maxkey+1);
 182
 183                 last->setRight(newLeaf);
 184                 newLeaf->setParent(last);
 185
 186                 if (newLeaf->getParent() != getNil()) updateCountersOnPathToRoot(newLeaf->getParent());
 187
 188                 rbInsertFixup(newLeaf, callHandleUpdateCounters);
 189
 190                 return newLeaf;
 191         }
 192
 193         HandleNode *newNode;
 194         ulong smallerkeys = 0;
 195         ulong lmax; //getLeft()->maxkey
 196         ulong lsub; //n->getLeft()->subtreeSize
 197         while (true) {
 198                 cout << "search first free key" << endl;
 199                 // search first free key
 200
 201                 lmax = n->getLeft()->maxkey;
 202                 lsub = n->getLeft()->subtreeSize;
 203
 204
 205                 if (lmax == 0) { // no left child
 206                         if (smallerkeys+1 < n->key) { // check if it is free
 207                                 newNode= new HandleNode(getNil(), smallerkeys+1);
 208                                 newNode->setParent(n);
 209                                 n->setLeft(newNode);
 210                                 updateCountersOnPathToRoot(n);
 211                                 rbInsertFixup(newNode, callHandleUpdateCounters);
 212                                 return newNode;
 213                         }
 214                 } else { //left child exists
 215                         if ( lmax > (lsub + smallerkeys) ) {
 216                                 // free key at left subtree
 217                                 n=n->getLeft();
 218                                 continue;
 219                         } else if (lmax + 1 < n->key) { // full left subtree, check if it is free inbetween
 220                                 // insert to predecessor
 221                                 n=(HandleNode*)treePredecessor(n);
 222                                 //found place ->  :predeccessor new key = lmax + 1
 223                                 newNode= new HandleNode(getNil(), lmax+1);
 224                                 newNode->setParent(n);
 225                                 n->setRight(newNode);
 226                                 updateCountersOnPathToRoot(n);
 227                                 rbInsertFixup(newNode, callHandleUpdateCounters);
 228                                 return newNode;
 229
 230                         }
 231                 }
 232
 233                 smallerkeys += 1+lsub;
 234
 235                 if (n->getRight() == getNil()) { // no right child, must be free
 236                         newNode= new HandleNode(getNil(), smallerkeys+1);
 237                         newNode->setParent(n);
 238                         n->setRight(newNode);
 239                         updateCountersOnPathToRoot(n);
 240                         rbInsertFixup(newNode, callHandleUpdateCounters);
 241                         return newNode;
 242                 } else { //right child exists
 243
 244                         //n=n->getRight();
 245                         if (n->getRight()->maxkey-smallerkeys == n->getRight()->subtreeSize) { // right subTree is full, insert in front
 246                                 ulong leftMinKey = n->getRight()->maxkey - n->getRight()->subtreeSize;
 247                                 if (leftMinKey -1 >  n->key) { //in front there is space
 248                                         //insert new n-key + 1
 249                                         newNode= new HandleNode(getNil(), n->key+1);
 250                                         n=(HandleNode*)treeSuccessor(n);
 251                                         newNode->setParent(n);
 252                                         n->setLeft(newNode);
 253                                         updateCountersOnPathToRoot(n);
 254                                         rbInsertFixup(newNode, callHandleUpdateCounters);
 255                                         return newNode;
 256                                 } else {
 257                                         cerr << "error: Handle::getNewKey: no space ?!? " << endl;
 258                                         exit(EXIT_FAILURE);
 259                                 }
 260                         } else {
 261                                 n=n->getRight();
 262                         }
 263
 264
 265                 }
 266
 267                 #ifndef NDEBUG
 268                 if (n==getNil()) {
 269                         cerr << "error: Handle::getNewKey: (A) something wrong ! " << endl;
 270                         exit(EXIT_FAILURE);
 271                 }
 272                 #endif
 273         }
 274         #ifndef NDEBUG
 275         cerr << "error: Handle::getNewKey: (B) something wrong ! " << endl;
 276         exit(EXIT_FAILURE);
 277         #endif
 278         return 0; // error
 279 }
 280
 281 void callHandleUpdateCounters(RBNode *n, RBTree *T){
 282         ((Handle *)T)->updateCounters((HandleNode*) n);
 283 }
 284
 285 void callHandleUpdateCountersOnPathToRoot(RBNode *n, RBTree *T){
 286         ((Handle *)T)->updateCountersOnPathToRoot((HandleNode*) n);
 287 }
 288