Thread: Tree of different items

Do not worry, I do not copy paste code, I judge it and get inspired!
This code - I have not run it - seems to work, but shouldn't we free what we allocated?

Here is the code with the delete operations. I think it's ok, if not let me know!

Code:

#include <iostream>
#include <vector>
 
typedef std::vector<int> VECTOR;
 
VECTOR nullVector;
 
class Node {
public:
    virtual Node*   getLeft()         = 0;
    virtual Node*   getRight()        = 0;
    virtual void    setLeft(Node* n)  = 0;
    virtual void    setRight(Node* n) = 0;
    virtual VECTOR& vec()             = 0;
    virtual void    print()           = 0;
    virtual void freeTree()           = 0;
};
  
class Inner : public Node {
    Node* pleft;
    Node* pright;
public:
    Inner() : pleft(0), pright(0) { }
    Node*   getLeft()         { return pleft;  }
    Node*   getRight()        { return pright; }
    void    setLeft(Node* n)  { pleft  = n; }
    void    setRight(Node* n) { pright = n; }
    VECTOR& vec()             { return nullVector; } // needs to return something
    void    print();
    void freeTree() {
        if (getLeft())  getLeft()->freeTree();
        if (getRight()) getRight()->freeTree();
        delete this;
    }
};
 
void Inner::print() {
    std::cout << "Inner\n";
    if (getLeft())  getLeft()->print();
    if (getRight()) getRight()->print();
}
  
class Leaf : public Node {
    VECTOR v;
public:
    Node*   getLeft()         { return 0; }
    Node*   getRight()        { return 0; }
    void    setLeft(Node* n)  { }  // unused parameter warning
    void    setRight(Node* n) { }  // ditto
    VECTOR& vec()             { return v; }
    void    print();
    void freeTree() {
        delete this;
    }
};
 
void Leaf::print() {
    for (size_t i = 0; i < v.size(); i++)
        std::cout << v[i] << ' ';
    std::cout << '\n';
}
 
int main() {
    Node* root = new Inner;
 
    root->setLeft(new Inner);
    root->setRight(new Inner);
 
    Node* node = root->getLeft();
 
    node->setLeft(new Leaf);
    node->setRight(new Leaf);
 
    node->getLeft()->vec().push_back(1);
    node->getLeft()->vec().push_back(2);
    node->getLeft()->vec().push_back(3);
 
    node->getRight()->vec().push_back(4);
    node->getRight()->vec().push_back(5);
    node->getRight()->vec().push_back(6);
 
    node = root->getRight();
 
    node->setLeft(new Leaf);
    node->setRight(new Leaf);
 
    node->getLeft()->vec().push_back(7);
    node->getLeft()->vec().push_back(8);
    node->getLeft()->vec().push_back(9);
 
    node->getRight()->vec().push_back(10);
    node->getRight()->vec().push_back(11);
    node->getRight()->vec().push_back(12);
 
    root->print();
 
    root->freeTree();
    return 0;
}

Of course, since we are in an OOP environment, this can be modified more.

Thanks again Canada guy

but shouldn't we free what we allocated?

Good point. Of course, the memory is (or should be) returned to the system when the process terminates anyway, but it's good practice to delete the elements yourself.

I'm not sure if your solution is entirely correct. Can an object safely delete itself?

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

Code:

void DeleteTree(Node *tree) {
    if (!tree) return;
    DeleteTree(tree->getLeft());
    DeleteTree(tree->getRight());
    delete tree;
}

And you need to add a virtual destructor to Node:

Code:

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

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

Code:

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

Yes, I like your delete function more. However, in my code it crashes, even thought it prints what it needs to print. Got to find the bug! Ciao!

But if I do it the way I tried before, it won't crash. It's actually an octree and my functions are these: (they are really dirty at the moment, beware )

Code:

class Pointer {
public:
    virtual Point3d& split()                           = 0;
    virtual const Point3d& split() const = 0;
    virtual Pointer** child() = 0;
    virtual const Pointer** child() const = 0;
    virtual std::vector<int>& relevantH() = 0;
    virtual const std::vector<int>& relevantH() const = 0;
    virtual TYPE type() const = 0;
    virtual void    print()           = 0;
    virtual void freeTree()           = 0;
};

