// SortTree
// Copyright, 2003, Jeff Schiller
//
//////////////////////////////////////////////////////////////////////

#if !defined(__LD_TSORTTREE_H)
#define __LD_TSORTTREE_H

#include <assert.h>
#include <list>
#include <vector>
#include <deque>

//#include "stdafx.h"
//#include "mmsystem.h"
#include "Memory.h"
using namespace Memory;

namespace LD {

	namespace SortTree {

	// -------------------------------------------------------------------
	// Forward Declaration of Mapper Policies
	// -------------------------------------------------------------------
	template<typename T> class TrivialKeyMapper;

	// -------------------------------------------------------------------
	// Forward Declaration of Allocator Policies
	// -------------------------------------------------------------------
	template<typename T> class StandardNodeAllocator;

	// -------------------------------------------------------------------
	// Forward Declaration of Canned Balancer Policies
	// -------------------------------------------------------------------
	template<typename T> class NeverTreeBalancer;
	template<typename T> class AlwaysTreeBalancer;

	// -------------------------------------------------------------------
	// Forward Declaration of Node Class
	// -------------------------------------------------------------------
	template<typename T> class TTreeNode;

	// -------------------------------------------------------------------
	// Forward Declaration of Tree Class
	// -------------------------------------------------------------------
	template<	typename T
				, template<class> class MappingPolicy
				, template<class> class AllocatorPolicy
				, template<class> class BalancerPolicy >
	class TSortTree;
	// -------------------------------------------------------------------

	// -------------------------------------------------------------------
	// Trivial key-lookup mapper class
	// -------------------------------------------------------------------
	template< typename T > class TrivialKeyMapper {
	public:
		typedef T KeyType;
		typedef T NodeType;
		const KeyType& getKey(const NodeType& t)
		{ return t; }
	};
	// -------------------------------------------------------------------

	// -------------------------------------------------------------------
	// Allocates nodes of type TBinaryTreeNode<T, M>
	// -------------------------------------------------------------------
	template<typename T>
	class StandardNodeAllocator {
	public:
		TTreeNode<T>* newNode(const T& val) 
		{
			return new TTreeNode<T>(val);
		}
		void deleteNode(TTreeNode<T>* pn) 
		{
			assert(0 != pn && "Cannot uncreate a NULL Tree Node in StandardNodeAllocator::deleteNode()");

			pn->m_pParent = 0;
			pn->m_pLeft = 0;
			pn->m_pRight = 0;

			delete pn;
		}
	}; // class StandardNodeAllocator
	// -------------------------------------------------------------------

	// -------------------------------------------------------------------
	// Allocates nodes of type TTreeNode<T> in a private heap to avoid heap 
	// fragmentation.  See TPrivateHeap<T,N> for more information.
	// -------------------------------------------------------------------
	template<
			// type of items to be stored in the tree
			typename T, 
			// number of node pointers to store in each "page" of memory
			unsigned int N = 100
			>
	class PrivateHeapNodeAllocator {
	protected:
		typedef TTreeNode<T>	NodeType;
		TPrivateHeap<NodeType, N>	m_heap;

	public:
		PrivateHeapNodeAllocator()
		{
		}

		~PrivateHeapNodeAllocator()
		{
		}

		NodeType* newNode(const T& val)
		{
		//	LogFile << "Going to Alloc()" << endl;
			// get a pointer to the allocated memory
			void* pNext = (void*)m_heap.Alloc();
			assert(pNext && "Could not allocate memory in PrivateHeapNodeAllocator::newNode()");

			// now run the constructor on this pointer using "placement" new
			NodeType* ptrNode = new (pNext) NodeType;

		//	LogFile << "Alloc'd()" << endl;
			ptrNode->m_Value = val;
			ptrNode->m_pParent = 0;
			ptrNode->m_pLeft = 0;
			ptrNode->m_pRight = 0;

			return ptrNode;
		}
		// -------------------------------------------------------------------

		void deleteNode(NodeType* pn)
		{
			assert(pn && "Error, NULL node sent to PrivateHeapNodeAllocator::deleteNode()");

			// need to explicitly call the destructor on the node
			pn->~NodeType();

			// now "free" the memory in the private heap
			m_heap.Free(pn);
		}

	};
	// -------------------------------------------------------------------

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	template<typename T>
	class NeverTreeBalancer {
	public:
		bool needsBalancing(TTreeNode<T>* pRoot) 
		{ return false; }
	};
	// -------------------------------------------------------------------

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	template<typename T>
	class AlwaysTreeBalancer {
	public:
		bool needsBalancing(TTreeNode<T>* pRoot) 
		{ return true; }
	};
	// -------------------------------------------------------------------

