<commit_before>// $Id: binarySearchTree.h,v 1.10 2000/08/06 15:27:52 amoll Exp $

#ifndef BALL_DATATYPE_BINARYSEARCHTREE_H
#define BALL_DATATYPE_BINARYSEARCHTREE_H

#ifndef BALL_COMMON_H
#	include <BALL/common.h>
#endif
 
#ifndef BALL_COMMON_COMMON_H
#	include <BALL/COMMON/rtti.h>
#endif
 
#ifndef BALL_CONCEPT_COMPARATOR_H
#	include <BALL/CONCEPT/comparator.h>
#endif

#ifndef BALL_CONCEPT_FORWARDITERATOR_H
#	include <BALL/CONCEPT/forwardIterator.h>
#endif

#ifndef BALL_CONCEPT_VISITOR_H
#	include <BALL/CONCEPT/visitor.h>
#endif

#ifndef BALL_DATATYPE_FOREACH_H
#	include <BALL/DATATYPE/forEach.h>
#endif

#ifndef BALL_CONCEPT_PROCESSOR_H
#	include <BALL/CONCEPT/processor.h>
#endif

#ifndef BALL_DATATYPE_LISTSTACK_H
#	include <BALL/DATATYPE/listStack.h>
#endif

namespace BALL 
{

	/**	Binary Search Tree Item.
			A red-black tree is a binary search tree with one extra bit of storage per node:
			its color, which can be either RED or BLACK. 
			A binary search tree is a red-black tree if it satisfies the following red-black
			properties:
			{\em 1.} Every node is either red or black.
			{\em 2.} Every leaf is black.
			{\em 3.} If a node is red, then both its children are black.
			{\em 4.} Every simple path from a node to a descendant leaf contains the same
							 number of black nodes.
	*/
	class BSTreeItem 
	{ 
		public:

		/**	@name	Enums
		*/
		//@{

		enum
		{
			/**	
			*/
			RED   = 0,

			/**	
			*/
			BLACK = 1
		};
		//@}

		/**	@name	Constructors and Destructors
		*/
		//@{

		/**	Default constructor.
				Create a new and empty BSTreeItem
		*/
		BSTreeItem();

		/**	Copy constructor.
				Create a new BSTreeItem from another
		*/
		BSTreeItem(const BSTreeItem& item, bool /* deep */= true);

		/**	Detailled Constructor.
				Create a new BSTreeItem with color {\tt color} and the two child items
				{\tt left_item} and {\tt right_item}.
				@param	color the node color
				@param	left_item the left child
				@param	right_item the right child
		*/
		BSTreeItem(BSTreeItem* left_item, BSTreeItem* right_item, char color = BSTreeItem::BLACK);

		/**	Destructor.
				Destruct the BSTreeItem
		*/
		~BSTreeItem();
		//@}

		/**	@name	Accessors
		*/
		//@{

		/**	Assign the left child.
				The item's left child is replaced by {\tt item}. The replaced item
				is not destructed.
				@param	item the new left child
		*/
		void setLeftChild(BSTreeItem* item);

		/**	Return the left child.
				@return the item's left child item
		*/
		BSTreeItem*& getLeftChild() const;
		
		/**	Assign the right child.
				The item's right child is replaced by {\tt item}. The replaced item
				is not destructed.
				@param	item the new right child
		*/
		void setRightChild(BSTreeItem *item);

		/**	Return the right child.
				@return the item's right child item
		*/
		BSTreeItem*& getRightChild() const;

		/**	Return the color of this instance.
				@return char the color 0 = RED, 1 = BLACK
		*/
		char getColor() const;

		/**	Set the color of this instance.
				If no suitable value for color is given nothing happens.
				@param color the color 0 = RED, 1 = BLACK
		*/
		void setColor(char color);

		/**	Get the size of this instance.
				The size is the number of all offsprings + 1.
				(The instance itselfs counts also).
				@return Size the size
		*/
		Size getSize() const;

		/**	Get the height of the tree with this instance as root.
				(The instance itselfs counts also).
				@return Size the height
		*/
		Size getHeight() const;