class Node : public Pointer {
    // Private members
    Point3d splitPoint;                  // Split point
    Pointer* childArray[1<<Dimension];   // Pointers to children
public:
    virtual const Point3d& split() const {return splitPoint;}
    virtual Point3d& split() {return splitPoint;}
    virtual Pointer** child() {return childArray;}
    virtual const Pointer** child() const {return (const Pointer**)childArray;}
    virtual std::vector<int>& relevantH() {}
    virtual const std::vector<int>& relevantH() const {}
    virtual TYPE type() const {return TYPE_INNER;}
    void print() {
        if (child()[0])  child()[0]->print();
        std::cout << "Inner\n" << split();
        if (child()[1])  child()[1]->print();
        if (child()[2])  child()[2]->print();
        if (child()[3])  child()[3]->print();
        if (child()[4])  child()[4]->print();
        if (child()[5])  child()[5]->print();
        if (child()[6])  child()[6]->print();
        if (child()[7])  child()[7]->print();
    }
    
    void freeTree() {
        if (child()[0])  child()[0]->freeTree();
        if (child()[1])  child()[1]->freeTree();
        if (child()[2])  child()[2]->freeTree();
        if (child()[3])  child()[3]->freeTree();
        if (child()[4])  child()[4]->freeTree();
        if (child()[5])  child()[5]->freeTree();
        if (child()[6])  child()[6]->freeTree();
        if (child()[7])  child()[7]->freeTree();
        delete this;
    }
};

class Leaf : public Pointer {
    // Private members
    std::vector<int> relevantHalfspaces;        // Relevant halfspaces to leaf
public:
    /**
     * Constructor of Leaf.
     * @param t - size of member vector of leaf
     */
    Leaf(const size_t& t, std::vector<int> relH) : relevantHalfspaces(relH) {
        // In order to avoid multiple re-allocations
        relevantHalfspaces.reserve(t);
        // Use only if compiler supports C+11 features. We reserve space,
        // we do not create 2*V - 4 objects, but if we do not use all the
        // space, it will wait to be allocated, unless we shrink_to_fit.
        // relevantHalfspaces.shrink_to_fit(); <-- This is the line of code.
    }
    virtual const Point3d& split() const {}
    virtual Point3d& split() {}
    virtual Pointer** child() {return 0;}
    virtual const Pointer** child() const {return 0;}
    virtual std::vector<int>& relevantH() {return relevantHalfspaces;}
    virtual const std::vector<int>& relevantH() const {return relevantHalfspaces;}
    virtual TYPE type() const {return TYPE_LEAF;}
    void print() {
        std::cout<<"Leaf\n";
        for( std::vector<int>::const_iterator it = 
                relevantHalfspaces.begin(); it != relevantHalfspaces.end(); ++it)
            std::cout << *it << ' ';
        std::cout << std::endl;
    }
    void freeTree() {
        delete this;
    }
};

is it safe? Does it delete the tree?

Run it on Linux too and it was ok!

I tried to use valgrind, like this:
linux06:/home/users/std10093/splitReduce>% valgrind --tool=memcheck --leak-check=yes run vertices.txt
%: Too many arguments.
linux06:/home/users/std10093/splitReduce>% valgrind --tool=memcheck --leak-check=yes ./run vertices.txt
%: Too many arguments.

I tried like this too
g++ main.cpp valgrind --leak-check=yes run vertices.txt
g++: error: valgrind: No such file or directory
g++: error: unrecognized option '--leak-check=yes'

Hopefully one of the C++ gurus will let us know if it's safe to delete in that way.
I await their pronouncement.

About valgrind, is your program called run? Try this:
valgrind --leak-check=yes progname args...
(memcheck is the default tool)

Me too.

Here you go
valgrind --leak-check=yes run vertices.txt
valgrind: Command not found.

run is the executable and vertices.txt the cmd arg

However, valgrind seems to exist
linux06:/home/users/std10093/splitReduce>locate valgrind
/usr/lib/valgrind
/usr/lib/valgrind/python.supp

>which valgrind
valgrind: Command not found.

I can not install anything, because I connect via putty in the lunix lab of my uni

I emailed the admins. They have told us not to install anything, so I will stick to that order. It won't harm to wait one day or two.
Meanwhile, one can take a look at my code above and tell if this is safe and if deletes all the tree.

We had it, but recently they upgraded the lab and might done something wrong with her.
My university is the best in Greece, when it comes to informatics.

And had make the top 100 some years ago, but this is not our case now. Thanks anyway!