--- a/trunk/src/docgen/graphutils/primitives.d	Sat Feb 02 23:17:14 2008 +0100
+++ b/trunk/src/docgen/graphutils/primitives.d	Sun Feb 03 19:43:53 2008 +0200
@@ -4,99 +4,139 @@
  */
 module docgen.graphutils.primitives;
 
-enum EdgeType {
-  Unspecified,
-  Aggregation,
-  Association,
-  Composition,
-  Dependency,
-  Generalization,
-  Inheritance,
-  PublicDependency
-}
+/**
+ * Extendible graph class. Should support separation of concerns now better with mixins.
+ * Provides a method for cycle marking.
+ */
+class Graph(alias V, alias E, int capacity = 1) {
+  static class Edge {
+    Vertex outgoing, incoming;
+    //bool cyclic = true;
 
-enum CycleType {
-  Unspecified,
-  Cyclefree,
-  Cyclic,
-  Reserved
-}
+    this(Vertex o, Vertex i) {
+      outgoing = o;
+      incoming = i;
+      o.outgoingEdges ~= this;
+      i.incomingEdges ~= this;
+    }
 
-class Edge {
-  Vertex outgoing;
-  Vertex incoming;
-  EdgeType type;
-  CycleType cycleType; // used by the cycle algorithm
+    bool cyclic() {
+      return outgoing.cyclic && incoming.cyclic;
+    }
 
-  this(Vertex o, Vertex i, EdgeType type = EdgeType.Unspecified) {
-    this.outgoing = o;
-    this.incoming = i;
-    this.type = type;
+    mixin E;
   }
 
-  bool isCyclic() {
-    return cycleType == CycleType.Cyclic;
+  static class Vertex {
+    Edge[] incomingEdges;
+    Edge[] outgoingEdges;
+    bool cyclic = true;
+
+    Edge addChild(Vertex v) {
+      return new Edge(v, this);
+    }
+
+    Edge addParent(Vertex v) {
+      return v.addChild(this);
+    }
+
+    Vertex[] incoming() {
+      Vertex[] tmp;
+
+      foreach(edge; incomingEdges)
+        tmp ~= edge.outgoing;
+
+      return tmp;
+    }
+
+    Vertex[] outgoing() {
+      Vertex[] tmp;
+
+      foreach(edge; outgoingEdges)
+        tmp ~= edge.incoming;
+
+      return tmp;
+    }
+
+    mixin V;
+  }
+
+  Vertex[] vertices;
+  Edge[] edges;
+
+  this() {
+    vertices.length = capacity;
+    vertices.length = 0;
+    edges.length = capacity;
+    edges.length = 0;
+  }
+
+  void add(Vertex vertex) { vertices ~= vertex; }
+
+  void add(Edge edge) { edges ~= edge; }
+
+  void connect(Vertex from, Vertex to) { edges ~= from.addParent(to); }
+
+  void connect(int from, int to) { connect(vertices[from], vertices[to]); }
+
+  /**
+   * Starts from non-cyclic nodes and propagates two both directions.
+   * Bugs: marks non-cyclic imports between two cycles as cyclic. Could be fixed later if it's really needed (slow)
+   */
+  void markCycles() {
+    void mark(Vertex v) {
+      v.cyclic = false;
+      foreach(o; v.outgoing) {
+        if (!o.cyclic) continue;
+
+        // propagate
+        bool cyclic = false;
+        foreach(p; o.incoming) if (p.cyclic) { cyclic = true; break; }
+        if (!cyclic) mark(o);
+      }
+    }
+
+    void mark2(Vertex v) {
+      v.cyclic = false;
+      foreach(o; v.incoming) {
+        if (!o.cyclic) continue;
+
+        // propagate
+        bool cyclic = false;
+        foreach(p; o.outgoing) if (p.cyclic) { cyclic = true; break; }
+        if (!cyclic) mark2(o);
+      }
+    }
+
+    foreach(e; vertices)
+      if (e.cyclic) {
+        if (!e.incoming.length) mark(e);
+        if (!e.outgoing.length) mark2(e);
+      }
   }
 }
 
-enum VertexType {
-  Module,
-  UnlocatableModule,
-  Package,
-  Class,
-  Interface,
-  Trait
+template Empty() {}
+
+
+// graph elements used in dep graphs
+
+
+template DepEdge() {
+  bool isPublic; /// Public import.
+  bool isStatic; /// Static import.
 }
 
-class Vertex {
+template DepVertex() {
   char[] name;
   char[] location;
   uint id;
 
-  Edge[] incomingEdges;
-  Edge[] outgoingEdges;
-  VertexType type;
-
   this(char[] name, char[] location, uint id = 0) {
     this.name = name;
     this.location = location;
     this.id = id;
   }
-
-  Edge addChild(Vertex v, EdgeType type = EdgeType.Unspecified) {
-    auto edge = new Edge(v, this, type);
-    incomingEdges ~= edge;
-    v.outgoingEdges ~= edge;
-    return edge;
-  }
-
-  Edge addParent(Vertex v, EdgeType type = EdgeType.Unspecified) {
-    return v.addChild(this, type);
-  }
-
-  Vertex[] incoming() {
-    Vertex[] tmp;
-
-    foreach(edge; incomingEdges)
-      tmp ~= edge.outgoing;
+}
 
-    return tmp;
-  }
-
-  Vertex[] outgoing() {
-    Vertex[] tmp;
-
-    foreach(edge; outgoingEdges)
-      tmp ~= edge.incoming;
-
-    return tmp;
-  }
-
-  bool isCyclic() {
-    foreach(edge; outgoingEdges)
-      if (edge.isCyclic)
-        return true;
-
-    return false;
-  }
-}
+alias Graph!(DepVertex, DepEdge, 100) DepGraph;