platform/openide.util/test/unit/src/org/openide/util/UtilitiesTopologicalSortTest.java - netbeans - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */

 package org.openide.util;

 import java.io.*;
 import java.util.*;

 import org.netbeans.junit.*;
 import junit.textui.TestRunner;

 /** Test BaseUtilities.topologicalSort.
  * @author Jesse Glick
  */
 public class UtilitiesTopologicalSortTest extends NbTestCase {

     public UtilitiesTopologicalSortTest(String name) {
         super(name);
     }

     public static void main(String[] args) {
         TestRunner.run(new NbTestSuite(UtilitiesTopologicalSortTest.class));
     }

     /**
      * @see "#27286"
      */
     public void testTopologicalSort() throws Exception {
         Collection c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "f"});
         Map m = new HashMap();
         m.put("f", Collections.singletonList("a"));
         List l = BaseUtilities.topologicalSort(c, m);
         assertNotNull(l);
         assertTrue(l.indexOf("f") < l.indexOf("a"));
         m.put("e", Collections.singletonList("b"));
         l = BaseUtilities.topologicalSort(c, m);
         assertNotNull(l);
         assertTrue(l.indexOf("f") < l.indexOf("a"));
         assertTrue(l.indexOf("e") < l.indexOf("b"));
         m.put("b", Collections.singletonList("a"));
         l = BaseUtilities.topologicalSort(c, m);
         assertNotNull(l);
         assertTrue(l.indexOf("f") < l.indexOf("a"));
         assertTrue(l.indexOf("e") < l.indexOf("b"));
         assertTrue(l.indexOf("b") < l.indexOf("a"));
         // Test that it is modifiable:
         l.add("foo");
         Collections.reverse(l);
         // Test cycles:
         m.put("a", Collections.singletonList("e"));
         try {
             l = BaseUtilities.topologicalSort(c, m);
             fail ("Should throw an exception");
         } catch (TopologicalSortException ex) {
         }
     }

     public void testTopologicalSortError() throws Exception {
         Collection c = Arrays.asList(new String[] {"first", "a", "b", "c", "d", "e", "f", "last"});
         Map m = new HashMap();
         // to make sure that not whole visited graph will be in the cycle
         m.put("first", Collections.singletonList ("f"));
         m.put("last", Collections.singletonList ("f"));


         m.put("f", Collections.singletonList("a"));
         BaseUtilities.topologicalSort (c, m); // does not throw an error
         m.put("e", Collections.singletonList("b"));
         BaseUtilities.topologicalSort (c, m); // does not throw an error
         m.put("b", Collections.singletonList("a"));
         BaseUtilities.topologicalSort (c, m); // does not throw an error
         m.put("a", Collections.singletonList("e"));

         try {
             BaseUtilities.topologicalSort (c, m);
             fail ("Should throw an error");
         } catch (TopologicalSortException ex) {
             Set[] sets = ex.topologicalSets();

             assertEquals ("There is one cycle of size 3, all other objects are sortable", 6, sets.length);

             Set cycle = null;
             for (int i = 0; i < sets.length; i++) {
                 if (sets[i].size () > 1) {
                     assertNull ("There is just one unsortable component", cycle);
                     cycle = sets[i];
                 } else {
                     assertEquals ("Size is 1", 1, sets[i].size ());
                 }
             }

             assertTrue ("a is there", cycle.contains ("a"));
             assertTrue ("b is there", cycle.contains ("b"));
             assertTrue ("e is there", cycle.contains ("e"));
             assertEquals ("Three vertexes are in the cycle", 3, cycle.size ());

             assertBefore ("first", "f", sets);
             assertBefore ("last", "f", sets);
             assertBefore ("f", "a", sets);
             assertBefore ("f", "b", sets);
             assertBefore ("f", "e", sets);

             List partial = ex.partialSort ();
             assertEquals ("Has the same size as the original", c.size (), partial.size ());
             assertBefore ("first", "f", partial);
             assertBefore ("last", "f", partial);
             assertBefore ("f", "a", partial);
             assertBefore ("f", "b", partial);
             assertBefore ("f", "e", partial);
         }
     }

     public void testMoreCycles () throws Exception {
         Collection c = Arrays.asList(new String[] {"first", "a", "b", "c", "d", "e", "f", "last"});
         Map m = new HashMap();
         // to make sure that not whole visited graph will be in the cycle

         m.put ("a", Collections.singletonList ("a")); // self cycle

         // cycle 2
         m.put ("b", Collections.singletonList ("c"));
         m.put ("c", Collections.singletonList ("b"));

         // cycle 3
         m.put ("d", Collections.singletonList ("e"));
         m.put ("e", Collections.singletonList ("f"));
         m.put ("f", Collections.singletonList ("d"));

         Collection sizes = new ArrayList ();

         try {
             BaseUtilities.topologicalSort (c, m);
             fail ("Should throw an error");
         } catch (TopologicalSortException ex) {
             Set[] sets = ex.topologicalSets();
             for (int i = 0; i < sets.length; i++) {
                 sizes.add (new Integer (sets[i].size ()));
             }

             assertEquals ("There were three cycles plus first+last", 5, sizes.size ());
             assertTrue ("One of size 1", sizes.contains (new Integer (1)));
             assertTrue ("One of size 2", sizes.contains (new Integer (2)));
             assertTrue ("One of size 3", sizes.contains (new Integer (3)));

             sets = ex.unsortableSets();
             assertEquals ("Three cycles", 3, sets.length);
         }
     }

     public void testDetectSelfCycle () throws Exception {
         Collection c = Arrays.asList(new String[] {"a", "b" });
         Map m = new HashMap();

         m.put ("a", Arrays.asList (new String[] { "a" }));
         m.put ("b", Arrays.asList (new String[] { "a" }));

         try {
             BaseUtilities.topologicalSort (c, m);
             fail ("Definitively there is a cycle");
         } catch (TopologicalSortException ex) {
             Set[] sets = ex.unsortableSets ();

             assertEquals ("One cycle", 1, sets.length);
             assertEquals ("Contains one item", 1, sets[0].size ());
             assertTrue ("Contains a", sets[0].contains ("a"));
         }
     }

     public void testFindLongestCycle () throws Exception {
         Collection c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "f" });
         Map m = new HashMap();
         // to make sure that not whole visited graph will be in the cycle

         m.put ("a", Arrays.asList (new String[] { "b", "c" }));
         m.put ("b", Arrays.asList (new String[] { "a", "d" }));
         m.put ("c", Arrays.asList (new String[] { "a", "d" }));
         m.put ("d", Arrays.asList (new String[] { "b", "c", "e" }));
         m.put ("f", Arrays.asList (new String[] { "a" }));

         try {
             BaseUtilities.topologicalSort (c, m);
             fail ("Definitively there is a cycle");
         } catch (TopologicalSortException ex) {
             Set[] sets = ex.topologicalSets();

             assertEquals ("There is one cycle and e+f", 3, sets.length);

             assertBefore ("f", "a", sets);
             assertBefore ("f", "b", sets);
             assertBefore ("f", "c", sets);
             assertBefore ("f", "d", sets);
             assertBefore ("f", "e", sets);

             assertBefore ("a", "e", sets);
             assertBefore ("b", "e", sets);
             assertBefore ("c", "e", sets);
             assertBefore ("d", "e", sets);

             assertEquals ("set of f", 1, sets[0].size ());
             assertEquals ("set of a,b,c,d", 4, sets[1].size ());
             assertEquals ("set of e", 1, sets[2].size ());
         }
     }

     public void testStability() throws Exception {
         Collection c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "f"});
         assertEquals(c, BaseUtilities.topologicalSort(c, Collections.EMPTY_MAP));
         Map m = new HashMap();
         m.put("e", Collections.singletonList("d"));
         List l = BaseUtilities.topologicalSort(c, m);
         assertNotNull(l);
         assertEquals(Arrays.asList(new String[] {"a", "b", "c"}), l.subList(0, 3));
         m = new HashMap();
         m.put("c", Collections.singletonList("a"));
         l = BaseUtilities.topologicalSort(c, m);
         assertNotNull(l);
         assertEquals(Arrays.asList(new String[] {"d", "e", "f"}), l.subList(3, 6));
         m = new HashMap();
         m.put("a", Collections.singletonList("f"));
         assertEquals(c, BaseUtilities.topologicalSort(c, m));
         m.put("a", Collections.singletonList("b"));
         assertEquals(c, BaseUtilities.topologicalSort(c, m));
         m.put("b", Collections.singletonList("f"));
         assertEquals(c, BaseUtilities.topologicalSort(c, m));
         m.put("c", Collections.singletonList("e"));
         assertEquals(c, BaseUtilities.topologicalSort(c, m));
         m.put("a", Collections.singletonList("e"));
         assertEquals(c, BaseUtilities.topologicalSort(c, m));
         /* Does not work - oh well:
         c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "x", "y"});
         m = new HashMap();
         m.put("c", Arrays.asList(new String[] {"x", "y"}));
         m.put("x", Collections.singletonList("d"));
         m.put("y", Collections.singletonList("d"));
         System.err.println("-----");
         l = BaseUtilities.topologicalSort(c, m);
         assertNotNull(l);
         System.err.println(l);
         assertEquals(Arrays.asList(new String[] {"a", "b", "c"}), l.subList(0, 3));
         assertEquals(Arrays.asList(new String[] {"d", "e"}), l.subList(5, 7));
         */
     }
     public void testTopologicalSortCompile() throws Exception {
         Collection<String> c = new ArrayList<String>();
         Map<Object, Collection<String>> edges = new HashMap<Object,Collection<String>>();

         List<String> result = BaseUtilities.topologicalSort(c, edges);
     }

     public void testTopologicalSortCompile2() throws Exception  {
         Collection<String> c = new ArrayList<String>();
         Map<Object, List<String>> edges = new HashMap<Object,List<String>>();

         List<String> result = BaseUtilities.topologicalSort(c, edges);
     }
     public void testTopologicalSortCompile3() throws Exception {
         Collection<Number> c = new ArrayList<Number>();
         Map<Object, List<Integer>> edges = new HashMap<Object,List<Integer>>();

         List<Number> result = BaseUtilities.topologicalSort(c, edges);
     }

     public void testTopologicalSortIssue101820() throws Exception {
         Object a = "a";
         Object b = "b";

         Map<Object, Collection<Object>> deps = new HashMap<Object, Collection<Object>>();

         deps.put(a, Arrays.asList(b));
         deps.put(b, Arrays.asList());

         assertEquals(Arrays.asList(a), BaseUtilities.topologicalSort(Arrays.asList(a), deps));
      }

     public void testErrorReporting () throws Exception {
         Collection c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "f"});
         Map m = new HashMap ();
         m.put ("a", Arrays.asList (new String[] { "a" }));
         m.put ("b", Arrays.asList (new String[] { "c" }));
         m.put ("c", Arrays.asList (new String[] { "b" }));

         try {
             BaseUtilities.topologicalSort(c, m);
             fail ("Unsortable");
         } catch (TopologicalSortException ex) {
             StringWriter w = new StringWriter ();
             ex.printStackTrace (new PrintWriter (w, true));

             ByteArrayOutputStream s = new ByteArrayOutputStream ();
             ex.printStackTrace (new java.io.PrintStream (s, true));

             byte[] warr = w.toString().getBytes("utf-8");
             byte[] sarr = s.toByteArray();

             assertTrue ("Both messages should be the same", Arrays.equals(warr, sarr));

             {
                 String msg = w.toString();

                 int cnt = 0;
                 int indx = -1;
                 for (;;) {
                     indx = msg.indexOf("Conflict #", indx + 1);
                     if (indx == -1) break;
                     cnt++;
                 }

                 assertEquals(
                     "There is the same number of lines with " +
                     "'Conflict #' as unsortable sets",
                     cnt, ex.unsortableSets().length
                 );
             }

             {
                 String msg = ex.getMessage();

                 int cnt = 0;
                 int indx = -1;
                 for (;;) {
                     indx = msg.indexOf("Conflict #", indx + 1);
                     if (indx == -1) break;
                     cnt++;
                 }

                 assertEquals(
                     "There is the same number of lines with " +
                     "'Conflict #' as unsortable sets",
                     cnt, ex.unsortableSets().length
                 );
             }

         }


     }

     private static void assertBefore (String first, String second, Collection c) {
         assertBefore (first, second, c, false);
     }

     private static void assertBefore (String first, String second, Set[] sets) {
         assertBefore (first, second, Arrays.asList (sets), true);
     }

     private static void assertBefore (String first, String second, Collection c, boolean useSets) {
         Iterator it = c.iterator();
         boolean wasFirst = false;
         boolean wasSecond = false;
         while (it.hasNext ()) {
             Object obj = it.next ();

             if (useSets ? ((Set)obj).contains (second) : obj == second) {
                 assertTrue ("[" + second + "] found before [" + first + "] in " + c, wasFirst);
                 wasSecond = true;
             }

             if (useSets ? ((Set)obj).contains (first) : obj == first) {
                 wasFirst = true;
             }
         }

         assertTrue ("[" + first + "] not found", wasFirst);
         assertTrue ("[" + second + "] not found", wasSecond);
     }
 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*/

	package org.openide.util;

	import java.io.*;
	import java.util.*;

	import org.netbeans.junit.*;
	import junit.textui.TestRunner;

	/** Test BaseUtilities.topologicalSort.
	* @author Jesse Glick
	*/
	public class UtilitiesTopologicalSortTest extends NbTestCase {

	public UtilitiesTopologicalSortTest(String name) {
	super(name);
	}

	public static void main(String[] args) {
	TestRunner.run(new NbTestSuite(UtilitiesTopologicalSortTest.class));
	}

	/**
	* @see "#27286"
	*/
	public void testTopologicalSort() throws Exception {
	Collection c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "f"});
	Map m = new HashMap();
	m.put("f", Collections.singletonList("a"));
	List l = BaseUtilities.topologicalSort(c, m);
	assertNotNull(l);
	assertTrue(l.indexOf("f") < l.indexOf("a"));
	m.put("e", Collections.singletonList("b"));
	l = BaseUtilities.topologicalSort(c, m);
	assertNotNull(l);
	assertTrue(l.indexOf("f") < l.indexOf("a"));
	assertTrue(l.indexOf("e") < l.indexOf("b"));
	m.put("b", Collections.singletonList("a"));
	l = BaseUtilities.topologicalSort(c, m);
	assertNotNull(l);
	assertTrue(l.indexOf("f") < l.indexOf("a"));
	assertTrue(l.indexOf("e") < l.indexOf("b"));
	assertTrue(l.indexOf("b") < l.indexOf("a"));
	// Test that it is modifiable:
	l.add("foo");
	Collections.reverse(l);
	// Test cycles:
	m.put("a", Collections.singletonList("e"));
	try {
	l = BaseUtilities.topologicalSort(c, m);
	fail ("Should throw an exception");
	} catch (TopologicalSortException ex) {
	}
	}

	public void testTopologicalSortError() throws Exception {
	Collection c = Arrays.asList(new String[] {"first", "a", "b", "c", "d", "e", "f", "last"});
	Map m = new HashMap();
	// to make sure that not whole visited graph will be in the cycle
	m.put("first", Collections.singletonList ("f"));
	m.put("last", Collections.singletonList ("f"));


	m.put("f", Collections.singletonList("a"));
	BaseUtilities.topologicalSort (c, m); // does not throw an error
	m.put("e", Collections.singletonList("b"));
	BaseUtilities.topologicalSort (c, m); // does not throw an error
	m.put("b", Collections.singletonList("a"));
	BaseUtilities.topologicalSort (c, m); // does not throw an error
	m.put("a", Collections.singletonList("e"));

	try {
	BaseUtilities.topologicalSort (c, m);
	fail ("Should throw an error");
	} catch (TopologicalSortException ex) {
	Set[] sets = ex.topologicalSets();

	assertEquals ("There is one cycle of size 3, all other objects are sortable", 6, sets.length);

	Set cycle = null;
	for (int i = 0; i < sets.length; i++) {
	if (sets[i].size () > 1) {
	assertNull ("There is just one unsortable component", cycle);
	cycle = sets[i];
	} else {
	assertEquals ("Size is 1", 1, sets[i].size ());
	}
	}

	assertTrue ("a is there", cycle.contains ("a"));
	assertTrue ("b is there", cycle.contains ("b"));
	assertTrue ("e is there", cycle.contains ("e"));
	assertEquals ("Three vertexes are in the cycle", 3, cycle.size ());

	assertBefore ("first", "f", sets);
	assertBefore ("last", "f", sets);
	assertBefore ("f", "a", sets);
	assertBefore ("f", "b", sets);
	assertBefore ("f", "e", sets);

	List partial = ex.partialSort ();
	assertEquals ("Has the same size as the original", c.size (), partial.size ());
	assertBefore ("first", "f", partial);
	assertBefore ("last", "f", partial);
	assertBefore ("f", "a", partial);
	assertBefore ("f", "b", partial);
	assertBefore ("f", "e", partial);
	}
	}

	public void testMoreCycles () throws Exception {
	Collection c = Arrays.asList(new String[] {"first", "a", "b", "c", "d", "e", "f", "last"});
	Map m = new HashMap();
	// to make sure that not whole visited graph will be in the cycle

	m.put ("a", Collections.singletonList ("a")); // self cycle

	// cycle 2
	m.put ("b", Collections.singletonList ("c"));
	m.put ("c", Collections.singletonList ("b"));

	// cycle 3
	m.put ("d", Collections.singletonList ("e"));
	m.put ("e", Collections.singletonList ("f"));
	m.put ("f", Collections.singletonList ("d"));

	Collection sizes = new ArrayList ();

	try {
	BaseUtilities.topologicalSort (c, m);
	fail ("Should throw an error");
	} catch (TopologicalSortException ex) {
	Set[] sets = ex.topologicalSets();
	for (int i = 0; i < sets.length; i++) {
	sizes.add (new Integer (sets[i].size ()));
	}

	assertEquals ("There were three cycles plus first+last", 5, sizes.size ());
	assertTrue ("One of size 1", sizes.contains (new Integer (1)));
	assertTrue ("One of size 2", sizes.contains (new Integer (2)));
	assertTrue ("One of size 3", sizes.contains (new Integer (3)));

	sets = ex.unsortableSets();
	assertEquals ("Three cycles", 3, sets.length);
	}
	}

	public void testDetectSelfCycle () throws Exception {
	Collection c = Arrays.asList(new String[] {"a", "b" });
	Map m = new HashMap();

	m.put ("a", Arrays.asList (new String[] { "a" }));
	m.put ("b", Arrays.asList (new String[] { "a" }));

	try {
	BaseUtilities.topologicalSort (c, m);
	fail ("Definitively there is a cycle");
	} catch (TopologicalSortException ex) {
	Set[] sets = ex.unsortableSets ();

	assertEquals ("One cycle", 1, sets.length);
	assertEquals ("Contains one item", 1, sets[0].size ());
	assertTrue ("Contains a", sets[0].contains ("a"));
	}
	}

	public void testFindLongestCycle () throws Exception {
	Collection c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "f" });
	Map m = new HashMap();
	// to make sure that not whole visited graph will be in the cycle

	m.put ("a", Arrays.asList (new String[] { "b", "c" }));
	m.put ("b", Arrays.asList (new String[] { "a", "d" }));
	m.put ("c", Arrays.asList (new String[] { "a", "d" }));
	m.put ("d", Arrays.asList (new String[] { "b", "c", "e" }));
	m.put ("f", Arrays.asList (new String[] { "a" }));

	try {
	BaseUtilities.topologicalSort (c, m);
	fail ("Definitively there is a cycle");
	} catch (TopologicalSortException ex) {
	Set[] sets = ex.topologicalSets();

	assertEquals ("There is one cycle and e+f", 3, sets.length);

	assertBefore ("f", "a", sets);
	assertBefore ("f", "b", sets);
	assertBefore ("f", "c", sets);
	assertBefore ("f", "d", sets);
	assertBefore ("f", "e", sets);

	assertBefore ("a", "e", sets);
	assertBefore ("b", "e", sets);
	assertBefore ("c", "e", sets);
	assertBefore ("d", "e", sets);

	assertEquals ("set of f", 1, sets[0].size ());
	assertEquals ("set of a,b,c,d", 4, sets[1].size ());
	assertEquals ("set of e", 1, sets[2].size ());
	}
	}

	public void testStability() throws Exception {
	Collection c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "f"});
	assertEquals(c, BaseUtilities.topologicalSort(c, Collections.EMPTY_MAP));
	Map m = new HashMap();
	m.put("e", Collections.singletonList("d"));
	List l = BaseUtilities.topologicalSort(c, m);
	assertNotNull(l);
	assertEquals(Arrays.asList(new String[] {"a", "b", "c"}), l.subList(0, 3));
	m = new HashMap();
	m.put("c", Collections.singletonList("a"));
	l = BaseUtilities.topologicalSort(c, m);
	assertNotNull(l);
	assertEquals(Arrays.asList(new String[] {"d", "e", "f"}), l.subList(3, 6));
	m = new HashMap();
	m.put("a", Collections.singletonList("f"));
	assertEquals(c, BaseUtilities.topologicalSort(c, m));
	m.put("a", Collections.singletonList("b"));
	assertEquals(c, BaseUtilities.topologicalSort(c, m));
	m.put("b", Collections.singletonList("f"));
	assertEquals(c, BaseUtilities.topologicalSort(c, m));
	m.put("c", Collections.singletonList("e"));
	assertEquals(c, BaseUtilities.topologicalSort(c, m));
	m.put("a", Collections.singletonList("e"));
	assertEquals(c, BaseUtilities.topologicalSort(c, m));
	/* Does not work - oh well:
	c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "x", "y"});
	m = new HashMap();
	m.put("c", Arrays.asList(new String[] {"x", "y"}));
	m.put("x", Collections.singletonList("d"));
	m.put("y", Collections.singletonList("d"));
	System.err.println("-----");
	l = BaseUtilities.topologicalSort(c, m);
	assertNotNull(l);
	System.err.println(l);
	assertEquals(Arrays.asList(new String[] {"a", "b", "c"}), l.subList(0, 3));
	assertEquals(Arrays.asList(new String[] {"d", "e"}), l.subList(5, 7));
	*/
	}
	public void testTopologicalSortCompile() throws Exception {
	Collection<String> c = new ArrayList<String>();
	Map<Object, Collection<String>> edges = new HashMap<Object,Collection<String>>();

	List<String> result = BaseUtilities.topologicalSort(c, edges);
	}

	public void testTopologicalSortCompile2() throws Exception {
	Collection<String> c = new ArrayList<String>();
	Map<Object, List<String>> edges = new HashMap<Object,List<String>>();

	List<String> result = BaseUtilities.topologicalSort(c, edges);
	}
	public void testTopologicalSortCompile3() throws Exception {
	Collection<Number> c = new ArrayList<Number>();
	Map<Object, List<Integer>> edges = new HashMap<Object,List<Integer>>();

	List<Number> result = BaseUtilities.topologicalSort(c, edges);
	}

	public void testTopologicalSortIssue101820() throws Exception {
	Object a = "a";
	Object b = "b";

	Map<Object, Collection<Object>> deps = new HashMap<Object, Collection<Object>>();

	deps.put(a, Arrays.asList(b));
	deps.put(b, Arrays.asList());

	assertEquals(Arrays.asList(a), BaseUtilities.topologicalSort(Arrays.asList(a), deps));
	}

	public void testErrorReporting () throws Exception {
	Collection c = Arrays.asList(new String[] {"a", "b", "c", "d", "e", "f"});
	Map m = new HashMap ();
	m.put ("a", Arrays.asList (new String[] { "a" }));
	m.put ("b", Arrays.asList (new String[] { "c" }));
	m.put ("c", Arrays.asList (new String[] { "b" }));

	try {
	BaseUtilities.topologicalSort(c, m);
	fail ("Unsortable");
	} catch (TopologicalSortException ex) {
	StringWriter w = new StringWriter ();
	ex.printStackTrace (new PrintWriter (w, true));

	ByteArrayOutputStream s = new ByteArrayOutputStream ();
	ex.printStackTrace (new java.io.PrintStream (s, true));

	byte[] warr = w.toString().getBytes("utf-8");
	byte[] sarr = s.toByteArray();

	assertTrue ("Both messages should be the same", Arrays.equals(warr, sarr));

	{
	String msg = w.toString();

	int cnt = 0;
	int indx = -1;
	for (;;) {
	indx = msg.indexOf("Conflict #", indx + 1);
	if (indx == -1) break;
	cnt++;
	}

	assertEquals(
	"There is the same number of lines with " +
	"'Conflict #' as unsortable sets",
	cnt, ex.unsortableSets().length
	);
	}

	{
	String msg = ex.getMessage();

	int cnt = 0;
	int indx = -1;
	for (;;) {
	indx = msg.indexOf("Conflict #", indx + 1);
	if (indx == -1) break;
	cnt++;
	}

	assertEquals(
	"There is the same number of lines with " +
	"'Conflict #' as unsortable sets",
	cnt, ex.unsortableSets().length
	);
	}

	}



	}

	private static void assertBefore (String first, String second, Collection c) {
	assertBefore (first, second, c, false);
	}

	private static void assertBefore (String first, String second, Set[] sets) {
	assertBefore (first, second, Arrays.asList (sets), true);
	}

	private static void assertBefore (String first, String second, Collection c, boolean useSets) {
	Iterator it = c.iterator();
	boolean wasFirst = false;
	boolean wasSecond = false;
	while (it.hasNext ()) {
	Object obj = it.next ();

	if (useSets ? ((Set)obj).contains (second) : obj == second) {
	assertTrue ("[" + second + "] found before [" + first + "] in " + c, wasFirst);
	wasSecond = true;
	}

	if (useSets ? ((Set)obj).contains (first) : obj == first) {
	wasFirst = true;
	}
	}

	assertTrue ("[" + first + "] not found", wasFirst);
	assertTrue ("[" + second + "] not found", wasSecond);
	}
	}