// DWBS ------------------------------------------------------------------ DWBS
//
// PLATFORM		: ALL
// PRODUCT		: BIT_DEMON
// VISIBILITY	: PUBLIC
//
// DWBS ------------------------------------------------------------------ DWBS

// PURPOSE: This ternary tree template provides an efficient way to store
// key-value-pairs. There are two template arguments, T and U.
// The key is an array of Us and the values (i.e. the
// data stored in the nodes) are of type T.

#ifndef BD_TERNARY_TREE_H
#define BD_TERNARY_TREE_H

#include <bdCore/bdMemory/bdMemory.h>
#include <bdCore/bdContainers/bdFastArray.h>

/// This ternary tree template provides an efficient way to store
/// key-value-pairs. There are two template arguments, T and U.
/// The key is an array of Us and the values (i.e. the
/// data stored in the nodes) are of type T.
template <typename T, typename U = bdByte8>
class bdTernaryTree
{
	public:

		BD_DECLARE_NEW_AND_DELETE_OPERATORS

	protected:

		/// A node in the ternary tree.
		class Node
		{
			public:

				BD_DECLARE_NEW_AND_DELETE_OPERATORS

				/// Default constructor.
				inline Node()
				: m_data(BD_NULL),
				  m_parent(BD_NULL),
				  m_lo(BD_NULL),
				  m_eq(BD_NULL),
				  m_hi(BD_NULL)
				{
				}

				/// Constructor taking initialisation args.
				inline Node(const U& splitval,
							Node *const parent)
				: m_splitval(splitval),
				  m_data(BD_NULL),
				  m_parent(parent),
				  m_lo(BD_NULL),
				  m_eq(BD_NULL),
				  m_hi(BD_NULL)
				{
				}

				/// Destructor.
				inline ~Node()
				{
					if (m_data)
					{
						delete m_data;
					}
				}

				/// The splitval for the node.
				/// \todo explain splitval
				U m_splitval;

				/// A pointer to the data that this node stores.
				T *m_data;

				/// A pointer to the parent node of this node.
				Node *m_parent;

				/// A pointer to the node with a value less than this node.
				Node *m_lo;

				/// A pointer to the node with a value equal to this node.
				Node *m_eq;

				/// A pointer to the node with a value more than this node.
				Node *m_hi;
		};

	public:

		/// Defines an abstract type to allow easy iteration of the list.
		typedef void* Position;

		/// Default constructor. Constructs an empty tree. The root
		/// node pointer is initialized to BD_NULL.
		inline bdTernaryTree();

		/// Destructor. Deletes the complete tree and
		/// frees all allocated memory. All stored data is lost.
		inline ~bdTernaryTree();

		/// Searches for the node in the tree with key equal to
		/// the array ptr of length len.
		/// \param ptr[]
		/// \param len[]
		inline Position search(const U *ptr,
							   const bdUInt len) const;

		/// Gets the data stored with key ptr[]. Returns a boolean
		/// value indicating if the lookup was successful. If the
		/// lookup was successful, the data found in the tree is copied into
		/// data, otherwise it is left unchanged.
		/// \param ptr[]
		/// \param len[]
		/// \param data[]
		/// \return
		///   - True if the lookup was successful.
		///   - False otherwise.
		inline bdBool get(const U *ptr,
						  const bdUInt len,
						  T &data) const;

		/// Gets the data stored at position pos in the tree. pos
		/// must be a valid node in the tree. Note that operations
		/// that change the tree may invalidate a Position which
		/// was previously valid. Returns a boolean
		/// value indicating if the lookup was successful. If the
		/// lookup was successful, the data found in the tree is copied into
		/// data, otherwise it is left unchanged
		/// \param pos[]
		/// \param data[]
		/// \return
		///   - True if the lookup was successful.
		///   - False otherwise.
		inline bdBool get(const Position pos,
						  T &data) const;

		/// Inserts data into the tree with the key equal
		/// to the array ptr[] of length len. The data put
		/// into the tree is a copy of the data passed.
		/// \param ptr[]
		/// \param len[]
		/// \param data[]
		/// \return
		///   - True if the data was successfully inserted.
		///   - False otherwise.
		inline bdBool insert(const U *ptr,
							 const bdUInt len,
							 const T &data);

