Building a tree cleanly

[hamsterman]

I'm looking for a way to write a tree so that it does not look ugly.
Let's say I have

struct Node{ /*abstract*/ };
struct Branch : Node{ std::vector< Node* > v; };

and several non abstract classes Apple, Banana, Candy : Node and Donkey, Elk : Branch.

Now I want a tree from these. The prettiest way I can think of is lisplike

my_tree = (Donkey Apple (Elk Banana) Candy)

and etc. I can't think of a good way to get something like that in C++ though.

I could write

template<typename T>
Class& operator << (T t){ v.push_back( new T(t) ); return *this; }

for Class= every child of Branch (I'm only going to have a few of them, so I guess it's ok) and get

my_tree = Donkey() << Apple() << ( Elk() << Banana() ) << Candy();

which looks somewhat acceptable but does way too much copies.. (unless half of them are inlined..)

Or I could have a

struct List{
   std::vector< Node* > v;
   List& operator << ( Node* ) { ... }
};

and then write constructors Class( const List& ) for Class= every child of Branch. Then I'd have

my_tree = new Donkey( List() << new Apple() << new Elk( List() << new Banana() ) << new Candy() );

which takes care of the copies and the silly template, but I'm not sure if I like all the List() and new..

I'd appreciate any suggestions on how to write this neatly.

[aquaz]

You could use list initializers, a C++1x feature:
Then your constructor looks like:

List(std::initializer_list<Node*> list) : v(list) {}

And you use it like this:

my_tree = new Donkey({new Apple(), new Elk({new Banana(), new Candy()}), new Candy()});

And if you really hate all the "new" you could use variadic templates:

template<typename T, typename First, typename... Args>
std::list<T*> make_list()
{
return make_list<T, Args...>().push_front(new First());
}

// to terminate recursion
template<typename T>
std::list<T*> make_list()
{
return std::list<T*>();
}

Not sure this work, and I use list to efficiently use push_front. Normally rvalue optimisation will prevent from copying the list at each call

[kfmfe04]

For compile-time/static parsing, I would dig into boost/assign and see if you can adapt some of techniques for your tree:

#include <boost/assign.hpp>
#include <map>
int main()
{
   std::map<int, char> example = 
      boost::assign::map_list_of(1, 'a') (2, 'b') (3, 'c');
}

[m4ster r0shi]

This uses your second interface and doesn't perform a single unnecessary copy.

#include <iostream>
#include <vector>