	// -------------------------------------------------------------------
	// TTreeNode class
	// -------------------------------------------------------------------
	template< typename T >
	class TTreeNode {
	private:
		void copy(const TTreeNode<T>& o)
		{
			if(&o != this) {
				m_Value = o.m_Value;
				m_pParent = o.m_pParent;
				m_pLeft = o.m_pLeft;
				m_pRight = o.m_pRight;
			}
		}
	public:
		T m_Value;
		TTreeNode<T>* m_pParent;
		TTreeNode<T>* m_pLeft;
		TTreeNode<T>* m_pRight;
	
		TTreeNode<T>() :
			m_Value(),
			m_pParent(0),
			m_pLeft(0),
			m_pRight(0)
		{
		}

		TTreeNode<T>(const T& t) :
			m_Value(t),
			m_pParent(0),
			m_pLeft(0),
			m_pRight(0)
		{
		}

		TTreeNode<T>(const TTreeNode<T>& o)
		{
			copy(o);
		}

		~TTreeNode<T>()
		{
			// we could set all the pointer values to 0, but is there a point?
			// TSortTree deleted this node's trees first, I think this should
			// be the responsibility of the tree, since removing a node might not
			// mean that you want to delete the children (you might only want to delete
			// this node)
		}

		TTreeNode<T>& operator=(const TTreeNode<T>& o)
		{
			copy(o);
			return *this;
		}

	}; // end of TTreeNode template declaration
	// -------------------------------------------------------------------

	template<	typename T
				// policy class to map an object of type T to an object of another type
				, template<class> class MappingPolicy = TrivialKeyMapper
				// policy class to handle the creation and deletion of nodes in the tree
				, template<class> class AllocatorPolicy = StandardNodeAllocator
				// policy class to handle when to balance the tree
				, template<class> class BalancerPolicy = NeverTreeBalancer >
	class TSortTree
	{
		typedef MappingPolicy<T>		M;
		typedef AllocatorPolicy<T>		A;
		typedef BalancerPolicy<T>		B;
		typedef typename M::KeyType		KeyType;
		typedef TTreeNode<T>			NodeType;

		// The policy objects are statically shared across all trees of this type.
		// This is done so that the size of the tree can remain as small as possible
		static M key_mapper;
		static A node_allocator;
		static B tree_balancer;

	protected:
		NodeType* m_pRoot;

		// ---------------------------------------------------------------
		// used by the constructor and when the balanceTree method is called
		// ---------------------------------------------------------------
		void createTreeFromList(std::list<T>& LItems)
		{
		//	LogFile << "Arrived in createTreeFromList" << endl;

			// copy to a temporary array of pointers to T
			T* tmpArr = new T[LItems.size()]; // tmpArr is created on heap
			int index = 0;
			for(std::list<T>::iterator lit = LItems.begin(); lit != LItems.end(); ++lit) {
				tmpArr[index] = *(lit);
				++index;
			}

		//	LogFile << "Created temp array holding " << index << " items" << endl;

			// use the temp array to create the nodes
			m_pRoot = split( &(tmpArr[0]), &(tmpArr[index-1]), 0);

			delete[] tmpArr; // tmpArr is deleted from heap, all temp T* objects gone
		}
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// used by createTreeFromList
		//
		// returns a pointer to a binary tree node for a type T
		// this function recursively creates nodes on the heap...
		// ---------------------------------------------------------------
		NodeType* split( T* first, T* last, NodeType* pParent )
		{
			int N = (int)(last - first + 1);
		//		LogFile << "length = " << N << endl;
		//		for(int loop = 0; loop < N; ++loop) {
		//			LogFile << "sort, ptr #" << loop << " = " << *(*(first + loop)) << endl;
		//		}

			T root = *(first + (N/2));
		//		LogFile << "split, root = " << root << endl;

			// create a tree node object on the heap here
			NodeType* node = node_allocator.newNode(root);
			node->m_pParent = pParent;
		//	LogFile << "Created Node " << endl;
		//	node->log();

		//		LogFile << "split, root node = " << node->m_Value << endl;

			if(N/2 > 0) {
				node->m_pLeft = split(first, first+(N/2)-1, node);
			}
			if(N/2 < N-1) {
				node->m_pRight = split(first+(N/2)+1, last, node);
			}
			return node;
		}
		// ---------------------------------------------------------------


	public:
		TSortTree() :
			m_pRoot(0)
		{
		}

		~TSortTree()
		{
		}
		
