Troubles with members override rules

[denis90]

First of all, this is my first post here, hello there folks!

I'm designing some simple bin_tree classes as exercise ( normal bin tree, red black bin tree ); for the base class (normal bin tree) I'm using a class Tnode<> as node type, anyway at first look its behavior would be better compared to a struct rather then a class (that is, it just has some readable/writable member):

template<class T> struct Tnode {
	Tnode<T>* right;
	Tnode<T>* left;
	Tnode<T>* father;
	T* data;
	int index;
};

This is not enough, I need Tnode to get some polimorphic behavior, in other words I need to modify the type of members like Tnode<>::right in derived classes to avoid dynamic_casting, hence I transformed the fine and clear struct in this sicky class :

template<class T> class Tnode {
public:
	Tnode() :
		right(0), left(0), father(0), data(0), index(0) {}
	virtual ~Tnode() { delete data; }
	virtual Tnode<T>* get_right() { return right; }
	virtual Tnode<T>* get_left() { return left; }
	virtual Tnode<T>* get_parent() { return father; }
	T& get_data();
        int get_index() { return index; }
	virtual void set_right(Tnode<T>* node) { right = node; }
	virtual void set_left(Tnode<T>* node) { left = node; }
	virtual void set_parent(Tnode<T>* node) { father = node; }
	void set_index(int indx) { index = indx; }
	void write_data(const T& obj) { delete data; data = new T(obj); }
private:
	Tnode<T>* right;
	Tnode<T>* left;
	Tnode<T>* father;
	T* data;
	int index;
};

Now I need to build a derived class and make it usable with red_black_trees ( that is, just add the notion of color ) :

template<class T> class Rbtnode : public Tnode<T> {
public:
	enum NodeColor { red, black };
	Rbtnode() : right(0), left(0), father(0), color(red) {}
	virtual ~Rbtnode() {}
	virtual Rbtnode<T>* get_right() { return right; }
	virtual Rbtnode<T>* get_left() { return left; }
	virtual Rbtnode<T>* get_parent() { return father; }
	NodeColor get_color() { return color; }
	virtual void set_right(Tnode<T>* node) { right = dynamic_cast<Rbtnode<T>* >(node); }
	virtual void set_left(Tnode<T>* node) { left = dynamic_cast<Rbtnode<T>* >(node); }
	virtual void set_parent(Tnode<T>* node) { father = dynamic_cast<Rbtnode<T>* >(node); }
	void set_color(NodeColor cc) { color = cc; }
private:
	Rbtnode<T>* right;
	Rbtnode<T>* left;
	Rbtnode<T>* father;
	NodeColor color;
};

As you can see the get_something() functions don't need casting on usage since they already return a Rbtnode<T>* ( instead of a Tnode<T>* ).
Anyway I can't do the same with set_something() functions since declaring something like this :

virtual void set_right(Rbtnode<T>* node) { right = node; }

Would not override the base-class method set_right().

Is there another way to solve my problem without having to whatever_casting ?

Thanks.

[Disch]

polymorphism might not be the answer here, as least not for some of this. Instead, I'd just change the Tnode template a bit

template <typename T , typename ndT>
class Tnode
{
public:
  ndT* get_left() { return left; }
  ndT* get_right() { return right; }  // etc

protected:  // probably not private, since you want
           // your derived classes to have access
  ndT* right;
  ndT* left;
  ndT* father;
  T* data;
};

//--------------------------

template <typename T>
class Rbtnode : public Tnode< T, Rbtnode<T> >
{
public:  // no need to override get_left, etc because its inherited
  // also no need for virtual anything except for maybe a virtual dtor

  // instead, only need to include stuff that's unique to Rbtnode:
  enum NodeColor { red, black };
  NodeColor get_color() { return color; }

protected:
  NodeColor color;
      // no need to include other node pointers because they're inherited
};

[writetonsharma]

will you mind if i say this:

template<class T> class Tnode {
public:
	Tnode() :
		right(0), left(0), father(0), data(0), index(0) {}
	virtual ~Tnode() { delete data; }
	virtual Tnode<T>* get_right() { return right; }
	virtual Tnode<T>* get_left() { return left; }
	virtual Tnode<T>* get_parent() { return father; }
	T& get_data();
        int get_index() { return index; }
	virtual void set_right(Tnode<T>* node) { right = node; }
	virtual void set_left(Tnode<T>* node) { left = node; }
	virtual void set_parent(Tnode<T>* node) { father = node; }
	void set_index(int indx) { index = indx; }
	void write_data(const T& obj) { delete data; data = new T(obj); }
protected:
	Tnode<T>* right;
	Tnode<T>* left;
	Tnode<T>* father;
	T* data;
	int index;
};