#define DEF_PRINT_NODE(TypeName) \
    void print() const { std::cout << #TypeName; }

#define DEF_PRINT_BRANCH(TypeName) \
    void print() const \
    { \
        std::cout << #TypeName << "<"; \
        for (unsigned i=0; i<v.size(); i++) \
        { \
            if (i!=0) std::cout << " "; \
            v[i]->print(); \
        } \
        std::cout << ">"; \
    }

#define DEF_CLONE(TypeName) \
    TypeName * clone() const { return new TypeName(*this); }

#define DEF_SWAP_CLONE(TypeName) \
    TypeName * swap_clone() const \
    { \
        TypeName * ret = new TypeName; \
        ret->swap(const_cast<TypeName&>(*this)); \
        return ret; \
    }

struct Node
{
    virtual Node * clone() const=0;
    virtual void print() const=0;
    virtual ~Node() {}
};

struct Branch : Node
{
    std::vector<Node*> v;

    virtual Branch * swap_clone() const=0;
    void swap(Branch & b) { v.swap(b.v); }
};

Branch & operator << (const Branch & cb1, const Branch & cb2)
{
    Branch & b1=const_cast<Branch&>(cb1);

    b1.v.push_back(cb2.swap_clone()); return b1;
}

Branch & operator << (const Branch & cb, const Node & cn)
{
    Branch & b=const_cast<Branch&>(cb);

    b.v.push_back(cn.clone()); return b;
}

struct Candy : Node { DEF_CLONE(Candy) DEF_PRINT_NODE(Candy) };
struct Apple : Node { DEF_CLONE(Apple) DEF_PRINT_NODE(Apple) };
struct Banana : Node { DEF_CLONE(Banana) DEF_PRINT_NODE(Banana) };

struct Donkey : Branch { DEF_SWAP_CLONE(Donkey)
     DEF_CLONE(Donkey) DEF_PRINT_BRANCH(Donkey) };

struct Elk : Branch { DEF_SWAP_CLONE(Elk)
     DEF_CLONE(Elk) DEF_PRINT_BRANCH(Elk) };

struct Tree : Branch { DEF_SWAP_CLONE(Tree)
     DEF_CLONE(Tree) DEF_PRINT_BRANCH(Tree) };

int main()
{
    Tree my_tree;

    my_tree.swap(

        Tree()
            << ( Donkey()
                    <<   Apple() )
            <<   Candy()
            << ( Elk()
                    <<   Banana()
                    <<   Apple() )
            << ( Donkey()
                    << ( Elk()
                            << Candy()
                            << Banana() )
                    <<   Apple() )

    );

    my_tree.print();

    return 0;
}

[hamsterman]

aquaz, that's neat, but I'd rather stick to the current standard..

kfmfe, the problem is that I have many different types (if I do it like my first example) or that you can't overload operators for two pointers (if I accept having new all over the place).
Also, why would you say compile-time ? It all seems quite run-time to me..

master roshi, this is awesome, I'm not sure if I'm going to use this, but still, awesome.

[webJose]

Since your collections are collections of pointers, why do you care about the copying? Just modify your original idea and make operator<< take pointers by value.

Class& operator << (node* n){ v.push_back( n ); return *this; }

Then just use new:

my_tree = Donkey() << new Apple() << ( new Elk() << new Banana() ) << new Candy();

Or did I miss something?

[hamsterman]

webJose, that would not compile (I think), as the left argument of << after Elk() is a pointer. If you removed the new before Elk, the right argument of the << before it would not be a pointer.
It would be awesome if it really worked that way though..

[webJose]

Hi. I think it does compile. Check out a simple example: https://ideone.com/SSWtl. Surely it doesn't have complex inheritance in place, but I believe it shows the operator works on pointers to Node. It works because operator << is evaluated left to right.

[helios]

If it does compile, it doesn't work. You're just shifting pointers, not calling overloaded operators.

[webJose]

Not sure I follow. Doesn't the output confirm the overload is being called???

EDIT: I'll add some confirmation by outputting the vector.

[webJose]

I just added the printing of the list contents. The nodes seem to be OK. No pointer shifting.

[webJose]

I went further to clear it up beyond a doubt. Now the sample code prints the pointer addresses when the objects are created and when the objects are received inside operator<<. They are the same. Furthermore, it works OK with derived objects.

This should then allow for easy construction of the tree without the multiple constructors.

[hamsterman]

https://ideone.com/SSWtl

You misunderstood. That code is fine. It's the parentheses that wouldn't compile.
Compile it with this main:

int main(){
    Branch B = Branch() << new Node(1) << (new Branch() << new Node(2)) << new Node(3);
    return 0;
}

I get

error C2296: '<<' : illegal, left operand has type 'Branch *'

On topic, I discovered that I actually don't need that tree at all. It was a result of my sin no. 12 I guess..

[m4ster r0shi]

hamsterman wrote:

I discovered that I actually don't need that tree at all.

Regardless, I thought you guys might want to see this.
It's way cleaner and doesn't perform any copying at all.

#include <iostream>
#include <vector>

#define DEF_PRINT_NODE(NodeType) void print() const { std::cout << #NodeType; }

#define DEF_PRINT_BRANCH(BranchType) \
    void print() const { \
        std::cout << #BranchType << "<"; \
        for (unsigned i = 0; i < v.size(); i++) { \
            if (i!=0) std::cout << " "; \
            v[i]->print(); } \
        std::cout << ">"; }

#define DEF_INSERT_NOD_TO_NOD(NodeType) Branch & \
    operator << (Branch & b, NodeType & n) { b.v.push_back(&n); return b; }

#define DEF_INSERT_NOD_TO_GEN(NodeType) template <class T> Branch & \
    operator << (BranchGenerator<T> & g, NodeType & n) { return g() << n; }

#define DEF_INSERT_GEN_TO_NOD(GeneratorType) template <class T> Branch & \
    operator << (Branch & b, GeneratorType<T> & g) { return b << g(); }

#define DEF_INSERT_GEN_TO_GEN(GeneratorType) template <class T1, class T2> Branch & \
    operator << (BranchGenerator<T1> & g1, GeneratorType<T2> & g2) { return g1() << g2(); }

struct Node { virtual void print() const = 0; virtual ~Node() {} };

struct Branch : Node
{
    std::vector<Node*> v;

    ~Branch() { for (unsigned i = 0; i < v.size(); i++) delete v[i]; }
};

struct Candy  : Node { DEF_PRINT_NODE(Candy)  };
struct Apple  : Node { DEF_PRINT_NODE(Apple)  };
struct Banana : Node { DEF_PRINT_NODE(Banana) };

struct Donkey : Branch { DEF_PRINT_BRANCH(Donkey) };
struct Elk    : Branch { DEF_PRINT_BRANCH(Elk)    };
struct Tree   : Branch { DEF_PRINT_BRANCH(Tree)   };

template <class T> struct NodeGenerator   { Node   & operator()() { return *(new T); } };
template <class T> struct BranchGenerator { Branch & operator()() { return *(new T); } };

DEF_INSERT_NOD_TO_NOD(Node)          DEF_INSERT_NOD_TO_NOD(Branch)
DEF_INSERT_NOD_TO_GEN(Node)          DEF_INSERT_NOD_TO_GEN(Branch)
DEF_INSERT_GEN_TO_NOD(NodeGenerator) DEF_INSERT_GEN_TO_NOD(BranchGenerator)
DEF_INSERT_GEN_TO_GEN(NodeGenerator) DEF_INSERT_GEN_TO_GEN(BranchGenerator)

NodeGenerator<Candy>     _candy; NodeGenerator<Apple> _apple; NodeGenerator<Banana> _banana;
BranchGenerator<Donkey> _donkey; BranchGenerator<Elk>   _elk; BranchGenerator<Tree>   _tree;

Tree * make_tree(Branch & b) { return &dynamic_cast<Tree&>(b); }

int main()
{
    Tree * my_tree = make_tree (

        _tree
            <<   _banana
            << ( _donkey
                    <<   _apple
                    <<   _candy )
            <<   _candy
            << ( _donkey
                    << ( _elk
                            <<   _apple
                            <<   _banana )
                    <<   _candy )
            <<   _apple

    );

    my_tree->print();

    delete my_tree;

    return 0;
}

Needless to say, I had a spiritual orgasm after I finished this.
I was sitting on my chair just looking at it and thinking
"Oh, God, this is so beautiful... Why is this so beautiful?"
for like half an hour... (or maybe a little bit more...)

[hamsterman]

Needless to say, I had a spiritual orgasm after I finished this.

I can see why you would..

Though this looses the ability to call constructors..

[m4ster r0shi]

hamsterman wrote:

Though this looses the ability to call constructors..

Oh... True... Well, I guess this can be solved by adding one more level of
indirection -> Generators that generate generators through operator().

Then, one can simply write:

Tree * my_tree = make_tree (

    _tree(8)
        <<   _banana(4)
        << ( _donkey(2)
                <<   _apple(3)
                <<   _candy(7) )
        <<   _candy(9)
        << ( _donkey(4)
                << ( _elk(1)
                        <<   _apple(6)
                        <<   _banana(0) )
                <<   _candy(4) )
        <<   _apple(5)

);

[hamsterman]

Or functions that return generators. Though I guess you would then have to do the constness hack you did in the previous code.

[m4ster r0shi]

hamsterman wrote:

Though I guess you would then have to do the constness hack you did in the previous code.

Mmmm... Not really.

The only reason I omitted the const qualifiers for the generator classes was laziness.
A generator doesn't have internal state and even if I add one (e.g. the Node/Branch
constructor arguments) the << operators won't modify it. It should be ok :D

