Thread: Tree of different items

I understand how you feel, but the admins said to us not to install anything, so I will feel bad if doing so.

shouldn't we free what we allocated?

O_o

Yes, but the "who" is important: who owns the resource allocated? The owner is responsible for deletion.

In other words, if you create multiple references to the same node, only one reference holder is the owner. If you say to yourself "each node owns its children" and structure your code accordingly chaining a `freeChildren' function as you have is perfectly fine.

You could go for shared ownership, but that is more complicated.

Can an object safely delete itself?

Yes, but care must be taken to ensure that nodes may only be created from `new'.

Consider what happens when you create a `Inner' on the stack and call `freeTree': most likely a crash or anything awful.

In practice, this approach is fine, but again care must be taken to ensure the object is created with `new'; this is usually accomplished by making the constructor `private' and making a factory function a `friend' of the class. (The factory function just forwards construction parameters returning a `new' pointer to the class.)

However, anyone attempting "self deletion" should realize that once `delete' is called the object literally does not exist: once `delete' is called no `virtual' methods, members, or of instance specific aspect of the object may be touched in any way.

This might be safer (a function that's not part of any object)

The example has all the appearance of being safer without being meaningfully safer when the rules of "self deletion" are followed.

Both `freeNode' and `DeleteTree' destroy an object and all children belonging to that object without otherwise touching any reference. Basically, if a reference to an object is used after `delete' operator is used the programmer is at fault for using an invalidated reference. With `DeleteTree' the point of invalidation is, semantically, the point after `DeleteTree' returns, but any references may still be, wrongly, used. A similar situation is true with `freeNode' where the primary difference is the point of invalidation; with `freeNode' the point of invalidation is the `delete' line which basically means even `this' is invalid within `freeNode'.

And you need to add a virtual destructor to Node

Well, certainly, you should have a virtual destructor if you plan on using `delete' polymorphically.

Here though, with destruction already `virtual' from `freeTree', you don't also need a `virtual' destructor. Wthin `freeTree' the exact type of `this' is known from within the overridden virtual method so `delete' will call the correct destructor. However, this is one of the problems with "self deletion" of the form posted: if `freeTree' is not overridden by a class, such as a refinement of `Leaf', `delete' will use the wrong destructor. So, yes, even with this type of "self deletion" the destructor should arguably be `virtual'.

That all said, a better approach is only using `delete' for owned objects and considering `this' as owned by some other object with a `virtual' destructor and appropriate interfaces.

Code:

class Node
{
    // ...
    virtual ~Node()
    {
    }
    // ...
};

class Inner:
    public Node
{
    // ...
    virtual ~Inner()
    {
        freeChildren();
    }
    // ...
    void freeChildren()
    {
        delete mLeft;
        delete mRight;
    }
    // ...
    void releaseChildren()
    {
        mLeft = 0;
        mRight = 0;
    }
    // ...
};

class Tree
{
    // ...
    ~Tree()
    {
        delete mRoot;
    }
    // ...
    Inner * mRoot;
    // ...
};

As you can see, there is no "delete this" in sight, but even still, the destruction of the tree happens recursively by virtue of the chain of ownership: the tree owns the "root" node, which is destroyed as part of the lifetime of a `Tree' object, where the "root" node is responsible for destroying its own owned nodes.

And you can eliminate the "unused parameter" warnings for setLeft and setRight in Leaf like this:

With most compilers it is sufficient to simply not name parameters which are unused:

Code:

void    setLeft(Node*)  {}  // avoid unused parameter warning
void    setRight(Node*) {}

That said, operations on pointers themselves are trivial, and you should use this fact. (Such trivial operations do not raise exceptions.) If we return, partially, to earlier code you had the right idea: the `VECTOR', named ` v', should be an owned reference to an allocated `VECTOR'. With that small change, allocating the storage `VECTOR', the allocation of new nodes may fail, but that is the only point of failure for most tree operations. Many primitive tree operations, such as inserting a new "inner node" node between a "leaf node" and "inner node", may be accomplished by allocating the new, setting the pointers, and swapping the node entirely with an existing node. Because the "swap" can't raise an exception, we have easy "commit or rollback" semantics: an insertion either completes entirely or fails entirely leaving the tree in the same state it was when the attempt to insert was made.

All that said, this is pretty bad way to go about this construct. You have, as it stands, broken polymorphisms with respect to a node, the tree, and multiple trees within the same program. I suggest at least exploring the possibility of just using dumb nodes.

Code:

struct node
{
    node * parent;
    node * left;
    node * right;
    std::vector<Data> * data;
};

This structure isn't fancy, but the tree can easily branch any node: if data is not null you allocate a new branch, swap the `data' pointers, and assign the newly created branch `left' or `right' depending on what kind of tree you are creating.

Soma

Originally Posted by phantomotap

Yes, but care must be taken to ensure that nodes may only be created from `new'.

Consider what happens when you create a `Inner' on the stack and call `freeTree': most likely a crash or anything awful.

In practice, this approach is fine, but again care must be taken to ensure the object is created with `new'; this is usually accomplished by making the constructor `private' and making a factory function a `friend' of the class. (The factory function just forwards construction parameters returning a `new' pointer to the class.)

I am not really sure how I can accomplish this, but I will try..

Originally Posted by phantomotap

Both `freeNode' and `DeleteTree' destroy an object and all children belonging to that object without otherwise touching any reference.

You mean freeTree, I guess.


For some reason, I trust phantomotap, so even though I can not run valgrind, I gained some confidence.

So, yes we need to get rid from the unused parameter warnings.
My Inner class has an object, that I need to get. The Leaf class does not have it.
I had:

Code:

virtual Point3d& split() { return p; }

and then I would do something like this

Code:

root->split().memberFunctionOfPoint3d

By going to this:

Code:

virtual void split(Point3d& )

I can not access the methods like before. Any ideas?

[EDIT]
I have tried many things but none of them worked. Maybe we should find another way to get rid of the unused parameter warning.

phantomotap pointed out (and I should have remembered this) that on most compilers simply leaving out the parameter name is enough to suppress the warning.

Code:

int func(int) { }

If that doesn't work on your compiler then you can do this:

Code:

int func(int x) { (void)x; }

But since you use gcc, the first solution should work and seems better, though it may be less portable (?).

I recommend commenting out the parameter name rather than deleting it outright.

I can not access the methods like before. Any ideas?

O_o

You weren't getting an unused parameter warning from `virtual Point3d& split()' in the first place. If you made the change for that sake, the warning comes elsewhere within your code.

If you are fine chancing it for the sake of syntax, return a pointer:

Code:

virtual Point3d* split(); // ...
// ...
root->split()->memberFunctionOfPoint3d

You could return a reference and use exceptions for an object where `split' would fail to provide a reference, but now you've added needless polymorphisms, exceptions, and sacrificed code readability for a tiny bit of syntax.

I wouldn't recommend such things unless you already know `split' returns a valid reference for a particular object. You can test this in several ways, but all of them leave you querying the type directly or indirectly so why not just do your job and test a pointer for validity on the spot?

Code:

virtual Point3d* split(); // ...
// ...
Whatever * s(root->split());
if(s)
    s->memberFunctionOfPoint3d // ...

Maybe we should find another way to get rid of the unused parameter warning.

You can't chain the methods with the example you posted because you chose to return `void'; the problem has nothing to do with parameters.

If `split' had a parameter, `virtual Point3d& split(int f)', then the omission works fine and without warnings for many compilers:

Code:

Point3d & split
(
    int
)
{
    // ...
}
// ...
root->split(/*whatever*/).memberFunctionOfPoint3d // ...

But since you use gcc, the first solution should work and seems better, though it may be less portable (?).

If you want portable, you will need macros of form:

Code:

#if defined(__GNUC__) /* || defined(others) */
#   define unused(X)
#   define suppress(X)
#else
#   define unused(X) X
#   define suppress(X) (void)X
#endif

void DoSomething
(
    void * unused(fWhatever)
)
{
    suppress(fWhatever);
}

I recommend commenting out the parameter name rather than deleting it outright.

... in defense of "self documentation"?

You can have the function declaration keep the parameter name yet not use it with the definition.

I would even recommend, as it is what I do, not "decorating" the parameter name in the headers if one goes the macro path.

Soma

I agree about readability. As oogabooga's signature says simplicity is the ultimate sophistication (L. da Vinci). The more simple our code is, the more readable it is!
So, I had a really rough time deciding to take or not the approach of polymorphism.
So - of course - I thought about the struct phantomotap suggested before, which was like this:
(D is the dimension in which the code runs, I have used D = 3 for simplicity)

Code:

struct{
    Point3d split;                      // Need this only in inner nodes
    std::vector<int> v;             // Need this only in leaves
    Pointers array[8];               // Need this only in inner nodes
}

So I thought to make them pointers, in order to dynamically allocate - deallocate data, so the struct would be actually something like this:

Code:

struct{
    Point3d* split;                      // Need this only in inner nodes
    std::vector<int>* v;             // Need this only in leaves
    Pointers array[8];                 // Need this only in inner nodes
}

So, the inner nodes, would have the split point and the pointers alive and the vector pointer set to null (a useless pointer per inner node).
As for the leaves, split and array would be useless pointers, 9 in number per leaf.

Imagine now an Octree of one-level depth only:
Number of unused pointers:
1 // vector pointer in root
+ 8 * 9 // 9 unused pointers per leaf
= 73 unused pointers for a tree of only one level.

I want to use as less memory as a programmer of my level can. Moreover, I saw that the readability is affected only in quadtree.h. Readability in implementation file of quadtree did not get affected from the its previous state (that used the struct I have above).
As a result, I decided to go for this approach (even if someone raises some great argument and convince me that I should give up on this approach and turn back to the struct I have above, I will not regret the time I spent on polymorphism (why is this red-highlighted by the spelling check? Did I spell it wrong?), because it really refreshed my knowledge. (thanks oogabooga)
I have a question however:

Code:

virtual ~Node() { }  // does nothing, but necessary

Why is this necessary?

As for the warning: no return statement in function returning non-void, I decided to go with the approach of returning a pointer, rather than a reference.
I have enclosed the classes Node, Inner and Leaf in the class of the tree (I made them Inner classes). That way, I do not think that I can have access issues outside the class of the tree.

Do you think using pointers rather than references in the return types can cause problems? The cost is the same I guess.

EDIT:
I also found the std:air, but I do not think I am going to go for this.

Code:

virtual ~Node() { }  // does nothing, but necessary

Why is this necessary?

Node's virtual destructor let's you completely delete Inner objects pointed to by Node* variables. Welcome to inheritance. And polymorphism.

Oh I see. Well I was welcomed in 2011, but I had to write a good C++ project from the summer of the same year.

And whiteflags, I am also interested in the question about having the returning type as a pointer, instead of a reference. Doesn't it have the same cost? Since the function returning the pointer is a public one of the inner class. The inner class is in the private field of the outer class. The outer class provides only two associated public methods, which are the factory functions phantomotap suggested. I can not make the returning pointer a const one, because, I want the private methods of the outer class to be able to modify the object that the pointer points to.

Code:

/**
     * Factory function for an inner node.
     * @return - pointer to the new inner node
     */
    Inner* createInner() { 
        Inner* temp = new Inner;
        if(temp) return temp; // Check if allocation succeeded
        else std::cout << "Error in createInner" << std::endl;
        return 0;
    }
    
    /**
     * Factory function for a leaf.
     * @return - pointer to the new leaf
     */
    Leaf* createLeaf() { 
        Leaf* temp = new Leaf;
        if(temp) return temp; // Check if allocation succeeded
        else std::cout << "Error in createLeaf" << std::endl;
        return 0;
    }

I am referring to the get functions of the Inner and Leaf classes.

Whiteflags has a point and I am going to do some changes. I can post it when I am done John, if you like of course.
In order to make the factory functions work, I had to do the outer class friend of the two inner classes (Inner and Leaf). That way I have access. However this will affect the readability a bit in the .cpp file, because of the static castings I am going to do.
As a consequence, all the get functions are not needed anymore. Moreover, the "getType" function is also unesescairy (whiteflags had told a mnemonic rule to remember the spelling, but I forgot, both the rule and the spelling :P ), since I can use dynamic_cast.

I wanted to do something like this:

Code:

typedef (static_cast<const Inner*>) (cast);

but did not work...