		/** Get the minimum node.
				The minimum is the leftmost node in the tree.
				@return BSTreeItem* the minimum node
		*/
		const BSTreeItem* getMinimum() const;

		/** Get the maximum node.
				The maximum is the rightmost node in the tree.
				@return BSTreeItem* the maximum node
		*/
		const BSTreeItem* getMaximum() const;

		/** Get the parent of the minimum node.
				The minimum node is the leftmost node in the tree.
				@return BSTreeItem* the parent of the minimum node
		*/
		BSTreeItem* getParentOfMinimum(); // ??? warum hier nich const?

		/** Get the parent of the maximum node.
				The maximum node is the rightmost node in the tree.
				@return BSTreeItem* the parent of the maximum node
		*/
		BSTreeItem* getParentOfMaximum();

		/** Get the parent of the predecessor.
				The successor of a node x is the node with the largest
				key smaller than key[x].
				Predecessor is the right child of node returned, unless item 
				itself is the parent. Then the left child is the predecessor. 
				If this is a leaf, 0 is returned. ASSUMES item isn't null.
		*/
		BSTreeItem* getParentOfPredecessor();	// ??? warum hier nich const?

		/** Get the parent of the successor.
				The successor of a node x is the node with the smallest
				key greater than key[x].
				Successor is the left child of node returned, unless item itself is the parent.
				Then the right child is the successor. 
				If item is a leaf, 0 is returned. ASSUMES item isn't null.
		*/
		BSTreeItem* getParentOfSuccessor();

		/** Detaches node item with parent p from the tree.
				Node item is the left child if right_side = false,
				else it's the right child.
				If p is 0, it means item is the root, and that is handled
				accordingly. Redundantly returns the pointer item. May
				have to update root pointer.
				@param root gets the address of the replacement if no parent of t was given
				@param p pointer to the parent of t
				@param t the item to remove
				@param right_side defines where to place the replacement, default = true => right child
				@return BSTreeItem* pointer to the removed item
		*/
		static BSTreeItem* detachNode
			(BSTreeItem*& root, BSTreeItem* t,
			 BSTreeItem* p, bool right_side);

		/** Rotate right a node an its children.
				PRECONDITION: left child exists.
				If left child does not exists 0 is returned.
		*/
		BSTreeItem* rotateRight();

		/** Rotate left a node an its children.
				PRECONDITION: right child exists.
				If right child does not exists 0 is returned.
		*/
		BSTreeItem* rotateLeft();

		//@}

		/**	@name	Processor Application Methods
		*/	
		//@{

		/** Apply a processor in preorder to the tree.
				Preorder means the root is processed first, than the left subtree
				and at the end the right subtree.
		*/
		bool applyPreorder(UnaryProcessor<BSTreeItem>& processor);
		
		/** Apply a processor in inorder to the tree.
				Inorder means the left subtree is processed first, than the root
				and at the end the right subtree.
		*/
		bool applyInorder(UnaryProcessor<BSTreeItem>& processor);

		/** Apply a processor in postorder to the tree.
				Postorder means the left subtree is processed first, than the right subtree
				and at the end the root.
		*/
		bool applyPostorder(UnaryProcessor<BSTreeItem>& processor);

		/** Apply a processor in levelorder to the tree.
				Levelorder means root is processed first, than all child, 
				after that all grandchilds, etc.
		*/
		bool applyLevelorder(UnaryProcessor<BSTreeItem>& processor);

		/**
		*/
		bool applyPreorderFlat(UnaryProcessor<BSTreeItem>& processor);

		/**
		*/
		bool applyInorderFlat(UnaryProcessor<BSTreeItem>& processor);

		/**
		*/
		bool applyPostorderFlat(UnaryProcessor<BSTreeItem>& processor);

		/** Apply a processor to all nodes of the tree.
				This method uses Preorder.
				@see applyPreorder
		*/
		bool apply(UnaryProcessor<BSTreeItem>& processor);
		//@}


		/**	@name Predicates 
		*/
		//@{

		/**	Return true if the node is a leaf of the tree.
				This method returns {\bf true} if the node is 
				a leaf of the tree, i.e. if it has no children.
				@return bool {\bf true} if the node has no children
		*/
		bool isLeaf() const;

