C++

Forum

 
Hierarchy design

denis90 (30)
Hi guys,
I have to build a GRbTree class ( that is, a red_black binary tree with a graphical interface, maybe with Gtkmm ).
At this moment I have already done some other binary tree classes I'd like to reuse, then here is my current simple hierarchy:
- SimpleTree ( this is a simple, concrete implementation of a binary tree )
- RbTree ( this is derived from SimpleTree, it's a red_black self-balanced tree )
For these to work there's also need of some Node classes ( with members like left, right etc. ). Since RbTree must use some of the public and protected methods of SimpleTree, which require the argument to be a SimpleNode, the node used by RbTree ( RbNode ) must also be a SimpleNode; in other words RbNode must be public derived from SimpleNode :
- SimpleNode ( this is the node used by SimpleTree )
- RbNode ( this is derived from SimpleNode, adding up the notion of color )

Well, now here is how, in this way, the Node classes would look like :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
class SimpleNode {
public:
	/* ... */
	virtual SimpleNode& get_left() const { /* ... */ }
	virtual SimpleNode& get_right() const { /* ... */ }
	virtual SimpleNode& get_parent() const { /* ... */ }

	virtual void set_left(SimpleNode& lc) { /* ... */ }
	virtual void set_right(SimpleNode& rc) { /* ... */ }
	virtual void set_parent(SimpleNode& father) { /* ... */ }

private:
	SimpleNode* parent;
	SimpleNode* left;
	SimpleNode* right;
	some_type* data;
	int index;
};


class RbNode : public SimpleNode {
public:
	/* ... */
	virtual RbNode& get_left() const 
		{ return static_cast<RbNode& >(SimpleNode::get_left()); }
	virtual RbNode& get_right() const 
		{ return static_cast<RbNode& >(SimpleNode::get_right()); }
	virtual RbNode& get_parent() const 
		{ return static_cast<RbNode& >(SimpleNode::get_parent()); }

	virtual void set_left(SimpleNode& lc) 
		{ SimpleNode::set_left(dynamic_cast<RbNode& >(lc)); }
	virtual void set_right(SimpleNode& rc) 
		{ SimpleNode::set_right(dynamic_cast<RbNode& >(rc)); }
	virtual void set_parent(SimpleNode& father) 
		{ SimpleNode::set_parent(dynamic_cast<RbNode& >(father)); }
	
	virtual void set_left(RbNode& lc) 
		{ SimpleNode::set_left(lc); }
	virtual void set_right(RbNode& rc) 
		{ SimpleNode::set_right(rc); }
	virtual void set_parent(RbNode& father) 
		{ SimpleNode::set_parent(father); }

private:
	NodeColor color;
};


As you can see, in the derived class there are 2 collections of set_something functions. The first one is overriding the set inherited from the base class and checking for bad arguments by dynamic_cast<> since is not possible to set a SimpleNode as parent or whatever of a RbNode.
Also, the get_something() methods need a static_cast<>, since nodes are stored in the base class as pointers to SimpleNodes, but surely the true types are RbNodes ( a tree is build up with the same type of nodes ).

Here is how the Tree classes would look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
class SimpleTree {
public:
	/* ... */

protected:
	virtual SimpleNode* make_node() 
            { return new SimpleNode; }
	/* ... */
	virtual void set_root(SimpleNode& nroot) 
            { root = &nroot; }
	virtual void set_node(SimpleNode& node) 
            { nodes[node.get_index()] = &node; }

private:
	/* ... */
	SimpleNode* root;
	std::vector<SimpleNode*> nodes;
};

class RbTree : public SimpleTree {
public:
	/* ... */
protected:
	virtual RbNode<T>* make_node() 
            { return new RbNode<T>; }
	/* ... */
	virtual void set_root(SimpleNode<T1>& nroot) 
            { root = &dynamic_cast<RbNode<T1>& >(nroot); }
	virtual void set_root(RbNode<T1>& nroot) 
            { root = &nroot; }
	virtual void set_node(SimpleNode<T1>& node) 
            { nodes[node.get_index()] = &dynamic_cast<RbNode<T1>& >(node); }
	virtual void set_node(SimpleNode<T1>& node) 
            { nodes[node.get_index()] = &node; }
	/* ... */
private:
	/* ... */
};


Here we have the same as before, 2 collections of set_something() functions for the previously exposed reasons.
The make_node() method is something like a "virtual constructor" and I'll make an example on how it's used in my case:
Let RbTree have a insert() method, let also SimpleTree have a insert() method, as you know the first step of the insertion of a node in a RbTree is done in the same way as in a SimpleTree, then RbTree::insert() will first call SimpleTree::insert() and then do something else.
In this way SimpleTree::insert() will create a node and attach it somewhere on the tree, but, as told before, "a tree is build up with the same type of nodes" and hence insert() is designed to call the virtual method make_node() which will create the right type of node ( RbNode in this case ) instead of make something like "new SimpleNode".

This workaround works quite well while handling 2 classes, but it becomes critical with 3+ classes, check it out:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
class GRbNode : public RbNode, public Gtk::DrawingArea {
public:
	/* ... */
	virtual GRbNode& get_left() const 
		{ return static_cast<GRbNode& >(RbNode::get_left()); }
	virtual GRbNode& get_right() const 
		{ return static_cast<GRbNode& >(RbNode::get_right()); }
	virtual GRbNode& get_parent() const 
		{ return static_cast<GRbNode& >(RbNode::get_parent()); }

	virtual void set_left(SimpleNode& lc)
		{ RbNode::set_left(dynamic_cast<GRbNode& >(lc)); }
	virtual void set_right(SimpleNode& rc)
		{ RbNode::set_right(dynamic_cast<GRbNode& >(rc)); }
	virtual void set_parent(SimpleNode& father) 
		{ RbNode::set_parent(dynamic_cast<GRbNode& >(father)); }

	virtual void set_left(RbNode& lc) 
		{ RbNode::set_left(dynamic_cast<GRbNode& >(lc)); }
	virtual void set_right(RbNode& rc) 
		{ RbNode::set_right(dynamic_cast<GRbNode& >(rc)); }
	virtual void set_parent(RbNode& father) 
		{ RbNode::set_parent(dynamic_cast<GRbNode& >(father)); }
	
	virtual void set_left(GRbNode& lc) 
		{ RbNode::set_left(lc); }
	virtual void set_right(GRbNode& rc) 
		{ RbNode::set_right(rc); }
	virtual void set_parent(GRbNode& father) 
		{ RbNode::set_parent(father); }

private:
	/* ... */
}


This is painful, 3 collections of set_something() functions !

For this reason I decided to seek out another solution, this is the idea: there is a base abstract class BaseTree which provide the common interface, all the Tree classes are derived from BaseTree and there's not anymore the Node hierarchy.
This would be the BaseTree class :

1
2
3
4
5
6
7
8
9
10
 
class BaseTree {
public:
	virtual int search(const some_type&) =0;
	virtual const some_type& get_data(int) =0;
	virtual void destroy() =0;
	virtual bool is_empty() =0;
	virtual int store(const some_type&) =0;
	virtual void remove(int) =0;
	virtual void print() =0;
};


Then I wouldn't require whatever_cast<> anymore, since all the 3 classes are independent each other, but, instead, I wouldn't be able, for example, to use the SimpleTree::insert() method from RbTree, meaning that I will need to copy-paste the insert() method from SimpleTree to RbTree ( at most changing its argument from SimpleTree to RbTree ), with some waste of memory.

I'm asking:
What of these approach is better ?
Is there another way to solve this problem ?

Thanks.

EDIT : typo.
Last edited on
jsmith (5804)
FWIW, inheritance is usually used to go from something generic to something more specific. In your first example, you are going the reverse: an rb tree is more general than a binary tree since a binary tree is implementable with an rb tree.

However, a GrbNode is NOT a GTK drawing area. To me the object hierarchy does not make sense to derive a node from a drawing area.
denis90 (30)
Hi jsmith,
The idea was that a SimpleTree is more general than a RbTree since for the user they behave in the same way, but a RbTree is also auto-balanced, what do you think about ?

Well, I derived GRbTree from Gtk::DrawingArea since I'd like to have a tree class which is able to print its representation in a graphical dialog ( in this case, Gtk::DrawingArea ) but at the same time the user can use it as it did with a normal RbTree ( same interface ).
I'd like to make something like this ( is built in java, but the idea is the same ) : http://gauss.ececs.uc.edu/RedBlack/redblack.html
Should I detach the Gtk::DrawingArea from the GRbTree ?

Thanks.
jsmith (5804)
So my question is then: what, exactly, is a SimpleTree? Is it an abstract class or a concrete thing? (Just trying to understand whether or not a SimpleTree is more general than an RbTree. I want to doubt it only because the STL uses rbtrees as its underlying data structure for lists, maps, etc.)

I would detach DrawingArea from GRbTree.
denis90 (30)
SimpleTree is a concrete class, the user interface is the same in SimpleTree and RbTree, the only thing which makes these different is the implementation, RbTree also uses some common methods from SimpleTree ( now I understand that, maybe, this is not a nice logical approach although let me to save some memory ).

So it seems that I should move to the common interface, and derive all trees from there ( therefore wasting some memory ).

But anyway, if I kept on the other way, how would I handle this trouble of exponential-growing functions ?
jsmith (5804)
Not sure there is a way of handling it. I still think the hierarchy is backwards.

What is a SimpleTree? I know what a linked list is. I know what a binary tree is. But what is a SimpleTree?
denis90 (30)
I know, saying SimpleTree is kinda ambiguous, here it is how SimpleTree looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
template<class T1> class SimpleTree {
public:
	SimpleTree() : root(0) {}
	virtual ~SimpleTree() {}

	enum { NOT_FOUND = -10, ALREADY_EXIST = -9 };

	virtual int search(const T1&);
	virtual const T1& get_data(int);
	virtual void destroy();
	virtual bool is_empty() { return !root; }

	virtual int store(const T1&);
	virtual void remove(int);
	virtual void print();

protected:
	SimpleNode<T1>* make_node() { return new SimpleNode<T1>; }

	void set_root(SimpleNode<T1>& nroot) { root = &nroot; }
	SimpleNode<T1>& get_root() { return *root; }
	SimpleNode<T1>& get_node(int index) { return *nodes[index]; }
	bool is_error_code(int index) { return index < 0 ? true : false; }

private:
	int search_impl(const T1& obj, SimpleNode<T1>&);
	void destroy_impl(SimpleNode<T1>&);
	int store_impl(const T1& obj, SimpleNode<T1>&);
	void print_impl(SimpleNode<T1>&);
	SimpleNode<T1>* root;
	std::vector<SimpleNode<T1>*> nodes;		// required for indexing.
};


The public interface would be the same for RbTree, as said before, the only thing which makes these different is the implementation.

Topic archived. No new replies allowed.