		/// Removes the data associated with the
		/// key ptr[] (with key length len). Also
		/// calls the cleanupNode() function to
		/// remove nodes which are not needed
		/// anymore.
		/// \param ptr[]
		/// \param len[]
		/// \return
		///   - True if the data was successfully removed.
		///   - False otherwise.
		inline bdBool remove(const U *ptr,
							 const bdUInt len);

		/// Removes the data at position pos in the
		/// tree. Also calls the cleanupNode()
		/// function to remove nodes which are
		/// not needed anymore.
		/// \param pos[]
		/// \return
		///   - True if the data was successfully removed from position pos.
		///   - False otherwise.
		inline bdBool remove(const Position pos);

		/// Replaces the data associated with key
		/// ptr[] with a copy of newData. A copy of the  old data is put
		/// into oldData. Returns a boolean value indicating
		/// if the operation was succesful or not.
		/// \param ptr[]
		/// \param len[]
		/// \param oldData[]
		/// \param newData[]
		/// \return
		///   - True if the data was successfully replaced.
		///   - False otherwise.
		inline bdBool replace(const U *ptr,
							  bdUInt len,
							  T &oldData,
							  const T &newData);

		/// Replaces the data associated at position pos
		/// in the tree with a copy of newData. The old data is put
		/// into oldData. Returns a boolean value indicating
		/// if the operation was succesful or not.
		/// \param pos[]
		/// \param oldData[]
		/// \param newData[]
		/// \return
		///   - True if the data was successfully replaced at position pos.
		///   - False otherwise.
		inline bdBool replace(const Position pos,
							  T &oldData,
							  const T &newData);

		/// Deletes the tree at position pos. This includes
		/// also the node at position pos. Deletes nodes and
		/// also the data.
		/// \param pos[]
		inline void deleteTree(const Position pos);

		/// Returns the root node of the tree.
		/// \return The root node of the tree
		inline Position getRoot() const;

		/// Returns the parent node of the node at position pos.
		/// \param pos[]
		/// \return The parent node of the node at position pos.
		inline Position getParent(const Position pos) const;

		/// Returns the equal child node of the node at position pos.
		/// \param pos[]
		/// \return The equal child node of the node at position pos.
		inline Position getEqNode(const Position pos) const;

		/// Returns the low child node of the node at position pos.
		/// \param pos[]
		/// \return The low child node of the node at position pos.
		inline Position getLoNode(const Position pos) const;

		/// Returns the high child node of the node at position pos.
		/// \param pos[]
		/// \return The high child node of the node at position pos.
		inline Position getHiNode(const Position pos) const;

		/// Prints a schematic view of the tree to the standard
		/// output. Nodes populated with data are depicted as '*', nodes
		/// without data as'o'.
		inline void print() const;

		/// Pushes all nodes to the back of an array.
		/// \param array[]
		/// \param pos[]
		inline void getAllDataNodes(bdFastArray<Position> &array,
									const Position pos = BD_NULL) const;

		/// Pushes the key associated with the position pos to the back
		/// of the key array.
		/// \param pos[]
		/// \param key[]
		inline void getKey(const Position pos, bdFastArray<U> &key) const;

	protected:

		/// Removes the node at position pos if it
		/// contains no data and no child nodes. Does
		/// the same recursively for the parent node
		/// of pos.
		/// \param pos[]
		inline void cleanupNode(const Position pos);

		/// \param array[]
		/// \param pos[]
		/// \param y[]
		inline void getAllNodes(bdFastArray<bdFastArray<Position>*> &array,
								const Position pos = BD_NULL,
								const bdUInt y = 0) const;
		/// \param node[]
		/// \param key[]
		inline void recursiveGetKey(Node* node, bdFastArray<U> &key) const;

	protected:

		Node *m_root;
};

#include <bdCore/bdContainers/bdTernaryTree.inl>

#endif // BD_TERNARY_TREE_H