		/**	Return true if the node is an interior node of the tree.
				This method returns {\bf true} if the node is 
				an interior node of the tree, i.e. if it has children.
				@return bool {\bf true} if the node has children
		*/
		bool isInterior() const;
		//@}

		struct Pack 
		{
			BSTreeItem* t;
			BSTreeItem* p;
			BSTreeItem* g;
			BSTreeItem* gg;
			BSTreeItem* s;
			BSTreeItem* rs;
			BSTreeItem* ls;
			BSTreeItem* m;
			BSTreeItem* pm;
		};

		static BSTreeItem* insertBalance(BSTreeItem* root, BSTreeItem::Pack& pp);
		
		static BSTreeItem* removeBalance(BSTreeItem* root, BSTreeItem::Pack& pp);
		
		static BSTreeItem* replace(BSTreeItem* root, BSTreeItem::Pack& pp);
		
		static BSTreeItem* detachMinimum(BSTreeItem*& root);
		
		static BSTreeItem* detachMaximum(BSTreeItem*& root);

		protected:

		/**	The left child.
				{\tt left} is a pointer to the left child of this node.
		*/
		BSTreeItem* left_;

		/**	The right child.
				{\tt right} is a pointer to the right child of this node.
		*/
		BSTreeItem* right_;

		/**	The color of the node.
				Each node has a color: either {\tt RED} or {\tt BLACK}.
		*/
		char color_;

		private:

		Processor::Result applyPreorder_(UnaryProcessor<BSTreeItem>& processor);
		
		Processor::Result applyInorder_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyPostorder_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyLevelorder_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyPreorderFlat_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyInorderFlat_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyPostorderFlat_(UnaryProcessor<BSTreeItem>& processor);
	};



	template<typename DataType>
	class TBSTreeItem
		: public BSTreeItem 
	{
		public:
			
		BALL_CREATE_NODEEP(TBSTreeItem)


		/**	@name Constructors and Destructors
		*/
		//@{

		/**	Default constructor.
				Create a new and empty TBSTreeItem
		*/
		TBSTreeItem()
			:	BSTreeItem()
		{
		}

		/**	Detailed constructor.
				Create a new TBSTreeItem from its {\tt data}, {\tt color},
				{\tt left_item} and {\tt right_item}.
				@param	data	the node's data
				@param	color the node's color
				@param	left_item the left child of the node
				@param	right_item the right child of the node
		*/
		TBSTreeItem
			(const DataType& data, TBSTreeItem* left_item, 
			 TBSTreeItem* right_item, char color = BSTreeItem::BLACK)
			: BSTreeItem(left_item, right_item, color),
				data_(data)
		{
		}

		/**	Destructor.
				Destruct the item.
		*/
		~TBSTreeItem()
		{
		}
		//@}
		
		/**	@name	Accessors
		*/
		//@{

		/**	Set the nodes data.
		*/
		void setData(const DataType& data)
		{
			data_ = data;
		}

		/**	Return the nodes data.
				@return the item's data
		*/
		DataType getData() const
		{
			return data_;
		}

		/**	Return the left child.
				@return the item's left child item
		*/
		TBSTreeItem*& getLeftChild()
		{
			return (TBSTreeItem*&)left_;
		}
		
		/**	Return the right child.
				@return the item's right child item
		*/
		TBSTreeItem*& getRightChild()
		{
			return (TBSTreeItem*&)right_;
		}

		/**
		*/
		Size count(const DataType& data, const Comparator<DataType>* comparator) const
		{
			if (comparator == 0)
			{
				throw Exception::NullPointer(__FILE__, __LINE__);
			}

			const TBSTreeItem* item = this;
			Size size = 0;

			while(item) 
			{
				if (comparator->isEqual(item->data_, data) == true)
				{
					++size;
				}

				if (item->left_)
				{
					size += ((TBSTreeItem*)item->left_)->count(data, comparator);
				}
	
				item = (TBSTreeItem*)item->right_;
			}

			return size;
		}
		//@}

		/**	@name	Processor application methods
		*/
		//@{

		/**
		*/
		bool applyPreorder(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyPreorder(tree_item_proc);
		}
		
		/**
		*/
		bool applyInorder(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyInorder(tree_item_proc);
		}

		/**
		*/
		bool applyPostorder(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyPostorder(tree_item_proc);
		}

		/**
		*/
		bool applyLevelorder(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyLevelorder(tree_item_proc);
		}

		/**
		*/
		bool applyPreorderFlat(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyPreorderFlat(tree_item_proc);
		}

		/**
		*/
		bool applyInorderFlat(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyInorderFlat(tree_item_proc);
		}

		/**
		*/
		bool applyPostorderFlat(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyPostorderFlat(tree_item_proc);
		}

		/**
		*/
		bool apply(UnaryProcessor<DataType>processor)
		{
			return applyPreorder(processor);
		}
		//@}

		private:

		DataType data_;

		friend class TreeItemProcessor_
			: public UnaryProcessor<BSTreeItem>
		{
			public:

			TreeItemProcessor_(UnaryProcessor<DataType>* processor = 0)
				:	processor_(processor)
			{
			}
			
			virtual Processor::Result operator () (BSTreeItem& item)
			{
				return processor_->operator()(((TBSTreeItem<DataType> &)item).data_);
			}

			UnaryProcessor<DataType>* processor_;
		};

	};



