/**
 * A generic algorithm for mapping a graph to a collection of nodes reachable
 * from a given root node. 
 * 
 * Basic idea: configuration of the form (todo, done, files), 
 * keep adding files corresponding to the names in \verb|todo| until empty
 */
module strategy/pack/graph
imports 
  term/string 
  collection/list/-
  
rules

  GnInit : 
    (root, graph, nodes) -> ([root], [root], graph, nodes, [])

  GnInitRoots : 
    (roots, graph, nodes) -> (roots, roots, graph, nodes, [])

  GnNext(get-node, out-edges, add-node) : 
    ([name | todo], done, graph, nodes, undef) ->
    (<conc> (todo', todo), <conc> (todo', done), 
     graph, <add-node> (name, node, nodes), undef)
    where <get-node> (name, graph) => node;
          <out-edges> node => names;
	  <diff> (names, done) => todo'

  GnNextChangeGraph(get-node, out-edges, add-node) : 
    ([name | todo], done, graph, nodes, undef) ->
    (<conc> (todo', todo), <conc> (todo', done), 
     graph', <add-node> (name, node, nodes), undef)
    where <get-node> (name, graph) => (node,graph');
          <out-edges> node => names;
	  <diff> (names, done) => todo'

  GnUndefined :
    ([name | todo], done, graph, nodes, undef) ->
    (todo, done, graph, nodes, [name | undef])

  GnExit : 
    ([], done, graph, nodes, undef) -> (nodes, undef)

strategies

  graph-nodes-undef-roots(get-node, out-edges, add-node) =
    for(GnInitRoots, GnExit, GnNext(get-node, out-edges, add-node)
                             <+ GnUndefined)

  graph-nodes-undef(get-node, out-edges, add-node) =
    for(GnInit, GnExit, GnNext(get-node, out-edges, add-node)
                        <+ GnUndefined)

  graph-nodes-undef-roots-chgr(get-node, out-edges, add-node) =
    for(GnInitRoots, GnExit, GnNextChangeGraph(get-node, out-edges, add-node)
                        <+ GnUndefined)

  graph-nodes-undef-chgr(get-node, out-edges, add-node) =
    for(GnInit, GnExit, GnNextChangeGraph(get-node, out-edges, add-node)
                        <+ GnUndefined)

 /**
  * The strategy 'graph-nodes' is a generic
  * algorithm for mapping a graph to a collection of nodes reachable
  * from a given root node. The algorithm is parameterized with the
  * following notions: 'get-node' maps a node name and a graph to the
  * node itself, 'out-edges' maps a node to the names of its out
  * edges, 'add-node' that adds a name and its corresponding node to a
  * collection of nodes.
  *
  *    get-node  :: name * graph -> node 
  *    out-edges :: node -> List(name)
  *    add-node  :: name * node * nodes -> nodes
  */
 graph-nodes(get-node, out-edges, add-node) =
    graph-nodes-undef(get-node, out-edges, add-node);
    \ (nodes, undef) -> nodes \

  graph-nodes-roots(get-node, out-edges, add-node) =
    graph-nodes-undef-roots(get-node, out-edges, add-node);
    \ (nodes, undef) -> nodes \