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 ***************************************************************************/
27 #define uchar unsigned char
30 #define ulong unsigned long
40 void callHandleUpdateCounters(RBNode *n, RBTree *T);
41 void callHandleUpdateCountersOnPathToRoot(RBNode *n, RBTree *T);
44 class HandleNode : public RBNode {
46 ulong key; //maximum for internal nodes
52 : RBNode(this), key(0), subtreeSize(0), maxkey(0){
56 HandleNode(HandleNode *n, ulong key)
57 : RBNode(n), key(key), subtreeSize(1), maxkey(key){
61 HandleNode* getParent(){
62 return ((HandleNode*) ((RBNode*) this)->parent);
65 HandleNode* getLeft(){
66 return ((HandleNode*) ((RBNode*) this)->left);
69 HandleNode* getRight(){
70 return ((HandleNode*) ((RBNode*) this)->right);
73 void setParent(HandleNode* n){
74 ((RBNode*) this)->parent=(RBNode*)n;
77 void setLeft(HandleNode* n){
78 ((RBNode*) this)->left=(RBNode*)n;
81 void setRight(HandleNode* n){
82 ((RBNode*) this)->right=(RBNode*)n;
87 class Handle : public RBTree{
92 setNil(new HandleNode());
97 void setRoot(HandleNode* n){
98 ((RBTree*) this)->root=(RBNode*)n;
101 HandleNode* getRoot(){
102 return ((HandleNode*) ((RBTree*) this)->root);
105 void setNil(HandleNode* n){
106 ((RBTree*) this)->nil=(RBNode*)n;
109 HandleNode* getNil(){
110 return ((HandleNode*) ((RBTree*) this)->nil);
115 return (getRoot()!=getNil())?getRoot()->subtreeSize:0;
120 ulong getPos(ulong key);
121 ulong* getEndPositions();
123 HandleNode* getKey(ulong key);
124 void deleteKey(ulong key);
125 void updateCountersOnPathToRoot(HandleNode *n);
126 void updateCounters(HandleNode *n);
128 HandleNode* getNewKey();