giffer

Create .gif images from sites like youtube.com
Log | Files | Refs | LICENSE

resolve.go (1875B)

      1 package main
      2 
      3 // Graph of Nodes that resolves dependencies.
      4 type Graph struct {
      5 	Nodes      []Node
      6 	unresolved *NodeMap
      7 	resolved   *NodeMap
      8 }
      9 
     10 // Append a node to the graph.
     11 func (g *Graph) Append(n Node) {
     12 	g.Nodes = append(g.Nodes, n)
     13 }
     14 
     15 // Resolve the graph.
     16 func (g *Graph) Resolve() []Node {
     17 	g.unresolved = &NodeMap{m: map[string]int{}}
     18 	g.resolved = &NodeMap{m: map[string]int{}}
     19 	for _, n := range g.Nodes {
     20 		g.resolve(n)
     21 	}
     22 	return g.resolved.List()
     23 }
     24 
     25 func (g *Graph) resolve(n Node) {
     26 	g.unresolved.Append(n)
     27 	defer g.resolved.Append(n)
     28 	defer g.unresolved.Remove(n)
     29 	for _, edge := range n.Requires() {
     30 		if _, resolved := g.resolved.Lookup(edge.ID()); !resolved {
     31 			if _, seen := g.unresolved.Lookup(edge.ID()); seen {
     32 				panic("Circular reference")
     33 			} else {
     34 				g.resolve(edge)
     35 			}
     36 		}
     37 	}
     38 }
     39 
     40 // Node on a graph.
     41 type Node interface {
     42 	ID() string
     43 	Requires() []Node
     44 }
     45 
     46 // NodeMap is a map of nodes.
     47 type NodeMap struct {
     48 	l []Node
     49 	m map[string]int
     50 }
     51 
     52 // List returns an ordered list of nodes.
     53 func (m *NodeMap) List() []Node {
     54 	return m.l
     55 }
     56 
     57 // Append a node.
     58 func (m *NodeMap) Append(n Node) {
     59 	m.l = append(m.l, n)
     60 	m.m[n.ID()] = len(m.l) - 1
     61 }
     62 
     63 // Remove a node.
     64 func (m *NodeMap) Remove(n Node) {
     65 	ii := m.m[n.ID()]
     66 	m.l = append(m.l[:ii], m.l[ii+1:]...)
     67 	delete(m.m, n.ID())
     68 }
     69 
     70 // Lookup a node for the given id.
     71 func (m *NodeMap) Lookup(id string) (Node, bool) {
     72 	ii, ok := m.m[id]
     73 	if !ok {
     74 		return nil, false
     75 	}
     76 	return m.l[ii], true
     77 }
     78 
     79 // taskNode wraps a Task to implement the Node interface.
     80 // Index allows us to return a Task object for a given Task name.
     81 type taskNode struct {
     82 	Task  Task
     83 	Index map[string]Task
     84 }
     85 
     86 func (n taskNode) ID() string {
     87 	return n.Task.Name
     88 }
     89 
     90 func (n taskNode) Requires() (list []Node) {
     91 	for _, r := range n.Task.Requires {
     92 		list = append(list, taskNode{Task: n.Index[r], Index: n.Index})
     93 	}
     94 	return list
     95 }