		// ---------------------------------------------------------------
		// Return the root node of the tree (could be NULL in an empty 
		// tree case)
		// ---------------------------------------------------------------
		const NodeType* getRootNode() const
		{ return m_pRoot; }
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// Returns true if the value mapped to key is in the tree
		// ---------------------------------------------------------------
		bool findItem(const KeyType& key)
		{
			bool bSuccess = false;
			T retVal;
			NodeType* pNode = m_pRoot;
			
		//	LogFile << "SORT: Search key is " << key << endl;

			while( (0 != pNode) && !bSuccess) {

				retVal = pNode->m_Value;
		//		LogFile << "SORT: At Node " << pNode->m_Value << ", pointer=" << pNode << endl;
		//		LogFile << "SORT: Node's key is " << getkey(pNode->m_Value) << endl;

				if( key_mapper.getKey(retVal) == key ) {
					// we found it, time to exit the while loop
					bSuccess = true;
				}
				else if( key_mapper.getKey(retVal) < key) {
		//			LogFile << "SORT: search goes to the right" << endl;
					pNode = pNode->m_pRight; // careful the comparison was reversed here...
				}
				else {
		//			LogFile << "SORT: search goes to the left" << endl;
					pNode = pNode->m_pLeft;
				}
			} // while(pNode != NULL....

			return bSuccess;
		}
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// Returns a reference to a variable of type T that "is equal to"
		// the given value key (of type KeyType as defined by the MappingPolicy)
		// ---------------------------------------------------------------
		bool findValue(const KeyType& key, T& out)
		{
			bool bSuccess = false;
			T retVal; // is this necessary?  can't I use out?
			NodeType* pNode = m_pRoot;
			
		//	LogFile << "SORT: Search key is " << key << endl;

			while( (0 != pNode) && !bSuccess) {

				retVal = pNode->m_Value;
		//		LogFile << "SORT: At Node " << pNode->m_Value << ", pointer=" << pNode << endl;
		//		LogFile << "SORT: Node's key is " << getkey(pNode->m_Value) << endl;

				if( key_mapper.getKey(retVal) == key ) {
					// we found it, time to exit the while loop
					bSuccess = true;
				}
				else if( key_mapper.getKey(retVal) < key) {
		//			LogFile << "SORT: search goes to the right" << endl;
					pNode = pNode->m_pRight; // careful the comparison was reversed here...
				}
				else {
		//			LogFile << "SORT: search goes to the left" << endl;
					pNode = pNode->m_pLeft;
				}
			} // while(pNode != NULL....

			if(bSuccess) {
				out = retVal;
			}

			return bSuccess;
		}
		// ---------------------------------------------------------------

		// -------------------------------------------------------------------
		// This clears the tree and de-allocates all the nodes in the subtree
		// where pNode is the root.  If pNode is not specified or is NULL 
		// then the entire tree is cleared.
		// -------------------------------------------------------------------
		void clear(NodeType* pNode = NULL)
		{
			// if this function was called with a NULL pointer, check
			// the parent node
			if(0 == pNode) {
				// if the root is not NULL, re-call this function 
				// with the root as the argument
				if(0 != m_pRoot) {
					clear(m_pRoot);
				}
				// else, we are done, the tree is empty
			}
			else { // else, this function was called with a non-NULL pointer
				if(0 != pNode->m_pLeft) {
					clear(pNode->m_pLeft);
				}
				if(0 != pNode->m_pRight) {
					clear(pNode->m_pRight);
				}
				node_allocator.deleteNode(pNode);

				// if this was the root node, need to set it to 0
				// (otherwise, when the tree is destroyed, it will clear
				// the tree again causing heap corruption!)
				if(pNode == m_pRoot) {
					m_pRoot = 0;
				}
	//		LogFile << "Deleted a node in TSortTree<T,M,A,B>::clear()" << endl;

				pNode = 0;
			}
		}

