001: package org.testng.internal;
002:
003: import java.util.ArrayList;
004: import java.util.Collection;
005: import java.util.HashMap;
006: import java.util.List;
007: import java.util.Map;
008: import java.util.Set;
009:
010: import org.testng.TestNGException;
011:
012: /**
013: * Simple graph class to implement topological sort (used to sort methods based on what groups
014: * they depend on).
015: *
016: * @author Cedric Beust, Aug 19, 2004
017: */
018: public class Graph<T extends Object> {
019: private static boolean m_verbose = false;
020: private Map<T, Node<T>> m_nodes = new HashMap<T, Node<T>>();
021: private List<T> m_strictlySortedNodes = null;
022:
023: // A map of nodes that are not the predecessors of any node
024: // (not needed for the algorithm but convenient to calculate
025: // the parallel/sequential lists in TestNG).
026: private Map<T, Node<T>> m_independentNodes = null;
027:
028: public void addNode(T tm) {
029: ppp("ADDING NODE " + tm + " " + tm.hashCode());
030: m_nodes.put(tm, new Node<T>(tm));
031: // Initially, all the nodes are put in the independent list as well
032: }
033:
034: /*private boolean hasBeenSorted() {
035: return null != m_strictlySortedNodes;
036: }*/
037:
038: public boolean isIndependent(T object) {
039: return m_independentNodes.containsKey(object);
040: }
041:
042: private Node<T> findNode(T object) {
043: return m_nodes.get(object);
044: }
045:
046: public void addPredecessor(T tm, T predecessor) {
047: Node<T> node = findNode(tm);
048: if (null == node) {
049: throw new TestNGException("Non-existing node: " + tm);
050: } else {
051: node.addPredecessor(predecessor);
052: // Remove these two nodes from the independent list
053: if (null == m_independentNodes) {
054: m_independentNodes = new HashMap<T, Node<T>>();
055: for (T k : m_nodes.keySet()) {
056: m_independentNodes.put(k, m_nodes.get(k));
057: }
058: }
059: m_independentNodes.remove(predecessor);
060: m_independentNodes.remove(tm);
061: ppp(" REMOVED " + predecessor
062: + " FROM INDEPENDENT OBJECTS");
063: }
064: }
065:
066: private Collection<Node<T>> getNodes() {
067: return m_nodes.values();
068: }
069:
070: /**
071: * @return All the nodes that don't have any order with each other.
072: */
073: public Set<T> getIndependentNodes() {
074: return m_independentNodes.keySet();
075: }
076:
077: /**
078: * @return All the nodes that have an order with each other, sorted
079: * in one of the valid sorts.
080: */
081: public List<T> getStrictlySortedNodes() {
082: return m_strictlySortedNodes;
083: }
084:
085: public void topologicalSort() {
086: ppp("================ SORTING");
087: m_strictlySortedNodes = new ArrayList<T>();
088: if (null == m_independentNodes) {
089: m_independentNodes = new HashMap<T, Node<T>>();
090: }
091:
092: //
093: // Clone the list of nodes but only keep those that are
094: // not independent.
095: //
096: List<Node<T>> nodes2 = new ArrayList<Node<T>>();
097: for (Node<T> n : getNodes()) {
098: if (!isIndependent((T) n.getObject())) {
099: ppp("ADDING FOR SORT: " + n.getObject());
100: nodes2.add(n.clone());
101: } else {
102: ppp("SKIPPING INDEPENDENT NODE " + n);
103: }
104: }
105:
106: //
107: // Sort
108: //
109: while (!nodes2.isEmpty()) {
110:
111: //
112: // Find all the nodes that don't have any predecessors, add
113: // them to the result and mark them for removal
114: //
115: Node<T> node = findNodeWithNoPredecessors(nodes2);
116: if (null == node) {
117: throw new TestNGException("Cyclic graph of methods");
118: } else {
119: m_strictlySortedNodes.add((T) node.getObject());
120: removeFromNodes(nodes2, node);
121: }
122: }
123:
124: ppp("=============== DONE SORTING");
125: if (m_verbose) {
126: dumpSortedNodes();
127: }
128: }
129:
130: private void dumpSortedNodes() {
131: System.out.println("====== SORTED NODES");
132: for (T n : m_strictlySortedNodes) {
133: System.out.println(" " + n);
134: }
135: System.out.println("====== END SORTED NODES");
136: }
137:
138: private void dumpGraph() {
139: System.out.println("====== GRAPH");
140: for (Node<T> n : m_nodes.values()) {
141: System.out.println(" " + n);
142: }
143: }
144:
145: /**
146: * Remove a node from a list of nodes and update the list of predecessors
147: * for all the remaining nodes.
148: */
149: private void removeFromNodes(List<Node<T>> nodes, Node<T> node) {
150: nodes.remove(node);
151: for (Node<T> n : nodes) {
152: n.removePredecessor(node.getObject());
153: }
154: }
155:
156: private static void ppp(String s) {
157: if (m_verbose) {
158: System.out.println("[Graph] " + s);
159: }
160: }
161:
162: private Node<T> findNodeWithNoPredecessors(List<Node<T>> nodes) {
163: for (Node<T> n : nodes) {
164: if (!n.hasPredecessors()) {
165: return n;
166: }
167: }
168:
169: return null;
170: }
171:
172: /**
173: * @param o
174: * @return A list of all the predecessors for o
175: */
176: public List<T> findPredecessors(T o) {
177: List<T> result = new ArrayList<T>();
178: // Locate the node
179: Node<T> node = findNode(o);
180:
181: if (null == node) {
182: throw new AssertionError("No such node: " + o);
183: } else {
184: List<Node<T>> nodesToWalk = new ArrayList<Node<T>>();
185:
186: // Found the nodes, now find all its predecessors
187: for (Node<T> n : getNodes()) {
188: T obj = n.getObject();
189: if (node.hasPredecessor(obj)) {
190: ppp("FOUND PREDECESSOR " + n);
191: if (!result.contains(obj)) {
192: result.add(0, obj);
193: nodesToWalk.add(n);
194: }
195: }
196: }
197:
198: // Add all the predecessors of the nodes we just found
199: for (Node<T> n : nodesToWalk) {
200: List<T> r = findPredecessors(n.getObject());
201: for (T obj : r) {
202: if (!result.contains(obj)) {
203: result.add(0, obj);
204: }
205: }
206: }
207: }
208:
209: return result;
210: }
211:
212: @Override
213: public String toString() {
214: StringBuffer result = new StringBuffer("[Graph ");
215: for (T node : m_nodes.keySet()) {
216: result.append(findNode(node)).append(" ");
217: }
218: result.append("]");
219:
220: return result.toString();
221: }
222:
223: /////
224: // class Node
225: //
226: static class Node<T> {
227: private T m_object = null;
228: private Map<T, T> m_predecessors = new HashMap<T, T>();
229:
230: public Node(T tm) {
231: m_object = tm;
232: }
233:
234: @Override
235: public Node<T> clone() {
236: Node<T> result = new Node<T>(m_object);
237: for (T pred : m_predecessors.values()) {
238: result.addPredecessor(pred);
239: }
240: return result;
241: }
242:
243: public T getObject() {
244: return m_object;
245: }
246:
247: public Map<T, T> getPredecessors() {
248: return m_predecessors;
249: }
250:
251: /**
252: *
253: * @return true if this predecessor was found and removed
254: */
255: public boolean removePredecessor(T o) {
256: boolean result = false;
257:
258: // dump();
259: T pred = m_predecessors.get(o);
260: if (null != pred) {
261: result = null != m_predecessors.remove(o);
262: if (result) {
263: ppp(" REMOVED PRED " + o + " FROM NODE "
264: + m_object);
265: } else {
266: ppp(" FAILED TO REMOVE PRED " + o + " FROM NODE "
267: + m_object);
268: }
269: }
270:
271: return result;
272: }
273:
274: private void dump() {
275: ppp(toString());
276: }
277:
278: @Override
279: public String toString() {
280: StringBuffer sb = new StringBuffer("[Node:" + m_object);
281: sb.append(" pred:");
282: for (T o : m_predecessors.values()) {
283: sb.append(" " + o.toString());
284: }
285: sb.append("]");
286: String result = sb.toString();
287: return result;
288: }
289:
290: public void addPredecessor(T tm) {
291: ppp(" ADDING PREDECESSOR FOR " + m_object + " ==> " + tm);
292: m_predecessors.put(tm, tm);
293: }
294:
295: public boolean hasPredecessors() {
296: return m_predecessors.size() > 0;
297: }
298:
299: public boolean hasPredecessor(T m) {
300: return m_predecessors.containsKey(m);
301: }
302: }
303:
304: //
305: // class Node
306: /////
307:
308: public static void main(String[] argv) {
309: Graph<String> g = new Graph<String>();
310: g.addNode("3");
311: g.addNode("1");
312: g.addNode("2.2");
313: g.addNode("independent");
314: g.addNode("2.1");
315: g.addNode("2");
316:
317: // 1 -> 2.1, 2.2, 2.3 --> 3
318: g.addPredecessor("3", "2");
319: g.addPredecessor("3", "2.1");
320: g.addPredecessor("3", "2.2");
321: g.addPredecessor("2", "1");
322: g.addPredecessor("2.1", "1");
323: g.addPredecessor("2.2", "1");
324:
325: g.topologicalSort();
326:
327: List<String> l = g.getStrictlySortedNodes();
328: for (String s : l) {
329: System.out.println(" " + s);
330: }
331: int i = 0;
332: assert "1".equals(l.get(i));
333: i++;
334: assert "2".equals(l.get(i)) || "2.1".equals(l.get(i))
335: || "2.2".equals(l.get(i));
336: i++;
337: assert "2".equals(l.get(i)) || "2.1".equals(l.get(i))
338: || "2.2".equals(l.get(i));
339: i++;
340: assert "2".equals(l.get(i)) || "2.1".equals(l.get(i))
341: || "2.2".equals(l.get(i));
342: i++;
343: assert "3".equals(l.get(i));
344:
345: assert 1 == g.getIndependentNodes().size();
346:
347: //
348: // Test findPredecessors
349: //
350: ppp("GRAPH:" + g);
351: {
352: List<String> predecessors = g.findPredecessors("2");
353: assert predecessors.size() == 1;
354: assert predecessors.get(0).equals("1");
355: }
356:
357: {
358: List<String> predecessors = g.findPredecessors("3");
359: assert predecessors.size() == 4;
360: assert predecessors.get(0).equals("1");
361: assert predecessors.get(1).equals("2.1")
362: || predecessors.get(2).equals("2.2")
363: || predecessors.get(2).equals("2");
364: assert predecessors.get(2).equals("2.1")
365: || predecessors.get(2).equals("2.2")
366: || predecessors.get(2).equals("2");
367: assert predecessors.get(3).equals("2.1")
368: || predecessors.get(2).equals("2.2")
369: || predecessors.get(2).equals("2");
370: }
371:
372: ppp("TESTS PASSED");
373: }
374:
375: }
|