2 /***************************************************************************
3 * Copyright (C) 2006 by Wolfgang Gerlach *
4 * No object matches key 'wgerlach'. *
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. *
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. *
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 ***************************************************************************/
31 ulong Handle::getPos(ulong key){
32 HandleNode *n = getKey(key);
35 PosNode *p = n->posNode;
38 if (p==pos->getNil()) {
39 cerr << "error: Handle::getPos: no PosNode found." << endl;
43 return (this->pos->getPos(p));
46 ulong* Handle::getEndPositions(){
47 ulong num = getSize();
50 if (this->root == getNil()) return 0;
52 ulong *positions= new ulong[num];
55 HandleNode *n = (HandleNode*) treeMinimum(root);
56 while (n != getNil()) {
58 //printf("node: %d", n);
59 positions[i] = this->pos->getPos(n->posNode);
61 n = (HandleNode*) treeSuccessor((RBNode*) n);
67 ulong* Handle::getKeys(){
68 ulong num = getSize();
71 if (this->root == getNil()) return 0;
73 ulong *keys= new ulong[num];
76 HandleNode *n = (HandleNode*) treeMinimum(root);
80 while (n != getNil()) {
82 //printf("node: %d", n);
88 n = (HandleNode*) treeSuccessor((RBNode*) n);
91 cerr << "old!" << endl;
98 cerr << "num: " << num << endl;
99 cerr << "i: " << i << endl;
100 cerr << "error: Handle::getKeys: key number was not correct." << endl;
107 void Handle::deleteKey(ulong key){
109 HandleNode *n = getKey(key);
110 this->pos->deletePosNode(n->posNode);
112 rbDelete( n, callHandleUpdateCountersOnPathToRoot);
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();
127 else n=n->getRight();
134 void Handle::updateCountersOnPathToRoot(HandleNode *n) {
135 while (n != getNil()) {
143 void Handle::updateCounters(HandleNode *n) {
146 cerr << "error: Handle::updateCounters" << endl;
153 n->subtreeSize += n->getLeft()->subtreeSize;
156 if ( n->getRight() != getNil()) {
157 n->subtreeSize += n->getRight()->subtreeSize;
158 n->maxkey=n->getRight()->maxkey;
159 } else n->maxkey=n->key;
164 HandleNode* Handle::getNewKey(){
165 HandleNode *n= getRoot();
169 HandleNode *newLeaf= new HandleNode(getNil(),1); // 1=smallest key, 0 = error
171 ((RBNode*)newLeaf)->color=BLACK;
176 if (n->maxkey == n->subtreeSize) {
178 HandleNode *last = (HandleNode*) treeMaximum(n);
181 HandleNode *newLeaf= new HandleNode(getNil(), n->maxkey+1);
183 last->setRight(newLeaf);
184 newLeaf->setParent(last);
186 if (newLeaf->getParent() != getNil()) updateCountersOnPathToRoot(newLeaf->getParent());
188 rbInsertFixup(newLeaf, callHandleUpdateCounters);
194 ulong smallerkeys = 0;
195 ulong lmax; //getLeft()->maxkey
196 ulong lsub; //n->getLeft()->subtreeSize
198 cout << "search first free key" << endl;
199 // search first free key
201 lmax = n->getLeft()->maxkey;
202 lsub = n->getLeft()->subtreeSize;
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);
210 updateCountersOnPathToRoot(n);
211 rbInsertFixup(newNode, callHandleUpdateCounters);
214 } else { //left child exists
215 if ( lmax > (lsub + smallerkeys) ) {
216 // free key at left subtree
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);
233 smallerkeys += 1+lsub;
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);
242 } else { //right child exists
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);
253 updateCountersOnPathToRoot(n);
254 rbInsertFixup(newNode, callHandleUpdateCounters);
257 cerr << "error: Handle::getNewKey: no space ?!? " << endl;
269 cerr << "error: Handle::getNewKey: (A) something wrong ! " << endl;
275 cerr << "error: Handle::getNewKey: (B) something wrong ! " << endl;
281 void callHandleUpdateCounters(RBNode *n, RBTree *T){
282 ((Handle *)T)->updateCounters((HandleNode*) n);
285 void callHandleUpdateCountersOnPathToRoot(RBNode *n, RBTree *T){
286 ((Handle *)T)->updateCountersOnPathToRoot((HandleNode*) n);