pos.cpp

   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 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.                                   *
  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 #include <iostream>
  23 #include <cstdlib>
  24
  25 #include "pos.h"
  26
  27 using std::cerr;
  28 using std::endl;
  29
  30 ulong Pos::getPos(PosNode *n){
  31         ulong position=0;
  32
  33         if (n->getLeft() != getNil()) position += n->getLeft()->subtreeSize;
  34
  35         while (n->getParent() != getNil()) {
  36                 if (n == n->getParent()->getRight()) {
  37                         // rightchild
  38                         if (n->getParent()->getLeft() != getNil()) position += n->getParent()->getLeft()->subtreeSize;
  39                         position++;
  40                 }
  41
  42                 n=n->getParent();
  43         }
  44
  45
  46         return position+1;
  47 }
  48
  49 ulong Pos::getTextSize(ulong pos){
  50         PosNode *n= getPosNode(pos);
  51
  52         return n->textSize;
  53 }
  54
  55 void Pos::deleteText(ulong pos){
  56         PosNode *n= getPosNode(pos);
  57
  58         // current node matches.
  59         rbDelete(n, callPosUpdateCountersOnPathToRoot);
  60         delete n;
  61 }
  62
  63 void Pos::deletePosNode(PosNode *n){
  64         rbDelete(n, callPosUpdateCountersOnPathToRoot);
  65         delete n;
  66 }
  67
  68 PosNode* Pos::getPosNode(ulong pos){
  69         // smallest pos is 1 !
  70         pos--;
  71         PosNode *n= getRoot();
  72         ulong leftTree=0;
  73         ulong leftSubTreeSize;
  74         while (true) {
  75                 leftSubTreeSize = n->getLeft()->subtreeSize;
  76
  77                 if (pos == leftTree + leftSubTreeSize ) {
  78                         // current node matches.
  79                         return n;
  80                 } else if (pos < leftTree + leftSubTreeSize){
  81                         n=n->getLeft();
  82                         }
  83                 else {
  84                         leftTree += leftSubTreeSize +1;
  85                         n=n->getRight();
  86                         }
  87         }
  88
  89
  90         cerr << "error: Pos::getPosNode: text POS " << pos << " not found!" << endl;
  91         exit(EXIT_FAILURE);
  92
  93         return  getNil();
  94 }
  95
  96
  97 ulong Pos::appendText(ulong textSize){
  98         PosNode *n= getRoot();
  99
 100         if (n == getNil()) {
 101                 PosNode *newLeaf= new PosNode(getNil(), textSize);
 102
 103                 setRoot(newLeaf);
 104                 ((RBNode*)newLeaf)->color = BLACK;
 105
 106                 HandleNode* hn = handle->getNewKey();
 107
 108                 // connect handleNode and posNode:
 109                 hn->posNode = newLeaf;
 110                 newLeaf->handleNode = hn;
 111
 112                 return hn->key;
 113         }
 114
 115         while (n->getRight() != getNil()) {
 116                 n=n->getRight();
 117         }
 118
 119         // new right child !
 120         PosNode *newLeaf= new PosNode(getNil(), textSize);
 121
 122
 123         n->setRight(newLeaf);
 124         newLeaf->setParent(n);
 125
 126         updateCountersOnPathToRoot(newLeaf);
 127
 128         rbInsertFixup(newLeaf, callPosUpdateCounters);
 129
 130         HandleNode* hn = handle->getNewKey();
 131
 132         // connect handleNode and posNode:
 133         hn->posNode = newLeaf;
 134         newLeaf->handleNode = hn;
 135
 136         return hn->key;
 137 }
 138
 139
 140
 141
 142 void Pos::updateCountersOnPathToRoot(PosNode *n) {
 143         while (n != getNil()) {
 144                 updateCounters(n);
 145
 146                 n = n->getParent();
 147         }
 148 }
 149
 150 void Pos::updateCounters(PosNode *n) {
 151         n->subtreeSize=1;
 152         //n->sumTextSize = n->textSize;
 153
 154         n->subtreeSize += n->getLeft()->subtreeSize;
 155         //n->sumTextSize += n->getLeft()->sumTextSize;
 156
 157         n->subtreeSize += n->getRight()->subtreeSize;
 158         //n->sumTextSize += n->getRight()->sumTextSize;
 159 }
 160
 161
 162
 163 void callPosUpdateCounters(RBNode *n, RBTree *T){
 164         ((Pos *)T)->updateCounters((PosNode*) n);
 165 }
 166
 167 void callPosUpdateCountersOnPathToRoot(RBNode *n, RBTree *T){
 168         ((Pos *)T)->updateCountersOnPathToRoot((PosNode*) n);
 169 }
 170