/*
* Copyright 2001 Adrian Thurston <thurston@complang.org>
*/
/* This file is part of Aapl.
*
* Aapl is free software; you can redistribute it and/or modify it under the
* terms of the GNU Lesser General Public License as published by the Free
* Software Foundation; either version 2.1 of the License, or (at your option)
* any later version.
*
* Aapl 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 Lesser General Public License for
* more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with Aapl; if not, write to the Free Software Foundation, Inc., 59
* Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
/* This header is not wrapped in ifndef becuase it is not intended to
* be included by the user. */
#include <assert.h>
#include "fix_leaks.h"
#ifdef AAPL_NAMESPACE
namespace Aapl {
#endif
#ifdef WALKABLE
/* This is used by AvlTree, AvlMel and AvlMelKey so it
* must be protected by global ifdefs. */
#ifndef __AAPL_AVLI_EL__
#define __AAPL_AVLI_EL__
/**
* \brief Tree element properties for linked AVL trees.
*
* AvliTreeEl needs to be inherited by classes that intend to be element in an
* AvliTree.
*/
template<class SubClassEl> struct AvliTreeEl : TmpObject<AvliTreeEl<SubClassEl>>
{
/**
* \brief Tree pointers connecting element in a tree.
*/
SubClassEl *left, *right, *parent;
/**
* \brief Linked list pointers.
*/
SubClassEl *prev, *next;
/**
* \brief Height of the tree rooted at this element.
*
* Height is required by the AVL balancing algorithm.
*/
long height;
};
#endif /* __AAPL_AVLI_EL__ */
#else /* not WALKABLE */
/* This is used by All the non walkable trees so it must be
* protected by a global ifdef. */
#ifndef __AAPL_AVL_EL__
#define __AAPL_AVL_EL__
/**
* \brief Tree element properties for linked AVL trees.
*
* AvlTreeEl needs to be inherited by classes that intend to be element in an
* AvlTree.
*/
template<class SubClassEl> struct AvlTreeEl : TmpObject<AvlTreeEl<SubClassEl>>
{
/**
* \brief Tree pointers connecting element in a tree.
*/
SubClassEl *left, *right, *parent;
/**
* \brief Height of the tree rooted at this element.
*
* Height is required by the AVL balancing algorithm.
*/
long height;
};
#endif /* __AAPL_AVL_EL__ */
#endif /* def WALKABLE */
#if defined( AVLTREE_MAP )
#ifdef WALKABLE
/**
* \brief Tree element for AvliMap
*
* Stores the key and value pair.
*/
template <class Key, class Value> struct AvliMapEl :
public AvliTreeEl< AvliMapEl<Key, Value> >
{
AvliMapEl(const Key &key)
: key(key) { }
AvliMapEl(const Key &key, const Value &value)
: key(key), value(value) { }
const Key &getKey() const { return key; }
/** \brief The key. */
Key key;
/** \brief The value. */
Value value;
};
#else /* not WALKABLE */
/**
* \brief Tree element for AvlMap
*
* Stores the key and value pair.
*/
template <class Key, class Value> struct AvlMapEl :
public AvlTreeEl< AvlMapEl<Key, Value> >
{
AvlMapEl(const Key &key)
: key(key) { }
AvlMapEl(const Key &key, const Value &value)
: key(key), value(value) { }
const Key &getKey() const { return key; }
/** \brief The key. */
Key key;
/** \brief The value. */
Value value;
};
#endif /* def WALKABLE */
#elif defined( AVLTREE_SET )
#ifdef WALKABLE
/**
* \brief Tree element for AvliSet
*
* Stores the key.
*/
template <class Key> struct AvliSetEl :
public AvliTreeEl< AvliSetEl<Key> >
{
AvliSetEl(const Key &key) : key(key) { }
const Key &getKey() const { return key; }
/** \brief The key. */
Key key;
};
#else /* not WALKABLE */
/**
* \brief Tree element for AvlSet
*
* Stores the key.
*/
template <class Key> struct AvlSetEl :
public AvlTreeEl< AvlSetEl<Key> >
{
AvlSetEl(const Key &key) : key(key) { }
const Key &getKey() const { return key; }
/** \brief The key. */
Key key;
};
#endif /* def WALKABLE */
#endif /* AVLTREE_SET */
/* Common AvlTree Class */
template < AVLMEL_CLASSDEF > class AvlTree
#if !defined( AVL_KEYLESS ) && defined ( WALKABLE )
: public Compare, public BASELIST
#elif !defined( AVL_KEYLESS )
: public Compare
#elif defined( WALKABLE )
: public BASELIST
#endif
{
public:
/**
* \brief Create an empty tree.
*/
#ifdef WALKABLE
AvlTree() : root(0), treeSize(0) { }
#else
AvlTree() : root(0), head(0), tail(0), treeSize(0) { }
#endif
/**
* \brief Perform a deep copy of the tree.
*
* Each element is duplicated for the new tree. Copy constructors are used
* to create the new elements.
*/
AvlTree(const AvlTree &other);
#if defined( AVLTREE_MAP ) || defined( AVLTREE_SET )
/**
* \brief Clear the contents of the tree.
*
* All element are deleted.
*/
~AvlTree() { empty(); }
/**
* \brief Perform a deep copy of the tree.
*
* Each element is duplicated for the new tree. Copy constructors are used
* to create the new element. If this tree contains items, they are first
* deleted.
*
* \returns A reference to this.
*/
AvlTree &operator=( const AvlTree &tree );
/**
* \brief Transfer the elements of another tree into this.
*
* First deletes all elements in this tree.
*/
void transfer( AvlTree &tree );
#else
/**
* \brief Abandon all elements in the tree.
*
* Tree elements are not deleted.
*/
~AvlTree() {}
/**
* \brief Perform a deep copy of the tree.
*
* Each element is duplicated for the new tree. Copy constructors are used
* to create the new element. If this tree contains items, they are
* abandoned.
*
* \returns A reference to this.
*/
AvlTree &operator=( const AvlTree &tree );
/**
* \brief Transfer the elements of another tree into this.
*
* All elements in this tree are abandoned first.
*/
void transfer( AvlTree &tree );
#endif
#ifndef AVL_KEYLESS
/* Insert a element into the tree. */
Element *insert( Element *element, Element **lastFound = 0 );
#ifdef AVL_BASIC
/* Find a element in the tree. Returns the element if
* element exists, false otherwise. */
Element *find( const Element *element ) const;
#else
Element *insert( const Key &key, Element **lastFound = 0 );
#ifdef AVLTREE_MAP
Element *insert( const Key &key, const Value &val,
Element **lastFound = 0 );
#endif
/* Find a element in the tree. Returns the element if
* key exists, false otherwise. */
Element *find( const Key &key ) const;
/* Detach a element from the tree. */
Element *detach( const Key &key );
/* Detach and delete a element from the tree. */
bool remove( const Key &key );
#endif /* AVL_BASIC */
#endif /* AVL_KEYLESS */
/* Detach a element from the tree. */
Element *detach( Element *element );
/* Detach and delete a element from the tree. */
void remove( Element *element );
/* Free all memory used by tree. */
void empty();
/* Abandon all element in the tree. Does not delete element. */
void abandon();
/** Root element of the tree. */
Element *root;
#ifndef WALKABLE
Element *head, *tail;
#endif
/** The number of element in the tree. */
long treeSize;
/** \brief Return the number of elements in the tree. */
long length() const { return treeSize; }
/** \brief Return the number of elements in the tree. */
long size() const { return treeSize; }
/* Various classes for setting the iterator */
struct Iter;
struct IterFirst { IterFirst( const AvlTree &t ) : t(t) { } const AvlTree &t; };
struct IterLast { IterLast( const AvlTree &t ) : t(t) { } const AvlTree &t; };
struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; };
struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; };
#ifdef WALKABLE
/**
* \brief Avl Tree Iterator.
* \ingroup iterators
*/
struct Iter
{
/* Default construct. */
Iter() : ptr(0) { }
/* Construct from an avl tree and iterator-setting classes. */
Iter( const AvlTree &t ) : ptr(t.head) { }
Iter( const IterFirst &af ) : ptr(af.t.head) { }
Iter( const IterLast &al ) : ptr(al.t.tail) { }
Iter( const IterNext &an ) : ptr(findNext(an.i.ptr)) { }
Iter( const IterPrev &ap ) : ptr(findPrev(ap.i.ptr)) { }
/* Assign from a tree and iterator-setting classes. */
Iter &operator=( const AvlTree &tree ) { ptr = tree.head; return *this; }
Iter &operator=( const IterFirst &af ) { ptr = af.t.head; return *this; }
Iter &operator=( const IterLast &al ) { ptr = al.t.tail; return *this; }
Iter &operator=( const IterNext &an ) { ptr = findNext(an.i.ptr); return *this; }
Iter &operator=( const IterPrev &ap ) { ptr = findPrev(ap.i.ptr); return *this; }
/** \brief Less than end? */
bool lte() const { return ptr != 0; }
/** \brief At end? */
bool end() const { return ptr == 0; }
/** \brief Greater than beginning? */
bool gtb() const { return ptr != 0; }
/** \brief At beginning? */
bool beg() const { return ptr == 0; }
/** \brief At first element? */
bool first() const { return ptr && ptr->BASE_EL(prev) == 0; }
/** \brief At last element? */
bool last() const { return ptr && ptr->BASE_EL(next) == 0; }
/** \brief Implicit cast to Element*. */
operator Element*() const { return ptr; }
/** \brief Dereference operator returns Element&. */
Element &operator *() const { return *ptr; }
/** \brief Arrow operator returns Element*. */
Element *operator->() const { return ptr; }
/** \brief Move to next item. */
inline Element *operator++();
/** \brief Move to next item. */
inline Element *operator++(int);
/** \brief Move to next item. */
inline Element *increment();
/** \brief Move to previous item. */
inline Element *operator--();
/** \brief Move to previous item. */
inline Element *operator--(int);
/** \brief Move to previous item. */
inline Element *decrement();
/** \brief Return the next item. Does not modify this. */
IterNext next() const { return IterNext( *this ); }
/** \brief Return the previous item. Does not modify this. */
IterPrev prev() const { return IterPrev( *this ); }
private:
static Element *findPrev( Element *element ) { return element->BASE_EL(prev); }
static Element *findNext( Element *element ) { return element->BASE_EL(next); }
public:
/** \brief The iterator is simply a pointer. */
Element *ptr;
};
#else
/**
* \brief Avl Tree Iterator.
* \ingroup iterators
*/
struct Iter
{
/* Default construct. */
Iter() : ptr(0), tree(0) { }
/* Construct from a tree and iterator-setting classes. */
Iter( const AvlTree &t ) : ptr(t.head), tree(&t) { }
Iter( const IterFirst &af ) : ptr(af.t.head), tree(&af.t) { }
Iter( const IterLast &al ) : ptr(al.t.tail), tree(&al.t) { }
Iter( const IterNext &an ) : ptr(findNext(an.i.ptr)), tree(an.i.tree) { }
Iter( const IterPrev &ap ) : ptr(findPrev(ap.i.ptr)), tree(ap.i.tree) { }
/* Assign from a tree and iterator-setting classes. */
Iter &operator=( const AvlTree &t )
{ ptr = t.head; tree = &t; return *this; }
Iter &operator=( const IterFirst &af )
{ ptr = af.t.head; tree = &af.t; return *this; }
Iter &operator=( const IterLast &al )
{ ptr = al.t.tail; tree = &al.t; return *this; }
Iter &operator=( const IterNext &an )
{ ptr = findNext(an.i.ptr); tree = an.i.tree; return *this; }
Iter &operator=( const IterPrev &ap )
{ ptr = findPrev(ap.i.ptr); tree = ap.i.tree; return *this; }
/** \brief Less than end? */
bool lte() const { return ptr != 0; }
/** \brief At end? */
bool end() const { return ptr == 0; }
/** \brief Greater than beginning? */
bool gtb() const { return ptr != 0; }
/** \brief At beginning? */
bool beg() const { return ptr == 0; }
/** \brief At first element? */
bool first() const { return ptr && ptr == tree->head; }
/** \brief At last element? */
bool last() const { return ptr && ptr == tree->tail; }
/** \brief Implicit cast to Element*. */
operator Element*() const { return ptr; }
/** \brief Dereference operator returns Element&. */
Element &operator *() const { return *ptr; }
/** \brief Arrow operator returns Element*. */
Element *operator->() const { return ptr; }
/** \brief Move to next item. */
inline Element *operator++();
/** \brief Move to next item. */
inline Element *operator++(int);
/** \brief Move to next item. */
inline Element *increment();
/** \brief Move to previous item. */
inline Element *operator--();
/** \brief Move to previous item. */
inline Element *operator--(int);
/** \brief Move to previous item. */
inline Element *decrement();
/** \brief Return the next item. Does not modify this. */
IterNext next() const { return IterNext( *this ); }
/** \brief Return the previous item. Does not modify this. */
IterPrev prev() const { return IterPrev( *this ); }
private:
static Element *findPrev( Element *element );
static Element *findNext( Element *element );
public:
/** \brief The iterator is simply a pointer. */
Element *ptr;
/* The list is not walkable so we need to keep a pointerto the tree
* so we can test against head and tail in O(1) time. */
const AvlTree *tree;
};
#endif
/** \brief Return first element. */
IterFirst first() { return IterFirst( *this ); }
/** \brief Return last element. */
IterLast last() { return IterLast( *this ); }
protected:
/* Recursive worker for the copy constructor. */
Element *copyBranch( Element *element );
/* Recursively delete element in the tree. */
void deleteChildrenOf(Element *n);
/* rebalance the tree beginning at the leaf whose
* grandparent is unbalanced. */
Element *rebalance(Element *start);
/* Move up the tree from a given element, recalculating the heights. */
void recalcHeights(Element *start);
/* Move up the tree and find the first element whose
* grand-parent is unbalanced. */
Element *findFirstUnbalGP(Element *start);
/* Move up the tree and find the first element which is unbalanced. */
Element *findFirstUnbalEl(Element *start);
/* Replace a element in the tree with another element not in the tree. */
void replaceEl(Element *element, Element *replacement);
/* Remove a element from the tree and put another (normally a child of element)
* in its place. */
void removeEl(Element *element, Element *filler);
/* Once an insertion point is found at a leaf then do the insert. */
void attachRebal( Element *element, Element *parentEl, Element *lastLess );
};
/* Copy constructor. New up each item. */
template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE>::
AvlTree(const AvlTree<AVLMEL_TEMPUSE> &other)
#ifdef WALKABLE
:
/* Make an empty list, copyBranch will fill in the details for us. */
BASELIST()
#endif
{
treeSize = other.treeSize;
root = other.root;
#ifndef WALKABLE
head = 0;
tail = 0;
#endif
/* If there is a root, copy the tree. */
if ( other.root != 0 )
root = copyBranch( other.root );
}
#if defined( AVLTREE_MAP ) || defined( AVLTREE_SET )
/* Assignment does deep copy. */
template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE> &AvlTree<AVLMEL_TEMPUSE>::
operator=( const AvlTree &other )
{
/* Clear the tree first. */
empty();
/* Reset the list pointers, the tree copy will fill in the list for us. */
#ifdef WALKABLE
BASELIST::abandon();
#else
head = 0;
tail = 0;
#endif
/* Copy the entire tree. */
treeSize = other.treeSize;
root = other.root;
if ( other.root != 0 )
root = copyBranch( other.root );
return *this;
}
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
transfer(AvlTree<AVLMEL_TEMPUSE> &other)
{
/* Clear the tree first. */
empty();
treeSize = other.treeSize;
root = other.root;
#ifdef WALKABLE
BASELIST::head = other.BASELIST::head;
BASELIST::tail = other.BASELIST::tail;
BASELIST::listLen = other.BASELIST::listLen;
#else
head = other.head;
tail = other.tail;
#endif
other.abandon();
}
#else /* ! AVLTREE_MAP && ! AVLTREE_SET */
/* Assignment does deep copy. This version does not clear the tree first. */
template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE> &AvlTree<AVLMEL_TEMPUSE>::
operator=( const AvlTree &other )
{
/* Reset the list pointers, the tree copy will fill in the list for us. */
#ifdef WALKABLE
BASELIST::abandon();
#else
head = 0;
tail = 0;
#endif
/* Copy the entire tree. */
treeSize = other.treeSize;
root = other.root;
if ( other.root != 0 )
root = copyBranch( other.root );
return *this;
}
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
transfer(AvlTree<AVLMEL_TEMPUSE> &other)
{
treeSize = other.treeSize;
root = other.root;
#ifdef WALKABLE
BASELIST::head = other.BASELIST::head;
BASELIST::tail = other.BASELIST::tail;
BASELIST::listLen = other.BASELIST::listLen;
#else
head = other.head;
tail = other.tail;
#endif
other.abandon();
}
#endif
/*
* Iterator operators.
*/
/* Prefix ++ */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
operator++()
{
return ptr = findNext( ptr );
}
/* Postfix ++ */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
operator++(int)
{
Element *rtn = ptr;
ptr = findNext( ptr );
return rtn;
}
/* increment */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
increment()
{
return ptr = findNext( ptr );
}
/* Prefix -- */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
operator--()
{
return ptr = findPrev( ptr );
}
/* Postfix -- */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
operator--(int)
{
Element *rtn = ptr;
ptr = findPrev( ptr );
return rtn;
}
/* decrement */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
decrement()
{
return ptr = findPrev( ptr );
}
#ifndef WALKABLE
/* Move ahead one. */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
findNext( Element *element )
{
/* Try to go right once then infinite left. */
if ( element->BASE_EL(right) != 0 ) {
element = element->BASE_EL(right);
while ( element->BASE_EL(left) != 0 )
element = element->BASE_EL(left);
}
else {
/* Go up to parent until we were just a left child. */
while ( true ) {
Element *last = element;
element = element->BASE_EL(parent);
if ( element == 0 || element->BASE_EL(left) == last )
break;
}
}
return element;
}
/* Move back one. */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
findPrev( Element *element )
{
/* Try to go left once then infinite right. */
if ( element->BASE_EL(left) != 0 ) {
element = element->BASE_EL(left);
while ( element->BASE_EL(right) != 0 )
element = element->BASE_EL(right);
}
else {
/* Go up to parent until we were just a left child. */
while ( true ) {
Element *last = element;
element = element->BASE_EL(parent);
if ( element == 0 || element->BASE_EL(right) == last )
break;
}
}
return element;
}
#endif
/* Recursive worker for tree copying. */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
copyBranch( Element *element )
{
/* Duplicate element. Either the base element's copy constructor or defaul
* constructor will get called. Both will suffice for initting the
* pointers to null when they need to be. */
Element *retVal = new Element(*element);
/* If the left tree is there, copy it. */
if ( retVal->BASE_EL(left) ) {
retVal->BASE_EL(left) = copyBranch(retVal->BASE_EL(left));
retVal->BASE_EL(left)->BASE_EL(parent) = retVal;
}
#ifdef WALKABLE
BASELIST::addAfter( BASELIST::tail, retVal );
#else
if ( head == 0 )
head = retVal;
tail = retVal;
#endif
/* If the right tree is there, copy it. */
if ( retVal->BASE_EL(right) ) {
retVal->BASE_EL(right) = copyBranch(retVal->BASE_EL(right));
retVal->BASE_EL(right)->BASE_EL(parent) = retVal;
}
return retVal;
}
/* Once an insertion position is found, attach a element to the tree. */
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
attachRebal( Element *element, Element *parentEl, Element *lastLess )
{
/* Increment the number of element in the tree. */
treeSize += 1;
/* Set element's parent. */
element->BASE_EL(parent) = parentEl;
/* New element always starts as a leaf with height 1. */
element->BASE_EL(left) = 0;
element->BASE_EL(right) = 0;
element->BASE_EL(height) = 1;
/* Are we inserting in the tree somewhere? */
if ( parentEl != 0 ) {
/* We have a parent so we are somewhere in the tree. If the parent
* equals lastLess, then the last traversal in the insertion went
* left, otherwise it went right. */
if ( lastLess == parentEl ) {
parentEl->BASE_EL(left) = element;
#ifdef WALKABLE
BASELIST::addBefore( parentEl, element );
#endif
}
else {
parentEl->BASE_EL(right) = element;
#ifdef WALKABLE
BASELIST::addAfter( parentEl, element );
#endif
}
#ifndef WALKABLE
/* Maintain the first and last pointers. */
if ( head->BASE_EL(left) == element )
head = element;
/* Maintain the first and last pointers. */
if ( tail->BASE_EL(right) == element )
tail = element;
#endif
}
else {
/* No parent element so we are inserting the root. */
root = element;
#ifdef WALKABLE
BASELIST::addAfter( BASELIST::tail, element );
#else
head = tail = element;
#endif
}
/* Recalculate the heights. */
recalcHeights(parentEl);
/* Find the first unbalance. */
Element *ub = findFirstUnbalGP(element);
/* rebalance. */
if ( ub != 0 )
{
/* We assert that after this single rotation the
* tree is now properly balanced. */
rebalance(ub);
}
}
#ifndef AVL_KEYLESS
/**
* \brief Insert an existing element into the tree.
*
* If the insert succeeds and lastFound is given then it is set to the element
* inserted. If the insert fails then lastFound is set to the existing element in
* the tree that has the same key as element. If the element's avl pointers are
* already in use then undefined behaviour results.
*
* \returns The element inserted upon success, null upon failure.
*/
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
insert( Element *element, Element **lastFound )
{
long keyRelation;
Element *curEl = root, *parentEl = 0;
Element *lastLess = 0;
while (true) {
if ( curEl == 0 ) {
/* We are at an external element and did not find the key we were
* looking for. Attach underneath the leaf and rebalance. */
attachRebal( element, parentEl, lastLess );
if ( lastFound != 0 )
*lastFound = element;
return element;
}
#ifdef AVL_BASIC
keyRelation = this->compare( *element, *curEl );
#else
keyRelation = this->compare( element->BASEKEY(getKey()),
curEl->BASEKEY(getKey()) );
#endif
/* Do we go left? */
if ( keyRelation < 0 ) {
parentEl = lastLess = curEl;
curEl = curEl->BASE_EL(left);
}
/* Do we go right? */
else if ( keyRelation > 0 ) {
parentEl = curEl;
curEl = curEl->BASE_EL(right);
}
/* We have hit the target. */
else {
if ( lastFound != 0 )
*lastFound = curEl;
return 0;
}
}
}
#ifdef AVL_BASIC
/**
* \brief Find a element in the tree with the given key.
*
* \returns The element if key exists, null if the key does not exist.
*/
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
find( const Element *element ) const
{
Element *curEl = root;
long keyRelation;
while (curEl) {
keyRelation = this->compare( *element, *curEl );
/* Do we go left? */
if ( keyRelation < 0 )
curEl = curEl->BASE_EL(left);
/* Do we go right? */
else if ( keyRelation > 0 )
curEl = curEl->BASE_EL(right);
/* We have hit the target. */
else {
return curEl;
}
}
return 0;
}
#else
/**
* \brief Insert a new element into the tree with given key.
*
* If the key is not already in the tree then a new element is made using the
* Element(const Key &key) constructor and the insert succeeds. If lastFound is
* given then it is set to the element inserted. If the insert fails then
* lastFound is set to the existing element in the tree that has the same key as
* element.
*
* \returns The new element upon success, null upon failure.
*/
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
insert( const Key &key, Element **lastFound )
{
long keyRelation;
Element *curEl = root, *parentEl = 0;
Element *lastLess = 0;
while (true) {
if ( curEl == 0 ) {
/* We are at an external element and did not find the key we were
* looking for. Create the new element, attach it underneath the leaf
* and rebalance. */
Element *element = new Element( key );
attachRebal( element, parentEl, lastLess );
if ( lastFound != 0 )
*lastFound = element;
return element;
}
keyRelation = this->compare( key, curEl->BASEKEY(getKey()) );
/* Do we go left? */
if ( keyRelation < 0 ) {
parentEl = lastLess = curEl;
curEl = curEl->BASE_EL(left);
}
/* Do we go right? */
else if ( keyRelation > 0 ) {
parentEl = curEl;
curEl = curEl->BASE_EL(right);
}
/* We have hit the target. */
else {
if ( lastFound != 0 )
*lastFound = curEl;
return 0;
}
}
}
#ifdef AVLTREE_MAP
/**
* \brief Insert a new element into the tree with key and value.
*
* If the key is not already in the tree then a new element is constructed and
* the insert succeeds. If lastFound is given then it is set to the element
* inserted. If the insert fails then lastFound is set to the existing element in
* the tree that has the same key as element. This insert routine is only
* available in AvlMap because it is the only class that knows about a Value
* type.
*
* \returns The new element upon success, null upon failure.
*/
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
insert( const Key &key, const Value &val, Element **lastFound )
{
long keyRelation;
Element *curEl = root, *parentEl = 0;
Element *lastLess = 0;
while (true) {
if ( curEl == 0 ) {
/* We are at an external element and did not find the key we were
* looking for. Create the new element, attach it underneath the leaf
* and rebalance. */
Element *element = new Element( key, val );
attachRebal( element, parentEl, lastLess );
if ( lastFound != 0 )
*lastFound = element;
return element;
}
keyRelation = this->compare(key, curEl->getKey());
/* Do we go left? */
if ( keyRelation < 0 ) {
parentEl = lastLess = curEl;
curEl = curEl->BASE_EL(left);
}
/* Do we go right? */
else if ( keyRelation > 0 ) {
parentEl = curEl;
curEl = curEl->BASE_EL(right);
}
/* We have hit the target. */
else {
if ( lastFound != 0 )
*lastFound = curEl;
return 0;
}
}
}
#endif /* AVLTREE_MAP */
/**
* \brief Find a element in the tree with the given key.
*
* \returns The element if key exists, null if the key does not exist.
*/
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
find( const Key &key ) const
{
Element *curEl = root;
long keyRelation;
while (curEl) {
keyRelation = this->compare( key, curEl->BASEKEY(getKey()) );
/* Do we go left? */
if ( keyRelation < 0 )
curEl = curEl->BASE_EL(left);
/* Do we go right? */
else if ( keyRelation > 0 )
curEl = curEl->BASE_EL(right);
/* We have hit the target. */
else {
return curEl;
}
}
return 0;
}
/**
* \brief Find a element, then detach it from the tree.
*
* The element is not deleted.
*
* \returns The element detached if the key is found, othewise returns null.
*/
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
detach(const Key &key)
{
Element *element = find( key );
if ( element ) {
detach(element);
}
return element;
}
/**
* \brief Find, detach and delete a element from the tree.
*
* \returns True if the element was found and deleted, false otherwise.
*/
template <AVLMEL_TEMPDEF> bool AvlTree<AVLMEL_TEMPUSE>::
remove(const Key &key)
{
/* Assume not found. */
bool retVal = false;
/* Look for the key. */
Element *element = find( key );
if ( element != 0 ) {
/* If found, detach the element and delete. */
detach( element );
delete element;
retVal = true;
}
return retVal;
}
#endif /* AVL_BASIC */
#endif /* AVL_KEYLESS */
/**
* \brief Detach and delete a element from the tree.
*
* If the element is not in the tree then undefined behaviour results.
*/
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
remove(Element *element)
{
/* Detach and delete. */
detach(element);
delete element;
}
/**
* \brief Detach a element from the tree.
*
* If the element is not in the tree then undefined behaviour results.
*
* \returns The element given.
*/
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
detach(Element *element)
{
Element *replacement, *fixfrom;
long lheight, rheight;
#ifdef WALKABLE
/* Remove the element from the ordered list. */
BASELIST::detach( element );
#endif
/* Update treeSize. */
treeSize--;
/* Find a replacement element. */
if (element->BASE_EL(right))
{
/* Find the leftmost element of the right subtree. */
replacement = element->BASE_EL(right);
while (replacement->BASE_EL(left))
replacement = replacement->BASE_EL(left);
/* If replacing the element the with its child then we need to start
* fixing at the replacement, otherwise we start fixing at the
* parent of the replacement. */
if (replacement->BASE_EL(parent) == element)
fixfrom = replacement;
else
fixfrom = replacement->BASE_EL(parent);
#ifndef WALKABLE
if ( element == head )
head = replacement;
#endif
removeEl(replacement, replacement->BASE_EL(right));
replaceEl(element, replacement);
}
else if (element->BASE_EL(left))
{
/* Find the rightmost element of the left subtree. */
replacement = element->BASE_EL(left);
while (replacement->BASE_EL(right))
replacement = replacement->BASE_EL(right);
/* If replacing the element the with its child then we need to start
* fixing at the replacement, otherwise we start fixing at the
* parent of the replacement. */
if (replacement->BASE_EL(parent) == element)
fixfrom = replacement;
else
fixfrom = replacement->BASE_EL(parent);
#ifndef WALKABLE
if ( element == tail )
tail = replacement;
#endif
removeEl(replacement, replacement->BASE_EL(left));
replaceEl(element, replacement);
}
else
{
/* We need to start fixing at the parent of the element. */
fixfrom = element->BASE_EL(parent);
#ifndef WALKABLE
if ( element == head )
head = element->BASE_EL(parent);
if ( element == tail )
tail = element->BASE_EL(parent);
#endif
/* The element we are deleting is a leaf element. */
removeEl(element, 0);
}
/* If fixfrom is null it means we just deleted
* the root of the tree. */
if ( fixfrom == 0 )
return element;
/* Fix the heights after the deletion. */
recalcHeights(fixfrom);
/* Fix every unbalanced element going up in the tree. */
Element *ub = findFirstUnbalEl(fixfrom);
while ( ub )
{
/* Find the element to rebalance by moving down from the first unbalanced
* element 2 levels in the direction of the greatest heights. On the
* second move down, the heights may be equal ( but not on the first ).
* In which case go in the direction of the first move. */
lheight = ub->BASE_EL(left) ? ub->BASE_EL(left)->BASE_EL(height) : 0;
rheight = ub->BASE_EL(right) ? ub->BASE_EL(right)->BASE_EL(height) : 0;
assert( lheight != rheight );
if (rheight > lheight)
{
ub = ub->BASE_EL(right);
lheight = ub->BASE_EL(left) ?
ub->BASE_EL(left)->BASE_EL(height) : 0;
rheight = ub->BASE_EL(right) ?
ub->BASE_EL(right)->BASE_EL(height) : 0;
if (rheight > lheight)
ub = ub->BASE_EL(right);
else if (rheight < lheight)
ub = ub->BASE_EL(left);
else
ub = ub->BASE_EL(right);
}
else
{
ub = ub->BASE_EL(left);
lheight = ub->BASE_EL(left) ?
ub->BASE_EL(left)->BASE_EL(height) : 0;
rheight = ub->BASE_EL(right) ?
ub->BASE_EL(right)->BASE_EL(height) : 0;
if (rheight > lheight)
ub = ub->BASE_EL(right);
else if (rheight < lheight)
ub = ub->BASE_EL(left);
else
ub = ub->BASE_EL(left);
}
/* rebalance returns the grandparant of the subtree formed
* by the element that were rebalanced.
* We must continue upward from there rebalancing. */
fixfrom = rebalance(ub);
/* Find the next unbalaced element. */
ub = findFirstUnbalEl(fixfrom);
}
return element;
}
/**
* \brief Empty the tree and delete all the element.
*
* Resets the tree to its initial state.
*/
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::empty()
{
if ( root ) {
/* Recursively delete from the tree structure. */
deleteChildrenOf(root);
delete root;
root = 0;
treeSize = 0;
#ifdef WALKABLE
BASELIST::abandon();
#endif
}
}
/**
* \brief Forget all element in the tree.
*
* Does not delete element. Resets the the tree to it's initial state.
*/
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::abandon()
{
root = 0;
treeSize = 0;
#ifdef WALKABLE
BASELIST::abandon();
#endif
}
/* Recursively delete all the children of a element. */
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
deleteChildrenOf( Element *element )
{
/* Recurse left. */
if (element->BASE_EL(left)) {
deleteChildrenOf(element->BASE_EL(left));
/* Delete left element. */
delete element->BASE_EL(left);
element->BASE_EL(left) = 0;
}
/* Recurse right. */
if (element->BASE_EL(right)) {
deleteChildrenOf(element->BASE_EL(right));
/* Delete right element. */
delete element->BASE_EL(right);
element->BASE_EL(left) = 0;
}
}
/* rebalance from a element whose gradparent is unbalanced. Only
* call on a element that has a grandparent. */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
rebalance(Element *n)
{
long lheight, rheight;
Element *a, *b, *c;
Element *t1, *t2, *t3, *t4;
Element *p = n->BASE_EL(parent); /* parent (Non-NUL). L*/
Element *gp = p->BASE_EL(parent); /* Grand-parent (Non-NULL). */
Element *ggp = gp->BASE_EL(parent); /* Great grand-parent (may be NULL). */
if (gp->BASE_EL(right) == p)
{
/* gp
* \
* p
*/
if (p->BASE_EL(right) == n)
{
/* gp
* \
* p
* \
* n
*/
a = gp;
b = p;
c = n;
t1 = gp->BASE_EL(left);
t2 = p->BASE_EL(left);
t3 = n->BASE_EL(left);
t4 = n->BASE_EL(right);
}
else
{
/* gp
* \
* p
* /
* n
*/
a = gp;
b = n;
c = p;
t1 = gp->BASE_EL(left);
t2 = n->BASE_EL(left);
t3 = n->BASE_EL(right);
t4 = p->BASE_EL(right);
}
}
else
{
/* gp
* /
* p
*/
if (p->BASE_EL(right) == n)
{
/* gp
* /
* p
* \
* n
*/
a = p;
b = n;
c = gp;
t1 = p->BASE_EL(left);
t2 = n->BASE_EL(left);
t3 = n->BASE_EL(right);
t4 = gp->BASE_EL(right);
}
else
{
/* gp
* /
* p
* /
* n
*/
a = n;
b = p;
c = gp;
t1 = n->BASE_EL(left);
t2 = n->BASE_EL(right);
t3 = p->BASE_EL(right);
t4 = gp->BASE_EL(right);
}
}
/* Perform rotation.
*/
/* Tie b to the great grandparent. */
if ( ggp == 0 )
root = b;
else if ( ggp->BASE_EL(left) == gp )
ggp->BASE_EL(left) = b;
else
ggp->BASE_EL(right) = b;
b->BASE_EL(parent) = ggp;
/* Tie a as a leftchild of b. */
b->BASE_EL(left) = a;
a->BASE_EL(parent) = b;
/* Tie c as a rightchild of b. */
b->BASE_EL(right) = c;
c->BASE_EL(parent) = b;
/* Tie t1 as a leftchild of a. */
a->BASE_EL(left) = t1;
if ( t1 != 0 ) t1->BASE_EL(parent) = a;
/* Tie t2 as a rightchild of a. */
a->BASE_EL(right) = t2;
if ( t2 != 0 ) t2->BASE_EL(parent) = a;
/* Tie t3 as a leftchild of c. */
c->BASE_EL(left) = t3;
if ( t3 != 0 ) t3->BASE_EL(parent) = c;
/* Tie t4 as a rightchild of c. */
c->BASE_EL(right) = t4;
if ( t4 != 0 ) t4->BASE_EL(parent) = c;
/* The heights are all recalculated manualy and the great
* grand-parent is passed to recalcHeights() to ensure
* the heights are correct up the tree.
*
* Note that recalcHeights() cuts out when it comes across
* a height that hasn't changed.
*/
/* Fix height of a. */
lheight = a->BASE_EL(left) ? a->BASE_EL(left)->BASE_EL(height) : 0;
rheight = a->BASE_EL(right) ? a->BASE_EL(right)->BASE_EL(height) : 0;
a->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1;
/* Fix height of c. */
lheight = c->BASE_EL(left) ? c->BASE_EL(left)->BASE_EL(height) : 0;
rheight = c->BASE_EL(right) ? c->BASE_EL(right)->BASE_EL(height) : 0;
c->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1;
/* Fix height of b. */
lheight = a->BASE_EL(height);
rheight = c->BASE_EL(height);
b->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1;
/* Fix height of b's parents. */
recalcHeights(ggp);
return ggp;
}
/* Recalculates the heights of all the ancestors of element. */
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
recalcHeights(Element *element)
{
long lheight, rheight, new_height;
while ( element != 0 )
{
lheight = element->BASE_EL(left) ? element->BASE_EL(left)->BASE_EL(height) : 0;
rheight = element->BASE_EL(right) ? element->BASE_EL(right)->BASE_EL(height) : 0;
new_height = (lheight > rheight ? lheight : rheight) + 1;
/* If there is no chage in the height, then there will be no
* change in any of the ancestor's height. We can stop going up.
* If there was a change, continue upward. */
if (new_height == element->BASE_EL(height))
return;
else
element->BASE_EL(height) = new_height;
element = element->BASE_EL(parent);
}
}
/* Finds the first element whose grandparent is unbalanced. */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
findFirstUnbalGP(Element *element)
{
long lheight, rheight, balanceProp;
Element *gp;
if ( element == 0 || element->BASE_EL(parent) == 0 ||
element->BASE_EL(parent)->BASE_EL(parent) == 0 )
return 0;
/* Don't do anything if we we have no grandparent. */
gp = element->BASE_EL(parent)->BASE_EL(parent);
while ( gp != 0 )
{
lheight = gp->BASE_EL(left) ? gp->BASE_EL(left)->BASE_EL(height) : 0;
rheight = gp->BASE_EL(right) ? gp->BASE_EL(right)->BASE_EL(height) : 0;
balanceProp = lheight - rheight;
if ( balanceProp < -1 || balanceProp > 1 )
return element;
element = element->BASE_EL(parent);
gp = gp->BASE_EL(parent);
}
return 0;
}
/* Finds the first element that is unbalanced. */
template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
findFirstUnbalEl(Element *element)
{
if ( element == 0 )
return 0;
while ( element != 0 )
{
long lheight = element->BASE_EL(left) ?
element->BASE_EL(left)->BASE_EL(height) : 0;
long rheight = element->BASE_EL(right) ?
element->BASE_EL(right)->BASE_EL(height) : 0;
long balanceProp = lheight - rheight;
if ( balanceProp < -1 || balanceProp > 1 )
return element;
element = element->BASE_EL(parent);
}
return 0;
}
/* Replace a element in the tree with another element not in the tree. */
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
replaceEl(Element *element, Element *replacement)
{
Element *parent = element->BASE_EL(parent),
*left = element->BASE_EL(left),
*right = element->BASE_EL(right);
replacement->BASE_EL(left) = left;
if (left)
left->BASE_EL(parent) = replacement;
replacement->BASE_EL(right) = right;
if (right)
right->BASE_EL(parent) = replacement;
replacement->BASE_EL(parent) = parent;
if (parent)
{
if (parent->BASE_EL(left) == element)
parent->BASE_EL(left) = replacement;
else
parent->BASE_EL(right) = replacement;
}
else
root = replacement;
replacement->BASE_EL(height) = element->BASE_EL(height);
}
/* Removes a element from a tree and puts filler in it's place.
* Filler should be null or a child of element. */
template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
removeEl(Element *element, Element *filler)
{
Element *parent = element->BASE_EL(parent);
if (parent)
{
if (parent->BASE_EL(left) == element)
parent->BASE_EL(left) = filler;
else
parent->BASE_EL(right) = filler;
}
else
root = filler;
if (filler)
filler->BASE_EL(parent) = parent;
return;
}
#ifdef AAPL_NAMESPACE
}
#endif