	class BSTreeIterator 
	{
		public:
			
			enum WalkOrder
			{
				WALK_ORDER__PREORDER,
				WALK_ORDER__INORDER,
				WALK_ORDER__POSTORDER,
				WALK_ORDER__LEVELORDER
			};

			BSTreeIterator
				(const BSTreeItem* item = 0, WalkOrder walk_order = BSTreeIterator::WALK_ORDER__PREORDER);
			
			BSTreeIterator(const BSTreeIterator& iterator);<commit_msg>fixed: illegal combination of friend declaration iwth a class definition<commit_after>// $Id: binarySearchTree.h,v 1.11 2000/08/07 09:53:32 oliver Exp $

#ifndef BALL_DATATYPE_BINARYSEARCHTREE_H
#define BALL_DATATYPE_BINARYSEARCHTREE_H

#ifndef BALL_COMMON_H
#	include <BALL/common.h>
#endif
 
#ifndef BALL_COMMON_COMMON_H
#	include <BALL/COMMON/rtti.h>
#endif
 
#ifndef BALL_CONCEPT_COMPARATOR_H
#	include <BALL/CONCEPT/comparator.h>
#endif

#ifndef BALL_CONCEPT_FORWARDITERATOR_H
#	include <BALL/CONCEPT/forwardIterator.h>
#endif

#ifndef BALL_CONCEPT_VISITOR_H
#	include <BALL/CONCEPT/visitor.h>
#endif

#ifndef BALL_DATATYPE_FOREACH_H
#	include <BALL/DATATYPE/forEach.h>
#endif

#ifndef BALL_CONCEPT_PROCESSOR_H
#	include <BALL/CONCEPT/processor.h>
#endif

#ifndef BALL_DATATYPE_LISTSTACK_H
#	include <BALL/DATATYPE/listStack.h>
#endif

namespace BALL 
{

	/**	Binary Search Tree Item.
			A red-black tree is a binary search tree with one extra bit of storage per node:
			its color, which can be either RED or BLACK. 
			A binary search tree is a red-black tree if it satisfies the following red-black
			properties:
			{\em 1.} Every node is either red or black.
			{\em 2.} Every leaf is black.
			{\em 3.} If a node is red, then both its children are black.
			{\em 4.} Every simple path from a node to a descendant leaf contains the same
							 number of black nodes.
	*/
	class BSTreeItem 
	{ 
		public:

		/**	@name	Enums
		*/
		//@{

		enum
		{
			/**	
			*/
			RED   = 0,

			/**	
			*/
			BLACK = 1
		};
		//@}

		/**	@name	Constructors and Destructors
		*/
		//@{

		/**	Default constructor.
				Create a new and empty BSTreeItem
		*/
		BSTreeItem();

		/**	Copy constructor.
				Create a new BSTreeItem from another
		*/
		BSTreeItem(const BSTreeItem& item, bool /* deep */= true);

