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 modquity *
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 ***************************************************************************/
30 ulong Pos::getPos(PosNode *n){
33 if (n->getLeft() != getNil()) position += n->getLeft()->subtreeSize;
35 while (n->getParent() != getNil()) {
36 if (n == n->getParent()->getRight()) {
38 if (n->getParent()->getLeft() != getNil()) position += n->getParent()->getLeft()->subtreeSize;
49 ulong Pos::getTextSize(ulong pos){
50 PosNode *n= getPosNode(pos);
55 void Pos::deleteText(ulong pos){
56 PosNode *n= getPosNode(pos);
58 // current node matches.
59 rbDelete(n, callPosUpdateCountersOnPathToRoot);
63 void Pos::deletePosNode(PosNode *n){
64 rbDelete(n, callPosUpdateCountersOnPathToRoot);
68 PosNode* Pos::getPosNode(ulong pos){
69 // smallest pos is 1 !
71 PosNode *n= getRoot();
73 ulong leftSubTreeSize;
75 leftSubTreeSize = n->getLeft()->subtreeSize;
77 if (pos == leftTree + leftSubTreeSize ) {
78 // current node matches.
80 } else if (pos < leftTree + leftSubTreeSize){
84 leftTree += leftSubTreeSize +1;
90 cerr << "error: Pos::getPosNode: text POS " << pos << " not found!" << endl;
97 ulong Pos::appendText(ulong textSize){
98 PosNode *n= getRoot();
101 PosNode *newLeaf= new PosNode(getNil(), textSize);
104 ((RBNode*)newLeaf)->color = BLACK;
106 HandleNode* hn = handle->getNewKey();
108 // connect handleNode and posNode:
109 hn->posNode = newLeaf;
110 newLeaf->handleNode = hn;
115 while (n->getRight() != getNil()) {
120 PosNode *newLeaf= new PosNode(getNil(), textSize);
123 n->setRight(newLeaf);
124 newLeaf->setParent(n);
126 updateCountersOnPathToRoot(newLeaf);
128 rbInsertFixup(newLeaf, callPosUpdateCounters);
130 HandleNode* hn = handle->getNewKey();
132 // connect handleNode and posNode:
133 hn->posNode = newLeaf;
134 newLeaf->handleNode = hn;
142 void Pos::updateCountersOnPathToRoot(PosNode *n) {
143 while (n != getNil()) {
150 void Pos::updateCounters(PosNode *n) {
152 //n->sumTextSize = n->textSize;
154 n->subtreeSize += n->getLeft()->subtreeSize;
155 //n->sumTextSize += n->getLeft()->sumTextSize;
157 n->subtreeSize += n->getRight()->subtreeSize;
158 //n->sumTextSize += n->getRight()->sumTextSize;
163 void callPosUpdateCounters(RBNode *n, RBTree *T){
164 ((Pos *)T)->updateCounters((PosNode*) n);
167 void callPosUpdateCountersOnPathToRoot(RBNode *n, RBTree *T){
168 ((Pos *)T)->updateCountersOnPathToRoot((PosNode*) n);