Thread: copy constructor doesn't invoke

Hi,
My RedBlackTree and RBNode classes has a static instance that represents the Nil of the rbtree (both point to the same node).
I encountered a bug during some tests and it seems that the nil instance is being modified during delete from rbtree (I think).
However, I thought that maybe overloading the copy constructor and making sure that the node is nil creating a new instance will solve the problem.
But the copy constructor doesn't run /:

The base class of BookNode is RBNode.
Here is the relevant definitions:

Code:

RBNode(const RBNode& other)
{
	other.CopyTo(this);
}

void RBNode::CopyTo(RBNode* node) const
{
	node->left = this->left;
	node->right = this->right;
	node->parent = this->parent;
	node->color = this->color;
}

BookNode(const BookNode& other) 
{
	other.CopyTo(this);
}

void BookNode::CopyTo(RBNode* node) const
{
	if (node == RBNode::myNil)
		node = new RBNode();

	RBNode::CopyTo(node);
	BookNode* the_node = (BookNode*)node;
	the_node->book_code = this->book_code;
	the_node->customer_pointer = this->customer_pointer;
	the_node->book_p2p = this->book_p2p;
}

I remind you that it just doesn't get to the lines above, probably the default conpy constructor is being invoked instead (or maybe not and it just changes pointers? @_@)

