How to Populate a 'Tree' structure 'Declaratively'

Question

I want to define a 'node' class/struct and then declare a tree of these nodes in code in such a way that the way the code is formatted reflects the tree structure, and there's not 'too much' boiler plate in the way.

Note that this isn't a question about data structures, but rather about what features of C++ I could use to arrive at a similar style of declarative code to the example below.

Possibly with C++0X this would be easier as it has more capabilities in the area of constructing objects and collections, but I'm using Visual Studio 2008.

Example tree node type:

struct node
{ 
  string name;
  node* children;

  node(const char* name, node* children);
  node(const char* name);
};

What I want to do:

Declare a tree so its structure is reflected in the source code

node root =
  node("foo",
  [
    node("child1"),
    node("child2", 
    [
      node("grand_child1"),
      node("grand_child2"),
      node("grand_child3"
    ]),
    node("child3")
  ]);

NB: what I don't want to do:

Declare a whole bunch of temporary objects/colls and construct the tree 'backwards'

node grandkids[] = node[3] 
{
  node("grand_child1"),
  node("grand_child2"),
  node("grand_child3"
};

node kids[] = node[3]
{
  node("child1"),
  node("child2", grandkids) 
  node("child3")
};

node root = node("foo", kids);

Answer 1

It's not difficult to write a parser for the syntax you'd like to use. Here is a simple but working code. I let myself change your node object slightly, it doesn't use an array of pointers for storing children but std::vector

The advantage of this approach is that you can construct a tree from a text supplied in runtime, e.g. read from a config file. Notice also that ostream& operator<<(ostream&, const node&) prints your trees in the same format, this can be handy for serializing your trees (to write them to a file or sending over network) or unit testing.

    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    #include <string>
    #include <vector>
    #include <iostream>


    using namespace std;

    struct node
    { 
      string name;
      vector<node*> children;

      node(const string& name, const vector<node*> children);
      node(const string& name);
    };

    ostream& operator<<(ostream& o, const node& n) {
        o << "node('" << n.name << "'";
        if (n.children.size()) {
            o << ", [";
            for (size_t i = 0; i < n.children.size(); ++i)
                o << (i ? "," : "") << *(n.children[i]);
            o << "]";
        }
        o << ")";
        return o;
    }

    node::node(const string& s, const vector<node*> children)
    : name(s), children(children) {}

    char* parseNode(node** n, const char *ss);

    char *skipSpace(const char *ss) {
        char *s = (char *) ss;
        while (isspace(*s))
            ++s;
        return s;
    }

    void expected_error(const char* s) { 
        fprintf(stderr, "Error: expected '%s'\n", s);
        exit(1);
    }

    char *expect(const char *expected, char *s) {
        char *ex = skipSpace(expected);
        s = skipSpace(s);
        for ( ; *ex && *s; ++ex, ++s)
            if (*ex != *s) expected_error(expected);
        if (*ex) expected_error(expected);
        return s;
    }

    char *expectString(string& str, const char *ss)
    {
        char *s = skipSpace(ss);
        s = expect("'", s);
        char *start = s++;
        while (*s != '\'')
            ++s;
        str = string(start, s - start);
        return ++s;
    }

    char * parseChildren(vector<node*>& children, char *s) {
        s = expect("[", s);
        s = skipSpace(s);
        while (*s != ']') {
            node *n = 0;
            s = parseNode(&n, s);
            children.push_back(n);
            s = skipSpace(s);
            if (*s == ',')
                ++s;
            else break;
        }
        s = expect("]", s);
        return s;
    }

    char* parseNode(node** n, const char *ss) {
        char *s = (char *) ss;
        s = expect("node", s);
        s = expect("(", s);
        string name;
        s = expectString(name, s);
        vector<node*> children;
        s = skipSpace(s);
        if (*s == ',') 
            s = parseChildren(children, ++s);
        *n = new node(name, children);
        s = expect(")", s);
        return s;
    }

    int main()
    {
        node * n = 0;
        parseNode(&n,
    " node('foo',"
    "  ["
    "    node('child1'),"
    "    node('child2', "
    "    ["
    "     node('grand_child1'),"
    "     node('grand_child2'),"
    "     node('grand_child3')"
    "    ]),"
    "   node('child3')"
    " ])"
    );
        cout << *n;
        return 0;
    }

Answer 2

If you don't mind excessive copying of the nodes and using parenthesis () instead of square brackets [] then this should work.

Actually you can avoid copying by storing pointers in the node_group rather than copies, but since this is friday afternoon and I'm very lazy, I'll leave it to you.

struct node
{
    std::string name;
    std::vector<node> children;

    node(const char* n)
        :   name (n)
    {
    }

    node(const char* n, const class node_group& group);
};

struct node_group
{
    std::vector<node> children;
};

node::node(const char* n, const class node_group& group)
    :   name (n)
    ,   children (group.children)
{
}

node_group operator ,(const node& n1, const node& n2)
{
    node_group group;
    group.children.push_back (n1);
    group.children.push_back (n2);
    return group;
}

node_group operator ,(const node_group& gr, const node& n2)
{
    node_group group (gr);
    group.children.push_back (n2);
    return group;
}


int main ()
{
    node root ("foo",
                (node("child1"),
                node("child2",
                    (node("grand_child1"),
                    node("grand_child2"),
                    node("grand_child3"))
                    ),
                node("child3"))
              );
}

Answer 3

http://en.wikipedia.org/wiki/Expression_templates

Using this technique, you can get syntax like:

Node root("bob") =
  (node("child1")
    <<(
      node("grandkid"),
      node("grandkid2")
    )
  ),
  node("child2");

where you overload operator, and operator<< to build an expression tree which is used to construct your root node.