Base-to-derived class typecast

Question

I have a base class:

class RedBlackTreeNode
{
// Interface is the same as the implementation
public:
    RedBlackTreeNode* left;
    RedBlackTreeNode* right;
    RedBlackTreeNode* parent;
    Color color;
    TreeNodeData* data;

    RedBlackTreeNode():
        left(0),
        right(0),
        parent(0),
        color(Black),
        data(0)
    {
    }
    // This method is to allow dynamic_cast
    virtual void foo()
    {
    }
};

and a derived from it one:

class IndIntRBNode : public RedBlackTreeNode
{
public:
    IndIntRBNode* left;
    IndIntRBNode* right;
    IndIntRBNode* parent;
    IndexedInteger* data;
    IndIntRBNode():
        RedBlackTreeNode(),
        left(0),
        right(0),
        parent(0),
        color(Black),
        data(0)
    {
    }
};

root() and rootHolder are defined in RedBlackTree class:

class RedBlackTree 
{
public:
    RedBlackTreeNode rootHolder;
    RedBlackTreeNode* root()
    {
        return rootHolder.left;
    }
    ...
}

Then I'm trying to typecast:

IndIntRBNode *x, *y, *z;

z = dynamic_cast<IndIntRBNode*>(root());

And "z" just becomes a zero-pointer, which means that typecast failed. So what's wrong with it, how can I fix it to be able to reference "z" as pointer to the IndIntRBNode?

Added: the initialization of the rootHolder.left was some kind of that:

    int n = atoi(line + i);

    tree.clear();
    int j = 0;
    if (n > 100)
    {
        n = 100;        // Maximum 100 nodes
    }
    while (j < n)
    {
        IndexedInteger num(j,j + 10);
        RedBlackTreeNode* node;
        int c = tree.search(&num, tree.root(), &node);
        if (c != 0)
        { // if value is not in the tree
            IndexedInteger* v = new IndexedInteger(num);
            tree.insert(node, v, c);
            ++j;
        }
    }

In the other words, it was initialized on the first iteration of "while" by the "insert" method in such way:

void RedBlackTree::insert(
    RedBlackTreeNode* parentNode,
    TreeNodeData* v,
    // If it's negative, then add as the left son, else as the right
    int compare
)
{
    assert(parentNode != 0 && compare != 0);
    RedBlackTreeNode* x = new RedBlackTreeNode;
    x->data = v;
    x->parent = parentNode;
    // If it's root
    if (parentNode == &rootHolder)
    {
        // Then it must be black
        x->color = Black;
    }
    else
    {
        // Leaf must be red
        x->color = Red;
    }
    if (compare < 0)
    {
        // Insert the node as the left son
        assert(parentNode->left == NULL);
        parentNode->left = x;
    }
    else
    {
        // Insert the node as the right son
        assert(parentNode != &rootHolder && parentNode->right == NULL);
        parentNode->right = x;
    }

    ++numNodes;

    if (x != root())
    {
        rebalanceAfterInsert(x);
    }
}

It actually was the problem: "insert" created the RedBlackTreeNode dinamically, so it couldn't be IndIntRBNode. I really have initialized it wrong, but then how can I derive the base class and not write the whole implementation of it from a scratch just to change the types? Do I really have to override all the "type-relative" methods in the derived class? It seems to be very stupid, I think there should be the other way - something with class deriving and typecasting, isn't it?

Answer 1

Wait .. you have a derived class with a type of the same name as the base class. How does that even compile?

how is rootHolder.left initialised? Because if a dynamic_cast fails then it is not of type IndIntRBNode.

Basically you haven't provided enough code to see hy what you are doing is wrong, but you ARE doing something wrong.

Answer 2

Are you sure that RedBlackTree::rootHolder.left has been initialized?

I think you somewhere initialized IndIntRBNode::left, but when you are accessing RedBlackTree::rootHolder.left you are accessing RedBlackTreeNode::left, which is not the same field.

Answer 3

If I'm reading your code correctly, you are not setting rootHolder.left to a IndIntRBNode pointer at all, but a vanilla RedBlackTreeNode.

Also, you don't need to make up a useless virtual function for polymorphism; just declare the destructor to be virtual and provide an empty implementation. Your use of polymorphism also isn't that great, as the IndIntRBNode members will hide the RedBlackTreeNode members, so they may well point to different things depending on whether you access them through an IndIntRBNode pointer/reference or a RedBlackTreeNode pointer/reference.

Answer 4

Regardless of whatever other flaws your example code may or may not have, it is written in a way that seems to misunderstand how inheritance and casting work. I recommend that you pick up a C++ book of your choosing and read up on it.

In particular, you should know that every object is one and only one type. Once an object has been created it never changes type. Casting a pointer does not convert an object from one type to another, nor does it create a new object of a new type. Casting allows you to work with an existing object in terms of the class type you specify, but only if that object is already of that class, or a class that is derived from it.

At the point where you currently have this line:

z = dynamic_cast<IndIntRBNode*>(root());

try this instead:

RedBlackTreeNode* other_z = root();

If *other_z* is not NULL, then root() is not an IndIntRBNode, and all the dynamic_casting in the world won't turn it into one.