[hamsterman]

Here's mine.
It doesn't seem to abuse copying of any sort and with this you can ( but don't have to ) call constructors.
Awesome, eh?

#include <iostream>
#include <vector>

#define PRINT_NODE(Name) virtual void print() {\
   std::cout << #Name;\
 }
#define PRINT_BRANCH(Name) virtual void print() {\
   std::cout << #Name << "(";\
   for(unsigned i = 0; i < v.size(); i++) {\
      if(i) std::cout << ", ";\
      v[i]->print();\
   }\
   std::cout << ")";\
 }

struct Node{
   virtual void print() = 0;
   virtual ~Node() {};
};
struct Branch : Node{
   std::vector< Node* > v;
   virtual ~Branch(){
      for(unsigned i = 0; i < v.size(); i++)
         delete v[i];
   }
};

struct Apple : Node{
   int n;

   Apple( int N ) : n(N) {}

   virtual void print() {
      std::cout << n << " Apples";
   }
};
struct Banana : Node{ PRINT_NODE(Banana) };
struct Candy : Node{ PRINT_NODE(Candy) };

struct Donkey : Branch{ PRINT_BRANCH(Donkey) };
struct Elk : Branch{ PRINT_BRANCH(Elk) };
struct Tree : Branch{ PRINT_BRANCH(Tree) };

struct Pointer{
   Node* ptr;

   Pointer& operator /( Node* p ){
      ptr = p;
      return *this;
   }
};

#define APPLE  Pointer()/new Apple
#define BANANA Pointer()/new Banana
#define CANDY  Pointer()/new Candy

struct Container{
   Branch* ptr;

   operator Branch*(){
      return ptr;
   }
   Container& operator /( Branch* p ){
      ptr = p;
      return *this;
   }
   Container& operator , ( Pointer p ) { 
      if(ptr) ptr->v.push_back(p.ptr);
      return *this;
   }
   Container& operator , ( Container c ) { 
      if(ptr) ptr->v.push_back(c.ptr);
      return *this;
   }
};

#define DONKEY Container()/new Donkey
#define ELK    Container()/new Elk

int main(){
   Branch* tree = ( DONKEY , APPLE(5) , ( ELK , BANANA ) , CANDY );
   tree->print();
   std::cin.get();
   return 0;
}

How come this is so much fun..?

[m4ster r0shi]

Ingenious!