		/**	Detailled Constructor.
				Create a new BSTreeItem with color {\tt color} and the two child items
				{\tt left_item} and {\tt right_item}.
				@param	color the node color
				@param	left_item the left child
				@param	right_item the right child
		*/
		BSTreeItem(BSTreeItem* left_item, BSTreeItem* right_item, char color = BSTreeItem::BLACK);

		/**	Destructor.
				Destruct the BSTreeItem
		*/
		~BSTreeItem();
		//@}

		/**	@name	Accessors
		*/
		//@{

		/**	Assign the left child.
				The item's left child is replaced by {\tt item}. The replaced item
				is not destructed.
				@param	item the new left child
		*/
		void setLeftChild(BSTreeItem* item);

		/**	Return the left child.
				@return the item's left child item
		*/
		BSTreeItem*& getLeftChild() const;
		
		/**	Assign the right child.
				The item's right child is replaced by {\tt item}. The replaced item
				is not destructed.
				@param	item the new right child
		*/
		void setRightChild(BSTreeItem *item);

		/**	Return the right child.
				@return the item's right child item
		*/
		BSTreeItem*& getRightChild() const;

		/**	Return the color of this instance.
				@return char the color 0 = RED, 1 = BLACK
		*/
		char getColor() const;

		/**	Set the color of this instance.
				If no suitable value for color is given nothing happens.
				@param color the color 0 = RED, 1 = BLACK
		*/
		void setColor(char color);

		/**	Get the size of this instance.
				The size is the number of all offsprings + 1.
				(The instance itselfs counts also).
				@return Size the size
		*/
		Size getSize() const;

		/**	Get the height of the tree with this instance as root.
				(The instance itselfs counts also).
				@return Size the height
		*/
		Size getHeight() const;

		/** Get the minimum node.
				The minimum is the leftmost node in the tree.
				@return BSTreeItem* the minimum node
		*/
		const BSTreeItem* getMinimum() const;

		/** Get the maximum node.
				The maximum is the rightmost node in the tree.
				@return BSTreeItem* the maximum node
		*/
		const BSTreeItem* getMaximum() const;

		/** Get the parent of the minimum node.
				The minimum node is the leftmost node in the tree.
				@return BSTreeItem* the parent of the minimum node
		*/
		BSTreeItem* getParentOfMinimum(); // ??? warum hier nich const?

		/** Get the parent of the maximum node.
				The maximum node is the rightmost node in the tree.
				@return BSTreeItem* the parent of the maximum node
		*/
		BSTreeItem* getParentOfMaximum();

		/** Get the parent of the predecessor.
				The successor of a node x is the node with the largest
				key smaller than key[x].
				Predecessor is the right child of node returned, unless item 
				itself is the parent. Then the left child is the predecessor. 
				If this is a leaf, 0 is returned. ASSUMES item isn't null.
		*/
		BSTreeItem* getParentOfPredecessor();	// ??? warum hier nich const?

		/** Get the parent of the successor.
				The successor of a node x is the node with the smallest
				key greater than key[x].
				Successor is the left child of node returned, unless item itself is the parent.
				Then the right child is the successor. 
				If item is a leaf, 0 is returned. ASSUMES item isn't null.
		*/
		BSTreeItem* getParentOfSuccessor();

		/** Detaches node item with parent p from the tree.
				Node item is the left child if right_side = false,
				else it's the right child.
				If p is 0, it means item is the root, and that is handled
				accordingly. Redundantly returns the pointer item. May
				have to update root pointer.
				@param root gets the address of the replacement if no parent of t was given
				@param p pointer to the parent of t
				@param t the item to remove
				@param right_side defines where to place the replacement, default = true => right child
				@return BSTreeItem* pointer to the removed item
		*/
		static BSTreeItem* detachNode
			(BSTreeItem*& root, BSTreeItem* t,
			 BSTreeItem* p, bool right_side);

		/** Rotate right a node an its children.
				PRECONDITION: left child exists.
				If left child does not exists 0 is returned.
		*/
		BSTreeItem* rotateRight();

		/** Rotate left a node an its children.
				PRECONDITION: right child exists.
				If right child does not exists 0 is returned.
		*/
		BSTreeItem* rotateLeft();

