RP411/MUNGA/TREE.h

#pragma once

#include "node.h"
#include "srtskt.h"
#include "memblock.h"

class Tree;
class TreeIterator;

class TreeNode : public Link
{
	friend class Tree;
	friend class TreeIterator;

public:
	~TreeNode();
	Logical TestInstance() const;

protected:
	TreeNode(Tree *tree, Plug *plug);

private:
	void SetupTreeLinks(TreeNode *less, TreeNode *greater, TreeNode *parent);

	TreeNode *less;
	TreeNode *greater;
	TreeNode *parent;
};

#define TREENODE_MEMORYBLOCK_ALLOCATION (100)

template <class V> class TreeNodeOf : public TreeNode
{
public:
	TreeNodeOf(Tree *tree, Plug *plug, const V &value);
	~TreeNodeOf();

	void* operator new(size_t);
	void operator delete(void *where);

	V GetValue()			{ return value; }
	V* GetValuePointer()	{ return &value; }

private:
	static MemoryBlock *allocatedMemory;
	static CollectionSize allocationCount;

	V value;
};

template <class V> MemoryBlock* TreeNodeOf<V>::allocatedMemory = NULL;
template <class V> CollectionSize TreeNodeOf<V>::allocationCount = 0;

template <class V> TreeNodeOf<V>::TreeNodeOf(Tree *tree, Plug *plug, const V &value) : TreeNode(tree, plug)
{
	this->value = value;
}

template <class V> TreeNodeOf<V>::~TreeNodeOf()
{
}

#if 0
	template <class V> void* TreeNodeOf<V>::operator new(size_t)
	{
		if (allocatedMemory == NULL)
			allocatedMemory = new MemoryBlock(sizeof(TreeNodeOf<V>), TREENODE_MEMORYBLOCK_ALLOCATION, TREENODE_MEMORYBLOCK_ALLOCATION);
		Check(allocatedMemory);
		return allocatedMemory->New();
	}

	template <class V> void TreeNodeOf<V>::operator delete(void *where)
	{
		Check(allocatedMemory);
		allocatedMemory->Delete(where);
	}
#else
	template <class V> void* TreeNodeOf<V>::operator new(size_t)
	{
		Verify(allocationCount >= 0);
		if (allocationCount++ == 0)
		{
			allocatedMemory = new MemoryBlock(sizeof(TreeNodeOf<V>), TREENODE_MEMORYBLOCK_ALLOCATION, TREENODE_MEMORYBLOCK_ALLOCATION, "TreeNodeOf");
			Register_Object(allocatedMemory);
		}
		Verify(allocationCount < INT_MAX);
		Check(allocatedMemory);
		return allocatedMemory->New();
	}

	template <class V> void TreeNodeOf<V>::operator delete(void *where)
	{
		Check(allocatedMemory);
		allocatedMemory->Delete(where);
		if (--allocationCount == 0)
		{
			Unregister_Object(allocatedMemory);
			delete allocatedMemory;
			allocatedMemory = NULL;
		}
		Verify(allocationCount >= 0);
	}
#endif

class Tree : public SortedSocket
{
	friend class TreeNode;
	friend class TreeIterator;

public:
	Tree(Node *node, Logical has_unique_entries);
	~Tree();

	Logical TestInstance() const;
	static void TestClass();
	static void	ProfileClass();

protected:
	void AddImplementation(Plug *);
	void AddValueImplementation(Plug *plug, const void *value);
	Plug *FindImplementation(const void *value);

private:
	virtual TreeNode*
  	MakeTreeNode(Plug *plug, const void *value);
	virtual int CompareTreeNodes(TreeNode *link1, TreeNode *link2);
	virtual int CompareValueToTreeNode(const void *value, TreeNode *link);

	void AddTreeNode(TreeNode *node);
	void SeverFromTreeNode(TreeNode *node);
	TreeNode* SearchForValue(const void *value);

	TreeNode *root;
};

