-/*\r
- Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
- Permission is hereby granted, free of charge, to any person obtaining a copy\r
- of this software and associated documentation files (the "Software"), to deal\r
- in the Software without restriction, including without limitation the rights\r
- to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
- copies of the Software, and to permit persons to whom the Software is\r
- furnished to do so, subject to the following conditions:\r
- \r
- The above copyright notice and this permission notice shall be included in\r
- all copies or substantial portions of the Software.\r
- \r
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
- FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
- AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
- LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
- SOFTWARE.\r
-*/\r
-\r
-// C5 example: topological sorting 2005-09-09\r
-\r
-// Compile with \r
-// csc /r:C5.dll Toposort.cs \r
-\r
-using System;\r
-using System.Text;\r
-using C5;\r
-using SCG = System.Collections.Generic;\r
-using SDD = System.Diagnostics.Debug;\r
-\r
-namespace Toposort {\r
- class TestToposort {\r
- public static void Main(String[] args) {\r
- Node<String> \r
- d = new Node<String>("d"), \r
- e = new Node<String>("e"),\r
- c = new Node<String>("c", d, e),\r
- b = new Node<String>("b", d),\r
- a = new Node<String>("a", d, b, c);\r
- foreach (Node<String> n in Toposort0(a))\r
- Console.WriteLine(n);\r
- Console.WriteLine();\r
- foreach (Node<String> n in Toposort1(a))\r
- Console.WriteLine(n);\r
- Console.WriteLine();\r
- foreach (Node<String> n in Toposort2(a))\r
- Console.WriteLine(n);\r
- }\r
-\r
- // Toposort 0, adding each node when finished, after its descendants.\r
- // Classic depth-first search. Does not terminate on cyclic graphs.\r
- \r
- public static IList<Node<T>> Toposort0<T>(params Node<T>[] starts) {\r
- HashedLinkedList<Node<T>> sorted = new HashedLinkedList<Node<T>>();\r
- foreach (Node<T> start in starts) \r
- if (!sorted.Contains(start)) \r
- AddNode0(sorted, start);\r
- return sorted; \r
- }\r
-\r
- private static void AddNode0<T>(IList<Node<T>> sorted, Node<T> node) {\r
- SDD.Assert(!sorted.Contains(node));\r
- foreach (Node<T> child in node.children) \r
- if (!sorted.Contains(child)) \r
- AddNode0(sorted, child);\r
- sorted.InsertLast(node);\r
- }\r
-\r
- // Toposort 1, using hash index to add each node before its descendants.\r
- // Terminates also on cyclic graphs.\r
- \r
- public static IList<Node<T>> Toposort1<T>(params Node<T>[] starts) {\r
- HashedLinkedList<Node<T>> sorted = new HashedLinkedList<Node<T>>();\r
- foreach (Node<T> start in starts) \r
- if (!sorted.Contains(start)) {\r
- sorted.InsertLast(start);\r
- AddNode1(sorted, start);\r
- }\r
- return sorted; \r
- }\r
-\r
- private static void AddNode1<T>(IList<Node<T>> sorted, Node<T> node) {\r
- SDD.Assert(sorted.Contains(node));\r
- foreach (Node<T> child in node.children) \r
- if (!sorted.Contains(child)) {\r
- sorted.ViewOf(node).InsertFirst(child);\r
- AddNode1(sorted, child);\r
- }\r
- }\r
-\r
- // Toposort 2, node rescanning using a view.\r
- // Uses no method call stack and no extra data structures, but slower.\r
-\r
- public static IList<Node<T>> Toposort2<T>(params Node<T>[] starts) {\r
- HashedLinkedList<Node<T>> sorted = new HashedLinkedList<Node<T>>();\r
- foreach (Node<T> start in starts) \r
- if (!sorted.Contains(start)) {\r
- sorted.InsertLast(start);\r
- using (IList<Node<T>> cursor = sorted.View(sorted.Count-1,1)) {\r
- do { \r
- Node<T> child;\r
- while (null != (child = PendingChild(sorted, cursor.First))) {\r
- cursor.InsertFirst(child);\r
- cursor.Slide(0,1);\r
- }\r
- } while (cursor.TrySlide(+1));\r
- }\r
- }\r
- return sorted; \r
- }\r
-\r
- static Node<T> PendingChild<T>(IList<Node<T>> sorted, Node<T> node) {\r
- foreach (Node<T> child in node.children) \r
- if (!sorted.Contains(child))\r
- return child;\r
- return null;\r
- }\r
- }\r
-\r
- class Node<T> { \r
- public readonly T id;\r
- public readonly Node<T>[] children;\r
-\r
- public Node(T id, params Node<T>[] children) { \r
- this.id = id; this.children = children;\r
- }\r
-\r
- public override String ToString() { \r
- return id.ToString();\r
- }\r
-\r
- public Node<T> this[int i] {\r
- set { children[i] = value; }\r
- get { return children[i]; }\r
- }\r
- }\r
-}\r
+/*
+ Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ SOFTWARE.
+*/
+
+// C5 example: topological sorting 2005-09-09
+
+// Compile with
+// csc /r:C5.dll Toposort.cs
+
+using System;
+using System.Text;
+using C5;
+using SCG = System.Collections.Generic;
+using SDD = System.Diagnostics.Debug;
+
+namespace Toposort {
+ class TestToposort {
+ public static void Main(String[] args) {
+ Node<String>
+ d = new Node<String>("d"),
+ e = new Node<String>("e"),
+ c = new Node<String>("c", d, e),
+ b = new Node<String>("b", d),
+ a = new Node<String>("a", d, b, c);
+ foreach (Node<String> n in Toposort0(a))
+ Console.WriteLine(n);
+ Console.WriteLine();
+ foreach (Node<String> n in Toposort1(a))
+ Console.WriteLine(n);
+ Console.WriteLine();
+ foreach (Node<String> n in Toposort2(a))
+ Console.WriteLine(n);
+ }
+
+ // Toposort 0, adding each node when finished, after its descendants.
+ // Classic depth-first search. Does not terminate on cyclic graphs.
+
+ public static IList<Node<T>> Toposort0<T>(params Node<T>[] starts) {
+ HashedLinkedList<Node<T>> sorted = new HashedLinkedList<Node<T>>();
+ foreach (Node<T> start in starts)
+ if (!sorted.Contains(start))
+ AddNode0(sorted, start);
+ return sorted;
+ }
+
+ private static void AddNode0<T>(IList<Node<T>> sorted, Node<T> node) {
+ SDD.Assert(!sorted.Contains(node));
+ foreach (Node<T> child in node.children)
+ if (!sorted.Contains(child))
+ AddNode0(sorted, child);
+ sorted.InsertLast(node);
+ }
+
+ // Toposort 1, using hash index to add each node before its descendants.
+ // Terminates also on cyclic graphs.
+
+ public static IList<Node<T>> Toposort1<T>(params Node<T>[] starts) {
+ HashedLinkedList<Node<T>> sorted = new HashedLinkedList<Node<T>>();
+ foreach (Node<T> start in starts)
+ if (!sorted.Contains(start)) {
+ sorted.InsertLast(start);
+ AddNode1(sorted, start);
+ }
+ return sorted;
+ }
+
+ private static void AddNode1<T>(IList<Node<T>> sorted, Node<T> node) {
+ SDD.Assert(sorted.Contains(node));
+ foreach (Node<T> child in node.children)
+ if (!sorted.Contains(child)) {
+ sorted.ViewOf(node).InsertFirst(child);
+ AddNode1(sorted, child);
+ }
+ }
+
+ // Toposort 2, node rescanning using a view.
+ // Uses no method call stack and no extra data structures, but slower.
+
+ public static IList<Node<T>> Toposort2<T>(params Node<T>[] starts) {
+ HashedLinkedList<Node<T>> sorted = new HashedLinkedList<Node<T>>();
+ foreach (Node<T> start in starts)
+ if (!sorted.Contains(start)) {
+ sorted.InsertLast(start);
+ using (IList<Node<T>> cursor = sorted.View(sorted.Count-1,1)) {
+ do {
+ Node<T> child;
+ while (null != (child = PendingChild(sorted, cursor.First))) {
+ cursor.InsertFirst(child);
+ cursor.Slide(0,1);
+ }
+ } while (cursor.TrySlide(+1));
+ }
+ }
+ return sorted;
+ }
+
+ static Node<T> PendingChild<T>(IList<Node<T>> sorted, Node<T> node) {
+ foreach (Node<T> child in node.children)
+ if (!sorted.Contains(child))
+ return child;
+ return null;
+ }
+ }
+
+ class Node<T> {
+ public readonly T id;
+ public readonly Node<T>[] children;
+
+ public Node(T id, params Node<T>[] children) {
+ this.id = id; this.children = children;
+ }
+
+ public override String ToString() {
+ return id.ToString();
+ }
+
+ public Node<T> this[int i] {
+ set { children[i] = value; }
+ get { return children[i]; }
+ }
+ }
+}
projects / mono.git / blobdiff