		// ---------------------------------------------------------------
		// This adds the value t to the tree at the proper position
		//
		// A return value of true indicates that the add was successful
		// A return value of false indicates that the add was unsuccessful
		// ---------------------------------------------------------------
		bool addItem(const T& t)
		{
			bool bSuccess = false;

			// special case when it's an empty tree
			if(0 == m_pRoot) {
		//		LogFile << "Creating the root" << endl;
				m_pRoot = node_allocator.newNode(t);
		//		LogFile << "Created the root" << endl;
				return true;
			}

			// start at the root
			NodeType* pNode = m_pRoot;

			// ---------------------------------------------------------------
			// loop forever until we add the node (using break to exit the loop)
			// ---------------------------------------------------------------
			while( true ) {
				// -----------------------------------------------------------
				// if the new value is less than or equal to the node, we
				// go to the left branch
				// -----------------------------------------------------------
				if( key_mapper.getKey(t) < key_mapper.getKey(pNode->m_Value) ||
					key_mapper.getKey(t) == key_mapper.getKey(pNode->m_Value) ) {
					// -------------------------------------------------------
					// if the left child exists, go to the left child
					// and loop again
					// -------------------------------------------------------
					if(0 != pNode->m_pLeft) {
						pNode = pNode->m_pLeft;
					}
					// -------------------------------------------------------
					// else, this new value should be the left child
					// -------------------------------------------------------
					else {
						// create the node
						NodeType* pNewNode = node_allocator.newNode(t);
						// assign the child and parent to each other
						pNewNode->m_pParent = pNode;
						pNode->m_pLeft = pNewNode;
						bSuccess = true;
						break;
					}
					// -------------------------------------------------------
				} // if(t < pNode->m_Value)
				// -----------------------------------------------------------
				else { // else, we go to the right branch
					if(0 != pNode->m_pRight) {
						pNode = pNode->m_pRight;
					}
					else {
						NodeType* pNewNode = node_allocator.newNode(t);
						// assign the child and parent to each other
						pNewNode->m_pParent = pNode;
						pNode->m_pRight = pNewNode;
						bSuccess = true;
						break;
					}
				} // else
				// -----------------------------------------------------------
			} // while( true )
			// ---------------------------------------------------------------

		//	LogFile << "Logging at the end of an addItem(T)" << endl;
		//	log();
			if( tree_balancer.needsBalancing(this->m_pRoot) ) {
				balance();
			}

			return bSuccess;
		}
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// ---------------------------------------------------------------
		bool removeItem(const KeyType& key)
		{
			bool bSuccess = true;

			// special case when it's an empty tree
			if(0 == m_pRoot) {
				return false;
			}

			// ---------------------------------------------------------------
			// start at the root
			// ---------------------------------------------------------------
			NodeType* pNode = m_pRoot;
			// ---------------------------------------------------------------

			// ---------------------------------------------------------------
			// loop until we find a node to match...
			// ---------------------------------------------------------------
			while( 0 != pNode ) {

				if( key_mapper.getKey(pNode->m_Value) == key ) {
					bSuccess = removeNode(pNode);

					pNode = NULL;
				} // if( key_mapper(pNode->m_Value) == key )
				// -----------------------------------------------------------
				// if this node does not match, then if the value is
				// less than the current node, go to the right
				// -----------------------------------------------------------
				else if( key_mapper.getKey(pNode->m_Value) < key) {
					pNode = pNode->m_pRight; // careful the comparison was reversed here...
				}
				// -----------------------------------------------------------
				// else, go to the left
				// -----------------------------------------------------------
				else { // node was greater
					pNode = pNode->m_pLeft;
				}	
				// -----------------------------------------------------------
			} // while( NULL != pNode )
			// ---------------------------------------------------------------

			if( tree_balancer.needsBalancing(this->m_pRoot) ) {
				balance();
			}

			return bSuccess;
		}
		// ---------------------------------------------------------------


		// -------------------------------------------------------------------
		// this is called to re-add a node into the tree...
		// -------------------------------------------------------------------
		bool addNode(NodeType* pNewNode)
		{
			bool bSuccess = false;

			if(0 == pNewNode) {
				return false;
			}

			// ---------------------------------------------------------------
			// special case when it's an empty tree
			// ---------------------------------------------------------------
			if(0 == m_pRoot) {
				m_pRoot = pNewNode;
				return true;
			}
			// ---------------------------------------------------------------

			// ---------------------------------------------------------------
			// start at the root
			// ---------------------------------------------------------------
			NodeType* pNode = m_pRoot;
			// ---------------------------------------------------------------

			// ---------------------------------------------------------------
			// loop forever until we add the node (using break to exit the loop)
			// ---------------------------------------------------------------
			while( true ) {
				// -----------------------------------------------------------
				// if the new value is less than or equal to the node
				// -----------------------------------------------------------
				if( key_mapper.getKey(pNewNode->m_Value) < key_mapper.getKey(pNode->m_Value) ||
					key_mapper.getKey(pNewNode->m_Value) == key_mapper.getKey(pNode->m_Value) ) {
					// -------------------------------------------------------
					// if the left child exists, go to the left child
					// and loop again
					// -------------------------------------------------------
					if(0 != pNode->m_pLeft) {
						pNode = pNode->m_pLeft;
					}
					// -------------------------------------------------------
					// else, this new value should be the left child
					// -------------------------------------------------------
					else {
						// assign the child and parent to each other
						pNode->m_pLeft = pNewNode;
						pNewNode->m_pParent = pNode;
						bSuccess = true;
						break;
					}
					// -------------------------------------------------------
				} // if(t <= pNode->m_Value)
				// -----------------------------------------------------------
				else { // node is greater 
					if(0 != pNode->m_pRight) {
						pNode = pNode->m_pRight;
					}
					else {
						// assign the child and parent to each other
						pNode->m_pRight = pNewNode;
						pNewNode->m_pParent = pNode;
						bSuccess = true;
						break;
					}
				} // else
				// -----------------------------------------------------------
			} // while( true )
			// ---------------------------------------------------------------

		//	LogFile << "Logging at the end of an addNode(Node*)" << endl;

		//	log();

			if( tree_balancer.needsBalancing(this->m_pRoot) ) {
				balance();
			}

			return bSuccess;
		}
		// -------------------------------------------------------------------

