How to implement a generic DOM data structure in C++?

Question

I'm trying to write a very simple implementation of Document Object Model library in order to provide a generic data structure to use in my further projects. Just to keep things simple I defined only three main classes: node, element and attribute. A node is defined by it's name (e.g. all html tags) and basically is a container for an element which can be both text and sub-nodes (stored in a std::vector<node>).

I just can't figure out how to define a whole tree structure.

I need templatized interfaces for the classed I referred.

Example of usage:

element<string> txt1("Some text");

element< element<string> > div1("div", txt1);

I don't want to create a complete DOM abstraction level with full support of XML. I just need ideas to organize information in DOM-like style. No parsing is required.

Thanks in advance!

Answer 1

If you look at my past answers, you will see that I am a proponent of templates, but if you have no other requirements, they will only get in the way. Parsers don't like lots of different types to deal with. (Although you say you don't need a parser — huh?)

The point of XML and DOM is to make it easy to translate to and from any internal structure. Not only shouldn't you need to define an XML node template, you shouldn't need any kind of custom data structure. Any structure is already in DOM-like style. DAGs are troublesome, because they're kinda-trees and kinda-graphs, but you don't hint that you're hitting that kind of roadblock.

You say (in comment to deleted answer) that you don't want to use an existing library. Why? What is it you're really trying to do?

Answer 2

Instead of trying to strongly type each node based on how many parents it has, organize your code as a tree structure:

class Element
{
public:
  std::string Name;
  std::map<std::string, std::string, std::less<std::string> > Attributes;
  std::list<Element> Children;
};

Your public interface will probably look much different from this. I'm just trying to show the general type layout.

You don't really need the Node or Attribute features, unless you need to iterate over them in a collection along with Elements. It is a useful feature for XML DOM libraries, but if you're just trying to create a data structure, you don't have to follow the DOM design to the letter.

In fact, if you're just going for a generic data structure, you might just want a property bag:

#include<map>
#include<string>
#include<iostream>

class PropertyBag;
typedef std::map<std::string, PropertyBag> PropertyMap;

class PropertyBag : public PropertyMap
{
public:
  PropertyBag(const std::string& value)
    : value(value)
  {
  }

  PropertyBag& operator=(const std::string& value)
  {
    this->value = value;
    return *this;
  }

  operator std::string& () { return value; }

private:
  std::string value;

  friend PropertyMap::mapped_type& PropertyMap::operator[](const PropertyMap::key_type&);
  PropertyBag() { }
};

void SomeFunction(const std::string& value)
{
  std::cout << value << "\n";
}

int main(int argc, char* argv[])
{
  PropertyBag config("configuration root");
  config["child1"] = "value1";
  config["child1"]["subchild1"] = "value2";

  SomeFunction(config["child1"]);
  SomeFunction(config["child1"]["subchild1"]);
  return 0;
}

Just talking about the syntax, you can also try to get tricky with overloading operator(), and/or chaining methods:

PropertyBag& SomeMethod(const std::string& someParam)
{
  // do something here...
  return *this;
}

PropertyBag& operator()(const std::string& p1, const std::string& p2)
{
  // ...
  return *this;
}

// ...

Configuration config1("root")
  .SomeMethod("p1")
  .SomeMethod("p2");
Configuration config2("root")
  ("Something", "blah")
  ("sizzle", "V2");

I imagine the less text/code duplication, the better. The closer you can get your code to have a syntax like JSON or YAML, the better.

Once c++0x comes out, you may have much simpler options available to you. You can also look into the boost::assign library for an easy initialization syntax to use on your data structure.

You can also look into the boost::any library for a datatype that you can use as the value, instead of strings (supports a type-safe method of inserting any value, as long as you extract it as the same type).