From 0f793111ef2bdfc44c395577c5d56373249e003a Mon Sep 17 00:00:00 2001 From: nvalimak Date: Fri, 9 Jan 2009 13:13:52 +0000 Subject: [PATCH] Not needed. git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/TextCollection@42 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- handle.cpp | 288 ----------------------------------------------------- 1 file changed, 288 deletions(-) delete mode 100644 handle.cpp diff --git a/handle.cpp b/handle.cpp deleted file mode 100644 index 9568dd4..0000000 --- a/handle.cpp +++ /dev/null @@ -1,288 +0,0 @@ - -/*************************************************************************** - * Copyright (C) 2006 by Wolfgang Gerlach * - * No object matches key 'wgerlach'. * - * * - * This program is free software; you can redistribute it and/or modify * - * it under the terms of the GNU General Public License as published by * - * the Free Software Foundation; either version 2 of the License, or * - * (at your option) any later version. * - * * - * This program is distributed in the hope that it will be useful, * - * but WITHOUT ANY WARRANTY; without even the implied warranty of * - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * - * GNU General Public License for more details. * - * * - * You should have received a copy of the GNU General Public License * - * along with this program; if not, write to the * - * Free Software Foundation, Inc., * - * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * - ***************************************************************************/ - -#include -#include - -#include "handle.h" - -using std::cerr; -using std::cout; -using std::endl; - -ulong Handle::getPos(ulong key){ - HandleNode *n = getKey(key); - if (n==0) return 0; - - PosNode *p = n->posNode; - - #ifndef NDEBUG - if (p==pos->getNil()) { - cerr << "error: Handle::getPos: no PosNode found." << endl; - exit(EXIT_FAILURE); - } - #endif - return (this->pos->getPos(p)); -} - -ulong* Handle::getEndPositions(){ - ulong num = getSize(); - ulong i = 0; - - if (this->root == getNil()) return 0; - - ulong *positions= new ulong[num]; - - - HandleNode *n = (HandleNode*) treeMinimum(root); - while (n != getNil()) { - - //printf("node: %d", n); - positions[i] = this->pos->getPos(n->posNode); - i++; - n = (HandleNode*) treeSuccessor((RBNode*) n); - } - return positions; -} - - -ulong* Handle::getKeys(){ - ulong num = getSize(); - ulong i = 0; - - if (this->root == getNil()) return 0; - - ulong *keys= new ulong[num]; - - - HandleNode *n = (HandleNode*) treeMinimum(root); - #ifndef NDEBUG - HandleNode *oldn; - #endif - while (n != getNil()) { - - //printf("node: %d", n); - keys[i] = n->key; - i++; - #ifndef NDEBUG - oldn = n; - #endif - n = (HandleNode*) treeSuccessor((RBNode*) n); - #ifndef NDEBUG - if (n == oldn) { - cerr << "old!" << endl; - exit(EXIT_FAILURE); - } - #endif - } - #ifndef NDEBUG - if (num != i) { - cerr << "num: " << num << endl; - cerr << "i: " << i << endl; - cerr << "error: Handle::getKeys: key number was not correct." << endl; - exit(EXIT_FAILURE); - } - #endif - return keys; -} - -void Handle::deleteKey(ulong key){ - - HandleNode *n = getKey(key); - this->pos->deletePosNode(n->posNode); - - rbDelete( n, callHandleUpdateCountersOnPathToRoot); - delete n; -} - - - - -HandleNode* Handle::getKey(ulong key){ - HandleNode *n= getRoot(); - while (n != getNil()) { - if (n->key == key) return n; - if (n->getLeft() != getNil()) { - if (key <= n->getLeft()->maxkey) n=n->getLeft(); - else n=n->getRight(); - } - else n=n->getRight(); - } - - - return 0; -} - -void Handle::updateCountersOnPathToRoot(HandleNode *n) { - while (n != getNil()) { - updateCounters(n); - - n = n->getParent(); - } -} - - -void Handle::updateCounters(HandleNode *n) { - #ifndef NDEBUG - if (n == getNil()) { - cerr << "error: Handle::updateCounters" << endl; - exit(EXIT_FAILURE); - } - #endif - n->subtreeSize=1; - - - n->subtreeSize += n->getLeft()->subtreeSize; - - - if ( n->getRight() != getNil()) { - n->subtreeSize += n->getRight()->subtreeSize; - n->maxkey=n->getRight()->maxkey; - } else n->maxkey=n->key; - -} - - -HandleNode* Handle::getNewKey(){ - HandleNode *n= getRoot(); - - if (n == getNil()) { - //tree is empty - HandleNode *newLeaf= new HandleNode(getNil(),1); // 1=smallest key, 0 = error - setRoot(newLeaf); - ((RBNode*)newLeaf)->color=BLACK; - - return newLeaf; - } - - if (n->maxkey == n->subtreeSize) { - // tree is full - HandleNode *last = (HandleNode*) treeMaximum(n); - - - HandleNode *newLeaf= new HandleNode(getNil(), n->maxkey+1); - - last->setRight(newLeaf); - newLeaf->setParent(last); - - if (newLeaf->getParent() != getNil()) updateCountersOnPathToRoot(newLeaf->getParent()); - - rbInsertFixup(newLeaf, callHandleUpdateCounters); - - return newLeaf; - } - - HandleNode *newNode; - ulong smallerkeys = 0; - ulong lmax; //getLeft()->maxkey - ulong lsub; //n->getLeft()->subtreeSize - while (true) { - cout << "search first free key" << endl; - // search first free key - - lmax = n->getLeft()->maxkey; - lsub = n->getLeft()->subtreeSize; - - - if (lmax == 0) { // no left child - if (smallerkeys+1 < n->key) { // check if it is free - newNode= new HandleNode(getNil(), smallerkeys+1); - newNode->setParent(n); - n->setLeft(newNode); - updateCountersOnPathToRoot(n); - rbInsertFixup(newNode, callHandleUpdateCounters); - return newNode; - } - } else { //left child exists - if ( lmax > (lsub + smallerkeys) ) { - // free key at left subtree - n=n->getLeft(); - continue; - } else if (lmax + 1 < n->key) { // full left subtree, check if it is free inbetween - // insert to predecessor - n=(HandleNode*)treePredecessor(n); - //found place -> :predeccessor new key = lmax + 1 - newNode= new HandleNode(getNil(), lmax+1); - newNode->setParent(n); - n->setRight(newNode); - updateCountersOnPathToRoot(n); - rbInsertFixup(newNode, callHandleUpdateCounters); - return newNode; - - } - } - - smallerkeys += 1+lsub; - - if (n->getRight() == getNil()) { // no right child, must be free - newNode= new HandleNode(getNil(), smallerkeys+1); - newNode->setParent(n); - n->setRight(newNode); - updateCountersOnPathToRoot(n); - rbInsertFixup(newNode, callHandleUpdateCounters); - return newNode; - } else { //right child exists - - //n=n->getRight(); - if (n->getRight()->maxkey-smallerkeys == n->getRight()->subtreeSize) { // right subTree is full, insert in front - ulong leftMinKey = n->getRight()->maxkey - n->getRight()->subtreeSize; - if (leftMinKey -1 > n->key) { //in front there is space - //insert new n-key + 1 - newNode= new HandleNode(getNil(), n->key+1); - n=(HandleNode*)treeSuccessor(n); - newNode->setParent(n); - n->setLeft(newNode); - updateCountersOnPathToRoot(n); - rbInsertFixup(newNode, callHandleUpdateCounters); - return newNode; - } else { - cerr << "error: Handle::getNewKey: no space ?!? " << endl; - exit(EXIT_FAILURE); - } - } else { - n=n->getRight(); - } - - - } - - #ifndef NDEBUG - if (n==getNil()) { - cerr << "error: Handle::getNewKey: (A) something wrong ! " << endl; - exit(EXIT_FAILURE); - } - #endif - } - #ifndef NDEBUG - cerr << "error: Handle::getNewKey: (B) something wrong ! " << endl; - exit(EXIT_FAILURE); - #endif - return 0; // error -} - -void callHandleUpdateCounters(RBNode *n, RBTree *T){ - ((Handle *)T)->updateCounters((HandleNode*) n); -} - -void callHandleUpdateCountersOnPathToRoot(RBNode *n, RBTree *T){ - ((Handle *)T)->updateCountersOnPathToRoot((HandleNode*) n); -} - -- 2.17.1