		// -------------------------------------------------------------------
		// -------------------------------------------------------------------
		bool removeNode( NodeType* pNode )
		{
			bool bSuccess = true;

			if(0 != pNode) {
				// now divorce it

				// -------------------------------------------------------
				// save the left and right child nodes
				// -------------------------------------------------------
				NodeType* leftNode = pNode->m_pLeft;
				if(0 != leftNode) {
					leftNode->m_pParent = 0;
				}
				NodeType* rightNode = pNode->m_pRight;
				if(0 != rightNode) {
					rightNode->m_pParent = 0;
				}
				// (the node's children have been divorced from their
				// parent, which is the node to be removed)
				// -------------------------------------------------------

				// -------------------------------------------------------
				// Now we must divorce the node to be removed from its parent
				// -------------------------------------------------------
				if(NULL != pNode->m_pParent) {
					// determine if it's a left or a right child
					if(pNode->m_pParent->m_pLeft == pNode) {
						(pNode->m_pParent)->m_pLeft = 0;
					}
					else {
						(pNode->m_pParent)->m_pRight = 0;
					}
					(pNode)->m_pParent = 0;
				}
				else { // else, this was the root node. must set it to NULL!
						// I've had two bugs because of this one...be careful...
					m_pRoot = 0;
				}
				// (the parent of the node to be removed no longer has a reference
				// to the node to be removed)
				// -------------------------------------------------------

				// -------------------------------------------------------
				// remove the node
				// -------------------------------------------------------
				node_allocator.deleteNode(pNode);
				// if this node was the parent, then we must set the m_parent
				// member to NULL so that the next add creates a root again
				if(m_pRoot == pNode) {
					m_pRoot = 0;
				}
				pNode = 0;
				// -------------------------------------------------------

				// -------------------------------------------------------
				// add back any children...
				// add the left and right child nodes back into the tree
				// NOTE: if the node that was removed was the root, 
				//	     then the left child becomes the new root
				// -------------------------------------------------------
				if(0 != leftNode) {
					bSuccess = addNode(leftNode);
				}
				if(0 != rightNode) {
					bSuccess = bSuccess && addNode(rightNode);
				}
				// -------------------------------------------------------
			} // if(NULL != pNode)

			return bSuccess;
		}
		// -------------------------------------------------------------------

		// ---------------------------------------------------------------
		// This call will balance the tree (should be done after addNode
		// operations are complete)
		//
		// TO DO:  There is no real reason to allocate new nodes, since the
		// data in the nodes themselves are not changing, only the nodes to
		// which they link and the parent of this tree might change.
		// Figure out a way to do this in place by iterating through the
		// tree (using our own iterator), storing the pointers to the nodes
		// sorted in an array and then re-assigning the node relationships 
		// one by one (using something like split)
		// ---------------------------------------------------------------
		void balance()
		{
			if(0 == m_pRoot) {
				return;
			}

			std::list<T> LItems;

			// stuff the values into the list
			stuffValuesIntoList(LItems, m_pRoot);
		
			// delete the tree
			clear(m_pRoot);

			// recreate the tree
			createTreeFromList(LItems);
		}
		// ---------------------------------------------------------------

		void stuffAllValuesIntoList(std::list<T>& LItems) const
		{
			stuffValuesIntoList(LItems, this->m_pRoot);
		}

		// ---------------------------------------------------------------
		// This function recursively stuffs the node's value (T object)
		// into a list in the proper order (it assumes the tree is already
		// ordered, which it will be).  This method is slow because it 
		// pushes items into the LItems output parameter (perhaps causing memory
		// allocation).  If you are looking to just iterate through the list
		// use TSortTree::iterator and begin().
		//
		// LItems is an output parameter.
		// ---------------------------------------------------------------
		void stuffValuesIntoList(std::list<T>& LItems, const NodeType* pNode) const
		{
			// return immediately if NULL node
			if(0 == pNode) {
				return;
			}
		
			if(0 != pNode->m_pLeft) {
				stuffValuesIntoList(LItems, pNode->m_pLeft);
			}
		
			LItems.push_back( pNode->m_Value );
		
			if(0 != pNode->m_pRight) {
				stuffValuesIntoList(LItems, pNode->m_pRight);
			}
		
			return;
		}
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// This is a forward iterator that steps from the left-most element
		// to the right-most element.  This iterator class is bidirectional. 
		// You can step from begin() to end(), using the prefix-increment 
		// operator, but you can't step "after" end() using ++.  You 
		// can step from end() to begin() using prefix-decrement but you 
		// can't step past "before" begin() using --.  begin() is an iterator
		// that points to the left-most element and end() is an iterator that
		// points one past the right-most element.
		// 
		// reverse_iterator does the opposite (can go from right-most element
		// to one before the left-most element)
		// ---------------------------------------------------------------
		class iterator {
		protected:
			typedef TSortTree<T,MappingPolicy,AllocatorPolicy,BalancerPolicy> TreeType;
			typedef TTreeNode<T> NodeType;