template <class T, class V> class TreeOf : public Tree
{
public:
	TreeOf(Node *node, Logical has_unique_entries);
	~TreeOf();

	void AddValue(T plug, const V &value)	{ AddValueImplementation(plug, &value); }
	T Find(const V &value)					{ return (T)FindImplementation(&value); }
		
private:
	TreeNode *MakeTreeNode(Plug *plug, const void *value)	{ return new TreeNodeOf<V>(this, plug, *(V*)value); }
	int CompareTreeNodes(TreeNode *link1, TreeNode *link2);
	int CompareValueToTreeNode(const void *value, TreeNode *link);
};

template <class T, class V> TreeOf<T, V>::TreeOf(Node *node, Logical has_unique_entries) : Tree(node, has_unique_entries)
{
}

template <class T, class V> TreeOf<T, V>::~TreeOf()
{
}

#if 0
	template <class T, class V> int TreeOf<T, V>::CompareTreeNodes(TreeNode *node1, TreeNode *node2)
	{
		V result = Cast_Object(TreeNodeOf<V>*, node1)->GetValue() - Cast_Object(TreeNodeOf<V>*, node2)->GetValue();

		if (result == (V)0)
			return 0;
		return (result > (V)0) ? 1 : -1;
	}
#else
	template <class T, class V> int TreeOf<T, V>::CompareTreeNodes(TreeNode *node1, TreeNode *node2)
	{
		V *ptr1 = Cast_Object(TreeNodeOf<V>*, node1)->GetValuePointer();
		V *ptr2 = Cast_Object(TreeNodeOf<V>*, node2)->GetValuePointer();

		Check_Pointer(ptr1);
		Check_Pointer(ptr2);

		if (*ptr1 == *ptr2)
			return 0;
		else
			return ((*ptr1 > *ptr2) ? 1 : -1);
	}
#endif

#if 0
	template <class T, class V> int TreeOf<T, V>::CompareValueToTreeNode(const void *value, TreeNode *node)
	{
		Check_Pointer(value);

		V result = *(V*)value - Cast_Object(TreeNodeOf<V>*, node)->GetValue();

		if (result == (V)0)
			return 0;
		return (result > (V)0) ? 1 : -1;
	}
#else
	template <class T, class V> int TreeOf<T, V>::CompareValueToTreeNode(const void *value, TreeNode *node)
	{
		Check_Pointer(value);

		V *ptr = Cast_Object(TreeNodeOf<V>*, node)->GetValuePointer();
		Check_Pointer(ptr);

		if (*(V*)value == *ptr)
			return 0;
		else
			return (*(V*)value > *ptr) ? 1 : -1;
	}
#endif

class TreeIterator : public SortedIterator
{
public:
	TreeIterator(Tree *tree);
	~TreeIterator();
	Logical TestInstance() const;

	void First();
	void Next();
	CollectionSize GetSize();
	void Remove();

protected:
	void* GetCurrentImplementation();
	Plug* FindImplementation(const void *value);

protected:
	TreeNode *currentNode;

private:
	void Last();				 // Marked as private so that clients do not use it
	void Previous();			 // Marked as private so that clients do not use it

	void ReceiveMemo(IteratorMemo memo, void *content);
};

template <class T, class V> class TreeIteratorOf : public TreeIterator
{
public:
	TreeIteratorOf(TreeOf<T, V> *tree);
	TreeIteratorOf(TreeOf<T, V> &tree);
	~TreeIteratorOf();

	T ReadAndNext()					{ return (T)ReadAndNextImplementation(); }
	T GetCurrent()					{ return (T)GetCurrentImplementation(); }
	T GetNth(CollectionSize index)	{ return (T)GetNthImplementation(index); }
	T Find(const V &value)			{ return (T)FindImplementation(&value); }
	V GetValue()					{ return Cast_Object(TreeNodeOf<V>*, currentNode)->GetValue(); }
};

//~~~~~~~~~~~~~~~~~~~~~~~~~~~ TreeIteratorOf templates ~~~~~~~~~~~~~~~~~~~~~~~~~~~

template <class T, class V> TreeIteratorOf<T, V>::TreeIteratorOf(TreeOf<T, V> *tree) : TreeIterator(tree)
{
}

template <class T, class V> TreeIteratorOf<T, V>::TreeIteratorOf(TreeOf<T, V> &tree) : TreeIterator(&tree)
{
}

template <class T, class V> TreeIteratorOf<T, V>::~TreeIteratorOf()
{
}