17dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beustpackage org.testng.internal; 27dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust 30ffd72689da00f24bb537d458c813b60ac8ceed5Cédric Beustimport org.testng.collections.ListMultiMap; 472ba60721cef0211f28f77078992858c27c97df0Cédric Beustimport org.testng.collections.Lists; 50ffd72689da00f24bb537d458c813b60ac8ceed5Cédric Beustimport org.testng.collections.Maps; 6e9a829e47a3f321807f9f3b6a15ec98ab6e22b98Julien Herrimport org.testng.collections.Sets; 77dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust 8d100d7188d4997b041c8c144876c9932a749485cCédric Beustimport java.util.Collection; 9cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beustimport java.util.Collections; 10cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beustimport java.util.Comparator; 117dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beustimport java.util.List; 12859c3c642255b01446a924d9a6d5f9816499acc6Cédric Beustimport java.util.Map; 137dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beustimport java.util.Set; 147dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust 157dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust/** 167dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust * Representation of the graph of methods. 177dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust */ 18d100d7188d4997b041c8c144876c9932a749485cCédric Beustpublic class DynamicGraph<T> { 19cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust private static final boolean DEBUG = false; 20cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust 21747a7142d6192fce94a1b2a6cf2ad376946b7e8eJulien Herr private List<T> m_nodesReady = Lists.newArrayList(); 22747a7142d6192fce94a1b2a6cf2ad376946b7e8eJulien Herr private List<T> m_nodesRunning = Lists.newArrayList(); 23747a7142d6192fce94a1b2a6cf2ad376946b7e8eJulien Herr private List<T> m_nodesFinished = Lists.newArrayList(); 24a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust 25cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust private Comparator<? super T> m_nodeComparator = null; 2681b9582101c1c347601618e6f0e63d3fda270022Cédric Beust 270ffd72689da00f24bb537d458c813b60ac8ceed5Cédric Beust private ListMultiMap<T, T> m_dependedUpon = Maps.newListMultiMap(); 280ffd72689da00f24bb537d458c813b60ac8ceed5Cédric Beust private ListMultiMap<T, T> m_dependingOn = Maps.newListMultiMap(); 29d100d7188d4997b041c8c144876c9932a749485cCédric Beust 30d100d7188d4997b041c8c144876c9932a749485cCédric Beust public static enum Status { 31d100d7188d4997b041c8c144876c9932a749485cCédric Beust READY, RUNNING, FINISHED 3281b9582101c1c347601618e6f0e63d3fda270022Cédric Beust } 337dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust 346c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust /** 35cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust * Define a comparator for the nodes of this graph, which will be used 36cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust * to order the free nodes when they are asked. 37cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust */ 38cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust public void setComparator(Comparator<? super T> c) { 39cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust m_nodeComparator = c; 40cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust } 41cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust 42cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust /** 436c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust * Add a node to the graph. 446c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust */ 457dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust public void addNode(T node) { 4681b9582101c1c347601618e6f0e63d3fda270022Cédric Beust m_nodesReady.add(node); 477dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust } 487dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust 496c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust /** 50747a7142d6192fce94a1b2a6cf2ad376946b7e8eJulien Herr * Add an edge between two nodes. 516c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust */ 527dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust public void addEdge(T from, T to) { 537dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust m_dependingOn.put(to, from); 547dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust m_dependedUpon.put(from, to); 557dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust } 567dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust 576c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust /** 586c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust * @return a set of all the nodes that don't depend on any other nodes. 596c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust */ 60cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust public List<T> getFreeNodes() { 61cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust List<T> result = Lists.newArrayList(); 6281b9582101c1c347601618e6f0e63d3fda270022Cédric Beust for (T m : m_nodesReady) { 63d4a501c03fc84a6b8ca1824ca32133044f37094dCédric Beust // A node is free if... 64d4a501c03fc84a6b8ca1824ca32133044f37094dCédric Beust 65859c3c642255b01446a924d9a6d5f9816499acc6Cédric Beust List<T> du = m_dependedUpon.get(m); 66d4a501c03fc84a6b8ca1824ca32133044f37094dCédric Beust // - no other nodes depend on it 670f7e671c94aeedee2fbc796b3318d44b0297b6cdnullin if (!m_dependedUpon.containsKey(m)) { 680f7e671c94aeedee2fbc796b3318d44b0297b6cdnullin result.add(m); 69859c3c642255b01446a924d9a6d5f9816499acc6Cédric Beust } else if (getUnfinishedNodes(du).size() == 0) { 700f7e671c94aeedee2fbc796b3318d44b0297b6cdnullin result.add(m); 710f7e671c94aeedee2fbc796b3318d44b0297b6cdnullin } 727dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust } 737e0abddc1ebbf548ebdf6e7cf4366e90f49c2eccCédric Beust 747e0abddc1ebbf548ebdf6e7cf4366e90f49c2eccCédric Beust // Sort the free nodes if requested (e.g. priorities) 757e0abddc1ebbf548ebdf6e7cf4366e90f49c2eccCédric Beust if (result != null && ! result.isEmpty()) { 767e0abddc1ebbf548ebdf6e7cf4366e90f49c2eccCédric Beust if (m_nodeComparator != null) { 777e0abddc1ebbf548ebdf6e7cf4366e90f49c2eccCédric Beust Collections.sort(result, m_nodeComparator); 787e0abddc1ebbf548ebdf6e7cf4366e90f49c2eccCédric Beust ppp("Nodes after sorting:" + result.get(0)); 797e0abddc1ebbf548ebdf6e7cf4366e90f49c2eccCédric Beust } 80cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust } 817e0abddc1ebbf548ebdf6e7cf4366e90f49c2eccCédric Beust 827dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust return result; 837dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust } 847dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust 856c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust /** 866c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust * @return a list of all the nodes that have a status other than FINISHED. 876c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust */ 88d100d7188d4997b041c8c144876c9932a749485cCédric Beust private Collection<? extends T> getUnfinishedNodes(List<T> nodes) { 89d100d7188d4997b041c8c144876c9932a749485cCédric Beust Set<T> result = Sets.newHashSet(); 9081b9582101c1c347601618e6f0e63d3fda270022Cédric Beust for (T node : nodes) { 910f7e671c94aeedee2fbc796b3318d44b0297b6cdnullin if (m_nodesReady.contains(node) || m_nodesRunning.contains(node)) { 920f7e671c94aeedee2fbc796b3318d44b0297b6cdnullin result.add(node); 930f7e671c94aeedee2fbc796b3318d44b0297b6cdnullin } 94d100d7188d4997b041c8c144876c9932a749485cCédric Beust } 95d100d7188d4997b041c8c144876c9932a749485cCédric Beust return result; 967dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust } 977dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust 986c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust /** 996c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust * Set the status for a set of nodes. 1006c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust */ 101d100d7188d4997b041c8c144876c9932a749485cCédric Beust public void setStatus(Collection<T> nodes, Status status) { 102d100d7188d4997b041c8c144876c9932a749485cCédric Beust for (T n : nodes) { 103d100d7188d4997b041c8c144876c9932a749485cCédric Beust setStatus(n, status); 104d100d7188d4997b041c8c144876c9932a749485cCédric Beust } 105d100d7188d4997b041c8c144876c9932a749485cCédric Beust } 106d100d7188d4997b041c8c144876c9932a749485cCédric Beust 1076c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust /** 1086c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust * Set the status for a node. 1096c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust */ 110d100d7188d4997b041c8c144876c9932a749485cCédric Beust public void setStatus(T node, Status status) { 11181b9582101c1c347601618e6f0e63d3fda270022Cédric Beust removeNode(node); 11281b9582101c1c347601618e6f0e63d3fda270022Cédric Beust switch(status) { 11381b9582101c1c347601618e6f0e63d3fda270022Cédric Beust case READY: m_nodesReady.add(node); break; 11481b9582101c1c347601618e6f0e63d3fda270022Cédric Beust case RUNNING: m_nodesRunning.add(node); break; 11581b9582101c1c347601618e6f0e63d3fda270022Cédric Beust case FINISHED: m_nodesFinished.add(node); break; 11681b9582101c1c347601618e6f0e63d3fda270022Cédric Beust default: throw new IllegalArgumentException(); 11781b9582101c1c347601618e6f0e63d3fda270022Cédric Beust } 11881b9582101c1c347601618e6f0e63d3fda270022Cédric Beust } 11981b9582101c1c347601618e6f0e63d3fda270022Cédric Beust 12081b9582101c1c347601618e6f0e63d3fda270022Cédric Beust private void removeNode(T node) { 12181b9582101c1c347601618e6f0e63d3fda270022Cédric Beust if (!m_nodesReady.remove(node)) { 12281b9582101c1c347601618e6f0e63d3fda270022Cédric Beust if (!m_nodesRunning.remove(node)) { 12381b9582101c1c347601618e6f0e63d3fda270022Cédric Beust m_nodesFinished.remove(node); 12481b9582101c1c347601618e6f0e63d3fda270022Cédric Beust } 12581b9582101c1c347601618e6f0e63d3fda270022Cédric Beust } 1261d7ff8cb575dec704d7f04d3af1c0abced6bd0dcCédric Beust } 127a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust 1286c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust /** 1296c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust * @return the number of nodes in this graph. 1306c8ca81bdb931a7dedab1d30b60fb7381ac3f868Cédric Beust */ 131a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust public int getNodeCount() { 13281b9582101c1c347601618e6f0e63d3fda270022Cédric Beust int result = m_nodesReady.size() + m_nodesRunning.size() + m_nodesFinished.size(); 13381b9582101c1c347601618e6f0e63d3fda270022Cédric Beust return result; 134a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust } 135a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust 13681b9582101c1c347601618e6f0e63d3fda270022Cédric Beust public int getNodeCountWithStatus(Status status) { 13781b9582101c1c347601618e6f0e63d3fda270022Cédric Beust switch(status) { 13881b9582101c1c347601618e6f0e63d3fda270022Cédric Beust case READY: return m_nodesReady.size(); 13981b9582101c1c347601618e6f0e63d3fda270022Cédric Beust case RUNNING: return m_nodesRunning.size(); 14081b9582101c1c347601618e6f0e63d3fda270022Cédric Beust case FINISHED: return m_nodesFinished.size(); 14181b9582101c1c347601618e6f0e63d3fda270022Cédric Beust default: throw new IllegalArgumentException(); 142a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust } 143a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust } 144a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust 14581b9582101c1c347601618e6f0e63d3fda270022Cédric Beust private static void ppp(String string) { 146a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust if (DEBUG) { 147a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust System.out.println(" [GroupThreadPoolExecutor] " + Thread.currentThread().getId() + " " 148a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust + string); 149a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust } 150a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust } 151a09103e6538f3bdcd46c289c614cea12ed3a9a8fCédric Beust 15281b9582101c1c347601618e6f0e63d3fda270022Cédric Beust @Override 15381b9582101c1c347601618e6f0e63d3fda270022Cédric Beust public String toString() { 15481b9582101c1c347601618e6f0e63d3fda270022Cédric Beust StringBuilder result = new StringBuilder("[DynamicGraph "); 15581b9582101c1c347601618e6f0e63d3fda270022Cédric Beust result.append("\n Ready:" + m_nodesReady); 15681b9582101c1c347601618e6f0e63d3fda270022Cédric Beust result.append("\n Running:" + m_nodesRunning); 15781b9582101c1c347601618e6f0e63d3fda270022Cédric Beust result.append("\n Finished:" + m_nodesFinished); 158859c3c642255b01446a924d9a6d5f9816499acc6Cédric Beust result.append("\n Edges:\n"); 159686e86e3395453eb841bce402bd8116a64b51655Julien Herr for (Map.Entry<T, List<T>> es : m_dependingOn.entrySet()) { 160859c3c642255b01446a924d9a6d5f9816499acc6Cédric Beust result.append(" " + es.getKey() + "\n"); 161859c3c642255b01446a924d9a6d5f9816499acc6Cédric Beust for (T t : es.getValue()) { 162859c3c642255b01446a924d9a6d5f9816499acc6Cédric Beust result.append(" " + t + "\n"); 163859c3c642255b01446a924d9a6d5f9816499acc6Cédric Beust } 164859c3c642255b01446a924d9a6d5f9816499acc6Cédric Beust } 16581b9582101c1c347601618e6f0e63d3fda270022Cédric Beust result.append("]"); 16681b9582101c1c347601618e6f0e63d3fda270022Cédric Beust return result.toString(); 16781b9582101c1c347601618e6f0e63d3fda270022Cédric Beust } 168e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust 169e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust private String getName(T t) { 170e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust String s = t.toString(); 171e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust int n1 = s.lastIndexOf('.') + 1; 172e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust int n2 = s.indexOf('('); 173e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust return s.substring(n1, n2); 174e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust } 175e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust 176d9f4b75b106b5e8548b980f7a51fc5070dd8662aCédric Beust /** 177d9f4b75b106b5e8548b980f7a51fc5070dd8662aCédric Beust * @return a .dot file (GraphViz) version of this graph. 178d9f4b75b106b5e8548b980f7a51fc5070dd8662aCédric Beust */ 179e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust public String toDot() { 180d9f4b75b106b5e8548b980f7a51fc5070dd8662aCédric Beust String FREE = "[style=filled color=yellow]"; 181d9f4b75b106b5e8548b980f7a51fc5070dd8662aCédric Beust String RUNNING = "[style=filled color=green]"; 182d9f4b75b106b5e8548b980f7a51fc5070dd8662aCédric Beust String FINISHED = "[style=filled color=grey]"; 183e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust StringBuilder result = new StringBuilder("digraph g {\n"); 184cc950e9c5f035c275e46d2e58901784e03b6959fCédric Beust List<T> freeNodes = getFreeNodes(); 185e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust String color; 186e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust for (T n : m_nodesReady) { 187d9f4b75b106b5e8548b980f7a51fc5070dd8662aCédric Beust color = freeNodes.contains(n) ? FREE : ""; 188e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust result.append(" " + getName(n) + color + "\n"); 189e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust } 190e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust for (T n : m_nodesRunning) { 1910f7e671c94aeedee2fbc796b3318d44b0297b6cdnullin color = freeNodes.contains(n) ? FREE : RUNNING; 192e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust result.append(" " + getName(n) + color + "\n"); 193e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust } 194e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust for (T n : m_nodesFinished) { 195d9f4b75b106b5e8548b980f7a51fc5070dd8662aCédric Beust result.append(" " + getName(n) + FINISHED+ "\n"); 196e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust } 197e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust result.append("\n"); 198e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust 199686e86e3395453eb841bce402bd8116a64b51655Julien Herr for (T k : m_dependingOn.keySet()) { 200e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust List<T> nodes = m_dependingOn.get(k); 201e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust for (T n : nodes) { 202e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust String dotted = m_nodesFinished.contains(k) ? "style=dotted" : ""; 203e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust result.append(" " + getName(k) + " -> " + getName(n) + " [dir=back " + dotted + "]\n"); 204e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust } 205e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust } 206e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust result.append("}\n"); 207e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust 208e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust return result.toString(); 209e7600490322b186042571fc3d8873eeeb6c2b433Cédric Beust } 210a17da98c9400d760ba306ed0d4017c9a4e64074fCédric Beust 211a17da98c9400d760ba306ed0d4017c9a4e64074fCédric Beust public ListMultiMap<T, T> getEdges() { 212a17da98c9400d760ba306ed0d4017c9a4e64074fCédric Beust return m_dependingOn; 213a17da98c9400d760ba306ed0d4017c9a4e64074fCédric Beust } 2147e0abddc1ebbf548ebdf6e7cf4366e90f49c2eccCédric Beust 2157dffa3bb2745b88b56757824d3dec63ddd16d33fCédric Beust} 216