|
1
19
20 package org.openide.util;
21
22 import java.io.*;
23 import java.util.*;
24
25 import org.netbeans.junit.*;
26 import junit.textui.TestRunner;
27
28
31 public class UtilitiesTopologicalSortTest extends NbTestCase {
32
33 public UtilitiesTopologicalSortTest(String  name) {
34 super(name);
35 }
36
37 public static void main(String [] args) {
38 TestRunner.run(new NbTestSuite(UtilitiesTopologicalSortTest.class));
39 }
40
41
44 public void testTopologicalSort() throws Exception {
45 Collection c = Arrays.asList(new String [] {"a", "b", "c", "d", "e", "f"});
46 Map m = new HashMap();
47 m.put("f", Collections.singletonList("a"));
48 List l = Utilities.topologicalSort(c, m);
49 assertNotNull(l);
50 assertTrue(l.indexOf("f") < l.indexOf("a"));
51 m.put("e", Collections.singletonList("b"));
52 l = Utilities.topologicalSort(c, m);
53 assertNotNull(l);
54 assertTrue(l.indexOf("f") < l.indexOf("a"));
55 assertTrue(l.indexOf("e") < l.indexOf("b"));
56 m.put("b", Collections.singletonList("a"));
57 l = Utilities.topologicalSort(c, m);
58 assertNotNull(l);
59 assertTrue(l.indexOf("f") < l.indexOf("a"));
60 assertTrue(l.indexOf("e") < l.indexOf("b"));
61 assertTrue(l.indexOf("b") < l.indexOf("a"));
62 l.add("foo");
64 Collections.reverse(l);
65 m.put("a", Collections.singletonList("e"));
67 try {
68 l = Utilities.topologicalSort(c, m);
69 fail ("Should throw an exception");
70 } catch (TopologicalSortException ex) {
71 }
72 }
73
74 public void testTopologicalSortError() throws Exception {
75 Collection c = Arrays.asList(new String [] {"first", "a", "b", "c", "d", "e", "f", "last"});
76 Map m = new HashMap();
77 m.put("first", Collections.singletonList ("f"));
79 m.put("last", Collections.singletonList ("f"));
80
81
82 m.put("f", Collections.singletonList("a"));
83 Utilities.topologicalSort (c, m); m.put("e", Collections.singletonList("b"));
85 Utilities.topologicalSort (c, m); m.put("b", Collections.singletonList("a"));
87 Utilities.topologicalSort (c, m); m.put("a", Collections.singletonList("e"));
89
90 try {
91 Utilities.topologicalSort (c, m);
92 fail ("Should throw an error");
93 } catch (TopologicalSortException ex) {
94 Set[] sets = ex.topologicalSets();
95
96 assertEquals ("There is one cycle of size 3, all other objects are sortable", 6, sets.length);
97
98 Set cycle = null;
99 for (int i = 0; i < sets.length; i++) {
100 if (sets[i].size () > 1) {
101 assertNull ("There is just one unsortable component", cycle);
102 cycle = sets[i];
103 } else {
104 assertEquals ("Size is 1", 1, sets[i].size ());
105 }
106 }
107
108 assertTrue ("a is there", cycle.contains ("a"));
109 assertTrue ("b is there", cycle.contains ("b"));
110 assertTrue ("e is there", cycle.contains ("e"));
111 assertEquals ("Three vertexes are in the cycle", 3, cycle.size ());
112
113 assertBefore ("first", "f", sets);
114 assertBefore ("last", "f", sets);
115 assertBefore ("f", "a", sets);
116 assertBefore ("f", "b", sets);
117 assertBefore ("f", "e", sets);
118
119 List partial = ex.partialSort ();
120 assertEquals ("Has the same size as the original", c.size (), partial.size ());
121 assertBefore ("first", "f", partial);
122 assertBefore ("last", "f", partial);
123 assertBefore ("f", "a", partial);
124 assertBefore ("f", "b", partial);
125 assertBefore ("f", "e", partial);
126 }
127 }
128
129 public void testMoreCycles () throws Exception {
130 Collection c = Arrays.asList(new String [] {"first", "a", "b", "c", "d", "e", "f", "last"});
131 Map m = new HashMap();
132
134 m.put ("a", Collections.singletonList ("a"));
136 m.put ("b", Collections.singletonList ("c"));
138 m.put ("c", Collections.singletonList ("b"));
139
140 m.put ("d", Collections.singletonList ("e"));
142 m.put ("e", Collections.singletonList ("f"));
143 m.put ("f", Collections.singletonList ("d"));
144
145 Collection sizes = new ArrayList ();
146
147 try {
148 Utilities.topologicalSort (c, m);
149 fail ("Should throw an error");
150 } catch (TopologicalSortException ex) {
151 Set[] sets = ex.topologicalSets();
152 for (int i = 0; i < sets.length; i++) {
153 sizes.add (new Integer (sets[i].size ()));
154 }
155
156 assertEquals ("There were three cycles plus first+last", 5, sizes.size ());
157 assertTrue ("One of size 1", sizes.contains (new Integer (1)));
158 assertTrue ("One of size 2", sizes.contains (new Integer (2)));
159 assertTrue ("One of size 3", sizes.contains (new Integer (3)));
160
161 sets = ex.unsortableSets();
162 assertEquals ("Three cycles", 3, sets.length);
163 }
164 }
165
166 public void testDetectSelfCycle () throws Exception {
167 Collection c = Arrays.asList(new String [] {"a", "b" });
168 Map m = new HashMap();
169
170 m.put ("a", Arrays.asList (new String [] { "a" }));
171 m.put ("b", Arrays.asList (new String [] { "a" }));
172
173 try {
174 Utilities.topologicalSort (c, m);
175 fail ("Definitively there is a cycle");
176 } catch (TopologicalSortException ex) {
177 Set[] sets = ex.unsortableSets ();
178
179 assertEquals ("One cycle", 1, sets.length);
180 assertEquals ("Contains one item", 1, sets[0].size ());
181 assertTrue ("Contains a", sets[0].contains ("a"));
182 }
183 }
184
185 public void testFindLongestCycle () throws Exception {
186 Collection c = Arrays.asList(new String [] {"a", "b", "c", "d", "e", "f" });
187 Map m = new HashMap();
188
190 m.put ("a", Arrays.asList (new String [] { "b", "c" }));
191 m.put ("b", Arrays.asList (new String [] { "a", "d" }));
192 m.put ("c", Arrays.asList (new String [] { "a", "d" }));
193 m.put ("d", Arrays.asList (new String [] { "b", "c", "e" }));
194 m.put ("f", Arrays.asList (new String [] { "a" }));
195
196 try {
197 Utilities.topologicalSort (c, m);
198 fail ("Definitively there is a cycle");
199 } catch (TopologicalSortException ex) {
200 Set[] sets = ex.topologicalSets();
201
202 assertEquals ("There is one cycle and e+f", 3, sets.length);
203
204 assertBefore ("f", "a", sets);
205 assertBefore ("f", "b", sets);
206 assertBefore ("f", "c", sets);
207 assertBefore ("f", "d", sets);
208 assertBefore ("f", "e", sets);
209
210 assertBefore ("a", "e", sets);
211 assertBefore ("b", "e", sets);
212 assertBefore ("c", "e", sets);
213 assertBefore ("d", "e", sets);
214
215 assertEquals ("set of f", 1, sets[0].size ());
216 assertEquals ("set of a,b,c,d", 4, sets[1].size ());
217 assertEquals ("set of e", 1, sets[2].size ());
218 }
219 }
220
221 public void testStability() throws Exception {
222 Collection c = Arrays.asList(new String [] {"a", "b", "c", "d", "e", "f"});
223 assertEquals(c, Utilities.topologicalSort(c, Collections.EMPTY_MAP));
224 Map m = new HashMap();
225 m.put("e", Collections.singletonList("d"));
226 List l = Utilities.topologicalSort(c, m);
227 assertNotNull(l);
228 assertEquals(Arrays.asList(new String [] {"a", "b", "c"}), l.subList(0, 3));
229 m = new HashMap();
230 m.put("c", Collections.singletonList("a"));
231 l = Utilities.topologicalSort(c, m);
232 assertNotNull(l);
233 assertEquals(Arrays.asList(new String [] {"d", "e", "f"}), l.subList(3, 6));
234 m = new HashMap();
235 m.put("a", Collections.singletonList("f"));
236 assertEquals(c, Utilities.topologicalSort(c, m));
237 m.put("a", Collections.singletonList("b"));
238 assertEquals(c, Utilities.topologicalSort(c, m));
239 m.put("b", Collections.singletonList("f"));
240 assertEquals(c, Utilities.topologicalSort(c, m));
241 m.put("c", Collections.singletonList("e"));
242 assertEquals(c, Utilities.topologicalSort(c, m));
243 m.put("a", Collections.singletonList("e"));
244 assertEquals(c, Utilities.topologicalSort(c, m));
245
258 }
259 public void testTopologicalSortCompile() throws Exception {
260 Collection<String > c = new ArrayList<String >();
261 Map<Object , Collection<String >> edges = new HashMap<Object ,Collection<String >>();
262
263 List<String > result = Utilities.topologicalSort(c, edges);
264 }
265
266 public void testTopologicalSortCompile2() throws Exception {
267 Collection<String > c = new ArrayList<String >();
268 Map<Object , List<String >> edges = new HashMap<Object ,List<String >>();
269
270 List<String > result = Utilities.topologicalSort(c, edges);
271 }
272 public void testTopologicalSortCompile3() throws Exception {
273 Collection<Number > c = new ArrayList<Number >();
274 Map<Object , List<Integer >> edges = new HashMap<Object ,List<Integer >>();
275
276 List<Number > result = Utilities.topologicalSort(c, edges);
277 }
278 public void testErrorReporting () throws Exception {
279 Collection c = Arrays.asList(new String [] {"a", "b", "c", "d", "e", "f"});
280 Map m = new HashMap ();
281 m.put ("a", Arrays.asList (new String [] { "a" }));
282 m.put ("b", Arrays.asList (new String [] { "c" }));
283 m.put ("c", Arrays.asList (new String [] { "b" }));
284
285 try {
286 Utilities.topologicalSort(c, m);
287 fail ("Unsortable");
288 } catch (TopologicalSortException ex) {
289 StringWriter w = new StringWriter ();
290 ex.printStackTrace (new PrintWriter (w, true));
291
292 ByteArrayOutputStream s = new ByteArrayOutputStream ();
293 ex.printStackTrace (new java.io.PrintStream (s, true));
294
295 byte[] warr = w.toString().getBytes("utf-8");
296 byte[] sarr = s.toByteArray();
297
298 assertTrue ("Both messages should be the same", Arrays.equals(warr, sarr));
299
300 String msg = w.toString();
301
302 int cnt = 0;
303 int indx = -1;
304 for (;;) {
305 indx = msg.indexOf("Conflict #", indx + 1);
306 if (indx == -1) break;
307 cnt++;
308 }
309
310 assertEquals ("There is the same number of lines with 'Conflict #' as unsortable sets", cnt, ex.unsortableSets().length);
311 }
312
313
314
315 }
316
317 private static void assertBefore (String first, String second, Collection c) {
318 assertBefore (first, second, c, false);
319 }
320
321 private static void assertBefore (String first, String second, Set[] sets) {
322 assertBefore (first, second, Arrays.asList (sets), true);
323 }
324
325 private static void assertBefore (String first, String second, Collection c, boolean useSets) {
326 Iterator it = c.iterator();
327 boolean wasFirst = false;
328 boolean wasSecond = false;
329 while (it.hasNext ()) {
330 Object obj = it.next ();
331
332 if (useSets ? ((Set)obj).contains (second) : obj == second) {
333 assertTrue ("[" + second + "] found before [" + first + "] in " + c, wasFirst);
334 wasSecond = true;
335 }
336
337 if (useSets ? ((Set)obj).contains (first) : obj == first) {
338 wasFirst = true;
339 }
340 }
341
342 assertTrue ("[" + first + "] not found", wasFirst);
343 assertTrue ("[" + second + "] not found", wasSecond);
344 }
345 }
346 |
Popular Tags |
Java API By Example, From Geeks To Geeks.