template<class T> class Rbtnode : public Tnode<T> {
public:
	enum NodeColor { red, black };
//	Rbtnode() : right(0), left(0), father(0), color(red) {}
	virtual ~Rbtnode() {}
//	virtual Rbtnode<T>* get_right() { return right; }
//	virtual Rbtnode<T>* get_left() { return left; }
//	virtual Rbtnode<T>* get_parent() { return father; }
	NodeColor get_color() { return color; }
//	virtual void set_right(Tnode<T>* node) { right = dynamic_cast<Rbtnode<T>* >(node); }
//	virtual void set_left(Tnode<T>* node) { left = dynamic_cast<Rbtnode<T>* >(node); }
//	virtual void set_parent(Tnode<T>* node) { father = dynamic_cast<Rbtnode<T>* >(node); }
	void set_color(NodeColor cc) { color = cc; }
private:
	//Rbtnode<T>* right;
	//Rbtnode<T>* left;
	//Rbtnode<T>* father;
	NodeColor color;
};

your derived class is specialized class, why are you including right, left, father!!
second, even if the pointers are of derived class in set_something, it wont harm to put them in base pointer.
that will solve.. i dont know if you agree.

[writetonsharma]

Actually this is what Disch is trying to say..

am i correct Disch??

[Disch]

Yeah that was half of it. The other half was to make the node type part of the template... so Tnode::get_left() returns type Rbtnode<T>* instead of Tnode<T>*. This gets rid of the unwanted casting scenario.

[denis90]

Thanks for the answers.

@ writetonsharma : I totally agree, redefining data in a specialization is not that nice, anyway I also don't want to receive generic Tnode<T>*s from get_something functions since in that way I would have to cast the pointer from user-code ( the BinaryTree class implementation ) to get a Rbtnode<T>*, your idea got me on this way:

template<class T> class Tnode {
public:
	Tnode() :
		right(0), left(0), father(0), data(0), index(0) {}
	virtual ~Tnode() { delete data; }
	virtual Tnode<T>* get_right() { return right; }
	virtual Tnode<T>* get_left() { return left; }
	virtual Tnode<T>* get_parent() { return father; }
	T& get_data();
        int get_index() { return index; }
	void set_right(Tnode<T>* node) { right = node; }
	void set_left(Tnode<T>* node) { left = node; }
	void set_parent(Tnode<T>* node) { father = node; }
	void set_index(int indx) { index = indx; }
	void write_data(const T& obj) { delete data; data = new T(obj); }
protected:
	Tnode<T>* right;
	Tnode<T>* left;
	Tnode<T>* father;
	T* data;
	int index;
};

template<class T> class Rbtnode : public Tnode<T> {
public:
	enum NodeColor { red, black };
	Rbtnode() : color(red) {}
	virtual ~Rbtnode() {}
	virtual Rbtnode<T>* get_right() { return dynamic_cast<Rbtnode<T>* >(Tnode<T>::get_right()); }
	virtual Rbtnode<T>* get_left() { return dynamic_cast<Rbtnode<T>* >(Tnode<T>::get_left()); }
	virtual Rbtnode<T>* get_parent() { return dynamic_cast<Rbtnode<T>* >(Tnode<T>::get_parent()); }
	NodeColor get_color() { return color; }
	void set_color(NodeColor cc) { color = cc; }
private:
	NodeColor color;
};

Which is surely better than my first one.




@Disch: your solution looks really nice and clear, with this trick I could get back to the struct idea, don't have to whatever_casting anymore, and remove all the get and set methods; anyway, as far as I understand, there must be a base class, from where to derive Tnode<> :

template<class T, class ndT> struct Base_Tnode {
	ndT* right;
	ndT* left;
	ndT* father;
	T* data;
	int index;
};

template<class T> struct Tnode : Base_Tnode<T, Tnode<T> > { };

template<class T> struct Rbtnode : Base_Tnode<T, Rbtnode<T> > {
	enum NodeColor { red, black };
	Rbtnode() : color(red) {}
	NodeColor color;
};

But in this way Rbtnode is not anymore a Tnode and hence cannot used where a Tnode can be.
I'd like to implement this solution, but i got blocked at this point.

EDIT : typo.

[writetonsharma]

Disch:

yup.. i missed on that.. that should be there.

denis90:

making a base class only of data with no getter/setter or any pure virtual is not a good idea.. what do you think??


so whats the final solution guys?? because we all are goin in the same direction but still a solution is not reached!!!

[Disch]

If the goal here is to have two seperate types of nodes (Tnode and Rbtnode) that share a common base, one way to go would be to have the shared base read-only. IE: 'get' functions can be polymorphed into derived types, but 'set' functions cannot be (at least not without killing type safety).

Breakdown:

