001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.openide.util;
043:
044: import java.io.*;
045: import java.util.*;
046:
047: import org.netbeans.junit.*;
048: import junit.textui.TestRunner;
049:
050: /** Test Utilities.topologicalSort.
051: * @author Jesse Glick
052: */
053: public class UtilitiesTopologicalSortTest extends NbTestCase {
054:
055: public UtilitiesTopologicalSortTest(String name) {
056: super (name);
057: }
058:
059: public static void main(String[] args) {
060: TestRunner.run(new NbTestSuite(
061: UtilitiesTopologicalSortTest.class));
062: }
063:
064: /**
065: * @see "#27286"
066: */
067: public void testTopologicalSort() throws Exception {
068: Collection c = Arrays.asList(new String[] { "a", "b", "c", "d",
069: "e", "f" });
070: Map m = new HashMap();
071: m.put("f", Collections.singletonList("a"));
072: List l = Utilities.topologicalSort(c, m);
073: assertNotNull(l);
074: assertTrue(l.indexOf("f") < l.indexOf("a"));
075: m.put("e", Collections.singletonList("b"));
076: l = Utilities.topologicalSort(c, m);
077: assertNotNull(l);
078: assertTrue(l.indexOf("f") < l.indexOf("a"));
079: assertTrue(l.indexOf("e") < l.indexOf("b"));
080: m.put("b", Collections.singletonList("a"));
081: l = Utilities.topologicalSort(c, m);
082: assertNotNull(l);
083: assertTrue(l.indexOf("f") < l.indexOf("a"));
084: assertTrue(l.indexOf("e") < l.indexOf("b"));
085: assertTrue(l.indexOf("b") < l.indexOf("a"));
086: // Test that it is modifiable:
087: l.add("foo");
088: Collections.reverse(l);
089: // Test cycles:
090: m.put("a", Collections.singletonList("e"));
091: try {
092: l = Utilities.topologicalSort(c, m);
093: fail("Should throw an exception");
094: } catch (TopologicalSortException ex) {
095: }
096: }
097:
098: public void testTopologicalSortError() throws Exception {
099: Collection c = Arrays.asList(new String[] { "first", "a", "b",
100: "c", "d", "e", "f", "last" });
101: Map m = new HashMap();
102: // to make sure that not whole visited graph will be in the cycle
103: m.put("first", Collections.singletonList("f"));
104: m.put("last", Collections.singletonList("f"));
105:
106: m.put("f", Collections.singletonList("a"));
107: Utilities.topologicalSort(c, m); // does not throw an error
108: m.put("e", Collections.singletonList("b"));
109: Utilities.topologicalSort(c, m); // does not throw an error
110: m.put("b", Collections.singletonList("a"));
111: Utilities.topologicalSort(c, m); // does not throw an error
112: m.put("a", Collections.singletonList("e"));
113:
114: try {
115: Utilities.topologicalSort(c, m);
116: fail("Should throw an error");
117: } catch (TopologicalSortException ex) {
118: Set[] sets = ex.topologicalSets();
119:
120: assertEquals(
121: "There is one cycle of size 3, all other objects are sortable",
122: 6, sets.length);
123:
124: Set cycle = null;
125: for (int i = 0; i < sets.length; i++) {
126: if (sets[i].size() > 1) {
127: assertNull(
128: "There is just one unsortable component",
129: cycle);
130: cycle = sets[i];
131: } else {
132: assertEquals("Size is 1", 1, sets[i].size());
133: }
134: }
135:
136: assertTrue("a is there", cycle.contains("a"));
137: assertTrue("b is there", cycle.contains("b"));
138: assertTrue("e is there", cycle.contains("e"));
139: assertEquals("Three vertexes are in the cycle", 3, cycle
140: .size());
141:
142: assertBefore("first", "f", sets);
143: assertBefore("last", "f", sets);
144: assertBefore("f", "a", sets);
145: assertBefore("f", "b", sets);
146: assertBefore("f", "e", sets);
147:
148: List partial = ex.partialSort();
149: assertEquals("Has the same size as the original", c.size(),
150: partial.size());
151: assertBefore("first", "f", partial);
152: assertBefore("last", "f", partial);
153: assertBefore("f", "a", partial);
154: assertBefore("f", "b", partial);
155: assertBefore("f", "e", partial);
156: }
157: }
158:
159: public void testMoreCycles() throws Exception {
160: Collection c = Arrays.asList(new String[] { "first", "a", "b",
161: "c", "d", "e", "f", "last" });
162: Map m = new HashMap();
163: // to make sure that not whole visited graph will be in the cycle
164:
165: m.put("a", Collections.singletonList("a")); // self cycle
166:
167: // cycle 2
168: m.put("b", Collections.singletonList("c"));
169: m.put("c", Collections.singletonList("b"));
170:
171: // cycle 3
172: m.put("d", Collections.singletonList("e"));
173: m.put("e", Collections.singletonList("f"));
174: m.put("f", Collections.singletonList("d"));
175:
176: Collection sizes = new ArrayList();
177:
178: try {
179: Utilities.topologicalSort(c, m);
180: fail("Should throw an error");
181: } catch (TopologicalSortException ex) {
182: Set[] sets = ex.topologicalSets();
183: for (int i = 0; i < sets.length; i++) {
184: sizes.add(new Integer(sets[i].size()));
185: }
186:
187: assertEquals("There were three cycles plus first+last", 5,
188: sizes.size());
189: assertTrue("One of size 1", sizes.contains(new Integer(1)));
190: assertTrue("One of size 2", sizes.contains(new Integer(2)));
191: assertTrue("One of size 3", sizes.contains(new Integer(3)));
192:
193: sets = ex.unsortableSets();
194: assertEquals("Three cycles", 3, sets.length);
195: }
196: }
197:
198: public void testDetectSelfCycle() throws Exception {
199: Collection c = Arrays.asList(new String[] { "a", "b" });
200: Map m = new HashMap();
201:
202: m.put("a", Arrays.asList(new String[] { "a" }));
203: m.put("b", Arrays.asList(new String[] { "a" }));
204:
205: try {
206: Utilities.topologicalSort(c, m);
207: fail("Definitively there is a cycle");
208: } catch (TopologicalSortException ex) {
209: Set[] sets = ex.unsortableSets();
210:
211: assertEquals("One cycle", 1, sets.length);
212: assertEquals("Contains one item", 1, sets[0].size());
213: assertTrue("Contains a", sets[0].contains("a"));
214: }
215: }
216:
217: public void testFindLongestCycle() throws Exception {
218: Collection c = Arrays.asList(new String[] { "a", "b", "c", "d",
219: "e", "f" });
220: Map m = new HashMap();
221: // to make sure that not whole visited graph will be in the cycle
222:
223: m.put("a", Arrays.asList(new String[] { "b", "c" }));
224: m.put("b", Arrays.asList(new String[] { "a", "d" }));
225: m.put("c", Arrays.asList(new String[] { "a", "d" }));
226: m.put("d", Arrays.asList(new String[] { "b", "c", "e" }));
227: m.put("f", Arrays.asList(new String[] { "a" }));
228:
229: try {
230: Utilities.topologicalSort(c, m);
231: fail("Definitively there is a cycle");
232: } catch (TopologicalSortException ex) {
233: Set[] sets = ex.topologicalSets();
234:
235: assertEquals("There is one cycle and e+f", 3, sets.length);
236:
237: assertBefore("f", "a", sets);
238: assertBefore("f", "b", sets);
239: assertBefore("f", "c", sets);
240: assertBefore("f", "d", sets);
241: assertBefore("f", "e", sets);
242:
243: assertBefore("a", "e", sets);
244: assertBefore("b", "e", sets);
245: assertBefore("c", "e", sets);
246: assertBefore("d", "e", sets);
247:
248: assertEquals("set of f", 1, sets[0].size());
249: assertEquals("set of a,b,c,d", 4, sets[1].size());
250: assertEquals("set of e", 1, sets[2].size());
251: }
252: }
253:
254: public void testStability() throws Exception {
255: Collection c = Arrays.asList(new String[] { "a", "b", "c", "d",
256: "e", "f" });
257: assertEquals(c, Utilities.topologicalSort(c,
258: Collections.EMPTY_MAP));
259: Map m = new HashMap();
260: m.put("e", Collections.singletonList("d"));
261: List l = Utilities.topologicalSort(c, m);
262: assertNotNull(l);
263: assertEquals(Arrays.asList(new String[] { "a", "b", "c" }), l
264: .subList(0, 3));
265: m = new HashMap();
266: m.put("c", Collections.singletonList("a"));
267: l = Utilities.topologicalSort(c, m);
268: assertNotNull(l);
269: assertEquals(Arrays.asList(new String[] { "d", "e", "f" }), l
270: .subList(3, 6));
271: m = new HashMap();
272: m.put("a", Collections.singletonList("f"));
273: assertEquals(c, Utilities.topologicalSort(c, m));
274: m.put("a", Collections.singletonList("b"));
275: assertEquals(c, Utilities.topologicalSort(c, m));
276: m.put("b", Collections.singletonList("f"));
277: assertEquals(c, Utilities.topologicalSort(c, m));
278: m.put("c", Collections.singletonList("e"));
279: assertEquals(c, Utilities.topologicalSort(c, m));
280: m.put("a", Collections.singletonList("e"));
281: assertEquals(c, Utilities.topologicalSort(c, m));
282: /* Does not work - oh well:
283: c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "x", "y"});
284: m = new HashMap();
285: m.put("c", Arrays.asList(new String[] {"x", "y"}));
286: m.put("x", Collections.singletonList("d"));
287: m.put("y", Collections.singletonList("d"));
288: System.err.println("-----");
289: l = Utilities.topologicalSort(c, m);
290: assertNotNull(l);
291: System.err.println(l);
292: assertEquals(Arrays.asList(new String[] {"a", "b", "c"}), l.subList(0, 3));
293: assertEquals(Arrays.asList(new String[] {"d", "e"}), l.subList(5, 7));
294: */
295: }
296:
297: public void testTopologicalSortCompile() throws Exception {
298: Collection<String> c = new ArrayList<String>();
299: Map<Object, Collection<String>> edges = new HashMap<Object, Collection<String>>();
300:
301: List<String> result = Utilities.topologicalSort(c, edges);
302: }
303:
304: public void testTopologicalSortCompile2() throws Exception {
305: Collection<String> c = new ArrayList<String>();
306: Map<Object, List<String>> edges = new HashMap<Object, List<String>>();
307:
308: List<String> result = Utilities.topologicalSort(c, edges);
309: }
310:
311: public void testTopologicalSortCompile3() throws Exception {
312: Collection<Number> c = new ArrayList<Number>();
313: Map<Object, List<Integer>> edges = new HashMap<Object, List<Integer>>();
314:
315: List<Number> result = Utilities.topologicalSort(c, edges);
316: }
317:
318: public void testTopologicalSortIssue101820() throws Exception {
319: Object a = "a";
320: Object b = "b";
321:
322: Map<Object, Collection<Object>> deps = new HashMap<Object, Collection<Object>>();
323:
324: deps.put(a, Arrays.asList(b));
325: deps.put(b, Arrays.asList());
326:
327: assertEquals(Arrays.asList(a), Utilities.topologicalSort(Arrays
328: .asList(a), deps));
329: }
330:
331: public void testErrorReporting() throws Exception {
332: Collection c = Arrays.asList(new String[] { "a", "b", "c", "d",
333: "e", "f" });
334: Map m = new HashMap();
335: m.put("a", Arrays.asList(new String[] { "a" }));
336: m.put("b", Arrays.asList(new String[] { "c" }));
337: m.put("c", Arrays.asList(new String[] { "b" }));
338:
339: try {
340: Utilities.topologicalSort(c, m);
341: fail("Unsortable");
342: } catch (TopologicalSortException ex) {
343: StringWriter w = new StringWriter();
344: ex.printStackTrace(new PrintWriter(w, true));
345:
346: ByteArrayOutputStream s = new ByteArrayOutputStream();
347: ex.printStackTrace(new java.io.PrintStream(s, true));
348:
349: byte[] warr = w.toString().getBytes("utf-8");
350: byte[] sarr = s.toByteArray();
351:
352: assertTrue("Both messages should be the same", Arrays
353: .equals(warr, sarr));
354:
355: {
356: String msg = w.toString();
357:
358: int cnt = 0;
359: int indx = -1;
360: for (;;) {
361: indx = msg.indexOf("Conflict #", indx + 1);
362: if (indx == -1)
363: break;
364: cnt++;
365: }
366:
367: assertEquals("There is the same number of lines with "
368: + "'Conflict #' as unsortable sets", cnt, ex
369: .unsortableSets().length);
370: }
371:
372: {
373: String msg = ex.getMessage();
374:
375: int cnt = 0;
376: int indx = -1;
377: for (;;) {
378: indx = msg.indexOf("Conflict #", indx + 1);
379: if (indx == -1)
380: break;
381: cnt++;
382: }
383:
384: assertEquals("There is the same number of lines with "
385: + "'Conflict #' as unsortable sets", cnt, ex
386: .unsortableSets().length);
387: }
388:
389: }
390:
391: }
392:
393: private static void assertBefore(String first, String second,
394: Collection c) {
395: assertBefore(first, second, c, false);
396: }
397:
398: private static void assertBefore(String first, String second,
399: Set[] sets) {
400: assertBefore(first, second, Arrays.asList(sets), true);
401: }
402:
403: private static void assertBefore(String first, String second,
404: Collection c, boolean useSets) {
405: Iterator it = c.iterator();
406: boolean wasFirst = false;
407: boolean wasSecond = false;
408: while (it.hasNext()) {
409: Object obj = it.next();
410:
411: if (useSets ? ((Set) obj).contains(second) : obj == second) {
412: assertTrue("[" + second + "] found before [" + first
413: + "] in " + c, wasFirst);
414: wasSecond = true;
415: }
416:
417: if (useSets ? ((Set) obj).contains(first) : obj == first) {
418: wasFirst = true;
419: }
420: }
421:
422: assertTrue("[" + first + "] not found", wasFirst);
423: assertTrue("[" + second + "] not found", wasSecond);
424: }
425: }
|