			friend class TreeType;

			const TreeType* m_pTree;
			NodeType* m_pNode;

			void copy(const iterator& o) {
				if( &o != this) {
					m_pTree = o.m_pTree;
					m_pNode = o.m_pNode;
				}
			}
		public:
			iterator() : m_pNode(0), m_pTree(0) {}
			iterator(const TreeType* pTree, NodeType* pNode) : m_pNode(pNode), m_pTree(pTree) {}
			iterator(const iterator& o) { copy(o); }
			// WARNING!  Uncommenting this destructor causes a C1001: INTERNAL COMPILER ERROR 
			// in VC6 (msvc1.cpp:1794)
			~iterator() {}
			iterator& operator=(const iterator& o) { copy(o); return *this; }

			// do this blindly...get a NULL pointer error if m_pNode is end()
			// (just like std::vector, etc)
			const T& operator*() {
				assert(0 != m_pNode && "Error!  m_pNode was NULL inside TSortTree::iterator::operator*()");
				return m_pNode->m_Value;
			}

			bool operator==(const iterator& it) 
			{ return (m_pTree == it.m_pTree) && (m_pNode == it.m_pNode); }

			bool operator!=(const iterator& it) 
			{ return (m_pTree != it.m_pTree) || (m_pNode != it.m_pNode); }

			// now to advance through the tree....
			// (only supply prefix notation for now)
			iterator& operator++()
			{
				// this ensures that an iterator can never go past the end() of the tree
				if(0 == m_pNode) {return *this;}

				const M::KeyType origValue = TreeType::key_mapper.getKey(m_pNode->m_Value);
				
				if(0 != m_pNode->m_pRight) {

					assert( TreeType::key_mapper.getKey(m_pNode->m_pRight->m_Value) > origValue && 
						"ERROR!  Right node was LESS THAN node above it!");

					// go to the right one node
					m_pNode = m_pNode->m_pRight;

					// and find the lowest node on the left in this branch
					while( 0 != m_pNode->m_pLeft ) {
						m_pNode = m_pNode->m_pLeft;
					} // while( NULL != m_pNode->m_pLeft ) 

					// m_pNode is the next value

					return *this;
				} // if(NULL != m_pNode->m_pRight)
				else { // else, we need to go up the tree

					while(0 != m_pNode->m_pParent) {

						m_pNode = m_pNode->m_pParent;

						// if the parent node was greater than the original
						// value, then return the parent node (because we were in 
						// a left branch)
						if(origValue <= TreeType::key_mapper.getKey(m_pNode->m_Value)) {
							return *this;
						}

					// otherwise, keep going up the tree
					} // while(NULL != m_pNode->m_pParent) 

				} // else

				// if we got through to here, that means that no node is
				// higher (in order) to this node, so we are now at the end()
				m_pNode = 0;
				return *this;
			}

