Thread: Tree of different items

  1. #1
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694

    Tree of different items

    I have a tree that will have the root and the inner nodes defined by a structure and the leaves defined by (each one of them) by a std::vector.

    But, take for example a tree two levels deep, with the root and only one inner node and only one child for example.
    The root has the data and the pointers to the next level, but these are pointers to the struct. We descend to the inner node, which has also pointers for a struct. But I need pointers for the vector (which is the leaf).

    Any ideas?

    // Happy the forum is back.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  2. #2
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Would a template help?

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Googling guide me a bit to this solution, but I do not see how I can get by with them. Probably the problem is that I do not know much about them and what I find on the internet is not accurate enough for me!
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #4
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    I think if you used something like

    Code:
    
    struct tree_node {
    
       template_type *data;
    }
    it might work. But I'm unsure. All you'd have to do is redefine the nametype, I think.

  5. #5
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    I am not sure either, so let's wait for other suggestions too and if nothing comes up, I can try it. Thanks John.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    You could try inherited classes:

    Code:
    enum NODETYPE{NODETYPEBASE, NODETYPETREE, NODETYPEVECTOR};
    
    class NODE{                             // base node class
    public:
        NODE * nextnode;
        NODETYPE nodetype;
        NODE(){nextnode = NULL; nodetype = NODETYPEBASE;}
    };
    
    class NODETREE : public NODE {          // tree node class
    public:
        NODE * subnode;                     // ptr to subnode
        NODETREE(){this->nodetype = NODETYPETREE; subnode = NULL;}
    };
    
    class NODEVECTOR : public NODE {        // vector node class
    public:
        std::vector <int> * pvector;        // ptr to vector
        NODEVECTOR(){this->nodetype = NODETYPEVECTOR; pvector = NULL;}
    };
    
    int main()
    {
        NODETREE   nodetree;
        NODEVECTOR nodevector;
    
        return(0);
    }
    Last edited by rcgldr; 08-31-2013 at 06:19 PM.

  7. #7
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    But that way, the node of the vector contains more things than just a vector. Probably, I can not avoid storing only the vectors in the leaves.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  8. #8
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Actually, I'm surprised I didn't even think of a polymorphic approach. Omg, I'm teh newbzness.

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by std10093 View Post
    But that way, the node of the vector contains more things than just a vector. Probably, I can not avoid storing only the vectors in the leaves.
    I'm not sure of your tree structure. I'm assuming that a vector node contains a pointer to the next vector node, and that a tree node contains a pointer to a lower level branch or tree, similar to a file system where vectors would be similar to files (except vectors would be part of a linked list), and tree nodes similar to sub folders.

    You could use a common class with both a sub-node pointer and a vector pointer, and the type determined by which pointer isn't NULL.
    Last edited by rcgldr; 08-31-2013 at 06:55 PM.

  10. #10
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Another idea.
    Code:
    #include <vector>
    
    typedef std::vector<int> VECTOR;
    
    enum TYPE { TYPE_INNER, TYPE_LEAF };
    
    class Node {
    public:
        virtual Node**  left()  = 0;
        virtual Node**  right() = 0;
        virtual VECTOR* data()  = 0;
        virtual TYPE    type()  = 0;
    };
    
    class Inner : public Node {
        Node* pleft;
        Node* pright;
    public:
        Inner() : pleft(0), pright(0) { }
        virtual Node**  left()  { return &pleft; }
        virtual Node**  right() { return &pright; }
        virtual VECTOR* data()  { return 0; }
        virtual TYPE    type()  { return TYPE_INNER; }
    };
    
    class Leaf : public Node {
        VECTOR v;
    public:
        virtual Node**  left()  { return 0; }
        virtual Node**  right() { return 0; }
        virtual VECTOR* data()  { return &v; }
        virtual TYPE    type()  { return TYPE_LEAF; }
    };
    
    int main() {
        Node* root = new Inner;
        Node** node = root->left();
        *node = new Inner;
        node = (*node)->left();
        *node = new Leaf;
        // ...
        return 0;
    }
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  11. #11
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    @John:
    The tree structure is: every node is actually a struct (that has some data and the children pointers) and the leaves are a vector (nothing else, only this).

    @Canada guy
    I could give it a try with this.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  12. #12
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    @Athens man
    Give it a go, buddy.
    It seems workable but I'm quite sure one of the C++ gurus will give a better solution.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  13. #13
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Any ideas?
    O_o

    If the "inner node" can never be a "leaf node" and a "leaf node" can never be a "inner node", polymorphisms of the variants rcgldr and oogabooga show are good starts. (Both examples have some oddities, but I imagine that is just because an "idea example" not an actual code example.)

    That said, it turns out a little more complex, but a strictly ordered tree can use the "left node pointer" as a signal: if the "left node pointer" is null when the "right node pointer" is not null you actually have a data node which you could access through a cast. (I use this approach where I can despite hate from the purists.)

    It seems workable but I'm quite sure one of the C++ gurus will give a better solution.
    If one approaches this as a strict modelling exercise, one is doomed to failure.

    I note that everything offered so far violates multiple designed principles the "Oh. My. God. OOPS!" crowd would murder the posters for suggesting.

    A pragmatic approach to implementation details is a fine one. I have plenty I might say about the code, but short of using an ugly complex approach involving dispatch, visitor lists, and multiple "RAII" classes to actually implement the various tree operations I see is no reasonable way to accomplish the goals without violating something of design theory.

    [Edit]
    Code:
    class Node
    {
        // ...
            void apply
            (
                RAIIMyTreeOperation * fOperation
            );
        // ...
    };
    
    class RAIIMyTreeNavigation
    {
        // ...
            RAIIMyTreeNavigation * next();
        // ...
             Node * get();
        // ...
    };
    
    class RAIIMyTreeParent; // ...
    
    class RAIIMyTreeLeft; // ...
    
    class RAIIMyTreeRight; // ...
    
    class RAIIMyTreeOperation
    {
        // ...
            void register
            (
                RAIIMyTreeNavigation * mOperand
            );
        // ...
            virtual void execute();
        // ...
    };
    
    class RAIIMyTreeInsert; // ...
    
    class RAIIMyTreeDelete; // ...
    This example is pretty much the worst design I can think of that also, I think, would not violate any of the design principles I referenced.
    [/Edit]

    Soma
    “Salem Was Wrong!” -- Pedant Necromancer
    “Four isn't random!” -- Gibbering Mouther

  14. #14
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    I went for the way of the canada guy, I enjoyed it.
    However, now I have a severe problem in print function.
    It crashes, after printing me all the nodes that are created. I mean I have the tree, all its nodes are printed and then it crashes.. What am I missing?

    Here is the function:
    Code:
    /**
     * Print the tree.
    */
    void Quadtree::print() const
    {
        std::cout << "Octree" << std::endl;
        print(root);
        cout<<"I am out"<<endl;
    }
    
    /**
     * Print the current node.
     * @param node - the node to be printed.
    */
    void Quadtree::print(const Pointer* node) const
    {       
        /*
         * Example: take an octree with one level of children.
         * It will print, the first child first, then the root
         * and then the rest of the children in increasing order.
        */
        cout<<"line1"<<endl;
        if(node)
        { cout<<"line2"<<endl;
            if(node->type() == TYPE_INNER)
            { cout<<"line3"<<endl;
                print(node->child()[0]);
                 cout<<"line4"<<endl;
                std::cout << "Inner node with "
                        "split point " << *(node->split());
                 cout<<"line5"<<endl;
                print(node->child()[1]);
                 cout<<"line6"<<endl;
                print(node->child()[2]);
                 cout<<"line7"<<endl;
                print(node->child()[3]);
                 cout<<"line8"<<endl;
                print(node->child()[4]);
                 cout<<"line9"<<endl;
                print(node->child()[5]);
                 cout<<"line10"<<endl;
                print(node->child()[6]);
                 cout<<"line11"<<endl;
                print(node->child()[7]);
                 cout<<"line12"<<endl;
           }
           if(node && !node->relevantH()->size())
           {
                cout<<"line13"<<endl;
               std::cout << "Leaf with empty vector, thus no"
                       " interesting halfspaces can be found here." << std::endl;
           }
           else if(node)
           {
                cout<<"line14"<<endl;
               std::cout << "Leaf with vector "; printVector(node->relevantH());
           }
        }
         cout<<"line15"<<endl;
    }
    and my output
    Code:
    Octree
    line1
    line2
    line3
    line1
    line2
    line14
    Leaf with vector 3 
    line15
    line4
    Inner node with split point 0.500000000500000,0.500000000500000,0.500000000500000
    line5
    line1
    line2
    line14
    Leaf with vector 3 
    line15
    line6
    line1
    line2
    line14
    Leaf with vector 3 
    line15
    line7
    line1
    line2
    line14
    Leaf with vector 3 
    line15
    line8
    line1
    line2
    line14
    Leaf with vector 3 
    line15
    line9
    line1
    line2
    line14
    Leaf with vector 3 
    line15
    line10
    line1
    line2
    line14
    Leaf with vector 3 
    line15
    line11
    line1
    line2
    line13
    Leaf with empty vector, thus no interesting halfspaces can be found here.
    line15
    line12
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  15. #15
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I'm really not much of a C++ guy, my friend, so be warned!
    But if you're going with that code, here's a bit of a rewrite.
    I added separate getters and setters for the pointers.
    I changed the function that gets the vector to return a reference.
    Oh, and I added print functions, too!
    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;
    };
     
    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 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 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();
    
        return 0;
    }
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  2. Replies: 5
    Last Post: 12-02-2006, 11:03 AM
  3. Tree-view bold items
    By mobazr in forum Windows Programming
    Replies: 3
    Last Post: 03-14-2005, 08:45 AM
  4. display tree data in binary tree format
    By xddxogm3 in forum C++ Programming
    Replies: 4
    Last Post: 12-11-2003, 12:47 AM
  5. Replies: 5
    Last Post: 05-23-2003, 01:11 PM