//------------------------------------------------------------------------------
// emAvlTree.h
//
// Copyright (C) 2005-2008 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


//==============================================================================
//================= Low-level stuff for programming AVL trees ==================
//==============================================================================

// For an example of how to use these things, please see the implementation of
// the template class emAvlTreeExample, which can be found 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
