1package org.testng.internal;
2
3import org.testng.collections.ListMultiMap;
4import org.testng.collections.Lists;
5import org.testng.collections.Maps;
6import org.testng.collections.Sets;
7
8import java.util.Collection;
9import java.util.Collections;
10import java.util.Comparator;
11import java.util.List;
12import java.util.Map;
13import java.util.Set;
14
15/**
16 * Representation of the graph of methods.
17 */
18public class DynamicGraph<T> {
19  private static final boolean DEBUG = false;
20
21  private List<T> m_nodesReady = Lists.newArrayList();
22  private List<T> m_nodesRunning = Lists.newArrayList();
23  private List<T> m_nodesFinished = Lists.newArrayList();
24
25  private Comparator<? super T> m_nodeComparator = null;
26
27  private ListMultiMap<T, T> m_dependedUpon = Maps.newListMultiMap();
28  private ListMultiMap<T, T> m_dependingOn = Maps.newListMultiMap();
29
30  public static enum Status {
31    READY, RUNNING, FINISHED
32  }
33
34  /**
35   * Define a comparator for the nodes of this graph, which will be used
36   * to order the free nodes when they are asked.
37   */
38  public void setComparator(Comparator<? super T> c) {
39    m_nodeComparator = c;
40  }
41
42  /**
43   * Add a node to the graph.
44   */
45  public void addNode(T node) {
46    m_nodesReady.add(node);
47  }
48
49  /**
50   * Add an edge between two nodes.
51   */
52  public void addEdge(T from, T to) {
53    m_dependingOn.put(to, from);
54    m_dependedUpon.put(from, to);
55  }
56
57  /**
58   * @return a set of all the nodes that don't depend on any other nodes.
59   */
60  public List<T> getFreeNodes() {
61    List<T> result = Lists.newArrayList();
62    for (T m : m_nodesReady) {
63      // A node is free if...
64
65      List<T> du = m_dependedUpon.get(m);
66      // - no other nodes depend on it
67      if (!m_dependedUpon.containsKey(m)) {
68        result.add(m);
69      } else if (getUnfinishedNodes(du).size() == 0) {
70        result.add(m);
71      }
72    }
73
74    // Sort the free nodes if requested (e.g. priorities)
75    if (result != null && ! result.isEmpty()) {
76      if (m_nodeComparator != null) {
77        Collections.sort(result, m_nodeComparator);
78        ppp("Nodes after sorting:" + result.get(0));
79      }
80    }
81
82    return result;
83  }
84
85  /**
86   * @return a list of all the nodes that have a status other than FINISHED.
87   */
88  private Collection<? extends T> getUnfinishedNodes(List<T> nodes) {
89    Set<T> result = Sets.newHashSet();
90    for (T node : nodes) {
91      if (m_nodesReady.contains(node) || m_nodesRunning.contains(node)) {
92        result.add(node);
93      }
94    }
95    return result;
96  }
97
98  /**
99   * Set the status for a set of nodes.
100   */
101  public void setStatus(Collection<T> nodes, Status status) {
102    for (T n : nodes) {
103      setStatus(n, status);
104    }
105  }
106
107  /**
108   * Set the status for a node.
109   */
110  public void setStatus(T node, Status status) {
111    removeNode(node);
112    switch(status) {
113      case READY: m_nodesReady.add(node); break;
114      case RUNNING: m_nodesRunning.add(node); break;
115      case FINISHED: m_nodesFinished.add(node); break;
116      default: throw new IllegalArgumentException();
117    }
118  }
119
120  private void removeNode(T node) {
121    if (!m_nodesReady.remove(node)) {
122      if (!m_nodesRunning.remove(node)) {
123        m_nodesFinished.remove(node);
124      }
125    }
126  }
127
128  /**
129   * @return the number of nodes in this graph.
130   */
131  public int getNodeCount() {
132    int result = m_nodesReady.size() + m_nodesRunning.size() + m_nodesFinished.size();
133    return result;
134  }
135
136  public int getNodeCountWithStatus(Status status) {
137    switch(status) {
138      case READY: return m_nodesReady.size();
139      case RUNNING: return m_nodesRunning.size();
140      case FINISHED: return m_nodesFinished.size();
141      default: throw new IllegalArgumentException();
142    }
143  }
144
145  private static void ppp(String string) {
146    if (DEBUG) {
147      System.out.println("   [GroupThreadPoolExecutor] " + Thread.currentThread().getId() + " "
148          + string);
149    }
150  }
151
152  @Override
153  public String toString() {
154    StringBuilder result = new StringBuilder("[DynamicGraph ");
155    result.append("\n  Ready:" + m_nodesReady);
156    result.append("\n  Running:" + m_nodesRunning);
157    result.append("\n  Finished:" + m_nodesFinished);
158    result.append("\n  Edges:\n");
159    for (Map.Entry<T, List<T>> es : m_dependingOn.entrySet()) {
160      result.append("     " + es.getKey() + "\n");
161      for (T t : es.getValue()) {
162        result.append("        " + t + "\n");
163      }
164    }
165    result.append("]");
166    return result.toString();
167  }
168
169  private String getName(T t) {
170    String s = t.toString();
171    int n1 = s.lastIndexOf('.') + 1;
172    int n2 = s.indexOf('(');
173    return s.substring(n1, n2);
174  }
175
176  /**
177   * @return a .dot file (GraphViz) version of this graph.
178   */
179  public String toDot() {
180    String FREE = "[style=filled color=yellow]";
181    String RUNNING = "[style=filled color=green]";
182    String FINISHED = "[style=filled color=grey]";
183    StringBuilder result = new StringBuilder("digraph g {\n");
184    List<T> freeNodes = getFreeNodes();
185    String color;
186    for (T n : m_nodesReady) {
187      color = freeNodes.contains(n) ? FREE : "";
188      result.append("  " + getName(n) + color + "\n");
189    }
190    for (T n : m_nodesRunning) {
191      color = freeNodes.contains(n) ? FREE : RUNNING;
192      result.append("  " + getName(n) + color + "\n");
193    }
194    for (T n : m_nodesFinished) {
195      result.append("  " + getName(n) + FINISHED+ "\n");
196    }
197    result.append("\n");
198
199    for (T k : m_dependingOn.keySet()) {
200      List<T> nodes = m_dependingOn.get(k);
201      for (T n : nodes) {
202        String dotted = m_nodesFinished.contains(k) ? "style=dotted" : "";
203        result.append("  " + getName(k) + " -> " + getName(n) + " [dir=back " + dotted + "]\n");
204      }
205    }
206    result.append("}\n");
207
208    return result.toString();
209  }
210
211  public ListMultiMap<T, T> getEdges() {
212    return m_dependingOn;
213  }
214
215}
216