Class design, for a binary tree.

[rince]

I have a class that implements a node in a binary tree. It is based on http://en.wikipedia.org/wiki/Binary_search_tree and looks something like this:

class IBinaryTreeNode
{
public:
IBinaryTreeNode();
virtual int GetKey() = 0;

private:
void Add(IBinaryTreeNode* pNode);
void Remove(IBinaryTreeNode** pRoot);
void DebugDraw(int Indent, char LR);

void ReplaceWith(IBinaryTreeNode* pNode);
void RemoveAtParent(IBinaryTreeNode** pRoot, IBinaryTreeNode* pNewChild);
IBinaryTreeNode* FindRightmost();

IBinaryTreeNode* m_pParent;
IBinaryTreeNode* m_pLeft;
IBinaryTreeNode* m_pRight;

};

The idea is that any class that wants to be in a tree will derive from it and implement the GetKey() function. I also have the actual binary tree class that looks like this:

class CBinaryTree
{
public:
CBinaryTree();
void AddNode(IBinaryTreeNode *pNode);
void RemoveNode(IBinaryTreeNode *pNode);

void DebugDrawTree();
void DebugDrawAscending();

private:
IBinaryTreeNode* m_pRoot;
};
What I want to do is make only the constructor and the GetValue member functions be accessable to any classes derived from IBinaryTreeNode.

Then

void Add(IBinaryTreeNode* pNode);
void Remove(IBinaryTreeNode** pRoot);
void DebugDraw(int Indent, char LR);

is only accessable to CBinaryTree

and

void ReplaceWith(IBinaryTreeNode* pNode);
void RemoveAtParent(IBinaryTreeNode** pRoot, IBinaryTreeNode* pNewChild);
IBinaryTreeNode* FindRightmost();

IBinaryTreeNode* m_pParent;
IBinaryTreeNode* m_pLeft;
IBinaryTreeNode* m_pRight;

is private to the IBinaryTreeNode class.

Please post your suggestion for this class design
Thanks.

[blackcoder41]

Uhm not sure about this http://www.cprogramming.com/tutorial/lesson18.html

[rince]

That works, but doesnt hide the internal implementation of the tree node, like I want to.

[Galik]

I don't think you can get the kind of access control that you are after.

As far as I can see the best you can do is to make CBinaryTree a friend class of IBinaryTreeNode which will give it full access.

[rince]

yeah, thats what the current implementation does. i guess CBinaryTree and IBinaryTreeNode as so strongly coupled that there is no harm in giving CBinaryTree full access even though some of the IBinaryTreeNode member functions should not be accessed by it.

[Galik]

I actually had a brainwave on how you could do this. But, to be honest, I think its a bit extreme ;o)

class CBinaryTree;
class IBinaryTreeNode;

struct node_data
{
	friend class IBinaryTreeNode;
private:
	IBinaryTreeNode* m_pParent;
	IBinaryTreeNode* m_pLeft;
	IBinaryTreeNode* m_pRight;
};

class IBinaryTreeNode
{
	friend class CBinaryTree;
public:
	IBinaryTreeNode();
	virtual int GetKey() = 0;

private:
	void Add(IBinaryTreeNode* pNode);
	void Remove(IBinaryTreeNode** pRoot);
	void DebugDraw(int Indent, char LR);

	void ReplaceWith(IBinaryTreeNode* pNode);
	void RemoveAtParent(IBinaryTreeNode** pRoot, IBinaryTreeNode* pNewChild);
	IBinaryTreeNode* FindRightmost();

	node_data data; // Hidden implementation

	void func()
	{
		data.m_pLeft = 0; // OKAY
	}
};

class CBinaryTree
{
public:
	CBinaryTree();
	void AddNode(IBinaryTreeNode *pNode);
	void RemoveNode(IBinaryTreeNode *pNode);

	void DebugDrawTree();
	void DebugDrawAscending();

	void func()
	{
		m_pRoot->data.m_pRight = 0; // ERROR
	}

private:
	IBinaryTreeNode* m_pRoot;
};

[Galik]

Perhaps a better way would be to use an inner class like this:

class CBinaryTree;
class IBinaryTreeNode;

struct node_data
{
	friend class IBinaryTreeNode;
private:
	IBinaryTreeNode* m_pParent;
	IBinaryTreeNode* m_pLeft;
	IBinaryTreeNode* m_pRight;
};

class IBinaryTreeNode
{
	friend class CBinaryTree;
public:
	IBinaryTreeNode();
	virtual int GetKey() = 0;

private:
	void Add(IBinaryTreeNode* pNode);
	void Remove(IBinaryTreeNode** pRoot);
	void DebugDraw(int Indent, char LR);

	class implementation
	{
		friend class IBinaryTreeNode;
		void ReplaceWith(IBinaryTreeNode* pNode);
		void RemoveAtParent(IBinaryTreeNode** pRoot, IBinaryTreeNode* pNewChild);
		IBinaryTreeNode* FindRightmost();

		void func()
		{
			m_pParent->Add(0);
		}

		IBinaryTreeNode* m_pParent;
		IBinaryTreeNode* m_pLeft;
		IBinaryTreeNode* m_pRight;
	} imp;

	void func()
	{
		imp.ReplaceWith(this); // OKAY
	}
};

class CBinaryTree
{
public:
	CBinaryTree();
	void AddNode(IBinaryTreeNode *pNode);
	void RemoveNode(IBinaryTreeNode *pNode);

	void DebugDrawTree();
	void DebugDrawAscending();

	void func()
	{
		m_pRoot->imp.m_pRight = 0; // ERROR
	}

private:
	IBinaryTreeNode* m_pRoot;
};

But I still think its overkill... hehe

[rince]

hhmm, actually thats a pretty good solution, thanks.
but like you said a bit of an overkill. and also abuses the friend keyword which strictly speaking is not oop.