//------------------------------------------------------------------------------
// emAvlTree.h
//
// Copyright (C) 2005-2008,2010 Oliver Hamann.
//
// Homepage: http://eaglemode.sourceforge.net/
//
// This program is free software: you can redistribute it and/or modify it under
// the terms of the GNU General Public License version 3 as published by the
// Free Software Foundation.
//
// 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 version 3 for
// more details.
//
// You should have received a copy of the GNU General Public License version 3
// along with this program. If not, see <http://www.gnu.org/licenses/>.
//------------------------------------------------------------------------------
#ifndef emAvlTree_h
#define emAvlTree_h
#ifndef emStd1_h
#include <emCore/emStd1.h>
#endif
//==============================================================================
//============================== AVL-tree macros ===============================
//==============================================================================
// Here you can find data types and macro definitions for a highly optimized AVL
// tree implementation. For an example of how to use it, see the implementation
// of the template class emAvlTreeExample more below.
//----------------------------------- Types ------------------------------------
struct emAvlNode {
emAvlNode * Left;
emAvlNode * Right;
int Balance;
};
typedef emAvlNode * emAvlTree;
struct emAvlIterator {
const emAvlNode * nstack[64];
int depth;
};
//--------------------------------- Utilities ----------------------------------
int emAvlCheck(const emAvlTree tree);
// Check consistency of the tree and return its height. Exits this
// process and prints a message on failure.
#define EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,NODE_POINTER) \
((ELEMENT_CLASS*)(((char*)(NODE_POINTER)) \
-offsetof(ELEMENT_CLASS,NODE_MEMBER)))
//---------------------- Macros for the insert algorithm -----------------------
#define EM_AVL_INSERT_VARS(ELEMENT_CLASS) \
emAvlTree * tstack[64]; \
int depth; \
emAvlNode * node1, * node2, * node3; \
emAvlTree * tree, * tree2; \
ELEMENT_CLASS * element;
#define EM_AVL_INSERT_BEGIN_SEARCH(ELEMENT_CLASS,NODE_MEMBER,TREE) \
tree=&TREE; \
depth=0; \
node1=*tree; \
if (!node1) element=NULL; \
else for (;;) { \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node1);
#define EM_AVL_INSERT_GO_LEFT \
{ \
tstack[depth++]=tree; \
tree=&node1->Left; \
node1=*tree; \
if (node1) continue; \
element=NULL; \
}
#define EM_AVL_INSERT_GO_RIGHT \
{ \
tstack[depth++]=tree; \
tree=&node1->Right; \
node1=*tree; \
if (node1) continue; \
element=NULL; \
}
#define EM_AVL_INSERT_END_SEARCH \
break; \
}
#define EM_AVL_INSERT_NOW(NODE_MEMBER) \
node1=&element->NODE_MEMBER; \
node1->Left=NULL; \
node1->Right=NULL; \
node1->Balance=0; \
*tree=node1; \
if (depth>0) for (;;) { \
tree2=tree; \
tree=tstack[--depth]; \
node1=*tree; \
if (tree2==&node1->Left) { \
if (node1->Balance==0) { \
node1->Balance=-1; \
if (depth>0) continue; \
} \
else if (node1->Balance>0) { \
node1->Balance=0; \
} \
else { \
node2=node1->Left; \
if (node2->Balance<0) { \
*tree=node2; \
node1->Left=node2->Right; \
node2->Right=node1; \
node1->Balance=0; \
node2->Balance=0; \
} \
else { \
node3=node2->Right; \
*tree=node3; \
node1->Left=node3->Right; \
node1->Balance=-(node3->Balance>>1); \
node2->Balance=(-node3->Balance)>>1; \
node2->Right=node3->Left; \
node3->Left=node2; \
node3->Right=node1; \
node3->Balance=0; \
} \
} \
} \
else { \
if (node1->Balance==0) { \
node1->Balance=1; \
if (depth>0) continue; \
} \
else if (node1->Balance<0) { \
node1->Balance=0; \
} \
else { \
node2=node1->Right; \
if (node2->Balance>0) { \
*tree=node2; \
node1->Right=node2->Left; \
node2->Left=node1; \
node1->Balance=0; \
node2->Balance=0; \
} \
else { \
node3=node2->Left; \
*tree=node3; \
node1->Right=node3->Left; \
node1->Balance=(-node3->Balance)>>1; \
node2->Balance=-(node3->Balance>>1); \
node2->Left=node3->Right; \
node3->Right=node2; \
node3->Left=node1; \
node3->Balance=0; \
} \
} \
} \
break; \
}
//---------------------- Macros for the remove algorithm -----------------------
#define EM_AVL_REMOVE_VARS(ELEMENT_CLASS) \
emAvlTree * tstack[64]; \
int depth, depth2; \
emAvlNode * node1, * node2, * node3; \
emAvlTree * tree, * tree2; \
ELEMENT_CLASS * element;
#define EM_AVL_REMOVE_BEGIN(ELEMENT_CLASS,NODE_MEMBER,TREE) \
tree=&TREE; \
depth=0; \
node1=*tree; \
if (!node1) element=NULL; \
else for (;;) { \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node1);
#define EM_AVL_REMOVE_GO_LEFT \
{ \
tstack[depth++]=tree; \
tree=&node1->Left; \
node1=*tree; \
if (node1) continue; \
element=NULL; \
}
#define EM_AVL_REMOVE_GO_RIGHT \
{ \
tstack[depth++]=tree; \
tree=&node1->Right; \
node1=*tree; \
if (node1) continue; \
element=NULL; \
}
#define EM_AVL_REMOVE_NOW \
{ \
if (!node1->Right) { \
*tree=node1->Left; \
} \
else if (!node1->Left) { \
*tree=node1->Right; \
} \
else { \
depth2=depth; \
tstack[depth++]=tree; \
tree=&node1->Left; \
node2=*tree; \
if (node2->Right) do { \
tstack[depth++]=tree; \
tree=&node2->Right; \
node2=*tree; \
} while (node2->Right); \
*tree=node2->Left; \
node2->Left=node1->Left; \
node2->Right=node1->Right; \
node2->Balance=node1->Balance; \
*tstack[depth2]=node2; \
tstack[depth]=tree; \
tstack[depth2+1]=&node2->Left; \
tree=tstack[depth]; \
} \
if (depth>0) for (;;) { \
tree2=tree; \
tree=tstack[--depth]; \
node1=*tree; \
if (tree2==&node1->Left) { \
if (node1->Balance<0) { \
node1->Balance=0; \
if (depth>0) continue; \
} \
else if (node1->Balance==0) { \
node1->Balance=1; \
} \
else { \
node2=node1->Right; \
if (node2->Balance>=0) { \
*tree=node2; \
node1->Right=node2->Left; \
node2->Left=node1; \
if (node2->Balance!=0) { \
node1->Balance=0; \
node2->Balance=0; \
if (depth>0) continue; \
} \
else { \
node1->Balance=1; \
node2->Balance=-1; \
} \
} \
else { \
node3=node2->Left; \
*tree=node3; \
node1->Right=node3->Left; \
node1->Balance=(-node3->Balance)>>1; \
node2->Balance=-(node3->Balance>>1); \
node2->Left=node3->Right; \
node3->Left=node1; \
node3->Right=node2; \
node3->Balance=0; \
if (depth>0) continue; \
} \
} \
} \
else { \
if (node1->Balance>0) { \
node1->Balance=0; \
if (depth>0) continue; \
} \
else if (node1->Balance==0) { \
node1->Balance=-1; \
} \
else { \
node2=node1->Left; \
if (node2->Balance<=0) { \
*tree=node2; \
node1->Left=node2->Right; \
node2->Right=node1; \
if (node2->Balance!=0) { \
node1->Balance=0; \
node2->Balance=0; \
if (depth>0) continue; \
} \
else { \
node1->Balance=-1; \
node2->Balance=1; \
} \
} \
else { \
node3=node2->Right; \
*tree=node3; \
node1->Left=node3->Right; \
node1->Balance=-(node3->Balance>>1); \
node2->Balance=(-node3->Balance)>>1; \
node2->Right=node3->Left; \
node3->Right=node1; \
node3->Left=node2; \
node3->Balance=0; \
if (depth>0) continue; \
} \
} \
} \
break; \
} \
}
#define EM_AVL_REMOVE_END \
break; \
}
//---------------------- Macros for the search algorithm -----------------------
#define EM_AVL_SEARCH_VARS(ELEMENT_CLASS) \
const emAvlNode * node; \
ELEMENT_CLASS * element;
#define EM_AVL_SEARCH_BEGIN(ELEMENT_CLASS,NODE_MEMBER,TREE) \
node=TREE; \
if (!node) element=NULL; \
else for (;;) { \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node);
#define EM_AVL_SEARCH_GO_LEFT \
{ \
node=node->Left; \
if (node) continue; \
element=NULL; \
}
#define EM_AVL_SEARCH_GO_LEFT_OR_FOUND \
{ \
node=node->Left; \
if (node) continue; \
}
#define EM_AVL_SEARCH_GO_RIGHT \
{ \
node=node->Right; \
if (node) continue; \
element=NULL; \
}
#define EM_AVL_SEARCH_GO_RIGHT_OR_FOUND \
{ \
node=node->Right; \
if (node) continue; \
}
#define EM_AVL_SEARCH_END \
break; \
}
//----------------------- Macros for the loop algorithm ------------------------
#define EM_AVL_LOOP_VARS(ELEMENT_CLASS) \
const emAvlNode * nstack[64]; \
const emAvlNode * node; \
int depth; \
ELEMENT_CLASS * element;
// - - - loop from first to last - - -
#define EM_AVL_LOOP_START(ELEMENT_CLASS,NODE_MEMBER,TREE) \
node=TREE; \
if (!node) element=NULL; \
else { \
depth=0; \
if (node->Left) do { \
nstack[depth++]=node; \
node=node->Left; \
} while (node->Left); \
for (;;) { \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node);
#define EM_AVL_LOOP_END \
node=node->Right; \
if (node) { \
if (node->Left) do { \
nstack[depth++]=node; \
node=node->Left; \
} while (node->Left); \
continue; \
} \
if (depth>0) { \
depth--; \
node=nstack[depth]; \
continue; \
} \
element=NULL; \
break; \
} \
}
// - - - loop from last to first - - -
#define EM_AVL_REV_LOOP_START(ELEMENT_CLASS,NODE_MEMBER,TREE) \
node=TREE; \
if (!node) element=NULL; \
else { \
depth=0; \
if (node->Right) do { \
nstack[depth++]=node; \
node=node->Right; \
} while (node->Right); \
for (;;) { \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node);
#define EM_AVL_REV_LOOP_END \
node=node->Left; \
if (node) { \
if (node->Right) do { \
nstack[depth++]=node; \
node=node->Right; \
} while (node->Right); \
continue; \
} \
if (depth>0) { \
depth--; \
node=nstack[depth]; \
continue; \
} \
element=NULL; \
break; \
} \
}
//---------------------- Macros for the iterate algorithm ----------------------
#define EM_AVL_ITER_VARS(ELEMENT_CLASS) \
const emAvlNode * node; \
ELEMENT_CLASS * element;
#define EM_AVL_ITER_FIRST(ELEMENT_CLASS,NODE_MEMBER,TREE,ITERATOR) \
{ \
node=TREE; \
ITERATOR.depth=0; \
if (!node) { \
ITERATOR.nstack[0]=NULL; \
element=NULL; \
} \
else { \
if (node->Left) do { \
ITERATOR.nstack[ITERATOR.depth++]=node; \
node=node->Left; \
} while (node->Left); \
ITERATOR.nstack[ITERATOR.depth]=node; \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node); \
} \
}
#define EM_AVL_ITER_LAST(ELEMENT_CLASS,NODE_MEMBER,TREE,ITERATOR) \
{ \
node=TREE; \
ITERATOR.depth=0; \
if (!node) { \
ITERATOR.nstack[0]=NULL; \
element=NULL; \
} \
else { \
if (node->Right) do { \
ITERATOR.nstack[ITERATOR.depth++]=node; \
node=node->Right; \
} while (node->Right); \
ITERATOR.nstack[ITERATOR.depth]=node; \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node); \
} \
}
#define EM_AVL_ITER_NEXT(ELEMENT_CLASS,NODE_MEMBER,ITERATOR) \
{ \
node=ITERATOR.nstack[ITERATOR.depth]; \
if (node->Right) { \
ITERATOR.depth++; \
node=node->Right; \
if (node->Left) do { \
ITERATOR.nstack[ITERATOR.depth++]=node; \
node=node->Left; \
} while (node->Left); \
ITERATOR.nstack[ITERATOR.depth]=node; \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node); \
} \
else if (ITERATOR.depth<=0) { \
ITERATOR.nstack[ITERATOR.depth]=NULL; \
element=NULL; \
} \
else { \
for (;;) { \
ITERATOR.depth--; \
if (node==ITERATOR.nstack[ITERATOR.depth]->Right) { \
node=ITERATOR.nstack[ITERATOR.depth]; \
if (ITERATOR.depth>0) continue; \
element=NULL; \
break; \
} \
node=ITERATOR.nstack[ITERATOR.depth]; \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node); \
break; \
} \
} \
}
#define EM_AVL_ITER_PREV(ELEMENT_CLASS,NODE_MEMBER,ITERATOR) \
{ \
node=ITERATOR.nstack[ITERATOR.depth]; \
if (node->Left) { \
ITERATOR.depth++; \
node=node->Left; \
if (node->Right) do { \
ITERATOR.nstack[ITERATOR.depth++]=node; \
node=node->Right; \
} while (node->Right); \
ITERATOR.nstack[ITERATOR.depth]=node; \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node); \
} \
else if (ITERATOR.depth<=0) { \
ITERATOR.nstack[ITERATOR.depth]=NULL; \
element=NULL; \
} \
else { \
for (;;) { \
ITERATOR.depth--; \
if (node==ITERATOR.nstack[ITERATOR.depth]->Left) { \
node=ITERATOR.nstack[ITERATOR.depth]; \
if (ITERATOR.depth>0) continue; \
element=NULL; \
break; \
} \
node=ITERATOR.nstack[ITERATOR.depth]; \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node); \
break; \
} \
} \
}
#define EM_AVL_ITER_START_ANY_BEGIN(ELEMENT_CLASS,NODE_MEMBER,TREE,ITERATOR) \
node=TREE; \
ITERATOR.depth=0; \
if (!node) { \
ITERATOR.nstack[0]=NULL; \
element=NULL; \
} \
else for (;;) { \
ITERATOR.nstack[ITERATOR.depth]=node; \
element=EM_AVL_ELEMENT(ELEMENT_CLASS,NODE_MEMBER,node);
#define EM_AVL_ITER_START_ANY_GO_LEFT(ITERATOR) \
{ \
ITERATOR.nstack[ITERATOR.depth++]=node; \
node=node->Left; \
if (node) continue; \
ITERATOR.nstack[ITERATOR.depth]=NULL; \
element=NULL; \
}
#define EM_AVL_ITER_START_ANY_GO_LEFT_OR_FOUND(ITERATOR) \
{ \
if (node->Left) { \
ITERATOR.nstack[ITERATOR.depth++]=node; \
node=node->Left; \
continue; \
} \
}
#define EM_AVL_ITER_START_ANY_GO_RIGHT(ITERATOR) \
{ \
ITERATOR.nstack[ITERATOR.depth++]=node; \
node=node->Right; \
if (node) continue; \
ITERATOR.nstack[ITERATOR.depth]=NULL; \
element=NULL; \
}
#define EM_AVL_ITER_START_ANY_GO_RIGHT_OR_FOUND(ITERATOR) \
{ \
if (node->Right) { \
ITERATOR.nstack[ITERATOR.depth++]=node; \
node=node->Right; \
continue; \
} \
}
#define EM_AVL_ITER_START_ANY_END \
break; \
}
//------------ Macros for unions of variable sets of the algorithms ------------
// this is dirty, isn't it?
#define EM_AVL_INS_LOOP_VARS(ELEMENT_CLASS) \
EM_AVL_INSERT_VARS(ELEMENT_CLASS) \
const emAvlNode * nstack[64]; \
const emAvlNode * node;
#define EM_AVL_INS_ITER_VARS(ELEMENT_CLASS) \
EM_AVL_INSERT_VARS(ELEMENT_CLASS) \
const emAvlNode * node;
//...to be continued...
//==============================================================================
//============================== emAvlTreeExample ==============================
//==============================================================================
template <class OBJ> class emAvlTreeExample {
public:
class Iterator;
private:
friend class Iterator;
struct Element {
OBJ Object;
emAvlNode Node;
};
emAvlTree Tree;
public:
// Template class for a sorted set of objects managed in an AVL tree.
// The objects are sorted by the normal compare operators.
//
// This tree class is meant as a programming example and should not be
// used - it may be removed one day.
//
//??? There are plans to define a better tree class which has the
//??? following features:
//???
//??? * User-defined compare function.
//??? * Nice interface for creating maps and sets.
//??? * Copy-on-write mechanism.
//??? * Both: stable iterators and fast unstable iterators.
//???
//??? The last feature would require to have parent pointers in the tree
//??? nodes. But the EM_AVL macros do not support such parent pointers,
//??? due to best performance in their original use (e.g. in emContext).
//??? Therefore, an additional set of tree macros has to be developed
//??? first - with parent pointers. Maybe it should be made with
//??? Red/Black trees instead of AVL. Red/Black trees are faster in
//??? removing elements for the cost of a possible worse balance.
emAvlTreeExample();
~emAvlTreeExample();
bool Insert(const OBJ & object);
// Insert a copy of the given object. If there is already an
// object which equals the given object, nothing is changed and
// false is returned.
bool Remove(const OBJ & object);
// Remove the object which equals the given object. If there is
// no such object, nothing is changed and false is returned.
void Empty();
// Remove all objects.
const OBJ * Search(const OBJ & object) const;
// Search for the object which equals the given object, and
// return a pointer to the found object. If there is no such
// object, NULL is returned.
int Count() const;
// Count the number of objects.
int Check() const;
// Check consistency of the tree and return its height. Exits
// this process and prints a message on failure.
class Iterator {
public:
// IMPORTANT:
// - After construction, one of the Start methods has to be
// called before calling Next, Prev or Get.
// - If the tree changes while iterating (inserting/removing
// objects), the iterators have to be restarted!
// - When Get() returns NULL, the end has been reached. Next
// and Prev must not be called then.
const OBJ * StartFirst(const emAvlTreeExample & treeSet);
const OBJ * StartLast(const emAvlTreeExample & treeSet);
// Start with the first or last object of the given
// tree. Return that object or NULL.
const OBJ * StartEqual(
const emAvlTreeExample & treeSet, const OBJ & object
);
const OBJ * StartGreater(
const emAvlTreeExample & treeSet, const OBJ & object
);
const OBJ * StartGreaterOrEqual(
const emAvlTreeExample & treeSet, const OBJ & object
);
const OBJ * StartLess(
const emAvlTreeExample & treeSet, const OBJ & object
);
const OBJ * StartLessOrEqual(
const emAvlTreeExample & treeSet, const OBJ & object
);
// Start with an object which is equal, greater, not
// less, less, or not greater than the given object.
// Return that object, or NULL if not found.
const OBJ * Get() const;
// Get the current object, or NULL...
const OBJ * Next();
const OBJ * Prev();
// Go to the next or previous object. Return that object
// or NULL.
private:
typedef Element TreeElement;
const OBJ * Current;
emAvlIterator Iter;
};
};
template <class OBJ> inline emAvlTreeExample<OBJ>::emAvlTreeExample()
{
Tree=NULL;
}
template <class OBJ> inline emAvlTreeExample<OBJ>::~emAvlTreeExample()
{
Empty();
}
template <class OBJ> bool emAvlTreeExample<OBJ>::Insert(const OBJ & object)
{
EM_AVL_INSERT_VARS(Element)
EM_AVL_INSERT_BEGIN_SEARCH(Element,Node,Tree)
if (object<element->Object) EM_AVL_INSERT_GO_LEFT
else if (object==element->Object) return false;
else EM_AVL_INSERT_GO_RIGHT
EM_AVL_INSERT_END_SEARCH
element=new Element;
element->Object=object;
EM_AVL_INSERT_NOW(Node)
return true;
}
template <class OBJ> bool emAvlTreeExample<OBJ>::Remove(const OBJ & object)
{
EM_AVL_REMOVE_VARS(Element)
EM_AVL_REMOVE_BEGIN(Element,Node,Tree)
if (object<element->Object) {
EM_AVL_REMOVE_GO_LEFT
}
else if (object==element->Object) {
EM_AVL_REMOVE_NOW
delete element;
return true;
}
else {
EM_AVL_REMOVE_GO_RIGHT
}
EM_AVL_REMOVE_END
return false;
}
template <class OBJ> void emAvlTreeExample<OBJ>::Empty()
{
while (Tree) {
Remove(EM_AVL_ELEMENT(Element,Node,Tree)->Object);
}
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Search(
const OBJ & object
) const
{
EM_AVL_SEARCH_VARS(Element)
EM_AVL_SEARCH_BEGIN(Element,Node,Tree)
if (object<element->Object) EM_AVL_SEARCH_GO_LEFT
else if (object==element->Object) return &element->Object;
else EM_AVL_SEARCH_GO_RIGHT
EM_AVL_SEARCH_END
return NULL;
}
template <class OBJ> int emAvlTreeExample<OBJ>::Count() const
{
EM_AVL_LOOP_VARS(Element)
int count;
count=0;
EM_AVL_LOOP_START(Element,Node,Tree)
count++;
EM_AVL_LOOP_END
return count;
}
template <class OBJ> inline int emAvlTreeExample<OBJ>::Check() const
{
return emAvlCheck(Tree);
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Iterator::StartFirst(
const emAvlTreeExample<OBJ> & treeSet
)
{
EM_AVL_ITER_VARS(TreeElement)
EM_AVL_ITER_FIRST(TreeElement,Node,treeSet.Tree,Iter)
Current= element ? &element->Object : NULL;
return Current;
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Iterator::StartLast(
const emAvlTreeExample<OBJ> & treeSet
)
{
EM_AVL_ITER_VARS(TreeElement)
EM_AVL_ITER_LAST(TreeElement,Node,treeSet.Tree,Iter)
Current= element ? &element->Object : NULL;
return Current;
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Iterator::StartEqual(
const emAvlTreeExample<OBJ> & treeSet, const OBJ & object
)
{
EM_AVL_ITER_VARS(TreeElement)
EM_AVL_ITER_START_ANY_BEGIN(TreeElement,Node,treeSet.Tree,Iter)
if (object<element->Object) EM_AVL_ITER_START_ANY_GO_LEFT(Iter)
else if (object>element->Object) EM_AVL_ITER_START_ANY_GO_RIGHT(Iter)
EM_AVL_ITER_START_ANY_END
Current= element ? &element->Object : NULL;
return Current;
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Iterator::StartGreater(
const emAvlTreeExample<OBJ> & treeSet, const OBJ & object
)
{
EM_AVL_ITER_VARS(TreeElement)
EM_AVL_ITER_START_ANY_BEGIN(TreeElement,Node,treeSet.Tree,Iter)
if (object<element->Object) EM_AVL_ITER_START_ANY_GO_LEFT_OR_FOUND(Iter)
else if (object>element->Object) EM_AVL_ITER_START_ANY_GO_RIGHT_OR_FOUND(Iter)
EM_AVL_ITER_START_ANY_END
if (element && object>=element->Object) {
EM_AVL_ITER_NEXT(TreeElement,Node,Iter)
}
Current= element ? &element->Object : NULL;
return Current;
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Iterator::StartGreaterOrEqual(
const emAvlTreeExample<OBJ> & treeSet, const OBJ & object
)
{
EM_AVL_ITER_VARS(TreeElement)
EM_AVL_ITER_START_ANY_BEGIN(TreeElement,Node,treeSet.Tree,Iter)
if (object<element->Object) EM_AVL_ITER_START_ANY_GO_LEFT_OR_FOUND(Iter)
else if (object>element->Object) EM_AVL_ITER_START_ANY_GO_RIGHT_OR_FOUND(Iter)
EM_AVL_ITER_START_ANY_END
if (element && object>element->Object) {
EM_AVL_ITER_NEXT(TreeElement,Node,Iter)
}
Current= element ? &element->Object : NULL;
return Current;
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Iterator::StartLess(
const emAvlTreeExample<OBJ> & treeSet, const OBJ & object
)
{
EM_AVL_ITER_VARS(TreeElement)
EM_AVL_ITER_START_ANY_BEGIN(TreeElement,Node,treeSet.Tree,Iter)
if (object<element->Object) EM_AVL_ITER_START_ANY_GO_LEFT_OR_FOUND(Iter)
else if (object>element->Object) EM_AVL_ITER_START_ANY_GO_RIGHT_OR_FOUND(Iter)
EM_AVL_ITER_START_ANY_END
if (element && object<=element->Object) {
EM_AVL_ITER_PREV(TreeElement,Node,Iter)
}
Current= element ? &element->Object : NULL;
return Current;
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Iterator::StartLessOrEqual(
const emAvlTreeExample<OBJ> & treeSet, const OBJ & object
)
{
EM_AVL_ITER_VARS(TreeElement)
EM_AVL_ITER_START_ANY_BEGIN(TreeElement,Node,treeSet.Tree,Iter)
if (object<element->Object) EM_AVL_ITER_START_ANY_GO_LEFT_OR_FOUND(Iter)
else if (object>element->Object) EM_AVL_ITER_START_ANY_GO_RIGHT_OR_FOUND(Iter)
EM_AVL_ITER_START_ANY_END
if (element && object<element->Object) {
EM_AVL_ITER_PREV(TreeElement,Node,Iter)
}
Current= element ? &element->Object : NULL;
return Current;
}
template <class OBJ> inline const OBJ * emAvlTreeExample<OBJ>::Iterator::Get() const
{
return Current;
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Iterator::Next()
{
EM_AVL_ITER_VARS(TreeElement)
EM_AVL_ITER_NEXT(TreeElement,Node,Iter)
Current= element ? &element->Object : NULL;
return Current;
}
template <class OBJ> const OBJ * emAvlTreeExample<OBJ>::Iterator::Prev()
{
EM_AVL_ITER_VARS(TreeElement)
EM_AVL_ITER_PREV(TreeElement,Node,Iter)
Current= element ? &element->Object : NULL;
return Current;
}
#endif