			// now to retreat through the tree....towards begin()
			// (only supply prefix notation for now)
			iterator& operator--()
			{
				// if m_pNode is NULL, then we are at end(), need to get
				// to most right node
				if(0 == m_pNode) {
					assert(0 != m_pTree && "Error!  Tree pointer was NULL inside iterator::operator--()");
					const NodeType* pRootNode = m_pTree->getRootNode();

					// if we have an empty tree, then simply return this iterator...
					if(0 == pRootNode) { return *this; }

					// else, we need to find the right-most element in the tree, 
					// which is (end() - 1)
					m_pNode = const_cast<NodeType*>(pRootNode);

					while(0 != m_pNode->m_pRight) {
						m_pNode = m_pNode->m_pRight;
					}
					return *this;
				}
				else { // else, we are on a valid node in the tree (the tree is non-empty)

					// the algorithm is this:
					//		- if we have a left child, 
					if(0 != m_pNode->m_pLeft) {
						//		- go to the left child, then 
						m_pNode = m_pNode->m_pLeft;
					
						//			- recurse down nodes until we no longer have a right child and return it
						while(0 != m_pNode->m_pRight) {
							m_pNode = m_pNode->m_pRight;
						}
						return *this;
					} // if(NULL != m_pNode->m_pLeft)
					else { // else, we go to the parent node and check:
						NodeType* pOrigNode = m_pNode;
						const M::KeyType origValue = TreeType::key_mapper.getKey(m_pNode->m_Value);

						while(0 != m_pNode->m_pParent) { 
							m_pNode = m_pNode->m_pParent;

							//	- if the parent's value is less than or equal to this node, then return it
							// (because we were in a right branch)
							if(TreeType::key_mapper.getKey(m_pNode->m_Value) <= origValue) {
								return *this;
							}

							//	- else, if the parent's value is greater than this node (i.e.
							//	we were in a left node), then keep going up the tree
						} // while(NULL != m_pNode->m_pParent)

						// if we got to here, then we need to just sit tight
						// (i.e. restore the previous node and return it as we are
						// at begin())
						m_pNode = pOrigNode;
					} // else (NULL == m_pNode->m_pLeft)

				} // if(NULL != m_pNode)

				return *this;
			}
		}; // end forward iterator class
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// this refers to the lowest element in order
		// ---------------------------------------------------------------
		iterator begin() const {
			NodeType* pNode = m_pRoot;
			if(0 == pNode) return end();

			while(0 != pNode->m_pLeft) {
				pNode = pNode->m_pLeft;
			}
			return iterator(this, pNode);
		}
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// this refers to "one past" the largest element in order
		// ---------------------------------------------------------------
		iterator end() const {
			return iterator(this, 0);
		}
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// Removes the node pointed to by iterator and returns an 
		// iterator that points to the next element in the sequence.
		// WARNING:  The iterator erased is invalidated.
		// ---------------------------------------------------------------
		iterator erase(iterator it) {
			NodeType* pNode = it.m_pNode;
			// increment the iterator
			++it;
			removeNode(pNode);
			return it;
		}
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// ---------------------------------------------------------------
		class reverse_iterator {
		protected:
			typedef TSortTree<T,MappingPolicy,AllocatorPolicy,BalancerPolicy> TreeType;
			typedef TTreeNode<T> NodeType;

			friend class TreeType;
			const TreeType* m_pTree;
			NodeType* m_pNode;

			void copy(const reverse_iterator& o) {
				if(&o != this) {
					m_pTree = o.m_pTree;
					m_pNode = o.m_pNode;
				}
			}
		public:
			reverse_iterator() : m_pNode(0), m_pTree(0) {}
			reverse_iterator(const TreeType* pTree, NodeType* pNode) : m_pNode(pNode), m_pTree(pTree) {}
			reverse_iterator(const reverse_iterator& o) { copy(o); }
			// WARNING!  Uncommenting this destructor causes a C1001: INTERNAL COMPILER ERROR 
			// on VC6 (msvc1.cpp:1794)
			~reverse_iterator() {}
			reverse_iterator& operator=(const reverse_iterator& o) { copy(o); return *this; }

			// do this blindly...get a NULL pointer error if m_pNode is end()
			// (just like std::vector, etc)
			const T& operator*() {
				assert(0 != m_pNode && "Error!  m_pNode was NULL inside TSortTree::iterator::operator*()");
				return m_pNode->m_Value;
			}

			bool operator==(const reverse_iterator& it) 
			{ return (m_pTree == it.m_pTree) && (m_pNode == it.m_pNode); }

			bool operator!=(const reverse_iterator& it) 
			{ return (m_pTree != it.m_pTree) || (m_pNode != it.m_pNode); }

			// now retreat through the tree....this goes from farthest right to farthest left
			// (only supply prefix notation for now)
			reverse_iterator& operator++()
			{
				// this ensures that a reverse_iterator can never go past the rend() of the tree
				if(0 == m_pNode) {return *this;}

				const M::KeyType origValue = TreeType::key_mapper.getKey(m_pNode->m_Value);
				
				if(0 != m_pNode->m_pLeft) {
					assert( TreeType::key_mapper.getKey(m_pNode->m_pLeft->m_Value) <= origValue &&
						"ERROR!  Left node was GREATER THAN node above it!");

					// go to the left one node
					m_pNode = m_pNode->m_pLeft;

					// and find the lowest node on the right in this branch
					while( 0 != m_pNode->m_pRight ) {
						m_pNode = m_pNode->m_pRight;
					} // while( NULL != m_pNode->m_pRight ) 

					// m_pNode is the next value

					return *this;
				} // if(NULL != m_pNode->m_pLeft)
				else { // else, we need to go up the tree

					while(0 != m_pNode->m_pParent) {

						m_pNode = m_pNode->m_pParent;

						// if the parent node was less than the original
						// value, then return the parent node
						if(origValue > TreeType::key_mapper.getKey(m_pNode->m_Value)) {
							return *this;
						}

					// otherwise, keep going up the tree
					} // while(NULL != m_pNode->m_pParent) 
				} // else

				// if we got through to here, that means that no node is
				// higher (in order) to this node, so we are now at the rend()
				m_pNode = 0;
				return *this;
			}