		//@}

		/**	@name	Processor Application Methods
		*/	
		//@{

		/** Apply a processor in preorder to the tree.
				Preorder means the root is processed first, than the left subtree
				and at the end the right subtree.
		*/
		bool applyPreorder(UnaryProcessor<BSTreeItem>& processor);
		
		/** Apply a processor in inorder to the tree.
				Inorder means the left subtree is processed first, than the root
				and at the end the right subtree.
		*/
		bool applyInorder(UnaryProcessor<BSTreeItem>& processor);

		/** Apply a processor in postorder to the tree.
				Postorder means the left subtree is processed first, than the right subtree
				and at the end the root.
		*/
		bool applyPostorder(UnaryProcessor<BSTreeItem>& processor);

		/** Apply a processor in levelorder to the tree.
				Levelorder means root is processed first, than all child, 
				after that all grandchilds, etc.
		*/
		bool applyLevelorder(UnaryProcessor<BSTreeItem>& processor);

		/**
		*/
		bool applyPreorderFlat(UnaryProcessor<BSTreeItem>& processor);

		/**
		*/
		bool applyInorderFlat(UnaryProcessor<BSTreeItem>& processor);

		/**
		*/
		bool applyPostorderFlat(UnaryProcessor<BSTreeItem>& processor);

		/** Apply a processor to all nodes of the tree.
				This method uses Preorder.
				@see applyPreorder
		*/
		bool apply(UnaryProcessor<BSTreeItem>& processor);
		//@}


		/**	@name Predicates 
		*/
		//@{

		/**	Return true if the node is a leaf of the tree.
				This method returns {\bf true} if the node is 
				a leaf of the tree, i.e. if it has no children.
				@return bool {\bf true} if the node has no children
		*/
		bool isLeaf() const;

		/**	Return true if the node is an interior node of the tree.
				This method returns {\bf true} if the node is 
				an interior node of the tree, i.e. if it has children.
				@return bool {\bf true} if the node has children
		*/
		bool isInterior() const;
		//@}

		struct Pack 
		{
			BSTreeItem* t;
			BSTreeItem* p;
			BSTreeItem* g;
			BSTreeItem* gg;
			BSTreeItem* s;
			BSTreeItem* rs;
			BSTreeItem* ls;
			BSTreeItem* m;
			BSTreeItem* pm;
		};

		static BSTreeItem* insertBalance(BSTreeItem* root, BSTreeItem::Pack& pp);
		
		static BSTreeItem* removeBalance(BSTreeItem* root, BSTreeItem::Pack& pp);
		
		static BSTreeItem* replace(BSTreeItem* root, BSTreeItem::Pack& pp);
		
		static BSTreeItem* detachMinimum(BSTreeItem*& root);
		
		static BSTreeItem* detachMaximum(BSTreeItem*& root);

		protected:

		/**	The left child.
				{\tt left} is a pointer to the left child of this node.
		*/
		BSTreeItem* left_;

		/**	The right child.
				{\tt right} is a pointer to the right child of this node.
		*/
		BSTreeItem* right_;

		/**	The color of the node.
				Each node has a color: either {\tt RED} or {\tt BLACK}.
		*/
		char color_;

		private:

		Processor::Result applyPreorder_(UnaryProcessor<BSTreeItem>& processor);
		
		Processor::Result applyInorder_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyPostorder_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyLevelorder_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyPreorderFlat_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyInorderFlat_(UnaryProcessor<BSTreeItem>& processor);

		Processor::Result applyPostorderFlat_(UnaryProcessor<BSTreeItem>& processor);
	};



