module visitor;

private import std.stdio;
//private import std.conv;

class NodeBase
{
  protected:
    NodeBase[] mInputs;
    char[]     mLabel;

  public:
    this(char[] label)
    {
      mLabel = label;
    }
  
    NodeBase[] inputs()
    {
      return mInputs;
    }
    
    char[] label()
    {
      return mLabel;
    }
  
    // add Nodes
    void append(NodeBase node)
    {
      mInputs ~= node;
    }

    // visitor support
    bool accept(Visitor visitor)   {  return visitor.visitBase(this);  }
}

class A : NodeBase
{
  public:
    this(char[] label)
    {
      super(label);
    }
  
    bool accept(Visitor visitor)   
    {  
      bool result = visitor.visitA(this);  
      if (!result)
      {
        // fallback to base class
        result = super.accept(visitor);
      }
      return result;
    }
}

class B : NodeBase
{
  public:
    this(char[] label)
    {
      super(label);
    }
    
    bool accept(Visitor visitor)
    {  
      bool result = visitor.visitB(this);  
      if (!result)
      {
        // fallback to base class
        result = super.accept(visitor);
      }
      return result;
    }
}

// visitor base class
abstract class Visitor
{
  // special method for NodeBase 
  bool visitBase(NodeBase base) { return true; }

  // return false to call accept() of base class
  bool visitA(A a) { return false; }
  bool visitB(B b) { return false; }

  // for edges
  void visitEdge(NodeBase from, NodeBase to, uint edgepos)
  {
    // do nothing
  }
};

// Node filter used to log already visited nodes
class NodeFilter
{
  protected:
    NodeBase[NodeBase] mVisitedNodes;

  public:
    bool isFiltered(NodeBase node)
    {
      return (null != (node in mVisitedNodes));
    }

    bool add(NodeBase node)
    {
      bool result = false;
      if (!(node in mVisitedNodes))
      {
        mVisitedNodes[node] = node;
        result = true;
      }
      return result;
    }
};

// Preorder visitor
class PreOrderVisitor : Visitor
{
  protected:
    NodeFilter mFilter;
    Visitor    mOperation;

  public:
    this(Visitor operation)
    {
      mFilter    = new NodeFilter;
      mOperation = operation;
    }

    bool visitBase(NodeBase      node)
    {
      bool bNotFiltered = mFilter.add(node);
      if (bNotFiltered)
      {
        node.accept(mOperation);

        foreach(int i, NodeBase dest; node.inputs)
        {
					if (null != dest)
					{
						dest.accept(this);
            
            // visit edge
   					mOperation.visitEdge(node, dest, i);
					}
        }
      }
      return bNotFiltered;
    }
}

// Print visitor
class PrintVisitor : Visitor
{
  bool visitA(A a)
  {
    writefln("A: ", a.label);
    return true;
  }

  bool visitB(B b)
  {
    writefln("B: ", b.label);
    return true;
  }
  
  void visitEdge(NodeBase from, NodeBase to, uint edgepos)
  {
    writefln("  ", from.label, "[", std.string.toString(edgepos), "] -> ", to.label);
  }
}

void main()
{
  // create graph:
  //
  //        node1 (A)
  //        /   \
  //     node2  node3 (B)
  //        \   /
  //        node4 (A)
  //
  A node1 = new A("node1");
  B node2 = new B("node2");
  B node3 = new B("node3");
  A node4 = new A("node4");
  
  node2.append(node1);
  node3.append(node1);
  node4.append(node2);
  node4.append(node3);

  // create visitor chain
  auto PrintVisitor printvisitor = new PrintVisitor();
  PreOrderVisitor   preorderVisitor = new PreOrderVisitor(printvisitor);
  
  // traverse
  node4.accept(preorderVisitor);
}