Thank you! (:

BookNode::CopyTo only allocates an RBNode, but you then cast it to a BookNode and try and write other stuff to it. That will likely crash because it isn't a BookNode and does not have a BookNode's extra fields.

Why does the CopyTo function exist at all? Why not just put that code into the copy-constructor?

Are you aware that you can just use NULL instead of a static nil-node in an RB-Tree?

You are right, my bad I sure have to allocate a BookNode there and it's in a another method since at start I haven't even declared my own cc and used it in rbt-Delete. At first glance it seems that I can just put the copyTo content in the cc but notice that I will have to exchange "node" with "this" which I think isn't allowed since "this" is const.
The nil has a color member that is set to black which is essential for the logic of red black trees.
However, point is, the cc is not used in the program, the assignment sign (=) between to nodes doesn't execute the cc...

Generally, the rule of the Big Three says that if you have something where you need to implement either a copy constructor, or an assignment operator, or a destructor, you probably need to implement all three.

Oh good to know, that got me confused.
The whole virtual assignment operator overloading thing seems confusing (since the return type is diffrent), can someone shoot a quick example on how to do that?

Thanks.

Originally Posted by gavra

The nil has a color member that is set to black which is essential for the logic of red black trees.

The alternative is to just treat NULL as black. I assure you it's perfectly common to use NULL rather than a static nil-node, but either will work.

Is your CopyTo method marked virtual?

Yeah I guess it's better, I'll have to make some modifications later.
I think I still need to fix that overloading problem.
Yes (in the base class "RBNode").

In RBNode:

Code:

virtual RBNode & operator=(const RBNode & rhs);

RBNode & RBNode::operator=(const RBNode & rhs)
{
	this->left = rhs.left;
	this->right = rhs.right;
	this->parent = rhs.parent;
	this->color = rhs.color;
	
	return *this;
}

I put a breakpoint there and it doesn't stop. It doesn't get there @_@
any ideas?

and yes I am sure there is an assignment in my code, for example, here:

Code:

RBNode* RedBlackTree::Delete(RBNode* z)
{
	RBNode *y, *x;

	if (z->left == this->nil || z->right == this->nil)
		y = z;
	else
		y = TreeSuccessor(z);
	if (y->left != this->nil)
		x = y->left;
	else
		x = y->right;
	x->parent = y->parent;
	if (y->parent == this->nil)
	{
		this->root = x;
	}
	else if (y == y->parent->left)
	{
		y->parent->left = x;
	}
	else
		y->parent->right = x;
	if (y != z)
	{
		y->CopyTo(z);
	}
	if (y->color == BLACK)
		this->DeleteFixup(x);
	return y;
}

Even though the pointers reffer to derived classes (such as BookNode) it still has to invoke the RBNode:perator = since the refferences declared as RBNode... (right?)

All I see is that you are assigning pointers, so of course the assignment operator isn't going to get invoked. You need to separate pointer and pointee.
I don't think a virtual assignment operator is going to help--or make any sense here, though. I can't outright think of a scenario where I'd want a virtual assignment operator.

Originally Posted by Elysia

All I see is that you are assigning pointers, so of course the assignment operator isn't going to get invoked. You need to separate pointer and pointee.
I don't think a virtual assignment operator is going to help--or make any sense here, though. I can't outright think of a scenario where I'd want a virtual assignment operator.

Yes, I read online and in order to overload asignment operator of pointers I'll need to wrap my class (it does make some sense). However, I think it is better to use it as a method (replacing '=' with a method call).
I'll try to make the changes needed to exchange the nil with NULL and see how it goes. I hope I won't need to replace the assignment with a method call.

You are missing the point.
You are exchanging pointers. Pointers have builtin assignment operator that work this way by design, because you are simply moving around addresses, and not objects.
If you want to invoke the assignment operator, you have to dereference the pointers first. But in a tree, you really shouldn't be doing that. That's often a sign of poor design (in trees).

Originally Posted by Elysia

You are missing the point.
You are exchanging pointers. Pointers have builtin assignment operator that work this way by design, because you are simply moving around addresses, and not objects.
If you want to invoke the assignment operator, you have to dereference the pointers first. But in a tree, you really shouldn't be doing that. That's often a sign of poor design (in trees).

Actually, that's a very good point. Why would you ever be copying these nodes? Is it for copying the whole tree?

Ideally BookNode would not derive from RBNode. Either RBNode would contain a pointer to the Book data (which would no longer have "Node" in its type name), or RBNode would take Book as a template parameter and copy just the Book in, by value.

Originally Posted by iMalc

Ideally BookNode would not derive from RBNode.

Agree there - go with composition, not inheritance. Think about how standard containers operate (e.g. std::map<>, which actually is usually implemented as a red-black or other self-balancing binary tree). You don't derive your data class from the container class; rather, you give instances of the data class to the container.

Originally Posted by Elysia

You are missing the point.
You are exchanging pointers. Pointers have builtin assignment operator that work this way by design, because you are simply moving around addresses, and not objects.
If you want to invoke the assignment operator, you have to dereference the pointers first. But in a tree, you really shouldn't be doing that. That's often a sign of poor design (in trees).

Originally Posted by iMalc

Actually, that's a very good point. Why would you ever be copying these nodes? Is it for copying the whole tree?

Ideally BookNode would not derive from RBNode. Either RBNode would contain a pointer to the Book data (which would no longer have "Node" in its type name), or RBNode would take Book as a template parameter and copy just the Book in, by value.

Originally Posted by Cat

Agree there - go with composition, not inheritance. Think about how standard containers operate (e.g. std::map<>, which actually is usually implemented as a red-black or other self-balancing binary tree). You don't derive your data class from the container class; rather, you give instances of the data class to the container.

First of all, I can't use any "ready for use" structures, the whole assignment idea is I'll implement everything by my self.
About the inheritance, I have been wondering some time what should be the right aproach. Since the course is data structres, I got to a conclusion that design isn't that much of an issue.
However, I don't see any other way here. Pay attention to the fact that I have three rb trees in my program, each with a diffrent node type (CNode for a customer node, BookNode and CountsNode - all that is needed inorder to ensure a logarithmic complexity for every request in the assignment).

About replacing NULL and Nil, I have just noticed that if I use NULL instead of nil, I won't be able to access the right/left/parent and color which I think is needed for the rbtree algorithem to work so I don't see how I can implement it with NULL..(?)

Thank you.