	template<typename DataType>
	class TBSTreeItem
		: public BSTreeItem 
	{
		public:
			
		BALL_CREATE_NODEEP(TBSTreeItem)


		/**	@name Constructors and Destructors
		*/
		//@{

		/**	Default constructor.
				Create a new and empty TBSTreeItem
		*/
		TBSTreeItem()
			:	BSTreeItem()
		{
		}

		/**	Detailed constructor.
				Create a new TBSTreeItem from its {\tt data}, {\tt color},
				{\tt left_item} and {\tt right_item}.
				@param	data	the node's data
				@param	color the node's color
				@param	left_item the left child of the node
				@param	right_item the right child of the node
		*/
		TBSTreeItem
			(const DataType& data, TBSTreeItem* left_item, 
			 TBSTreeItem* right_item, char color = BSTreeItem::BLACK)
			: BSTreeItem(left_item, right_item, color),
				data_(data)
		{
		}

		/**	Destructor.
				Destruct the item.
		*/
		~TBSTreeItem()
		{
		}
		//@}
		
		/**	@name	Accessors
		*/
		//@{

		/**	Set the nodes data.
		*/
		void setData(const DataType& data)
		{
			data_ = data;
		}

		/**	Return the nodes data.
				@return the item's data
		*/
		DataType getData() const
		{
			return data_;
		}

		/**	Return the left child.
				@return the item's left child item
		*/
		TBSTreeItem*& getLeftChild()
		{
			return (TBSTreeItem*&)left_;
		}
		
		/**	Return the right child.
				@return the item's right child item
		*/
		TBSTreeItem*& getRightChild()
		{
			return (TBSTreeItem*&)right_;
		}

		/**
		*/
		Size count(const DataType& data, const Comparator<DataType>* comparator) const
		{
			if (comparator == 0)
			{
				throw Exception::NullPointer(__FILE__, __LINE__);
			}

			const TBSTreeItem* item = this;
			Size size = 0;

			while(item) 
			{
				if (comparator->isEqual(item->data_, data) == true)
				{
					++size;
				}

				if (item->left_)
				{
					size += ((TBSTreeItem*)item->left_)->count(data, comparator);
				}
	
				item = (TBSTreeItem*)item->right_;
			}

			return size;
		}
		//@}

		/**	@name	Processor application methods
		*/
		//@{

		/**
		*/
		bool applyPreorder(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyPreorder(tree_item_proc);
		}
		
		/**
		*/
		bool applyInorder(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyInorder(tree_item_proc);
		}

		/**
		*/
		bool applyPostorder(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyPostorder(tree_item_proc);
		}

		/**
		*/
		bool applyLevelorder(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyLevelorder(tree_item_proc);
		}

		/**
		*/
		bool applyPreorderFlat(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyPreorderFlat(tree_item_proc);
		}

		/**
		*/
		bool applyInorderFlat(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyInorderFlat(tree_item_proc);
		}

		/**
		*/
		bool applyPostorderFlat(UnaryProcessor<DataType>& processor)
		{
			TreeItemProcessor_ tree_item_proc(&processor);
			
			return BSTreeItem::applyPostorderFlat(tree_item_proc);
		}

		/**
		*/
		bool apply(UnaryProcessor<DataType>processor)
		{
			return applyPreorder(processor);
		}
		//@}

		private:

		DataType data_;

		class TreeItemProcessor_
			: public UnaryProcessor<BSTreeItem>
		{
			public:

			TreeItemProcessor_(UnaryProcessor<DataType>* processor = 0)
				:	processor_(processor)
			{
			}
			
			virtual Processor::Result operator () (BSTreeItem& item)
			{
				return processor_->operator()(((TBSTreeItem<DataType> &)item).data_);
			}

			UnaryProcessor<DataType>* processor_;
		};
		friend class TreeItemProcessor_;

	};



	class BSTreeIterator 
	{
		public:
			
			enum WalkOrder
			{
				WALK_ORDER__PREORDER,
				WALK_ORDER__INORDER,
				WALK_ORDER__POSTORDER,
				WALK_ORDER__LEVELORDER
			};

			BSTreeIterator
				(const BSTreeItem* item = 0, WalkOrder walk_order = BSTreeIterator::WALK_ORDER__PREORDER);
			
			BSTreeIterator(const BSTreeIterator& iterator);
{'fraction_non_alphanumeric': 0.09927254023072966, 'fraction_numerical': 0.002718789036666912, 'mean_word_length': 3.120345140781108, 'pattern_counts': {'":': 0, '<': 77, '<?xml version=': 0, '>': 93, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2636515', 'n_tokens_mistral': 10715, 'n_tokens_neox': 8837, 'n_words': 2824}