Creating in c#,c++ and java a strong typed version of a python weak typed structure

Question

In python I have the following:

graph = {}

graph[1] = {}
graph[2] = {}
graph[3] = {}

graph[1][3] = graph[3]

graph[2][1] = graph[1]
graph[2][3] = graph[3]

graph[3][2] = graph[2]

this is a structure to represent a graph and that I find nice because its structure is the same as the one of one of it's nodes so I can use it directly to initiate a search (as in depth-first). The printed version of it is:

{1: {3: {2: {1: {...}, 3: {...}}}}, 2: {1: {3: {2: {...}}}, 3: {2: {...}}}, 3: {
2: {1: {3: {...}}, 3: {...}}}}

And it can be used like:

graph[1][3][2][3][2][1][3][2][1][3][2].keys()

Now, I'm curious to know how would one implement it in C++, C# and Java without resorting to "Object" tricks that would fill the code with ugly casts. For C++ I was thinking in templatemeta programming but that would generate "finite data types" when what is needed is something like

map<int,map<int,...>> or map<int,...>

Answer 1

Here's a simple hack:

#include <map>
#include <memory>

struct GraphNode
{
  std::map<std::size_t, std::unique_ptr<GraphNode>> m;

  GraphNode & operator[](std::size_t i)
  {
    if (!m[i]) { m[i].reset(new GraphNode); }
    return *m[i];
  }
};

We add some ostream overloads for printing:

#include <prettyprint.hpp>

std::ostream & operator<<(std::ostream & o, GraphNode const & g)
{
  if (g.m.empty()) return o << "*";
  return o << g.m;
}
std::ostream & operator<<(std::ostream & o, std::unique_ptr<GraphNode> const & p)
{
  if (!p) return o << "*";
  return o << *p;
}

Example usage:

#include <iostream>

int main()
{
  GraphNode n;

  n[2] = GraphNode();
  n[4] = GraphNode();

  n[2][3] = GraphNode();
  n[2][8] = GraphNode();
  n[2][1] = GraphNode();

  std::cout << n << std::endl;
}

Prints: [(2, [(1, *), (3, *), (8, *)]), (4, *)]

Further features are easily added; at the moment it's not clear to me whether you want all nodes to also support satellite data ("values"), or whether only leaf nodes can have values, or if there isn't any additional data.