logo

class

sql::TypeGraph

sys::Obj
  sql::TypeGraph
   1  //
   2  // Copyright (c) 2008, John Sublett
   3  // Licensed under the Academic Free License version 3.0
   4  //
   5  // History:
   6  //   01 Jan 08  John Sublett  Creation
   7  //
   8  
   9  **
  10  ** TypeGraph is used to sort a set of types based on
  11  ** their dependencies on each other.  A set of types
  12  ** cannot be sorted if the types have cyclic dependencies.
  13  **
  14  class TypeGraph
  15  {
  16    **
  17    ** Add a type to the graph without specifying a dependency.
  18    **
  19    Void addType(Type t)
  20    {
  21      node(t)
  22    }
  23  
  24    **
  25    ** Add a dependency from the 'from' type to the 'to' type.
  26    **
  27    Void addDependency(Type from, Type to)
  28    {
  29      parent := node(to)
  30      child := node(from)
  31  
  32      parent.addChild(child);
  33    }
  34  
  35    **
  36    ** Get the list of types in the graph sorted by dependency.
  37    ** A type will always be later in the list than the types
  38    ** it depends on.  That is, if type B depends on type A, the
  39    ** sorted result will be '[A, B]'.
  40    **
  41    Type[] sort()
  42    {
  43      return rsort.reverse
  44    }
  45  
  46    **
  47    ** Get the list of types in the graph sorted in reverse order.
  48    **
  49    Type[] rsort()
  50    {
  51      nodes.each |TypeGraphNode n| { n.nodeState = NodeState.unvisited }
  52  
  53      Type[] rsorted := Type[,]
  54      nodes.each |TypeGraphNode n| { n.visit(rsorted) }
  55      return rsorted
  56    }
  57  
  58    **
  59    ** Get the existing node for the specified
  60    ** type or create a new node if one does not
  61    ** already exist.
  62    **
  63    private TypeGraphNode node(Type nodeType)
  64    {
  65      n := nodes[nodeType.qname]
  66      if (n == null)
  67      {
  68        n = TypeGraphNode.make(nodeType)
  69        nodes[nodeType.qname] = n
  70      }
  71      return n
  72    }
  73  
  74    **
  75    ** The list of nodes in the graph.  A node wraps
  76    ** a Type and contains a child node for each dependent
  77    ** Type.
  78    **
  79    private Str:TypeGraphNode nodes := Str:TypeGraphNode[:]
  80  }
  81  
  82  //////////////////////////////////////////////////////////////////////////
  83  // TypeGraphNode
  84  //////////////////////////////////////////////////////////////////////////
  85  
  86  internal class TypeGraphNode
  87  {
  88    new make(Type nodeType)
  89    {
  90      this.nodeType = nodeType
  91    }
  92  
  93    Void visit(Type[] rsorted, TypeGraphNode[] path := TypeGraphNode[,])
  94    {
  95      path.add(this)
  96      switch (nodeState)
  97      {
  98        case NodeState.unvisited:
  99          nodeState = NodeState.visiting
 100          if (!children.isEmpty)
 101            children.each |TypeGraphNode child| { child.visit(rsorted, path) }
 102          nodeState = NodeState.visited
 103          rsorted.add(nodeType)
 104  
 105        case NodeState.visiting:
 106          pathStr := path.join(" > ") |TypeGraphNode n->Str| { return n.nodeType.toStr }
 107          throw Err.make("Cycle detected: $pathStr")
 108  
 109        case NodeState.visited:
 110          return
 111      }
 112    }
 113  
 114    Void addChild(TypeGraphNode child)
 115    {
 116      children.add(child)
 117    }
 118  
 119    Type nodeType
 120    TypeGraphNode[] children := TypeGraphNode[,]
 121    NodeState nodeState := NodeState.unvisited
 122  }
 123  
 124  //////////////////////////////////////////////////////////////////////////
 125  // NodeState
 126  //////////////////////////////////////////////////////////////////////////
 127  
 128  internal enum NodeState { visited, unvisited, visiting }