			// now to advance through the tree....towards rbegin()
			// (only supply prefix notation for now)
			reverse_iterator& operator--()
			{
				// if m_pNode is NULL, then we are at rend(), need to get
				// to most left node
				if(0 == m_pNode) {
					assert(0 != m_pTree && "Error!  Tree pointer was NULL inside iterator::operator--()");
					const NodeType* pRootNode = m_pTree->getRootNode();

					// if we have an empty tree, then simply return this iterator...
					if(0 == pRootNode) { return *this; }

					// else, we need to find the left-most element in the tree, 
					// which is (rend() - 1)
					m_pNode = const_cast<NodeType*>(pRootNode);

					while(0 != m_pNode->m_pLeft) {
						m_pNode = m_pNode->m_pLeft;
					}
					return *this;
				}
				else { // else, we are on a valid node in the tree (the tree is non-empty)

					// the algorithm is this:
					//		- if we have a right child, 
					if(0 != m_pNode->m_pRight) {
						//		- go to the right child, then 
						m_pNode = m_pNode->m_pRight;
					
						//			- recurse down nodes until we no longer have a left child and return it
						while(0 != m_pNode->m_pLeft) {
							m_pNode = m_pNode->m_pLeft;
						}
						return *this;
					} // if(NULL != m_pNode->m_pRight)
					else { // else, we go to the parent node and check:
						NodeType* pOrigNode = m_pNode;
						const M::KeyType origValue = TreeType::key_mapper.getKey(m_pNode->m_Value);

						while(0 != m_pNode->m_pParent) { 
							m_pNode = m_pNode->m_pParent;

							//	- if the parent's value is greater than this node, then return it
							if(TreeType::key_mapper.getKey(m_pNode->m_Value) > origValue) {
								return *this;
							}

							//	- else, if the parent's value is less than or equal to than this node 
							// (i.e. we were in a right node), then keep going up the tree
						} // while(NULL != m_pNode->m_pParent)

						// if we got to here, then we need to just sit tight
						// (i.e. restore the previous node and return it as we are
						// at begin())
						m_pNode = pOrigNode;
					} // else (NULL == m_pNode->m_pLeft)

				} // if(NULL != m_pNode)

				return *this;
			}
		}; // end class reverse_iterator
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// this refers to the largest element in order
		// ---------------------------------------------------------------
		reverse_iterator rbegin() const {
			NodeType* pNode = m_pRoot;
			if(0 == pNode) return rend();

			while(0 != pNode->m_pRight) {
				pNode = pNode->m_pRight;
			}
			return reverse_iterator(this, pNode);
		}
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// this refers to "one before" the lowest element in order
		// ---------------------------------------------------------------
		reverse_iterator rend() const {
			return reverse_iterator(this, 0);
		}
		// ---------------------------------------------------------------


		// ---------------------------------------------------------------
		// Removes the node pointed to by iterator and returns an 
		// iterator that points to the next element in the sequence.
		// WARNING:  The iterator erased is invalidated.
		// ---------------------------------------------------------------
		reverse_iterator erase(reverse_iterator it) {
			NodeType* pNode = it.m_pNode;
			// increment the iterator
			++it;
			removeNode(pNode);
			return it;
		}
		// ---------------------------------------------------------------

		// ---------------------------------------------------------------
		// returns the number of nodes in the tree
		// ---------------------------------------------------------------
		size_t size() const {
			size_t numNodes = 0;
			for(iterator tit = begin(); tit != end(); ++tit) { ++numNodes; }
			return numNodes;
		}
		// ---------------------------------------------------------------

	}; // end of TSortTree template declaration

	// TSortTree implementation
	template<typename T, template<class> class M, template<class> class A, template<class> class B>
	// Shouldn't this be TSortTree<T,M<T>,A<T>,B<T> > ???
	M<T> TSortTree<T,M,A,B>::key_mapper;

	template<typename T, template<class> class M, template<class> class A, template<class> class B>
	A<T> TSortTree<T,M,A,B>::node_allocator;

	template<typename T, template<class> class M, template<class> class A, template<class> class B>
	B<T> TSortTree<T,M,A,B>::tree_balancer;

/*
// -------------------------------------------------------------------
// -------------------------------------------------------------------
class TSortTree 
public:

	bool findNode(const KeyType& key, NodeType& outNode);
	void log() const;

}; // template class TSortTree
// -------------------------------------------------------------------
	*/

	}; // namespace SortTree

}; // namespace LD

#endif // __LD_TSORTTREE_H