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 ***************************************************************************/
23 //TODO check star color of the nodes pos and handle!
29 #define uchar unsigned char
32 #define ulong unsigned long
41 void callPosUpdateCounters(RBNode *n, RBTree *T);
42 void callPosUpdateCountersOnPathToRoot(RBNode *n, RBTree *T);
44 class PosNode : public RBNode {
47 HandleNode *handleNode;
49 ulong textSize; // size including endmarker!
50 //ulong sumTextSize; // sum of textlength of all texts located in this subtree;
53 : RBNode(this),subtreeSize(0),textSize(0) {
56 PosNode(PosNode *n, ulong textSize)
57 : RBNode(n),subtreeSize(1),textSize(textSize) {
62 return ((PosNode*) ((RBNode*) this)->parent);
66 return ((PosNode*) ((RBNode*) this)->left);
70 return ((PosNode*) ((RBNode*) this)->right);
73 void setParent(PosNode* n){
74 ((RBNode*) this)->parent=(RBNode*)n;
77 void setLeft(PosNode* n){
78 ((RBNode*) this)->left=(RBNode*)n;
81 void setRight(PosNode* n){
82 ((RBNode*) this)->right=(RBNode*)n;
86 class Pos: public RBTree
97 Pos(ulong sampleInterval){
98 setNil(new PosNode());
100 this->sampleInterval=sampleInterval;
103 void setRoot(PosNode* n){
104 ((RBTree*) this)->root=(RBNode*)n;
108 return ((PosNode*) ((RBTree*) this)->root);
111 void setNil(PosNode* n){
112 ((RBTree*) this)->nil=(RBNode*)n;
116 return ((PosNode*) ((RBTree*) this)->nil);
120 return (getRoot()!=getNil())?getRoot()->subtreeSize:0;
125 ulong getPos(PosNode *n);
128 PosNode* getPosNode(ulong text);
129 ulong getTextSize(ulong pos);
130 void deleteText(ulong pos);
131 void deletePosNode(PosNode *n);
132 ulong appendText(ulong textSize);
134 void updateCountersOnPathToRoot(PosNode *n);
135 void updateCounters(PosNode *n);