handle.h

   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
  23 #ifndef Handle
  24 #define Handle Handle
  25
  26 #ifndef uchar
  27 #define uchar unsigned char
  28 #endif
  29 #ifndef ulong
  30 #define ulong unsigned long
  31 #endif
  32
  33 #include "rbtree.h"
  34 #include "pos.h"
  35
  36
  37 class Pos;
  38 class PosNode;
  39
  40 void callHandleUpdateCounters(RBNode *n, RBTree *T);
  41 void callHandleUpdateCountersOnPathToRoot(RBNode *n, RBTree *T);
  42
  43
  44 class HandleNode : public RBNode {
  45         public:
  46         ulong key; //maximum for internal nodes
  47         ulong subtreeSize;
  48         ulong maxkey;
  49         PosNode *posNode;
  50
  51         HandleNode()
  52                 : RBNode(this), key(0), subtreeSize(0), maxkey(0){
  53         }
  54
  55
  56         HandleNode(HandleNode *n, ulong key)
  57                 : RBNode(n), key(key), subtreeSize(1), maxkey(key){
  58         }
  59
  60
  61         HandleNode* getParent(){
  62                 return ((HandleNode*) ((RBNode*) this)->parent);
  63         }
  64
  65         HandleNode* getLeft(){
  66                 return ((HandleNode*) ((RBNode*) this)->left);
  67         }
  68
  69         HandleNode* getRight(){
  70                 return ((HandleNode*) ((RBNode*) this)->right);
  71         }
  72
  73         void setParent(HandleNode* n){
  74                 ((RBNode*) this)->parent=(RBNode*)n;
  75         }
  76
  77         void setLeft(HandleNode* n){
  78                 ((RBNode*) this)->left=(RBNode*)n;
  79         }
  80
  81         void setRight(HandleNode* n){
  82                 ((RBNode*) this)->right=(RBNode*)n;
  83         }
  84
  85 };
  86
  87 class Handle : public RBTree{
  88         public:
  89         Pos *pos;
  90
  91         Handle(){
  92                 setNil(new HandleNode());
  93                 setRoot(getNil());
  94         }
  95
  96
  97         void setRoot(HandleNode* n){
  98                 ((RBTree*) this)->root=(RBNode*)n;
  99         }
 100
 101         HandleNode* getRoot(){
 102                 return ((HandleNode*) ((RBTree*) this)->root);
 103         }
 104
 105         void setNil(HandleNode* n){
 106                 ((RBTree*) this)->nil=(RBNode*)n;
 107         }
 108
 109         HandleNode* getNil(){
 110                 return ((HandleNode*) ((RBTree*) this)->nil);
 111         }
 112
 113
 114         ulong getSize(){
 115                 return (getRoot()!=getNil())?getRoot()->subtreeSize:0;
 116         }
 117
 118         ulong* getKeys();
 119
 120         ulong getPos(ulong key);
 121         ulong* getEndPositions();
 122
 123         HandleNode* getKey(ulong key);
 124         void deleteKey(ulong key);
 125         void updateCountersOnPathToRoot(HandleNode *n);
 126         void updateCounters(HandleNode *n);
 127
 128         HandleNode* getNewKey();
 129
 130
 131
 132 };
 133
 134 #endif