template <typename T> class NodeBase
{
public:
  NodeBase() : left(0), right(0), father(0), data(0), index(0) { }

  virtual NodeBase<T>* get_left() = 0;  // note:  pure virtual
  virtual NodeBase<T>* get_right() = 0;
  virtual NodeBase<T>* get_father() = 0;

  T& get_data() { return *data; }

  // note:  no 'set' methods for the nodes, but you can have set methods
  //   for data/index
  void set_data(const T& d) { /*add code here*/ }
  void set_index(int i) { index = i; }

protected:
  NodeBase<T>* left;
  NodeBase<T>* right;
  NodeBase<T>* father;
  T* data;
  int index;
};

//-------------------------------------------

template <typename T> class Tnode
{
public:
  // polymorph get functions
  virtual Tnode<T>* get_left() { return static_cast< Tnode<T>* >(left); }
    // same for get_right, get_father

  // implement set functions
  void set_left(TNode<T>* l) { left = l; }
    // same for set_right, set_father
};

// do same for Rbtnode 

You can polymorph the 'get' functions for these to have derived classes return a derived type. IE: Tnode can return a Tnode* even though the original function is declared as NodeBase*. Note however that since (in this example) NodeBase contains 'NodeBase*' for nodes, Tnode's get functions need to downcast with static_cast (you could use dynamic_cast, too, but would be more expensive, and unnecessary if you guarantee only Tnode*s can be added to another Tnode.

--------------------------------------------

Set functions can be done in a similar manner, but you can't have a one-size-fits-all version in the base class. For example, consider the following situation:

template <typename T> class NodeBase
{
 ...
  void set_left(NodeBase<T>* l) { left = l; }
};

void somefunc()
{
  Tnode* tree = GetTreeFromSomewhere();
  NodeBase* foo = tree;  // upcast to generic base class

  Rbnode* bar = GetRBNode();

  foo->set_left( bar );  // no compiler error, 'bar' is indeed a NodeBase*

  Tnode* nd = foo->get_left();  // no compiler error, but your program explodes! (bad cast)
}

The above code (what it sounds like you're trying to accomplish) cannot be [easily] done for this very reason.

Because a generic base class 'set' implementation would accept any generic node, there's no type checks to ensure that the node is the right type. In this example we "successfully" added an Rbtnode to a Tnode tree -- so when Tnode's get_left function tries to cast the given NodeBase pointer to a Tnode pointer, you get [quietly] hosed. Very, very bad.

The alternative is to derive 'set' methods, but do type checking with dynamic_cast to ensure the right node is being added:

template <typename T> class NodeBase
{
   ...
  virtual void set_left(NodeBase<T>* l) = 0;  // again, pure virtual
};


template <typename T> class Tnode
{
   ...
  virtual void set_left(NodeBase<T>* l)
  {
    left = dynamic_cast< Tnode<T>* >(l);  // MUST be dynamic_cast, static_cast is no good here
  }
};

If we try the foo/bar example thing with this setup, the dynamic_cast would fail, resulting in left = 0;. This might be bad if you expect the tree to clean up the nodes (this bad cast might lead to a memory leak if you don't check whether or not it was successful). So you might want to go with the "louder" version of dynamic_cast instead:

  virtual void set_left(NodeBase<T>* l)
  {
    left = &(dynamic_cast< Tnode<T>& >(*l)); // dynamic_cast to a reference
  }

Same end result if the cast is successful, but here, if the cast is unsuccessful, instead of quietly returning null leading to a potential memory leak, dynamic_cast will throw an exception.


This will let you have both get/set functions available with just a parent 'NodeBase' class pointer. The downside is you need to polymorph all 6 get/set functions for each derived class (extra typing -- but not much of a performance hit). Plus as you can see, casting is still a necessity, however it can all remain inside the classes.

It's also worth mentioning that dynamic_cast requires runtime checks to ensure the type is really what you're casting it to, and therefore it's a little slower. Consider the following:

Rbtnode* tree = GetRBTree();
Rbtnode* foo = GetNode();

tree->set_left( foo ); // <--- unnecessary dynamic_cast, we already know the type is correct 

To work around that, you can have two versions of the set functions in your class. A virtual one which polymorphs the parent class (downcasts with dynamic_cast), and a non-virtual one which takes a specific type (no need to dynamic_cast):

// in class 'Rbtnode'

  virtual void set_left(NodeBase<T>* l)
  {
    // do dynamic_cast here
  }

  void set_left(Rbtnode<T>* l)
  {
    left = l;  // no need to dynamic_cast, type is already known to be legit
  }

[denis90]

The only-when-needed dynamic_cast<> solution proposed by Disch seems to me as the most clear.

In fact I didn't even know about the exception thrown by dynamic_cast<> when failing on cast with a reference as target type.

I'm marking this as solved, thank you all guys !