diff options
| author | Martin Baulig <martin@novell.com> | 2006-02-16 17:01:28 +0300 |
|---|---|---|
| committer | Martin Baulig <martin@novell.com> | 2006-02-16 17:01:28 +0300 |
| commit | 335c858b754608e5fff58a47a983da54ae035825 (patch) | |
| tree | fe102bdcfc74ad3e60db1d911cc11c811512f884 /mcs/class/Mono.C5 | |
| parent | 20e991683a82bd8752bf0a22fd9b4a891afd6492 (diff) | |
Bringing C5 1.0 into the main branch.
svn path=/trunk/mcs/; revision=56933
Diffstat (limited to 'mcs/class/Mono.C5')
39 files changed, 8020 insertions, 0 deletions
diff --git a/mcs/class/Mono.C5/UserGuideExamples/AnagramHashBag.cs b/mcs/class/Mono.C5/UserGuideExamples/AnagramHashBag.cs new file mode 100644 index 00000000000..cc1ca504d10 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/AnagramHashBag.cs @@ -0,0 +1,158 @@ +/*
+ 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: anagrams 2004-08-08, 2004-11-16
+
+// Compile with
+// csc /r:C5.dll AnagramHashBag.cs
+
+using System;
+using System.IO; // StreamReader, TextReader
+using System.Text; // Encoding
+using System.Text.RegularExpressions; // Regex
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace AnagramHashBag
+{
+ class MyTest
+ {
+ public static void Main(String[] args)
+ {
+ Console.OutputEncoding = Encoding.GetEncoding("iso-8859-1");
+ SCG.IEnumerable<String> ss;
+ if (args.Length == 2)
+ ss = ReadFileWords(args[0], int.Parse(args[1]));
+ else
+ ss = args;
+ // foreach (String s in FirstAnagramOnly(ss))
+ // Console.WriteLine(s);
+ // Console.WriteLine("===");
+ Timer t = new Timer();
+ SCG.IEnumerable<SCG.IEnumerable<String>> classes = AnagramClasses(ss);
+ int count = 0;
+ foreach (SCG.IEnumerable<String> anagramClass in classes)
+ {
+ count++;
+ foreach (String s in anagramClass)
+ Console.Write(s + " ");
+ Console.WriteLine();
+ }
+ Console.WriteLine("{0} non-trivial anagram classes", count);
+ Console.WriteLine(t.Check());
+ }
+
+ // Read words at most n words from a file
+
+ public static SCG.IEnumerable<String> ReadFileWords(String filename, int n)
+ {
+ Regex delim = new Regex("[^a-zæøåA-ZÆØÅ0-9-]+");
+ Encoding enc = Encoding.GetEncoding("iso-8859-1");
+ using (TextReader rd = new StreamReader(filename, enc))
+ {
+ for (String line = rd.ReadLine(); line != null; line = rd.ReadLine()) {
+ foreach (String s in delim.Split(line))
+ if (s != "")
+ yield return s.ToLower();
+ if (--n == 0)
+ yield break;
+ }
+ }
+ }
+
+ // From an anagram point of view, a word is just a bag of
+ // characters. So an anagram class is represented as HashBag<char>
+ // which permits fast equality comparison -- we shall use them as
+ // elements of hash sets or keys in hash maps.
+
+ public static HashBag<char> AnagramClass(String s) {
+ HashBag<char> anagram = new HashBag<char>();
+ foreach (char c in s)
+ anagram.Add(c);
+ return anagram;
+ }
+
+ // Given a sequence of strings, return only the first member of each
+ // anagram class.
+
+ public static SCG.IEnumerable<String> FirstAnagramOnly(SCG.IEnumerable<String> ss)
+ {
+ HashSet<HashBag<char>> anagrams = new HashSet<HashBag<char>>();
+ foreach (String s in ss) {
+ HashBag<char> anagram = AnagramClass(s);
+ if (!anagrams.Contains(anagram)) {
+ anagrams.Add(anagram);
+ yield return s;
+ }
+ }
+ }
+
+ // Given a sequence of strings, return all non-trivial anagram
+ // classes.
+
+ // Using HashBag<char> and an unsequenced equalityComparer, this performs as
+ // follows on 1600 MHz Mobile P4 and .Net 2.0 beta 1 (wall-clock
+ // time):
+ // 50 000 words 2 822 classes 2.0 sec
+ // 100 000 words 5 593 classes 4.3 sec
+ // 200 000 words 11 705 classes 8.8 sec
+ // 300 000 words 20 396 classes 52.0 sec includes swapping
+ // 347 165 words 24 428 classes 146.0 sec includes swapping
+
+ // The maximal memory consumption is less than 180 MB.
+
+ public static SCG.IEnumerable<SCG.IEnumerable<String>>
+ AnagramClasses(SCG.IEnumerable<String> ss)
+ {
+ IDictionary<HashBag<char>, TreeSet<String>> classes
+ = new HashDictionary<HashBag<char>, TreeSet<String>>();
+ foreach (String s in ss) {
+ HashBag<char> anagram = AnagramClass(s);
+ TreeSet<String> anagramClass;
+ if (!classes.Find(anagram, out anagramClass))
+ classes[anagram] = anagramClass = new TreeSet<String>();
+ anagramClass.Add(s);
+ }
+ foreach (TreeSet<String> anagramClass in classes.Values)
+ if (anagramClass.Count > 1)
+ yield return anagramClass;
+ }
+ }
+
+// Crude timing utility ----------------------------------------
+
+ public class Timer
+ {
+ private DateTime start;
+
+ public Timer()
+ {
+ start = DateTime.Now;
+ }
+
+ public double Check()
+ {
+ TimeSpan dur = DateTime.Now - start;
+ return dur.TotalSeconds;
+ }
+ }
+
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/AnagramStrings.cs b/mcs/class/Mono.C5/UserGuideExamples/AnagramStrings.cs new file mode 100644 index 00000000000..314e7a41111 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/AnagramStrings.cs @@ -0,0 +1,159 @@ +/*
+ 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: anagrams represented as sorted strings 2004-08-26
+
+// To represent an anagram class, use a string containing the sorted
+// characters of a word.
+
+// This is faster than a TreeBag<char> because the words and hence
+// bags are small. Takes 15 CPU seconds and 138 MB RAM to find the
+// 26,058 anagram classes among 347,000 distinct words.
+
+// Compile with
+// csc /r:C5.dll Anagrams.cs
+
+using System;
+using System.IO; // StreamReader, TextReader
+using System.Text; // Encoding
+using System.Text.RegularExpressions; // Regex
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace AnagramStrings
+{
+ class MyTest
+ {
+ public static void Main(String[] args)
+ {
+ Console.OutputEncoding = Encoding.GetEncoding("iso-8859-1");
+ SCG.IEnumerable<String> ss;
+ if (args.Length == 1)
+ ss = ReadFileWords(args[0]);
+ else
+ ss = args;
+
+ Timer t = new Timer();
+ SCG.IEnumerable<SCG.IEnumerable<String>> classes = AnagramClasses(ss);
+ int count = 0;
+ foreach (SCG.IEnumerable<String> anagramClass in classes)
+ {
+ count++;
+ // foreach (String s in anagramClass)
+ // Console.Write(s + " ");
+ // Console.WriteLine();
+ }
+ Console.WriteLine("{0} anagram classes", count);
+ Console.WriteLine(t.Check());
+ }
+
+ // Read words from a file
+
+ public static SCG.IEnumerable<String> ReadFileWords(String filename)
+ {
+ Regex delim = new Regex("[^a-zæøåA-ZÆØÅ0-9-]+");
+ using (TextReader rd = new StreamReader(filename, Encoding.GetEncoding("iso-8859-1")))
+ {
+ for (String line = rd.ReadLine(); line != null; line = rd.ReadLine())
+ foreach (String s in delim.Split(line))
+ if (s != "")
+ yield return s.ToLower();
+ }
+ }
+
+ // From an anagram point of view, a word is just a bag of characters.
+
+ public static CharBag AnagramClass(String s)
+ {
+ return new CharBag(s);
+ }
+
+ // Given a sequence of strings, return all non-trivial anagram classes
+
+ public static SCG.IEnumerable<SCG.IEnumerable<String>> AnagramClasses(SCG.IEnumerable<String> ss)
+ {
+ IDictionary<CharBag, HashSet<String>> classes
+ = new TreeDictionary<CharBag, HashSet<String>>();
+ foreach (String s in ss)
+ {
+ CharBag anagram = AnagramClass(s);
+ HashSet<String> anagramClass;
+ if (!classes.Find(anagram, out anagramClass))
+ classes[anagram] = anagramClass = new HashSet<String>();
+ anagramClass.Add(s);
+ }
+ foreach (HashSet<String> anagramClass in classes.Values)
+ if (anagramClass.Count > 1
+ ) // && anagramClass.Exists(delegate(String s) { return !s.EndsWith("s"); }))
+ yield return anagramClass;
+ }
+ }
+
+// A bag of characters is represented as a sorted string of the
+// characters, with multiplicity. Since natural language words are
+// short, the bags are small, so this is vastly better than
+// representing character bags using HashBag<char> or TreeBag<char>
+
+ class CharBag : IComparable<CharBag>
+ {
+ private readonly String contents; // The bag's characters, sorted, with multiplicity
+
+ public CharBag(String s)
+ {
+ char[] chars = s.ToCharArray();
+ Array.Sort(chars);
+ this.contents = new String(chars);
+ }
+
+ public override int GetHashCode()
+ {
+ return contents.GetHashCode();
+ }
+
+ public bool Equals(CharBag that)
+ {
+ return this.contents.Equals(that.contents);
+ }
+
+ public int CompareTo(CharBag that)
+ {
+ return this.contents.CompareTo(that.contents);
+ }
+ }
+
+// Crude timing utility ----------------------------------------
+
+ public class Timer
+ {
+ private DateTime start;
+
+ public Timer()
+ {
+ start = DateTime.Now;
+ }
+
+ public double Check()
+ {
+ TimeSpan dur = DateTime.Now - start;
+ return dur.TotalSeconds;
+ }
+ }
+}
\ No newline at end of file diff --git a/mcs/class/Mono.C5/UserGuideExamples/AnagramTreeBag.cs b/mcs/class/Mono.C5/UserGuideExamples/AnagramTreeBag.cs new file mode 100644 index 00000000000..e8120758ca8 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/AnagramTreeBag.cs @@ -0,0 +1,163 @@ +/*
+ 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: anagrams 2004-08-08, 2004-11-16
+
+// Compile with
+// csc /r:C5.dll AnagramTreeBag.cs
+
+using System;
+using System.IO; // StreamReader, TextReader
+using System.Text; // Encoding
+using System.Text.RegularExpressions; // Regex
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace AnagramTreeBag
+{
+ class MyTest
+ {
+ public static void Main(String[] args)
+ {
+ Console.OutputEncoding = Encoding.GetEncoding("iso-8859-1");
+ SCG.IEnumerable<String> ss;
+ if (args.Length == 2)
+ ss = ReadFileWords(args[0], int.Parse(args[1]));
+ else
+ ss = args;
+ // foreach (String s in FirstAnagramOnly(ss))
+ // Console.WriteLine(s);
+ // Console.WriteLine("===");
+ Timer t = new Timer();
+ SCG.IEnumerable<SCG.IEnumerable<String>> classes = AnagramClasses(ss);
+ int count = 0;
+ foreach (SCG.IEnumerable<String> anagramClass in classes)
+ {
+ count++;
+ // foreach (String s in anagramClass)
+ // Console.Write(s + " ");
+ // Console.WriteLine();
+ }
+ Console.WriteLine("{0} non-trivial anagram classes", count);
+ Console.WriteLine(t.Check());
+ }
+
+ // Read words at most n words from a file
+
+ public static SCG.IEnumerable<String> ReadFileWords(String filename, int n)
+ {
+ Regex delim = new Regex("[^a-zæøåA-ZÆØÅ0-9-]+");
+ Encoding enc = Encoding.GetEncoding("iso-8859-1");
+ using (TextReader rd = new StreamReader(filename, enc))
+ {
+ for (String line = rd.ReadLine(); line != null; line = rd.ReadLine())
+ {
+ foreach (String s in delim.Split(line))
+ if (s != "")
+ yield return s.ToLower();
+ if (--n == 0)
+ yield break;
+ }
+ }
+ }
+
+ // From an anagram point of view, a word is just a bag of
+ // characters. So an anagram class is represented as TreeBag<char>
+ // which permits fast equality comparison -- we shall use them as
+ // elements of hash sets or keys in hash maps.
+
+ public static TreeBag<char> AnagramClass(String s)
+ {
+ TreeBag<char> anagram = new TreeBag<char>(Comparer<char>.Default, EqualityComparer<char>.Default);
+ foreach (char c in s)
+ anagram.Add(c);
+ return anagram;
+ }
+
+ // Given a sequence of strings, return only the first member of each
+ // anagram class.
+
+ public static SCG.IEnumerable<String> FirstAnagramOnly(SCG.IEnumerable<String> ss)
+ {
+ HashSet<TreeBag<char>> anagrams = new HashSet<TreeBag<char>>();
+ foreach (String s in ss)
+ {
+ TreeBag<char> anagram = AnagramClass(s);
+ if (!anagrams.Contains(anagram))
+ {
+ anagrams.Add(anagram);
+ yield return s;
+ }
+ }
+ }
+
+ // Given a sequence of strings, return all non-trivial anagram
+ // classes.
+
+ // Using TreeBag<char> and an unsequenced equalityComparer, this performs as
+ // follows on 1600 MHz Mobile P4 and .Net 2.0 beta 1 (wall-clock
+ // time; number of distinct words):
+
+ // 50 000 words 2 822 classes 2.4 sec
+ // 100 000 words 5 593 classes 4.6 sec
+ // 200 000 words 11 705 classes 9.6 sec
+ // 300 000 words 20 396 classes 88.2 sec (includes swapping)
+ // 347 165 words 24 428 classes 121.3 sec (includes swapping)
+
+ // The maximal memory consumption is around 180 MB.
+
+ public static SCG.IEnumerable<SCG.IEnumerable<String>>
+ AnagramClasses(SCG.IEnumerable<String> ss)
+ {
+ IDictionary<TreeBag<char>, TreeSet<String>> classes;
+ classes = new HashDictionary<TreeBag<char>, TreeSet<String>>();
+ foreach (String s in ss)
+ {
+ TreeBag<char> anagram = AnagramClass(s);
+ TreeSet<String> anagramClass;
+ if (!classes.Find(anagram, out anagramClass))
+ classes[anagram] = anagramClass = new TreeSet<String>();
+ anagramClass.Add(s);
+ }
+ foreach (TreeSet<String> anagramClass in classes.Values)
+ if (anagramClass.Count > 1)
+ yield return anagramClass;
+ }
+ }
+
+// Crude timing utility ----------------------------------------
+
+ public class Timer
+ {
+ private DateTime start;
+
+ public Timer()
+ {
+ start = DateTime.Now;
+ }
+
+ public double Check()
+ {
+ TimeSpan dur = DateTime.Now - start;
+ return dur.TotalSeconds;
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Anagrams.cs b/mcs/class/Mono.C5/UserGuideExamples/Anagrams.cs new file mode 100644 index 00000000000..64ca20f515f --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Anagrams.cs @@ -0,0 +1,177 @@ +/*
+ 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: anagrams 2004-08-08, 2004-11-16
+
+// Compile with
+// csc /r:C5.dll Anagrams.cs
+
+using System;
+using System.IO; // StreamReader, TextReader
+using System.Text; // Encoding
+using System.Text.RegularExpressions; // Regex
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace Anagrams
+{
+ class MyTest
+ {
+ public static void Main(String[] args)
+ {
+ Console.OutputEncoding = Encoding.GetEncoding("iso-8859-1");
+ SCG.IEnumerable<String> ss;
+ if (args.Length == 2)
+ ss = ReadFileWords(args[0], int.Parse(args[1]));
+ else
+ ss = args;
+ // foreach (String s in FirstAnagramOnly(ss))
+ // Console.WriteLine(s);
+ // Console.WriteLine("===");
+ Timer t = new Timer();
+ SCG.IEnumerable<SCG.IEnumerable<String>> classes = AnagramClasses(ss);
+ int count = 0;
+ foreach (SCG.IEnumerable<String> anagramClass in classes)
+ {
+ count++;
+ // foreach (String s in anagramClass)
+ // Console.Write(s + " ");
+ // Console.WriteLine();
+ }
+ Console.WriteLine("{0} non-trivial anagram classes", count);
+ Console.WriteLine(t.Check());
+ }
+
+ // Read words at most n words from a file
+
+ public static SCG.IEnumerable<String> ReadFileWords(String filename, int n)
+ {
+ Regex delim = new Regex("[^a-zæøåA-ZÆØÅ0-9-]+");
+ Encoding enc = Encoding.GetEncoding("iso-8859-1");
+ using (TextReader rd = new StreamReader(filename, enc))
+ {
+ for (String line = rd.ReadLine(); line != null; line = rd.ReadLine())
+ {
+ foreach (String s in delim.Split(line))
+ if (s != "")
+ yield return s.ToLower();
+ if (--n == 0)
+ yield break;
+ }
+ }
+ }
+
+ // From an anagram point of view, a word is just a bag of
+ // characters. So an anagram class is represented as TreeBag<char>
+ // which permits fast equality comparison -- we shall use them as
+ // elements of hash sets or keys in hash maps.
+
+ public static TreeBag<char> AnagramClass(String s)
+ {
+ TreeBag<char> anagram = new TreeBag<char>(Comparer<char>.Default, EqualityComparer<char>.Default);
+ foreach (char c in s)
+ anagram.Add(c);
+ return anagram;
+ }
+
+ // Given a sequence of strings, return only the first member of each
+ // anagram class.
+
+ public static SCG.IEnumerable<String> FirstAnagramOnly(SCG.IEnumerable<String> ss)
+ {
+ SCG.IEqualityComparer<TreeBag<char>> tbh
+ = UnsequencedCollectionEqualityComparer<TreeBag<char>, char>.Default;
+ HashSet<TreeBag<char>> anagrams = new HashSet<TreeBag<char>>(tbh);
+ foreach (String s in ss)
+ {
+ TreeBag<char> anagram = AnagramClass(s);
+ if (!anagrams.Contains(anagram))
+ {
+ anagrams.Add(anagram);
+ yield return s;
+ }
+ }
+ }
+
+ // Given a sequence of strings, return all non-trivial anagram
+ // classes. Should use a *sequenced* equalityComparer on a TreeBag<char>,
+ // obviously: after all, characters can be sorted by ASCII code. On
+ // 347 000 distinct Danish words this takes 70 cpu seconds, 180 MB
+ // memory, and 263 wall-clock seconds (due to swapping).
+
+ // Using a TreeBag<char> and a sequenced equalityComparer takes 82 cpu seconds
+ // and 180 MB RAM to find the 26,058 anagram classes among 347,000
+ // distinct words.
+
+ // Using an unsequenced equalityComparer on TreeBag<char> or HashBag<char>
+ // makes it criminally slow: at least 1200 cpu seconds. This must
+ // be because many bags get the same hash code, so that there are
+ // many collisions. But exactly how the unsequenced equalityComparer works is
+ // not clear ... or is it because unsequenced equality is slow?
+
+ public static SCG.IEnumerable<SCG.IEnumerable<String>> AnagramClasses(SCG.IEnumerable<String> ss)
+ {
+ bool unseq = true;
+ IDictionary<TreeBag<char>, TreeSet<String>> classes;
+ if (unseq)
+ {
+ SCG.IEqualityComparer<TreeBag<char>> unsequencedTreeBagEqualityComparer
+ = UnsequencedCollectionEqualityComparer<TreeBag<char>, char>.Default;
+ classes = new HashDictionary<TreeBag<char>, TreeSet<String>>(unsequencedTreeBagEqualityComparer);
+ }
+ else
+ {
+ SCG.IEqualityComparer<TreeBag<char>> sequencedTreeBagEqualityComparer
+ = SequencedCollectionEqualityComparer<TreeBag<char>, char>.Default;
+ classes = new HashDictionary<TreeBag<char>, TreeSet<String>>(sequencedTreeBagEqualityComparer);
+ }
+ foreach (String s in ss)
+ {
+ TreeBag<char> anagram = AnagramClass(s);
+ TreeSet<String> anagramClass;
+ if (!classes.Find(anagram, out anagramClass))
+ classes[anagram] = anagramClass = new TreeSet<String>();
+ anagramClass.Add(s);
+ }
+ foreach (TreeSet<String> anagramClass in classes.Values)
+ if (anagramClass.Count > 1)
+ yield return anagramClass;
+ }
+ }
+
+// Crude timing utility ----------------------------------------
+
+ public class Timer
+ {
+ private DateTime start;
+
+ public Timer()
+ {
+ start = DateTime.Now;
+ }
+
+ public double Check()
+ {
+ TimeSpan dur = DateTime.Now - start;
+ return dur.TotalSeconds;
+ }
+ }
+}
\ No newline at end of file diff --git a/mcs/class/Mono.C5/UserGuideExamples/Antipatterns.cs b/mcs/class/Mono.C5/UserGuideExamples/Antipatterns.cs new file mode 100644 index 00000000000..94d373434b8 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Antipatterns.cs @@ -0,0 +1,103 @@ +/*
+ 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: Antipatterns 2004-12-29
+
+// Compile with
+// csc /r:C5.dll Antipatterns.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace Antipatterns {
+ class Antipatterns {
+ public static void Main(String[] args) {
+ ModifyInner();
+ DontModifyInner();
+ }
+
+ // Anti-pattern: modifying an inner collection while it is a
+ // member of an outer one may cause it to be lost from the outer
+ // collection.
+
+ private static void ModifyInner() {
+ Console.WriteLine("\nAnti-pattern: Add to outer, modify, lose");
+ ICollection<ISequenced<int>> outer = new HashSet<ISequenced<int>>();
+ for (int i=0; i<100; i++) {
+ ISequenced<int> inner = new TreeSet<int>();
+ inner.Add(i); inner.Add(i+1);
+ outer.Add(inner);
+ }
+ ISequenced<int>
+ inner1 = new TreeSet<int>(),
+ inner2 = new TreeSet<int>(),
+ inner3 = new TreeSet<int>();
+ inner1.AddAll<int>(new int[] { 2, 3, 5, 7, 11 });
+ inner2.AddAll(inner1); inner2.Add(13);
+ inner3.AddAll(inner1);
+ outer.Add(inner1);
+ Console.WriteLine("inner1 in outer: {0}", outer.Contains(inner1));
+ Console.WriteLine("inner2 in outer: {0}", outer.Contains(inner2));
+ Console.WriteLine("inner3 in outer: {0}", outer.Contains(inner3));
+ inner1.Add(13);
+ Console.WriteLine("inner1 equals inner2: {0}",
+ outer.EqualityComparer.Equals(inner1, inner2));
+ Console.WriteLine("inner1 equals inner3: {0}",
+ outer.EqualityComparer.Equals(inner1, inner3));
+ Console.WriteLine("inner1 in outer: {0}", outer.Contains(inner1));
+ Console.WriteLine("inner2 in outer: {0}", outer.Contains(inner2));
+ Console.WriteLine("inner3 in outer: {0}", outer.Contains(inner3));
+ Console.WriteLine("outer.Count: {0}", outer.Count);
+ }
+
+ private static void DontModifyInner() {
+ Console.WriteLine("\nMake a snapshot and add it to outer");
+ ICollection<ISequenced<int>> outer = new HashSet<ISequenced<int>>();
+ for (int i=0; i<100; i++) {
+ ISequenced<int> inner = new TreeSet<int>();
+ inner.Add(i); inner.Add(i+1);
+ outer.Add(inner);
+ }
+ IPersistentSorted<int>
+ inner1 = new TreeSet<int>(),
+ inner2 = new TreeSet<int>(),
+ inner3 = new TreeSet<int>();
+ inner1.AddAll<int>(new int[] { 2, 3, 5, 7, 11 });
+ inner2.AddAll(inner1); inner2.Add(13);
+ inner3.AddAll(inner1);
+ // Take a snapshot and add it to outer:
+ outer.Add(inner1.Snapshot());
+ Console.WriteLine("inner1 in outer: {0}", outer.Contains(inner1));
+ Console.WriteLine("inner2 in outer: {0}", outer.Contains(inner2));
+ Console.WriteLine("inner3 in outer: {0}", outer.Contains(inner3));
+ inner1.Add(13);
+ Console.WriteLine("inner1 equals inner2: {0}",
+ outer.EqualityComparer.Equals(inner1, inner2));
+ Console.WriteLine("inner1 equals inner3: {0}",
+ outer.EqualityComparer.Equals(inner1, inner3));
+ Console.WriteLine("inner1 in outer: {0}", outer.Contains(inner1));
+ Console.WriteLine("inner2 in outer: {0}", outer.Contains(inner2));
+ Console.WriteLine("inner3 in outer: {0}", outer.Contains(inner3));
+ Console.WriteLine("outer.Count: {0}", outer.Count);
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Cloning.cs b/mcs/class/Mono.C5/UserGuideExamples/Cloning.cs new file mode 100644 index 00000000000..beeea8f0c8a --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Cloning.cs @@ -0,0 +1,45 @@ +/*
+ 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: anagrams 2004-12-
+
+// Compile with
+// csc /r:C5.dll Cloning.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace MyCloningTest {
+ class MyTest {
+ public static void Main(String[] args) {
+ IList<int> lst = new ArrayList<int>();
+ lst.AddAll(new int[] { 2, 3, 5, 7, 11, 13 });
+ Console.WriteLine(lst);
+ IList<int> v1 = lst.ViewOf(7);
+ Console.WriteLine(v1);
+ IList<int> v2 = (IList<int>)v1.Clone();
+ v2.Slide(1);
+ Console.WriteLine(v1);
+ Console.WriteLine(v2);
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/CollectionCollection.cs b/mcs/class/Mono.C5/UserGuideExamples/CollectionCollection.cs new file mode 100644 index 00000000000..5e90c1cff72 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/CollectionCollection.cs @@ -0,0 +1,125 @@ +/*
+ 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: collections of collections 2004-11-16
+
+// Compile with
+// csc /r:C5.dll CollectionCollection.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace CollectionCollection
+{
+ class MyTest
+ {
+ private static IList<int> col1 = new LinkedList<int>(),
+ col2 = new LinkedList<int>(), col3 = new LinkedList<int>();
+
+ public static void Main(String[] args) {
+ ListEqualityComparers();
+ IntSetSet();
+ CharBagSet();
+ }
+
+ public static void ListEqualityComparers() {
+ col1.AddAll<int>(new int[] { 7, 9, 13 });
+ col2.AddAll<int>(new int[] { 7, 9, 13 });
+ col3.AddAll<int>(new int[] { 9, 7, 13 });
+
+ // Default equality and hasher == sequenced equality and hasher
+ HashSet<IList<int>> hs1 = new HashSet<IList<int>>();
+ Equalities("Default equality (sequenced equality)", hs1.EqualityComparer);
+ hs1.Add(col1); hs1.Add(col2); hs1.Add(col3);
+ Console.WriteLine("hs1.Count = {0}", hs1.Count);
+
+ // Sequenced equality and hasher
+ SCG.IEqualityComparer<IList<int>> seqEqualityComparer
+ = SequencedCollectionEqualityComparer<IList<int>, int>.Default;
+ HashSet<IList<int>> hs2 = new HashSet<IList<int>>(seqEqualityComparer);
+ Equalities("Sequenced equality", hs2.EqualityComparer);
+ hs2.Add(col1); hs2.Add(col2); hs2.Add(col3);
+ Console.WriteLine("hs2.Count = {0}", hs2.Count);
+
+ // Unsequenced equality and hasher
+ SCG.IEqualityComparer<IList<int>> unseqEqualityComparer
+ = UnsequencedCollectionEqualityComparer<IList<int>, int>.Default;
+ HashSet<IList<int>> hs3 = new HashSet<IList<int>>(unseqEqualityComparer);
+ Equalities("Unsequenced equality", hs3.EqualityComparer);
+ hs3.Add(col1); hs3.Add(col2); hs3.Add(col3);
+ Console.WriteLine("hs3.Count = {0}", hs3.Count);
+
+ // Reference equality and hasher
+ SCG.IEqualityComparer<IList<int>> refEqEqualityComparer
+ = ReferenceEqualityComparer<IList<int>>.Default;
+ HashSet<IList<int>> hs4 = new HashSet<IList<int>>(refEqEqualityComparer);
+ Equalities("Reference equality", hs4.EqualityComparer);
+ hs4.Add(col1); hs4.Add(col2); hs4.Add(col3);
+ Console.WriteLine("hs4.Count = {0}", hs4.Count);
+ }
+
+ public static void Equalities(String msg, SCG.IEqualityComparer<IList<int>> equalityComparer)
+ {
+ Console.WriteLine("\n{0}:", msg);
+ Console.Write("Equals(col1,col2)={0,-5}; ", equalityComparer.Equals(col1, col2));
+ Console.Write("Equals(col1,col3)={0,-5}; ", equalityComparer.Equals(col1, col3));
+ Console.WriteLine("Equals(col2,col3)={0,-5}", equalityComparer.Equals(col2, col3));
+ }
+
+ public static void IntSetSet() {
+ ICollection<ISequenced<int>> outer = new HashSet<ISequenced<int>>();
+ int[] ss = { 2, 3, 5, 7 };
+ TreeSet<int> inner = new TreeSet<int>();
+ outer.Add(inner.Snapshot());
+ foreach (int i in ss) {
+ inner.Add(i);
+ outer.Add(inner.Snapshot());
+ }
+ foreach (ISequenced<int> s in outer) {
+ int sum = 0;
+ s.Apply(delegate(int x) { sum += x; });
+ Console.WriteLine("Set has {0} elements and sum {1}", s.Count, sum);
+ }
+ }
+
+ public static void CharBagSet() {
+ String text =
+ @"three sorted streams aligned by leading masters are stored
+ there; an integral triangle ends, and stable tables keep;
+ being alert, they later reread the logarithm, peek at the
+ recent center, then begin to send their reader algorithm.";
+ String[] words = text.Split(' ', '\n', '\r', ';', ',', '.');
+ ICollection<ICollection<char>> anagrams
+ = new HashSet<ICollection<char>>();
+ int count = 0;
+ foreach (String word in words) {
+ if (word != "") {
+ count++;
+ HashBag<char> anagram = new HashBag<char>();
+ anagram.AddAll<char>(word.ToCharArray());
+ anagrams.Add(anagram);
+ }
+ }
+ Console.WriteLine("Found {0} anagrams", count - anagrams.Count);
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/CollectionSanity.cs b/mcs/class/Mono.C5/UserGuideExamples/CollectionSanity.cs new file mode 100644 index 00000000000..fa332ee763b --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/CollectionSanity.cs @@ -0,0 +1,65 @@ +/*
+ 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: anagrams 2004-12-08
+
+// Compile with
+// csc /r:C5.dll CollectionSanity.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace CollectionSanity {
+ class CollectionSanity {
+ public static void Main(String[] args) {
+ IList<int> col1 = new LinkedList<int>(),
+ col2 = new LinkedList<int>(), col3 = new LinkedList<int>();
+ col1.AddAll<int>(new int[] { 7, 9, 13 });
+ col2.AddAll<int>(new int[] { 7, 9, 13 });
+ col3.AddAll<int>(new int[] { 9, 7, 13 });
+
+ HashSet<IList<int>> hs1 = new HashSet<IList<int>>();
+ hs1.Add(col1); hs1.Add(col2); hs1.Add(col3);
+ Console.WriteLine("hs1 is sane: {0}", EqualityComparerSanity<int,IList<int>>(hs1));
+ }
+
+ // When colls is a collection of collections, this method checks
+ // that all `inner' collections use the exact same equalityComparer. Note
+ // that two equalityComparer objects may be functionally (extensionally)
+ // identical, yet be distinct objects. However, if the equalityComparers
+ // were obtained from EqualityComparer<T>.Default, there will be at most one
+ // equalityComparer for each type T.
+
+ public static bool EqualityComparerSanity<T,U>(ICollectionValue<U> colls)
+ where U : IExtensible<T>
+ {
+ SCG.IEqualityComparer<T> equalityComparer = null;
+ foreach (IExtensible<T> coll in colls) {
+ if (equalityComparer == null)
+ equalityComparer = coll.EqualityComparer;
+ if (equalityComparer != coll.EqualityComparer)
+ return false;
+ }
+ return true;
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/EventPatterns.cs b/mcs/class/Mono.C5/UserGuideExamples/EventPatterns.cs new file mode 100644 index 00000000000..36d41a66ef4 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/EventPatterns.cs @@ -0,0 +1,213 @@ +/*
+ 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: EventPatterns.cs for pattern chapter
+
+// Compile with
+// csc /r:C5.dll EventPatterns.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace EventPatterns {
+ class EventPatterns {
+ public static void Main(String[] args) {
+ UnindexedCollectionEvents();
+ Console.WriteLine("--------------------");
+ IndexedCollectionEvents();
+ Console.WriteLine("--------------------");
+ UpdateEvent();
+ }
+
+ public static void UnindexedCollectionEvents() {
+ ICollection<int> coll = new ArrayList<int>();
+ ICollection<int> bag1 = new HashBag<int>();
+ bag1.AddAll(new int[] { 3, 2, 5, 5, 7, 7, 5, 3, 7, 7 });
+ // Add change handler
+ coll.CollectionChanged
+ += delegate(Object c) {
+ Console.WriteLine("Collection changed");
+ };
+ // Add cleared handler
+ coll.CollectionCleared
+ += delegate(Object c, ClearedEventArgs args) {
+ Console.WriteLine("Collection cleared");
+ };
+ // Add added handler
+ coll.ItemsAdded
+ += delegate(Object c, ItemCountEventArgs<int> args) {
+ Console.WriteLine("Item {0} added", args.Item);
+ };
+ // Add item count handler
+ AddItemsAddedCounter(coll);
+ AddItemsRemovedCounter(coll);
+ coll.AddAll(bag1);
+ coll.RemoveAll(new int[] { 2, 5, 6, 3, 7, 2 });
+ coll.Clear();
+ ICollection<int> bag2 = new HashBag<int>();
+ // Add added handler with multiplicity
+ bag2.ItemsAdded
+ += delegate(Object c, ItemCountEventArgs<int> args) {
+ Console.WriteLine("{0} copies of {1} added",
+ args.Count, args.Item);
+ };
+ bag2.AddAll(bag1);
+ // Add removed handler with multiplicity
+ bag2.ItemsRemoved
+ += delegate(Object c, ItemCountEventArgs<int> args) {
+ Console.WriteLine("{0} copies of {1} removed",
+ args.Count, args.Item);
+ };
+ bag2.RemoveAllCopies(7);
+ }
+
+ // This works for all kinds of collections, also those with bag
+ // semantics and representing duplicates by counting:
+
+ private static void AddItemsAddedCounter<T>(ICollection<T> coll) {
+ int addedCount = 0;
+ coll.ItemsAdded
+ += delegate(Object c, ItemCountEventArgs<T> args) {
+ addedCount += args.Count;
+ };
+ coll.CollectionChanged
+ += delegate(Object c) {
+ if (addedCount > 0)
+ Console.WriteLine("{0} items were added", addedCount);
+ addedCount = 0;
+ };
+ }
+
+ // This works for all kinds of collections, also those with bag
+ // semantics and representing duplicates by counting:
+
+ private static void AddItemsRemovedCounter<T>(ICollection<T> coll) {
+ int removedCount = 0;
+ coll.ItemsRemoved
+ += delegate(Object c, ItemCountEventArgs<T> args) {
+ removedCount += args.Count;
+ };
+ coll.CollectionChanged
+ += delegate(Object c) {
+ if (removedCount > 0)
+ Console.WriteLine("{0} items were removed", removedCount);
+ removedCount = 0;
+ };
+ }
+
+ // Event patterns on indexed collections
+
+ public static void IndexedCollectionEvents() {
+ IList<int> coll = new ArrayList<int>();
+ ICollection<int> bag = new HashBag<int>();
+ bag.AddAll(new int[] { 3, 2, 5, 5, 7, 7, 5, 3, 7, 7 });
+ // Add item inserted handler
+ coll.ItemInserted
+ += delegate(Object c, ItemAtEventArgs<int> args) {
+ Console.WriteLine("Item {0} inserted at {1}",
+ args.Item, args.Index);
+ };
+ coll.InsertAll(0, bag);
+ // Add item removed-at handler
+ coll.ItemRemovedAt
+ += delegate(Object c, ItemAtEventArgs<int> args) {
+ Console.WriteLine("Item {0} removed at {1}",
+ args.Item, args.Index);
+ };
+ coll.RemoveLast();
+ coll.RemoveFirst();
+ coll.RemoveAt(1);
+ }
+
+ // Recognizing Update event as a Removed-Added-Changed sequence
+
+ private enum State { Before, Removed, Updated };
+
+ private static void AddItemUpdatedHandler<T>(ICollection<T> coll) {
+ State state = State.Before;
+ T removed = default(T), added = default(T);
+ coll.ItemsRemoved
+ += delegate(Object c, ItemCountEventArgs<T> args) {
+ if (state==State.Before) {
+ state = State.Removed;
+ removed = args.Item;
+ } else
+ state = State.Before;
+ };
+ coll.ItemsAdded
+ += delegate(Object c, ItemCountEventArgs<T> args) {
+ if (state==State.Removed) {
+ state = State.Updated;
+ added = args.Item;
+ } else
+ state = State.Before;
+ };
+ coll.CollectionChanged
+ += delegate(Object c) {
+ if (state==State.Updated)
+ Console.WriteLine("Item {0} was updated to {1}",
+ removed, added);
+ state = State.Before;
+ };
+ }
+
+ public static void UpdateEvent() {
+ ICollection<Teacher> coll = new HashSet<Teacher>();
+ AddItemUpdatedHandler(coll);
+ Teacher kristian = new Teacher("Kristian", "physics");
+ coll.Add(kristian);
+ coll.Add(new Teacher("Poul Einer", "mathematics"));
+ // This should be caught by the update handler:
+ coll.Update(new Teacher("Thomas", "mathematics"));
+ // This should not be caught by the update handler:
+ coll.Remove(kristian);
+ coll.Add(new Teacher("Jens", "physics"));
+ // The update handler is activated also by indexed updates
+ IList<int> list = new ArrayList<int>();
+ list.AddAll(new int[] { 7, 11, 13 });
+ AddItemUpdatedHandler(list);
+ list[1] = 9;
+ }
+ }
+
+ // Example class where objects may be equal yet display differently
+
+ class Teacher : IEquatable<Teacher> {
+ private readonly String name, subject;
+
+ public Teacher(String name, String subject) {
+ this.name = name; this.subject = subject;
+ }
+
+ public bool Equals(Teacher that) {
+ return this.subject.Equals(that.subject);
+ }
+
+ public override int GetHashCode() {
+ return subject.GetHashCode();
+ }
+
+ public override String ToString() {
+ return name + "[" + subject + "]";
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Fileindex.cs b/mcs/class/Mono.C5/UserGuideExamples/Fileindex.cs new file mode 100644 index 00000000000..e609031ce87 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Fileindex.cs @@ -0,0 +1,82 @@ +/*
+ 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: File index: read a text file, build and print a list of
+// words and the line numbers (without duplicates) on which they occur.
+
+// Compile with
+// csc /r:C5.dll Fileindex.cs
+
+using System; // Console
+using System.IO; // StreamReader, TextReader
+using System.Text.RegularExpressions; // Regex
+using C5; // IDictionary, TreeDictionary, TreeSet
+
+namespace FileIndex
+{
+ class Fileindex
+ {
+ static void Main(String[] args)
+ {
+ if (args.Length != 1)
+ Console.WriteLine("Usage: Fileindex <filename>\n");
+ else
+ {
+ IDictionary<String, TreeSet<int>> index = IndexFile(args[0]);
+ PrintIndex(index);
+ }
+ }
+
+ static IDictionary<String, TreeSet<int>> IndexFile(String filename)
+ {
+ IDictionary<String, TreeSet<int>> index = new TreeDictionary<String, TreeSet<int>>();
+ Regex delim = new Regex("[^a-zA-Z0-9]+");
+ using (TextReader rd = new StreamReader(filename))
+ {
+ int lineno = 0;
+ for (String line = rd.ReadLine(); line != null; line = rd.ReadLine())
+ {
+ String[] res = delim.Split(line);
+ lineno++;
+ foreach (String s in res)
+ if (s != "")
+ {
+ if (!index.Contains(s))
+ index[s] = new TreeSet<int>();
+ index[s].Add(lineno);
+ }
+ }
+ }
+ return index;
+ }
+
+ static void PrintIndex(IDictionary<String, TreeSet<int>> index)
+ {
+ foreach (String word in index.Keys)
+ {
+ Console.Write("{0}: ", word);
+ foreach (int ln in index[word])
+ Console.Write("{0} ", ln);
+ Console.WriteLine();
+ }
+ }
+ }
+}
\ No newline at end of file diff --git a/mcs/class/Mono.C5/UserGuideExamples/GCHForm.cs b/mcs/class/Mono.C5/UserGuideExamples/GCHForm.cs new file mode 100644 index 00000000000..dc37742d2fb --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/GCHForm.cs @@ -0,0 +1,271 @@ +/*
+ 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.
+*/
+
+using System;
+using System.Drawing;
+using System.Collections;
+using System.ComponentModel;
+using System.Windows.Forms;
+using System.Diagnostics;
+using C5;
+
+namespace GConvexHull
+{
+ /// <summary>
+ /// Summary description for Form1.
+ /// </summary>
+ public class TesterForm : System.Windows.Forms.Form
+ {
+ //My data
+
+ //My GUI stuff
+ private System.Windows.Forms.Panel drawarea;
+
+ private Graphics drawg;
+
+ //Std stuff
+ private System.Windows.Forms.Button runButton;
+ private TextBox pointCount;
+
+ /// <summary>
+ /// Required designer variable.
+ /// </summary>
+ private System.ComponentModel.Container components = null;
+
+
+ public TesterForm()
+ {
+ //
+ // Required for Windows Form Designer support
+ //
+ InitializeComponent();
+
+ //
+ // TODO: Add any constructor code after InitializeComponent call
+ //
+ drawg = drawarea.CreateGraphics();
+ reset();
+ }
+
+
+ /// <summary>
+ /// Clean up any resources being used.
+ /// </summary>
+ protected override void Dispose(bool disposing)
+ {
+ if (disposing)
+ {
+ if (components != null)
+ {
+ components.Dispose();
+ }
+ }
+
+ base.Dispose(disposing);
+ }
+
+ #region Windows Form Designer generated code
+ /// <summary>
+ /// Required method for Designer support - do not modify
+ /// the contents of this method with the code editor.
+ /// </summary>
+ private void InitializeComponent()
+ {
+ this.drawarea = new System.Windows.Forms.Panel();
+ this.runButton = new System.Windows.Forms.Button();
+ this.pointCount = new System.Windows.Forms.TextBox();
+ this.SuspendLayout();
+ //
+ // drawarea
+ //
+ this.drawarea.BackColor = System.Drawing.Color.White;
+ this.drawarea.Location = new System.Drawing.Point(8, 9);
+ this.drawarea.Name = "drawarea";
+ this.drawarea.Size = new System.Drawing.Size(500, 500);
+ this.drawarea.TabIndex = 0;
+ this.drawarea.Paint += new System.Windows.Forms.PaintEventHandler(this.drawarea_Paint);
+ this.drawarea.Invalidated += new System.Windows.Forms.InvalidateEventHandler(this.drawarea_Invalidated);
+ this.drawarea.MouseMove += new System.Windows.Forms.MouseEventHandler(this.drawarea_MouseMove);
+ this.drawarea.MouseClick += new System.Windows.Forms.MouseEventHandler(this.drawarea_MouseClick);
+ //
+ // runButton
+ //
+ this.runButton.Location = new System.Drawing.Point(8, 516);
+ this.runButton.Name = "runButton";
+ this.runButton.Size = new System.Drawing.Size(42, 20);
+ this.runButton.TabIndex = 1;
+ this.runButton.Text = "Run";
+ this.runButton.Click += new System.EventHandler(this.runButton_Click);
+ //
+ // pointCount
+ //
+ this.pointCount.Location = new System.Drawing.Point(97, 517);
+ this.pointCount.Name = "pointCount";
+ this.pointCount.Size = new System.Drawing.Size(55, 20);
+ this.pointCount.TabIndex = 5;
+ //
+ // TesterForm
+ //
+ this.ClientSize = new System.Drawing.Size(524, 550);
+ this.Controls.Add(this.pointCount);
+ this.Controls.Add(this.runButton);
+ this.Controls.Add(this.drawarea);
+ this.Name = "TesterForm";
+ this.Text = "C5 Tester";
+ this.Load += new System.EventHandler(this.TesterForm_Load);
+ this.ResumeLayout(false);
+ this.PerformLayout();
+
+ }
+ #endregion
+
+ /// <summary>
+ /// The main entry point for the application.
+ /// </summary>
+ [STAThread]
+ static void Main()
+ {
+ Application.EnableVisualStyles();
+ Application.Run(new TesterForm());
+ }
+
+ Point[] pts;
+ Point[] chpts;
+
+ private void runButton_Click(object sender, System.EventArgs e)
+ {
+ int N = int.Parse(pointCount.Text);
+ pts = new Point[N];
+ for (int i = 0; i < N; i++)
+ pts[i] = Point.Random(500, 500);
+ chpts = Convexhull.ConvexHull(pts);
+
+ drawarea.Invalidate();
+ }
+
+
+ private void drawarea_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
+ {
+ mydraw();
+ }
+
+
+ private void resetButton_Click(object sender, System.EventArgs e)
+ {
+ reset();
+ }
+
+
+ private void reset()
+ {
+ drawarea.Invalidate();//(new Rectangle(0, 0, 40, 40));
+ }
+
+
+
+ public void mydraw()
+ {
+ if (pts == null)
+ {
+ return;
+ }
+ for (int i = 0; i < pts.Length; i++)
+ {
+ Point p = pts[i];
+ drawg.DrawEllipse(new Pen(Color.Red), transx(p.x) - 2, transy(p.y) - 2, 4, 4);
+ }
+ for (int i = 0; i < chpts.Length; i++)
+ {
+ int j = i + 1 < chpts.Length ? i + 1 : 0;
+ drawg.DrawEllipse(new Pen(Color.Blue), transx(chpts[i].x) - 2, transy(chpts[i].y) - 2, 4, 4);
+ drawg.DrawLine(new Pen(Color.LawnGreen), transx(chpts[i].x), transx(chpts[i].y), transx(chpts[j].x), transx(chpts[j].y));
+ }
+ }
+
+
+
+ private int transx(double x)
+ {
+ return (int)x;
+ }
+
+
+ private int transy(double y)
+ {
+ return (int)y;
+ }
+
+
+ private void dumpButton_Click(object sender, System.EventArgs e)
+ {
+ Debug.WriteLine("###############");
+ Debug.WriteLine("###############");
+ }
+
+
+ private void graphTypeControlArray_Click(object sender, System.EventArgs e)
+ {
+ Debug.WriteLine(e.GetType());
+ Debug.WriteLine(sender.GetType());
+ drawarea.Invalidate();
+ }
+
+
+ private void drawarea_MouseMove(object sender, MouseEventArgs e)
+ {
+ }
+
+
+ private void drawarea_MouseClick(object sender, MouseEventArgs e)
+ {
+ //double x = untransx(e.X), y = untransy(e.Y);
+
+ }
+
+
+ private void drawarea_Invalidated(object sender, InvalidateEventArgs e)
+ {
+ //msg.Text = e.InvalidRect + "";
+ //mydraw();
+ }
+
+
+ private void preparedFigureSelection_SelectedIndexChanged(object sender, System.EventArgs e)
+ {
+ }
+
+ private void voronoiButton_CheckedChanged(object sender, EventArgs e)
+ {
+ graphTypeControlArray_Click(sender, e);
+ }
+
+ private void delaunayButton_CheckedChanged(object sender, EventArgs e)
+ {
+ graphTypeControlArray_Click(sender, e);
+ }
+
+ private void TesterForm_Load(object sender, EventArgs e)
+ {
+
+ }
+
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/GCHForm.resx b/mcs/class/Mono.C5/UserGuideExamples/GCHForm.resx new file mode 100644 index 00000000000..04d94f3d103 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/GCHForm.resx @@ -0,0 +1,120 @@ +<?xml version="1.0" encoding="utf-8"?>
+<root>
+ <!--
+ Microsoft ResX Schema
+
+ Version 2.0
+
+ The primary goals of this format is to allow a simple XML format
+ that is mostly human readable. The generation and parsing of the
+ various data types are done through the TypeConverter classes
+ associated with the data types.
+
+ Example:
+
+ ... ado.net/XML headers & schema ...
+ <resheader name="resmimetype">text/microsoft-resx</resheader>
+ <resheader name="version">2.0</resheader>
+ <resheader name="reader">System.Resources.ResXResourceReader, System.Windows.Forms, ...</resheader>
+ <resheader name="writer">System.Resources.ResXResourceWriter, System.Windows.Forms, ...</resheader>
+ <data name="Name1"><value>this is my long string</value><comment>this is a comment</comment></data>
+ <data name="Color1" type="System.Drawing.Color, System.Drawing">Blue</data>
+ <data name="Bitmap1" mimetype="application/x-microsoft.net.object.binary.base64">
+ <value>[base64 mime encoded serialized .NET Framework object]</value>
+ </data>
+ <data name="Icon1" type="System.Drawing.Icon, System.Drawing" mimetype="application/x-microsoft.net.object.bytearray.base64">
+ <value>[base64 mime encoded string representing a byte array form of the .NET Framework object]</value>
+ <comment>This is a comment</comment>
+ </data>
+
+ There are any number of "resheader" rows that contain simple
+ name/value pairs.
+
+ Each data row contains a name, and value. The row also contains a
+ type or mimetype. Type corresponds to a .NET class that support
+ text/value conversion through the TypeConverter architecture.
+ Classes that don't support this are serialized and stored with the
+ mimetype set.
+
+ The mimetype is used for serialized objects, and tells the
+ ResXResourceReader how to depersist the object. This is currently not
+ extensible. For a given mimetype the value must be set accordingly:
+
+ Note - application/x-microsoft.net.object.binary.base64 is the format
+ that the ResXResourceWriter will generate, however the reader can
+ read any of the formats listed below.
+
+ mimetype: application/x-microsoft.net.object.binary.base64
+ value : The object must be serialized with
+ : System.Serialization.Formatters.Binary.BinaryFormatter
+ : and then encoded with base64 encoding.
+
+ mimetype: application/x-microsoft.net.object.soap.base64
+ value : The object must be serialized with
+ : System.Runtime.Serialization.Formatters.Soap.SoapFormatter
+ : and then encoded with base64 encoding.
+
+ mimetype: application/x-microsoft.net.object.bytearray.base64
+ value : The object must be serialized into a byte array
+ : using a System.ComponentModel.TypeConverter
+ : and then encoded with base64 encoding.
+ -->
+ <xsd:schema id="root" xmlns="" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:msdata="urn:schemas-microsoft-com:xml-msdata">
+ <xsd:element name="root" msdata:IsDataSet="true">
+ <xsd:complexType>
+ <xsd:choice maxOccurs="unbounded">
+ <xsd:element name="metadata">
+ <xsd:complexType>
+ <xsd:sequence>
+ <xsd:element name="value" type="xsd:string" minOccurs="0" />
+ </xsd:sequence>
+ <xsd:attribute name="name" type="xsd:string" />
+ <xsd:attribute name="type" type="xsd:string" />
+ <xsd:attribute name="mimetype" type="xsd:string" />
+ </xsd:complexType>
+ </xsd:element>
+ <xsd:element name="assembly">
+ <xsd:complexType>
+ <xsd:attribute name="alias" type="xsd:string" />
+ <xsd:attribute name="name" type="xsd:string" />
+ </xsd:complexType>
+ </xsd:element>
+ <xsd:element name="data">
+ <xsd:complexType>
+ <xsd:sequence>
+ <xsd:element name="value" type="xsd:string" minOccurs="0" msdata:Ordinal="1" />
+ <xsd:element name="comment" type="xsd:string" minOccurs="0" msdata:Ordinal="2" />
+ </xsd:sequence>
+ <xsd:attribute name="name" type="xsd:string" msdata:Ordinal="1" />
+ <xsd:attribute name="type" type="xsd:string" msdata:Ordinal="3" />
+ <xsd:attribute name="mimetype" type="xsd:string" msdata:Ordinal="4" />
+ </xsd:complexType>
+ </xsd:element>
+ <xsd:element name="resheader">
+ <xsd:complexType>
+ <xsd:sequence>
+ <xsd:element name="value" type="xsd:string" minOccurs="0" msdata:Ordinal="1" />
+ </xsd:sequence>
+ <xsd:attribute name="name" type="xsd:string" use="required" />
+ </xsd:complexType>
+ </xsd:element>
+ </xsd:choice>
+ </xsd:complexType>
+ </xsd:element>
+ </xsd:schema>
+ <resheader name="resmimetype">
+ <value>text/microsoft-resx</value>
+ </resheader>
+ <resheader name="version">
+ <value>2.0</value>
+ </resheader>
+ <resheader name="reader">
+ <value>System.Resources.ResXResourceReader, System.Windows.Forms, Version=2.0.3600.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value>
+ </resheader>
+ <resheader name="writer">
+ <value>System.Resources.ResXResourceWriter, System.Windows.Forms, Version=2.0.3600.0, Culture=neutral, PublicKeyToken=b77a5c561934e089</value>
+ </resheader>
+ <metadata name="$this.TrayHeight" type="System.Int32, mscorlib, Version=2.0.3600.0, Culture=neutral, PublicKeyToken=b77a5c561934e089">
+ <value>25</value>
+ </metadata>
+</root>
\ No newline at end of file diff --git a/mcs/class/Mono.C5/UserGuideExamples/GConvexHull.cs b/mcs/class/Mono.C5/UserGuideExamples/GConvexHull.cs new file mode 100644 index 00000000000..48675b3bc69 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/GConvexHull.cs @@ -0,0 +1,178 @@ +/*
+ 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.
+*/
+
+// Compile with
+// csc /r:C5.dll GConvexHull.cs
+
+using System;
+using C5;
+
+namespace GConvexHull
+{
+// Find the convex hull of a point set in the plane
+
+// An implementation of Graham's (1972) point elimination algorithm,
+// as modified by Andrew (1979) to find lower and upper hull separately.
+
+// This implementation correctly handle duplicate points, and
+// multiple points with the same x-coordinate.
+
+// 1. Sort the points lexicographically by increasing (x,y), thus
+// finding also a leftmost point L and a rightmost point R.
+// 2. Partition the point set into two lists, upper and lower, according as
+// point is above or below the segment LR. The upper list begins with
+// L and ends with R; the lower list begins with R and ends with L.
+// 3. Traverse the point lists clockwise, eliminating all but the extreme
+// points (thus eliminating also duplicate points).
+// 4. Join the point lists (in clockwise order) in an array,
+// leaving out L from lower and R from upper.
+
+ public class Convexhull
+ {
+ public static Point[] ConvexHull(Point[] pts)
+ {
+ // 1. Sort points lexicographically by increasing (x, y)
+ int N = pts.Length;
+ Array.Sort(pts);
+ Point left = pts[0], right = pts[N - 1];
+ // 2. Partition into lower hull and upper hull
+ IList<Point> lower = new LinkedList<Point>(),
+ upper = new LinkedList<Point>();
+ lower.InsertFirst(left); upper.InsertLast(left);
+ for (int i = 0; i < N; i++)
+ {
+ double det = Point.Area2(left, right, pts[i]);
+ if (det < 0)
+ lower.InsertFirst(pts[i]);
+ else if (det > 0)
+ upper.InsertLast(pts[i]);
+ }
+ lower.InsertFirst(right);
+ upper.InsertLast(right);
+ // 3. Eliminate points not on the hull
+ Eliminate(lower);
+ Eliminate(upper);
+ // 4. Join the lower and upper hull, leaving out lower.Last and upper.Last
+ Point[] res = new Point[lower.Count + upper.Count - 2];
+ lower[0, lower.Count - 1].CopyTo(res, 0);
+ upper[0, upper.Count - 1].CopyTo(res, lower.Count - 1);
+ return res;
+ }
+
+ // Graham's scan
+ public static void Eliminate(IList<Point> lst)
+ {
+ IList<Point> view = lst.View(0, 0);
+ int slide = 0;
+ while (view.TrySlide(slide, 3))
+ if (Point.Area2(view[0], view[1], view[2]) < 0) // right turn
+ slide = 1;
+ else
+ { // left or straight
+ view.RemoveAt(1);
+ slide = view.Offset != 0 ? -1 : 0;
+ }
+ }
+ }
+
+// ------------------------------------------------------------
+
+// Points in the plane
+
+ public class Point : IComparable<Point>
+ {
+ private static readonly C5Random rnd = new C5Random(42);
+
+ public readonly double x, y;
+
+ public Point(double x, double y)
+ {
+ this.x = x; this.y = y;
+ }
+
+ public override string ToString()
+ {
+ return "(" + x + ", " + y + ")";
+ }
+
+ public static Point Random(int w, int h)
+ {
+ return new Point(rnd.Next(w), rnd.Next(h));
+ }
+
+ public bool Equals(Point p2)
+ {
+ return x == p2.x && y == p2.y;
+ }
+
+ public int CompareTo(Point p2)
+ {
+ int major = x.CompareTo(p2.x);
+ return major != 0 ? major : y.CompareTo(p2.y);
+ }
+
+ // Twice the signed area of the triangle (p0, p1, p2)
+ public static double Area2(Point p0, Point p1, Point p2)
+ {
+ return p0.x * (p1.y - p2.y) + p1.x * (p2.y - p0.y) + p2.x * (p0.y - p1.y);
+ }
+ }
+
+// ------------------------------------------------------------
+
+ class GConvexHull
+ {
+ static void Main(String[] args)
+ {
+ if (args.Length == 1)
+ {
+ string arg = args[0];
+ int N = int.Parse(arg);
+ Point[] pts = new Point[N];
+ for (int i = 0; i < N; i++)
+ pts[i] = Point.Random(500, 500);
+ Point[] chpts = Convexhull.ConvexHull(pts);
+ Console.WriteLine("Area is " + Area(chpts));
+ Print(chpts);
+ }
+ else
+ Console.WriteLine("Usage: GConvexHull <pointcount>\n");
+ }
+
+ // The area of a polygon (represented by an array of ordered vertices)
+ public static double Area(Point[] pts)
+ {
+ int N = pts.Length;
+ Point origo = new Point(0, 0);
+ double area2 = 0;
+ for (int i = 0; i < N; i++)
+ area2 += Point.Area2(origo, pts[i], pts[(i + 1) % N]);
+ return Math.Abs(area2 / 2);
+ }
+
+ public static void Print(Point[] pts)
+ {
+ int N = pts.Length;
+ for (int i = 0; i < N; i++)
+ Console.WriteLine(pts[i]);
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/GNfaToDfa.cs b/mcs/class/Mono.C5/UserGuideExamples/GNfaToDfa.cs new file mode 100644 index 00000000000..86766061162 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/GNfaToDfa.cs @@ -0,0 +1,666 @@ +/*
+ 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.
+*/
+
+// Compile with
+// csc /r:C5.dll GNfaToDfa.cs
+
+// C5 examples: RegExp -> NFA -> DFA -> Graph
+// Java 2000-10-07, GC# 2001-10-23, C# 2.0 2003-09-03, C# 2.0+C5 2004-08-08
+
+// This file contains, in order:
+// * Helper class Set<T> defined in terms of C5 classes.
+// * A class Nfa for representing an NFA (a nondeterministic finite
+// automaton), and for converting it to a DFA (a deterministic
+// finite automaton). Most complexity is in this class.
+// * A class Dfa for representing a DFA, a deterministic finite
+// automaton, and for writing a dot input file representing the DFA.
+// * Classes for representing regular expressions, and for building an
+// NFA from a regular expression
+// * A test class that creates an NFA, a DFA, and a dot input file
+// for a number of small regular expressions. The DFAs are
+// not minimized.
+
+using System;
+using System.Text;
+using System.IO;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace GNfaToDfa
+{
+
+ public class Set<T> : HashSet<T> {
+ public Set(SCG.IEnumerable<T> enm) : base() {
+ AddAll(enm);
+ }
+
+ public Set(params T[] elems) : this((SCG.IEnumerable<T>)elems) { }
+
+ // Set union (+), difference (-), and intersection (*):
+
+ public static Set<T> operator +(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set+Set");
+ else {
+ Set<T> res = new Set<T>(s1);
+ res.AddAll(s2);
+ return res;
+ }
+ }
+
+ public static Set<T> operator -(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set-Set");
+ else {
+ Set<T> res = new Set<T>(s1);
+ res.RemoveAll(s2);
+ return res;
+ }
+ }
+
+ public static Set<T> operator *(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set*Set");
+ else {
+ Set<T> res = new Set<T>(s1);
+ res.RetainAll(s2);
+ return res;
+ }
+ }
+
+ // Equality of sets; take care to avoid infinite loops
+
+ public static bool operator ==(Set<T> s1, Set<T> s2) {
+ return EqualityComparer<Set<T>>.Default.Equals(s1, s2);
+ }
+
+ public static bool operator !=(Set<T> s1, Set<T> s2) {
+ return !(s1 == s2);
+ }
+
+ public override bool Equals(Object that) {
+ return this == (that as Set<T>);
+ }
+
+ public override int GetHashCode() {
+ return EqualityComparer<Set<T>>.Default.GetHashCode(this);
+ }
+
+ // Subset (<=) and superset (>=) relation:
+
+ public static bool operator <=(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set<=Set");
+ else
+ return s1.ContainsAll(s2);
+ }
+
+ public static bool operator >=(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set>=Set");
+ else
+ return s2.ContainsAll(s1);
+ }
+
+ public override String ToString() {
+ StringBuilder sb = new StringBuilder();
+ sb.Append("{");
+ bool first = true;
+ foreach (T x in this) {
+ if (!first)
+ sb.Append(",");
+ sb.Append(x);
+ first = false;
+ }
+ sb.Append("}");
+ return sb.ToString();
+ }
+ }
+
+// ----------------------------------------------------------------------
+
+// Regular expressions, NFAs, DFAs, and dot graphs
+// sestoft@dina.kvl.dk *
+// Java 2001-07-10 * C# 2001-10-22 * Gen C# 2001-10-23, 2003-09-03
+
+// In the Generic C# 2.0 version we
+// use Queue<int> and Queue<Set<int>> for worklists
+// use Set<int> for pre-DFA states
+// use ArrayList<Transition> for NFA transition relations
+// use HashDictionary<Set<int>, HashDictionary<String, Set<int>>>
+// and HashDictionary<int, HashDictionary<String, int>> for DFA transition relations
+
+/* Class Nfa and conversion from NFA to DFA ---------------------------
+
+ A nondeterministic finite automaton (NFA) is represented as a
+ dictionary mapping a state number (int) to an arraylist of
+ Transitions, a Transition being a pair of a label lab (a string,
+ null meaning epsilon) and a target state (an int).
+
+ A DFA is created from an NFA in two steps:
+
+ (1) Construct a DFA whose each of whose states is composite,
+ namely a set of NFA states (Set of int). This is done by
+ methods CompositeDfaTrans and EpsilonClose.
+
+ (2) Replace composite states (Set of int) by simple states
+ (int). This is done by methods Rename and MkRenamer.
+
+ Method CompositeDfaTrans works as follows:
+
+ Create the epsilon-closure S0 (a Set of ints) of the start state
+ s0, and put it in a worklist (a Queue). Create an empty DFA
+ transition relation, which is a dictionary mapping a composite
+ state (an epsilon-closed set of ints) to a dictionary mapping a
+ label (a non-null string) to a composite state.
+
+ Repeatedly choose a composite state S from the worklist. If it is
+ not already in the keyset of the DFA transition relation, compute
+ for every non-epsilon label lab the set T of states reachable by
+ that label from some state s in S. Compute the epsilon-closure
+ Tclose of every such state T and put it on the worklist. Then add
+ the transition S -lab-> Tclose to the DFA transition relation, for
+ every lab.
+
+ Method EpsilonClose works as follows:
+
+ Given a set S of states. Put the states of S in a worklist.
+ Repeatedly choose a state s from the worklist, and consider all
+ epsilon-transitions s -eps-> s' from s. If s' is in S already,
+ then do nothing; otherwise add s' to S and the worklist. When the
+ worklist is empty, S is epsilon-closed; return S.
+
+ Method MkRenamer works as follows:
+
+ Given a dictionary mapping a set of int to something, create an
+ injective dictionary mapping from set of int to int, by choosing a
+ fresh int for every key in the given dictionary.
+
+ Method Rename works as follows:
+
+ Given a dictionary mapping a set of int to a dictionary mapping a
+ string to set of int, use the result of MkRenamer to replace all
+ sets of ints by ints.
+
+*/
+
+ class Nfa {
+ private readonly int startState;
+ private readonly int exitState; // This is the unique accept state
+ private readonly IDictionary<int, ArrayList<Transition>> trans;
+
+ public Nfa(int startState, int exitState) {
+ this.startState = startState; this.exitState = exitState;
+ trans = new HashDictionary<int, ArrayList<Transition>>();
+ if (!startState.Equals(exitState))
+ trans.Add(exitState, new ArrayList<Transition>());
+ }
+
+ public int Start { get { return startState; } }
+
+ public int Exit { get { return exitState; } }
+
+ public IDictionary<int, ArrayList<Transition>> Trans {
+ get { return trans; }
+ }
+
+ public void AddTrans(int s1, String lab, int s2) {
+ ArrayList<Transition> s1Trans;
+ if (trans.Contains(s1))
+ s1Trans = trans[s1];
+ else {
+ s1Trans = new ArrayList<Transition>();
+ trans.Add(s1, s1Trans);
+ }
+ s1Trans.Add(new Transition(lab, s2));
+ }
+
+ public void AddTrans(KeyValuePair<int, ArrayList<Transition>> tr) {
+ // Assumption: if tr is in trans, it maps to an empty list (end state)
+ trans.Remove(tr.Key);
+ trans.Add(tr.Key, tr.Value);
+ }
+
+ public override String ToString() {
+ return "NFA start=" + startState + " exit=" + exitState;
+ }
+
+ // Construct the transition relation of a composite-state DFA from
+ // an NFA with start state s0 and transition relation trans (a
+ // dictionary mapping int to arraylist of Transition). The start
+ // state of the constructed DFA is the epsilon closure of s0, and
+ // its transition relation is a dictionary mapping a composite state
+ // (a set of ints) to a dictionary mapping a label (a string) to a
+ // composite state (a set of ints).
+
+ static IDictionary<Set<int>, IDictionary<String, Set<int>>>
+ CompositeDfaTrans(int s0, IDictionary<int, ArrayList<Transition>> trans) {
+ Set<int> S0 = EpsilonClose(new Set<int>(s0), trans);
+ IQueue<Set<int>> worklist = new CircularQueue<Set<int>>();
+ worklist.Enqueue(S0);
+ // The transition relation of the DFA
+ IDictionary<Set<int>, IDictionary<String, Set<int>>> res =
+ new HashDictionary<Set<int>, IDictionary<String, Set<int>>>();
+ while (!worklist.IsEmpty) {
+ Set<int> S = worklist.Dequeue();
+ if (!res.Contains(S)) {
+ // The S -lab-> T transition relation being constructed for a given S
+ IDictionary<String, Set<int>> STrans =
+ new HashDictionary<String, Set<int>>();
+ // For all s in S, consider all transitions s -lab-> t
+ foreach (int s in S) {
+ // For all non-epsilon transitions s -lab-> t, add t to T
+ foreach (Transition tr in trans[s]) {
+ if (tr.lab != null) { // Non-epsilon transition
+ Set<int> toState;
+ if (STrans.Contains(tr.lab)) // Already a transition on lab
+ toState = STrans[tr.lab];
+ else { // No transitions on lab yet
+ toState = new Set<int>();
+ STrans.Add(tr.lab, toState);
+ }
+ toState.Add(tr.target);
+ }
+ }
+ }
+ // Epsilon-close all T such that S -lab-> T, and put on worklist
+ IDictionary<String, Set<int>> STransClosed =
+ new HashDictionary<String, Set<int>>();
+ foreach (KeyValuePair<String, Set<int>> entry in STrans) {
+ Set<int> Tclose = EpsilonClose(entry.Value, trans);
+ STransClosed.Add(entry.Key, Tclose);
+ worklist.Enqueue(Tclose);
+ }
+ res.Add(S, STransClosed);
+ }
+ }
+ return res;
+ }
+
+ // Compute epsilon-closure of state set S in transition relation trans.
+
+ static Set<int>
+ EpsilonClose(Set<int> S, IDictionary<int, ArrayList<Transition>> trans) {
+ // The worklist initially contains all S members
+ IQueue<int> worklist = new CircularQueue<int>();
+ S.Apply(worklist.Enqueue);
+ Set<int> res = new Set<int>(S);
+ while (!worklist.IsEmpty) {
+ int s = worklist.Dequeue();
+ foreach (Transition tr in trans[s]) {
+ if (tr.lab == null && !res.Contains(tr.target)) {
+ res.Add(tr.target);
+ worklist.Enqueue(tr.target);
+ }
+ }
+ }
+ return res;
+ }
+
+ // Compute a renamer, which is a dictionary mapping set of int to int
+
+ static IDictionary<Set<int>, int> MkRenamer(ICollectionValue<Set<int>> states)
+ {
+ IDictionary<Set<int>, int> renamer = new HashDictionary<Set<int>, int>();
+ int count = 0;
+ foreach (Set<int> k in states)
+ renamer.Add(k, count++);
+ return renamer;
+ }
+
+ // Using a renamer (a dictionary mapping set of int to int), replace
+ // composite (set of int) states with simple (int) states in the
+ // transition relation trans, which is a dictionary mapping set of
+ // int to a dictionary mapping from string to set of int. The
+ // result is a dictionary mapping from int to a dictionary mapping
+ // from string to int.
+
+ static IDictionary<int, IDictionary<String, int>>
+ Rename(IDictionary<Set<int>, int> renamer,
+ IDictionary<Set<int>, IDictionary<String, Set<int>>> trans)
+ {
+ IDictionary<int, IDictionary<String, int>> newtrans =
+ new HashDictionary<int, IDictionary<String, int>>();
+ foreach (KeyValuePair<Set<int>, IDictionary<String, Set<int>>> entry
+ in trans) {
+ Set<int> k = entry.Key;
+ IDictionary<String, int> newktrans = new HashDictionary<String, int>();
+ foreach (KeyValuePair<String, Set<int>> tr in entry.Value)
+ newktrans.Add(tr.Key, renamer[tr.Value]);
+ newtrans.Add(renamer[k], newktrans);
+ }
+ return newtrans;
+ }
+
+ static Set<int> AcceptStates(ICollectionValue<Set<int>> states,
+ IDictionary<Set<int>, int> renamer,
+ int exit)
+ {
+ Set<int> acceptStates = new Set<int>();
+ foreach (Set<int> state in states)
+ if (state.Contains(exit))
+ acceptStates.Add(renamer[state]);
+ return acceptStates;
+ }
+
+ public Dfa ToDfa() {
+ IDictionary<Set<int>, IDictionary<String, Set<int>>>
+ cDfaTrans = CompositeDfaTrans(startState, trans);
+ Set<int> cDfaStart = EpsilonClose(new Set<int>(startState), trans);
+ ICollectionValue<Set<int>> cDfaStates = cDfaTrans.Keys;
+ IDictionary<Set<int>, int> renamer = MkRenamer(cDfaStates);
+ IDictionary<int, IDictionary<String, int>> simpleDfaTrans =
+ Rename(renamer, cDfaTrans);
+ int simpleDfaStart = renamer[cDfaStart];
+ Set<int> simpleDfaAccept = AcceptStates(cDfaStates, renamer, exitState);
+ return new Dfa(simpleDfaStart, simpleDfaAccept, simpleDfaTrans);
+ }
+
+ // Nested class for creating distinctly named states when constructing NFAs
+
+ public class NameSource {
+ private static int nextName = 0;
+
+ public int next() {
+ return nextName++;
+ }
+ }
+
+ // Write an input file for the dot program. You can find dot at
+ // http://www.research.att.com/sw/tools/graphviz/
+
+ public void WriteDot(String filename) {
+ TextWriter wr =
+ new StreamWriter(new FileStream(filename, FileMode.Create,
+ FileAccess.Write));
+ wr.WriteLine("// Format this file as a Postscript file with ");
+ wr.WriteLine("// dot " + filename + " -Tps -o out.ps\n");
+ wr.WriteLine("digraph nfa {");
+ wr.WriteLine("size=\"11,8.25\";");
+ wr.WriteLine("rotate=90;");
+ wr.WriteLine("rankdir=LR;");
+ wr.WriteLine("start [style=invis];"); // Invisible start node
+ wr.WriteLine("start -> d" + startState); // Edge into start state
+
+ // The accept state has a double circle
+ wr.WriteLine("d" + exitState + " [peripheries=2];");
+
+ // The transitions
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in trans) {
+ int s1 = entry.Key;
+ foreach (Transition s1Trans in entry.Value) {
+ String lab = s1Trans.lab ?? "eps";
+ int s2 = s1Trans.target;
+ wr.WriteLine("d" + s1 + " -> d" + s2 + " [label=\"" + lab + "\"];");
+ }
+ }
+ wr.WriteLine("}");
+ wr.Close();
+ }
+ }
+
+// Class Transition, a transition from one state to another ----------
+
+ public class Transition {
+ public readonly String lab;
+ public readonly int target;
+
+ public Transition(String lab, int target) {
+ this.lab = lab; this.target = target;
+ }
+
+ public override String ToString() {
+ return "-" + lab + "-> " + target;
+ }
+ }
+
+// Class Dfa, deterministic finite automata --------------------------
+
+/*
+ A deterministic finite automaton (DFA) is represented as a
+ dictionary mapping state number (int) to a dictionary mapping label
+ (a non-null string) to a target state (an int).
+*/
+
+ class Dfa {
+ private readonly int startState;
+ private readonly Set<int> acceptStates;
+ private readonly IDictionary<int, IDictionary<String, int>> trans;
+
+ public Dfa(int startState, Set<int> acceptStates,
+ IDictionary<int, IDictionary<String, int>> trans)
+ {
+ this.startState = startState;
+ this.acceptStates = acceptStates;
+ this.trans = trans;
+ }
+
+ public int Start { get { return startState; } }
+
+ public Set<int> Accept { get { return acceptStates; } }
+
+ public IDictionary<int, IDictionary<String, int>> Trans {
+ get { return trans; }
+ }
+
+ public override String ToString() {
+ return "DFA start=" + startState + "\naccept=" + acceptStates;
+ }
+
+ // Write an input file for the dot program. You can find dot at
+ // http://www.research.att.com/sw/tools/graphviz/
+
+ public void WriteDot(String filename) {
+ TextWriter wr =
+ new StreamWriter(new FileStream(filename, FileMode.Create,
+ FileAccess.Write));
+ wr.WriteLine("// Format this file as a Postscript file with ");
+ wr.WriteLine("// dot " + filename + " -Tps -o out.ps\n");
+ wr.WriteLine("digraph dfa {");
+ wr.WriteLine("size=\"11,8.25\";");
+ wr.WriteLine("rotate=90;");
+ wr.WriteLine("rankdir=LR;");
+ wr.WriteLine("start [style=invis];"); // Invisible start node
+ wr.WriteLine("start -> d" + startState); // Edge into start state
+
+ // Accept states are double circles
+ foreach (int state in trans.Keys)
+ if (acceptStates.Contains(state))
+ wr.WriteLine("d" + state + " [peripheries=2];");
+
+ // The transitions
+ foreach (KeyValuePair<int, IDictionary<String, int>> entry in trans) {
+ int s1 = entry.Key;
+ foreach (KeyValuePair<String, int> s1Trans in entry.Value) {
+ String lab = s1Trans.Key;
+ int s2 = s1Trans.Value;
+ wr.WriteLine("d" + s1 + " -> d" + s2 + " [label=\"" + lab + "\"];");
+ }
+ }
+ wr.WriteLine("}");
+ wr.Close();
+ }
+ }
+
+// Regular expressions ----------------------------------------------
+//
+// Abstract syntax of regular expressions
+// r ::= A | r1 r2 | (r1|r2) | r*
+//
+
+ abstract class Regex {
+ abstract public Nfa MkNfa(Nfa.NameSource names);
+ }
+
+ class Eps : Regex {
+ // The resulting nfa0 has form s0s -eps-> s0e
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ int s0s = names.next();
+ int s0e = names.next();
+ Nfa nfa0 = new Nfa(s0s, s0e);
+ nfa0.AddTrans(s0s, null, s0e);
+ return nfa0;
+ }
+ }
+
+ class Sym : Regex {
+ String sym;
+
+ public Sym(String sym) {
+ this.sym = sym;
+ }
+
+ // The resulting nfa0 has form s0s -sym-> s0e
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ int s0s = names.next();
+ int s0e = names.next();
+ Nfa nfa0 = new Nfa(s0s, s0e);
+ nfa0.AddTrans(s0s, sym, s0e);
+ return nfa0;
+ }
+ }
+
+ class Seq : Regex {
+ Regex r1, r2;
+
+ public Seq(Regex r1, Regex r2) {
+ this.r1 = r1; this.r2 = r2;
+ }
+
+ // If nfa1 has form s1s ----> s1e
+ // and nfa2 has form s2s ----> s2e
+ // then nfa0 has form s1s ----> s1e -eps-> s2s ----> s2e
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ Nfa nfa1 = r1.MkNfa(names);
+ Nfa nfa2 = r2.MkNfa(names);
+ Nfa nfa0 = new Nfa(nfa1.Start, nfa2.Exit);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)
+ nfa0.AddTrans(entry);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa2.Trans)
+ nfa0.AddTrans(entry);
+ nfa0.AddTrans(nfa1.Exit, null, nfa2.Start);
+ return nfa0;
+ }
+ }
+
+ class Alt : Regex {
+ Regex r1, r2;
+
+ public Alt(Regex r1, Regex r2) {
+ this.r1 = r1; this.r2 = r2;
+ }
+
+ // If nfa1 has form s1s ----> s1e
+ // and nfa2 has form s2s ----> s2e
+ // then nfa0 has form s0s -eps-> s1s ----> s1e -eps-> s0e
+ // s0s -eps-> s2s ----> s2e -eps-> s0e
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ Nfa nfa1 = r1.MkNfa(names);
+ Nfa nfa2 = r2.MkNfa(names);
+ int s0s = names.next();
+ int s0e = names.next();
+ Nfa nfa0 = new Nfa(s0s, s0e);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)
+ nfa0.AddTrans(entry);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa2.Trans)
+ nfa0.AddTrans(entry);
+ nfa0.AddTrans(s0s, null, nfa1.Start);
+ nfa0.AddTrans(s0s, null, nfa2.Start);
+ nfa0.AddTrans(nfa1.Exit, null, s0e);
+ nfa0.AddTrans(nfa2.Exit, null, s0e);
+ return nfa0;
+ }
+ }
+
+ class Star : Regex {
+ Regex r;
+
+ public Star(Regex r) {
+ this.r = r;
+ }
+
+ // If nfa1 has form s1s ----> s1e
+ // then nfa0 has form s0s ----> s0s
+ // s0s -eps-> s1s
+ // s1e -eps-> s0s
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ Nfa nfa1 = r.MkNfa(names);
+ int s0s = names.next();
+ Nfa nfa0 = new Nfa(s0s, s0s);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)
+ nfa0.AddTrans(entry);
+ nfa0.AddTrans(s0s, null, nfa1.Start);
+ nfa0.AddTrans(nfa1.Exit, null, s0s);
+ return nfa0;
+ }
+ }
+
+// Trying the RE->NFA->DFA translation on three regular expressions
+
+ class TestNFA {
+ public static void Main(String[] args) {
+ Regex a = new Sym("A");
+ Regex b = new Sym("B");
+ Regex c = new Sym("C");
+ Regex abStar = new Star(new Alt(a, b));
+ Regex bb = new Seq(b, b);
+ Regex r = new Seq(abStar, new Seq(a, b));
+ // The regular expression (a|b)*ab
+ BuildAndShow("ex1", r);
+ // The regular expression ((a|b)*ab)*
+ BuildAndShow("ex2", new Star(r));
+ // The regular expression ((a|b)*ab)((a|b)*ab)
+ BuildAndShow("ex3", new Seq(r, r));
+ // The regular expression (a|b)*abb, from ASU 1986 p 136
+ BuildAndShow("ex4", new Seq(abStar, new Seq(a, bb)));
+ // SML reals: sign?((digit+(\.digit+)?))([eE]sign?digit+)?
+ Regex d = new Sym("digit");
+ Regex dPlus = new Seq(d, new Star(d));
+ Regex s = new Sym("sign");
+ Regex sOpt = new Alt(s, new Eps());
+ Regex dot = new Sym(".");
+ Regex dotDigOpt = new Alt(new Eps(), new Seq(dot, dPlus));
+ Regex mant = new Seq(sOpt, new Seq(dPlus, dotDigOpt));
+ Regex e = new Sym("e");
+ Regex exp = new Alt(new Eps(), new Seq(e, new Seq(sOpt, dPlus)));
+ Regex smlReal = new Seq(mant, exp);
+ BuildAndShow("ex5", smlReal);
+ }
+
+ public static void BuildAndShow(String fileprefix, Regex r) {
+ Nfa nfa = r.MkNfa(new Nfa.NameSource());
+ Console.WriteLine(nfa);
+ Console.WriteLine("Writing NFA graph to file");
+ nfa.WriteDot(fileprefix + "nfa.dot");
+ Console.WriteLine("---");
+ Dfa dfa = nfa.ToDfa();
+ Console.WriteLine(dfa);
+ Console.WriteLine("Writing DFA graph to file");
+ dfa.WriteDot(fileprefix + "dfa.dot");
+ Console.WriteLine();
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/GettingStarted.cs b/mcs/class/Mono.C5/UserGuideExamples/GettingStarted.cs new file mode 100644 index 00000000000..8fac0f9d23e --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/GettingStarted.cs @@ -0,0 +1,50 @@ +/*
+ 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: GettingStarted 2005-01-18
+
+// Compile with
+// csc /r:C5.dll GettingStarted.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace GettingStarted {
+ class GettingStarted {
+ public static void Main(String[] args) {
+ IList<String> names = new ArrayList<String>();
+ names.AddAll(new String[] { "Hoover", "Roosevelt",
+ "Truman", "Eisenhower", "Kennedy" });
+ // Print list:
+ Console.WriteLine(names);
+ // Print item 1 ("Roosevelt") in the list:
+ Console.WriteLine(names[1]);
+ // Create a list view comprising post-WW2 presidents:
+ IList<String> postWWII = names.View(2, 3);
+ // Print item 2 ("Kennedy") in the view:
+ Console.WriteLine(postWWII[2]);
+ // Enumerate and print the list view in reverse chronological order:
+ foreach (String name in postWWII.Backwards())
+ Console.WriteLine(name);
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Graph.cs b/mcs/class/Mono.C5/UserGuideExamples/Graph.cs new file mode 100644 index 00000000000..6c52f2f125e --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Graph.cs @@ -0,0 +1,1679 @@ +/*
+ 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: Graph representation with basic algorithms using C5
+
+
+// Compile with
+// csc /r:C5.dll Graph.cs
+
+
+// The code is structured as a rudimentary Graph library, with an interface
+// for (edge)weighted graphs and a single implementation based on an
+// adjacency list representation using hash dictionaries.
+
+
+// The algorithms implemented include:
+//
+// Breadth-First-Search and Depth-First-Search, with an interface based on actions
+// to be taken as edges are traversed. Applications are checking for connectedness,
+// counting components
+//
+// Priority-First-Search, where edges are traversed according to either weight or
+// accumulated weight from the start of the search.
+// An application of the non-accumulating version is the construction of a minimal
+// spanning tree and therefore the following approximation algorithm.
+// Applications of the accumulating version are the construction of a shortest path
+// and the computation of the distance from one vertex to another one.
+//
+// An approximation algorithm for Travelling Salesman Problems,
+// where the weights satisfies the triangle inequality.
+
+
+// Pervasive generic parameters:
+// V: The type of a vertex in a graph. Vertices are identified
+// by the Equals method inherited from object (or overridden).
+// E: The type of additional data associated with edges in a graph.
+// W: The type of values of weights on edges in a weighted graph,
+// in practise usually int or double. Must be comparable and
+// there must be given a compatible way to add values.
+
+// Interfaces:
+// IGraph<V,E,W>: The interface for a graph implementation with
+// vertex type V, edge dat type E and weight values of type W.
+// IWeight<E,W>: The interface of a weight function
+
+// Classes:
+// HashGraph<V,E,W>: An implementation of IWeightedGraph<V,E,W> based on
+// adjacency lists represented as hash dictionaries.
+// HashGraph<V,E,W>.EdgesValue: A helper class for the Edges() method
+// CountWeight<E>: A
+// IntWeight:
+// DoubleWeight:
+
+// Value Types:
+// Edge<V,E>:
+// EdgeAction<V,E,U>:
+
+// Some notes:
+// The code only supports "natural" equality of vertices.
+
+using C5;
+using System;
+using SCG = System.Collections.Generic;
+
+namespace Graph
+{
+ /// <summary>
+ /// (Duer ikke)
+ /// </summary>
+ /// <typeparam name="V"></typeparam>
+ /// <typeparam name="E"></typeparam>
+ interface IGraphVertex<V, E,W> where W : IComparable<W>
+ {
+ V Value { get;}
+ IGraph<V, E, W> Graph { get;}
+ ICollectionValue<KeyValuePair<V, E>> Adjacent { get;}
+
+ }
+
+ class Vertex<V>
+ {
+ //V v;
+ }
+/// <summary>
+///
+/// </summary>
+/// <typeparam name="V"></typeparam>
+/// <typeparam name="E"></typeparam>
+/// <typeparam name="W"></typeparam>
+ interface IGraph<V, E, W> where W : IComparable<W>
+ {
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>The weight object for this graph</value>
+ IWeight<E, W> Weight { get;}
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>The number of vertices in this graph</value>
+ int VertexCount { get;}
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>The number of edges in this graph</value>
+ int EdgeCount { get;}
+
+ /// <summary>
+ /// The collection of vertices of this graph.
+ /// The return value is a snapshot, not a live view onto the graph.
+ /// </summary>
+ /// <returns></returns>
+ ICollectionValue<V> Vertices();
+
+ /// <summary>
+ /// The collection of edges incident to a particular vertex.
+ /// The return value is a snapshot og (endvertex, edgedata) pairs.
+ /// </summary>
+ /// <param name="vertex"></param>
+ /// <returns></returns>
+ ICollectionValue<KeyValuePair<V, E>> Adjacent(V vertex);
+
+ /// <summary>
+ /// The collection of all edges in the graph. The return value is a snapshot
+ /// of Edge values. Each edge is present once for an undefined direction.
+ /// </summary>
+ /// <returns></returns>
+ ICollectionValue<Edge<V, E>> Edges();
+
+ /// <summary>
+ /// Add a(n isolated) vertex to the graph Ignore if vertex is already in the graph.
+ /// </summary>
+ /// <param name="vertex"></param>
+ /// <returns>True if the vertex was added.</returns>
+ bool AddVertex(V vertex);
+
+ /// <summary>
+ /// Add an edge to the graph. If the edge is already in the graph, update the
+ /// edge data. Add vertices as needed.
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ /// <param name="edgedata"></param>
+ /// <returns>True if the edge was added</returns>
+ bool AddEdge(V start, V end, E edgedata);
+
+ /// <summary>
+ /// Remove a vertex and all its incident edges from the graph.
+ /// </summary>
+ /// <returns>True if the vertex was already in the graph and hence was removed</returns>
+ bool RemoveVertex(V vertex);
+
+ /// <summary>
+ /// Remove an edge from the graph. Do not remove the vertices if they become isolated.
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ /// <param name="edgedata">On output, the edge data associated with the removed edge.</param>
+ /// <returns>True if </returns>
+ bool RemoveEdge(V start, V end, out E edgedata);
+
+ /// <summary>
+ /// Is there an edge from start to end in this graph, and if so, what is
+ /// the data on that edge.
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ /// <param name="edge"></param>
+ /// <returns></returns>
+ bool FindEdge(V start, V end, out E edge);
+
+ /// <summary>
+ /// Construct the subgraph corresponding to a set of vertices.
+ /// </summary>
+ /// <param name="vs"></param>
+ /// <returns></returns>
+ IGraph<V, E, W> SubGraph(ICollectionValue<V> vs);
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>True if graph is connected</value>
+ bool IsConnected { get; }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <value>The number of connected components of this graph</value>
+ int ComponentCount { get;}
+
+ /// <summary>
+ /// Compute the connnected components of this graph.
+ /// </summary>
+ /// <returns>A collection of (vertex,component) pairs, where the first part of the
+ /// pair is some vertex in the component.</returns>
+ ICollectionValue<KeyValuePair<V, IGraph<V, E, W>>> Components();
+
+ /// <summary>
+ /// Traverse the connected component containing the <code>start</code> vertex,
+ /// in either BFS or DFS order, beginning at <code>start</code> and performing the action
+ /// <code>act</code> on each edge part of the constructed tree.
+ /// </summary>
+ /// <param name="bfs">True if BFS, false if DFS</param>
+ /// <param name="start">The vertex to start at</param>
+ /// <param name="act">The action to perform at each node</param>
+ void TraverseVertices(bool bfs, V start, Action<Edge<V, E>> act);
+
+ /// <summary>
+ /// Traverse an undirected graph in either BFS or DFS order, performing the action
+ /// <code>act</code> on each vertex.
+ /// The start vertex of each component of the graph is undefinded.
+ /// </summary>
+ /// <param name="bfs">True if BFS, false if DFS</param>
+ /// <param name="act"></param>
+ void TraverseVertices(bool bfs, Action<V> act);
+
+ /// <summary>
+ /// Traverse an undirected graph in either BFS or DFS order, performing the action
+ /// <code>act</code> on each edge in the traversal and beforecomponent/aftercomponent
+ /// at the start and end of each component (with argument: the start vertex of the component).
+ /// </summary>
+ /// <param name="bfs">True if BFS, false if DFS</param>
+ /// <param name="act"></param>
+ /// <param name="beforecomponent"></param>
+ /// <param name="aftercomponent"></param>
+ void TraverseVertices(bool bfs, Action<Edge<V, E>> act, Action<V> beforecomponent, Action<V> aftercomponent);
+
+ /// <summary>
+ /// A more advanced Depth First Search traversal.
+ /// </summary>
+ /// <param name="start">The vertex to start the search at</param>
+ /// <param name="beforevertex">Action to perform when a vertex is first encountered.</param>
+ /// <param name="aftervertex">Action to perform when all edges out of a vertex has been handles.</param>
+ /// <param name="onfollow">Action to perform as an edge is traversed.</param>
+ /// <param name="onfollowed">Action to perform when an edge is travesed back.</param>
+ /// <param name="onnotfollowed">Action to perform when an edge (a backedge)is seen, but not followed.</param>
+ void DepthFirstSearch(V start, Action<V> beforevertex, Action<V> aftervertex,
+ Action<Edge<V, E>> onfollow, Action<Edge<V, E>> onfollowed, Action<Edge<V, E>> onnotfollowed);
+
+ //TODO: perhaps we should avoid exporting this?
+ /// <summary>
+ /// Traverse the part of the graph reachable from start in order of least distance
+ /// from start according to the weight function. Perform act on the edges of the
+ /// traversal as they are recognised.
+ /// </summary>
+ /// <typeparam name="W"></typeparam>
+ /// <param name="weight"></param>
+ /// <param name="start"></param>
+ /// <param name="act"></param>
+ void PriorityFirstTraverse(bool accumulating, V start, EdgeAction<V, E, W> act);
+
+ /// <summary>
+ /// Compute the (a) shortest path from start to end. THrow an exception if end cannot be reached rom start.
+ /// </summary>
+ /// <param name="weight"></param>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ /// <returns></returns>
+ ICollectionValue<Edge<V, E>> ShortestPath(V start, V end);
+
+ /// <summary>
+ /// Compute the Distance from start to end, i.e. the total weight of a shortest path from start to end.
+ /// Throw an exception if end cannot be reached rom start.
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ /// <returns></returns>
+ W Distance(V start, V end);
+
+ /// <summary>
+ /// Compute a minimum spanning tree for the graph.
+ /// Throw an exception if this graph is not connected.
+ /// </summary>
+ /// <param name="root">(The starting point of the PFS, to be removed)</param>
+ /// <returns></returns>
+ IGraph<V, E, W> MinimumSpanningTree(out V root);
+
+ /// <summary>
+ /// Compute a factor 2 approximation to a Minimum Weight
+ /// Perfect Matching in a graph using NNs
+ /// </summary>
+ /// <returns></returns>
+ ICollectionValue<Edge<V, E>> ApproximateMWPM();
+
+ /// <summary>
+ /// Construct a closed Euler tour of this graph if one exists, i.e. if
+ /// the graph is connected and all vertices have even degrees. Throw an
+ /// ArgumentException if no closed Euler tour exists.
+ /// </summary>
+ /// <returns>A list of vertices in an Euler tour of this graph.</returns>
+ IList<V> EulerTour();
+
+ /// <summary>
+ /// This is intended for implementations of the very simple factor 2 approximation
+ /// algorithms for the travelling salesman problem for Euclidic weight/distance
+ /// functions, i.e. distances that satisfy the triangle inequality. (We do not do 3/2)
+ /// </summary>
+ /// <returns></returns>
+ IDirectedCollectionValue<V> ApproximateTSP();
+
+ /// <summary>
+ /// Pretty-print the graph to the console (for debugging purposes).
+ /// </summary>
+ void Print(System.IO.TextWriter output);
+ }
+
+/// <summary>
+/// The type of an edge in a graph. An edge is identified by its pair of
+/// vertices. The pair is considered ordered, and so an Edge really describes
+/// an edge of the graph in a particular traversal direction.
+/// </summary>
+/// <typeparam name="V">The type of a vertex.</typeparam>
+/// <typeparam name="E">The type of data asociated with edges.</typeparam>
+ struct Edge<V, E>
+ {
+ static SCG.IEqualityComparer<V> vequalityComparer = EqualityComparer<V>.Default;
+ public readonly V start, end;
+ public readonly E edgedata;
+ public Edge(V start, V end, E edgedata)
+ {
+ if (vequalityComparer.Equals(start, end))
+ throw new ArgumentException("Illegal: start and end are equal");
+ this.start = start; this.end = end; this.edgedata = edgedata;
+ }
+
+ public Edge<V, E> Reverse()
+ {
+ return new Edge<V, E>(end, start, edgedata);
+ }
+
+ public override string ToString()
+ {
+ return String.Format("(start='{0}', end='{1}', edgedata='{2}')", start, end, edgedata); ;
+ }
+
+ public override bool Equals(object obj)
+ {
+ if (obj is Edge<V, E>)
+ {
+ Edge<V, E> other = (Edge<V, E>)obj;
+ return vequalityComparer.Equals(start, other.start) && vequalityComparer.Equals(end, other.end);
+ }
+ return false;
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public override int GetHashCode()
+ {
+ //TODO: should we use xor? Or a random factor?
+ return start.GetHashCode() + 148712671 * end.GetHashCode();
+ }
+
+ /// <summary>
+ /// The unordered equalityComparer compares edges independent of the order of the vertices.
+ /// </summary>
+ public class UnorderedEqualityComparer : SCG.IEqualityComparer<Edge<V, E>>
+ {
+ /// <summary>
+ /// Check if two edges have the same vertices irrespective of order.
+ /// </summary>
+ /// <param name="i1"></param>
+ /// <param name="i2"></param>
+ /// <returns></returns>
+ public bool Equals(Edge<V, E> i1, Edge<V, E> i2)
+ {
+ return (vequalityComparer.Equals(i1.start, i2.start) && vequalityComparer.Equals(i1.end, i2.end)) ||
+ (vequalityComparer.Equals(i1.end, i2.start) && vequalityComparer.Equals(i1.start, i2.end));
+ }
+
+ /// <summary>
+ /// Return a hash code compatible with the unordered equals.
+ /// </summary>
+ /// <param name="item"></param>
+ /// <returns></returns>
+ public int GetHashCode(Edge<V, E> item)
+ {
+ return item.start.GetHashCode() ^ item.end.GetHashCode();
+ }
+ }
+ }
+
+/// <summary>
+/// The type of the weight object of a graph. This consists of a function mapping
+/// edge data values to weight values, and an operation to add two weight values.
+/// It is required that weight values are comparable.
+///
+/// The user must assure that the add operation is commutative and fulfills
+/// Add(w1,w2) ≤ w1 for all w1 and w2 that can appear as weights or sums of
+/// weights. In practise, W will be int or double, all weight values will be
+/// non-negative and the addition will be the natural addition on W.
+/// </summary>
+/// <typeparam name="E"></typeparam>
+/// <typeparam name="W"></typeparam>
+ interface IWeight<E, W> where W : IComparable<W>
+ {
+ /// <summary>
+ /// Compute the weight value corresponding to specific edge data.
+ /// </summary>
+ /// <param name="edgedata"></param>
+ /// <returns></returns>
+ W Weight(E edgedata);
+
+ /// <summary>
+ /// Add two weight values.
+ /// </summary>
+ /// <param name="w1"></param>
+ /// <param name="w2"></param>
+ /// <returns></returns>
+ W Add(W w1, W w2);
+ }
+
+/// <summary>
+/// An action to perform when an edge is encountered during a traversal of the graph.
+/// The "extra" parameter is for additional information supplied by the traversal
+/// algorithm.
+/// The intention of the bool return value is that returning false is a signal to the
+/// traversal algorithm to abandon the traversl because the user has already found
+/// what he was looking for.
+/// </summary>
+/// <typeparam name="V"></typeparam>
+/// <typeparam name="E"></typeparam>
+/// <typeparam name="U"></typeparam>
+/// <param name="edge"></param>
+/// <param name="extra"></param>
+/// <returns></returns>
+ delegate bool EdgeAction<V, E, U>(Edge<V, E> edge, U extra);
+
+
+/*
+ For a dense graph, we would use data fields:
+
+ E'[,] or E'[][] for the matrix. Possibly E'[][] for a triangular one!
+ Here E' = struct{E edgedata, bool present} or class{E edgedata}, or if E is a class just E.
+ Thus E' is E! for value types. Or we could have two matrices: E[][] and bool[][].
+
+ HashDictionary<V,int> to map vertex ids to indices.
+ ArrayList<V> for the map the other way.
+ Or simply a HashedArrayList<V> to get both?
+
+ PresentList<int>, FreeList<int> or similar, if we do not want to compact the indices in the matrix on each delete.
+ If we compact, we always do a delete on the vertex<->index map by a replace and a removelast:
+ vimap[ind]=vimap[vimap.Count]; vimap.RemoveLast(); //also reorder matrix!
+
+
+*/
+
+/// <summary>
+/// An implementation of IGraph≤V,E,W≥ based on an adjacency list representation using hash dictionaries.
+/// As a consequence, this will be most efficient for sparse graphs.
+/// </summary>
+/// <typeparam name="V"></typeparam>
+/// <typeparam name="E"></typeparam>
+/// <typeparam name="W"></typeparam>
+ class HashGraph<V, E, W> : IGraph<V, E, W> where W : IComparable<W>
+ {
+ int edgecount;
+
+ HashDictionary<V, HashDictionary<V, E>> graph;
+
+ IWeight<E, W> weight;
+
+ public IWeight<E, W> Weight { get { return weight; } }
+
+
+ /// <summary>
+ /// Create an initially empty graph.
+ /// </summary>
+ /// <param name="weight"></param>
+ [UsedBy("testTSP")]
+ public HashGraph(IWeight<E, W> weight)
+ {
+ this.weight = weight;
+ edgecount = 0;
+ graph = new HashDictionary<V, HashDictionary<V, E>>();
+ }
+
+ /// <summary>
+ /// Constructing a graph with no isolated vertices given a collection of edges.
+ /// </summary>
+ /// <param name="edges"></param>
+ [UsedBy()]
+ public HashGraph(IWeight<E, W> weight, SCG.IEnumerable<Edge<V, E>> edges) : this(weight)
+ {
+ foreach (Edge<V, E> edge in edges)
+ {
+ if (edge.start.Equals(edge.end))
+ throw new ApplicationException("Edge has equal start and end");
+ {
+ HashDictionary<V, E> edgeset;
+ //TODO: utilize upcoming FindOrAddSome operation
+ if (!graph.Find(edge.start, out edgeset))
+ graph.Add(edge.start, edgeset = new HashDictionary<V, E>());
+ if (!edgeset.UpdateOrAdd(edge.end, edge.edgedata))
+ edgecount++;
+ if (!graph.Find(edge.end, out edgeset))
+ graph.Add(edge.end, edgeset = new HashDictionary<V, E>());
+ edgeset.UpdateOrAdd(edge.start, edge.edgedata);
+ }
+ }
+ }
+
+ /// <summary>
+ /// This constructs a graph with a given set of vertices.
+ /// Will only allow these vertices.
+ /// Duplicate edges are allowed.
+ /// </summary>
+ /// <param name="vertices"></param>
+ /// <param name="edges"></param>
+ public HashGraph(IWeight<E, W> weight, SCG.IEnumerable<V> vertices, SCG.IEnumerable<Edge<V, E>> edges) : this(weight)
+ {
+ foreach (V v in vertices)
+ graph.Add(v, new HashDictionary<V, E>());
+ foreach (Edge<V, E> edge in edges)
+ {
+ HashDictionary<V, E> edgeset;
+ if (edge.start.Equals(edge.end))
+ throw new ApplicationException("Edge has equal start and end");
+ if (!graph.Find(edge.start, out edgeset))
+ throw new ApplicationException("Edge has unknown start");
+ if (!edgeset.UpdateOrAdd(edge.end, edge.edgedata))
+ edgecount++;
+ if (!graph.Find(edge.end, out edgeset))
+ throw new ApplicationException("Edge has unknown end");
+ edgeset.UpdateOrAdd(edge.start, edge.edgedata);
+ }
+ }
+
+ [UsedBy("testCOMP")]
+ public int VertexCount { get { return graph.Count; } }
+
+ [UsedBy("testCOMP")]
+ public int EdgeCount { get { return edgecount; } }
+
+ public ICollectionValue<V> Vertices()
+ {
+ return new GuardedCollectionValue<V>(graph.Keys);
+ }
+
+ public ICollectionValue<KeyValuePair<V, E>> Adjacent(V vertex)
+ {
+ return new GuardedCollectionValue<KeyValuePair<V, E>>(graph[vertex]);
+ }
+
+ class EdgesValue : CollectionValueBase<Edge<V, E>>
+ {
+ HashGraph<V, E, W> graph;
+ internal EdgesValue(HashGraph<V, E, W> g) { graph = g; }
+
+ public override bool IsEmpty { get { return graph.edgecount == 0; } }
+
+ public override int Count { get { return graph.edgecount; } }
+
+ public override Speed CountSpeed { get { return Speed.Constant; } }
+
+
+ public override Edge<V, E> Choose()
+ {
+ KeyValuePair<V, HashDictionary<V, E>> adjacent = graph.graph.Choose();
+ KeyValuePair<V, E> otherend = graph.graph[adjacent.Key].Choose();
+ return new Edge<V, E>(adjacent.Key, otherend.Key, otherend.Value);
+ }
+
+ public override SCG.IEnumerator<Edge<V, E>> GetEnumerator()
+ {
+ HashSet<Edge<V, E>> seen = new HashSet<Edge<V, E>>(new Edge<V, E>.UnorderedEqualityComparer());
+ foreach (V v in graph.graph.Keys)
+ foreach (KeyValuePair<V, E> p in graph.graph[v])
+ {
+ Edge<V, E> edge = new Edge<V, E>(v, p.Key, p.Value);
+ if (!seen.FindOrAdd(ref edge))
+ yield return edge;
+ }
+ }
+ }
+
+ public ICollectionValue<Edge<V, E>> Edges()
+ {
+ return new EdgesValue(this);
+ }
+
+ public bool AddVertex(V v)
+ {
+ if (graph.Contains(v))
+ return false;
+ graph.Add(v, new HashDictionary<V, E>());
+ return true;
+ }
+
+ //Note: no warning on update of edgedata!
+ //TODO: Shouldn´t Update or Add return the old value?
+ //Then it would be easy to check for updates
+ public bool AddEdge(V start, V end, E edgedata)
+ {
+ bool retval = false;
+ HashDictionary<V, E> edgeset;
+ if (graph.Find(start, out edgeset))
+ retval = !edgeset.UpdateOrAdd(end, edgedata);
+ else
+ {
+ graph[start] = edgeset = new HashDictionary<V, E>();
+ edgeset[end] = edgedata;
+ retval = true;
+ }
+ if (graph.Find(end, out edgeset))
+ edgeset.UpdateOrAdd(start, edgedata);
+ else
+ {
+ graph[end] = edgeset = new HashDictionary<V, E>();
+ edgeset[start] = edgedata;
+ }
+ if (retval)
+ edgecount++;
+ return retval;
+ }
+
+ public bool RemoveVertex(V vertex)
+ {
+ HashDictionary<V, E> edgeset;
+ if (!graph.Find(vertex, out edgeset))
+ return false;
+ foreach (V othervertex in edgeset.Keys)
+ graph[othervertex].Remove(vertex); //Assert retval==true
+ edgecount -= edgeset.Count;
+ graph.Remove(vertex);
+ return true;
+ }
+
+ public bool RemoveEdge(V start, V end, out E edgedata)
+ {
+ HashDictionary<V, E> edgeset;
+ if (!graph.Find(start, out edgeset))
+ {
+ edgedata = default(E);
+ return false;
+ }
+ if (!edgeset.Remove(end, out edgedata))
+ return false;
+ graph[end].Remove(start);
+ edgecount--;
+ return true;
+ }
+
+ public bool FindEdge(V start, V end, out E edgedata)
+ {
+ HashDictionary<V, E> edges;
+ if (!graph.Find(start, out edges))
+ {
+ edgedata = default(E);
+ return false;
+ }
+ return edges.Find(end, out edgedata);
+ }
+
+ public IGraph<V, E, W> SubGraph(ICollectionValue<V> vs)
+ {
+ HashSet<V> vertexset = vs as HashSet<V>;
+ if (vertexset == null)
+ {
+ vertexset = new HashSet<V>();
+ vertexset.AddAll(vs);
+ }
+
+ return new HashGraph<V, E, W>(weight,
+ vs,
+ Edges().Filter(delegate(Edge<V, E> e) { return vertexset.Contains(e.start) && vertexset.Contains(e.end); }));
+ }
+
+ public bool IsConnected
+ {
+ //TODO: optimize: needs to change Action<Edge<V,E>> to EdgeAction to be able to break out
+ get { return ComponentCount <= 1; }
+ }
+
+ public int ComponentCount
+ {
+ get
+ {
+ int components = 0;
+ TraverseVertices(false, null, delegate(V v) { components++; }, null);
+ return components;
+ }
+ }
+
+ public ICollectionValue<KeyValuePair<V, IGraph<V, E, W>>> Components()
+ {
+ ArrayList<KeyValuePair<V, IGraph<V, E, W>>> retval = new ArrayList<KeyValuePair<V, IGraph<V, E, W>>>();
+ HashGraph<V, E, W> component;
+ ArrayList<V> vertices = null;
+ Action<Edge<V, E>> edgeaction = delegate(Edge<V, E> e)
+ {
+ vertices.Add(e.end);
+ };
+ Action<V> beforecomponent = delegate(V v)
+ {
+ vertices = new ArrayList<V>();
+ vertices.Add(v);
+ };
+ Action<V> aftercomponent = delegate(V v)
+ {
+ //component = SubGraph(vertices);
+ component = new HashGraph<V, E, W>(weight);
+ foreach (V start in vertices)
+ {
+ //component.graph[start] = graph[start].Clone();
+ HashDictionary<V, E> edgeset = component.graph[start] = new HashDictionary<V, E>();
+ foreach (KeyValuePair<V, E> adjacent in graph[start])
+ edgeset[adjacent.Key] = adjacent.Value;
+ }
+ retval.Add(new KeyValuePair<V, IGraph<V, E, W>>(v, component));
+ };
+ TraverseVertices(false, edgeaction, beforecomponent, aftercomponent);
+ return retval;
+ }
+
+ [UsedBy("test1")]
+ public void TraverseVertices(bool bfs, V start, Action<Edge<V, E>> act)
+ {
+ if (!graph.Contains(start))
+ throw new ArgumentException("start Vertex not in graph");
+ IList<Edge<V, E>> todo = new LinkedList<Edge<V, E>>();
+ todo.FIFO = bfs;
+ HashSet<V> seen = new HashSet<V>();
+ V v;
+ while (!todo.IsEmpty || seen.Count == 0)
+ {
+ if (seen.Count > 1)
+ {
+ Edge<V, E> e = todo.Remove();
+ if (act != null)
+ act(e);
+ v = e.end;
+ }
+ else
+ {
+ seen.Add(start);
+ v = start;
+ }
+
+ HashDictionary<V, E> adjacent;
+ if (graph.Find(v, out adjacent))
+ {
+ foreach (KeyValuePair<V, E> p in adjacent)
+ {
+ V end = p.Key;
+ if (!seen.FindOrAdd(ref end))
+ todo.Add(new Edge<V, E>(v, end, p.Value));
+ }
+ }
+ }
+ }
+
+ public void TraverseVertices(bool bfs, Action<V> act)
+ {
+ TraverseVertices(bfs, delegate(Edge<V, E> e) { act(e.end); }, act, null);
+ }
+
+ //TODO: merge the hash set here with the intra omponent one?
+ public void TraverseVertices(bool bfs, Action<Edge<V, E>> act, Action<V> beforecomponent, Action<V> aftercomponent)
+ {
+ HashSet<V> missing = new HashSet<V>();
+ missing.AddAll(Vertices());
+ Action<Edge<V, E>> myact = act + delegate(Edge<V, E> e) { missing.Remove(e.end); };
+ Action<V> mybeforecomponent = beforecomponent + delegate(V v) { missing.Remove(v); };
+ while (!missing.IsEmpty)
+ {
+ V start = default(V);
+ foreach (V v in missing)
+ { start = v; break; }
+ mybeforecomponent(start);
+ TraverseVertices(bfs, start, myact);
+ if (aftercomponent != null)
+ aftercomponent(start);
+ }
+ }
+
+ delegate void Visitor(V v, V parent, bool atRoot);
+
+ //TODO: allow actions to be null
+ [UsedBy("testDFS")]
+ public void DepthFirstSearch(V start, Action<V> before, Action<V> after,
+ Action<Edge<V, E>> onfollow, Action<Edge<V, E>> onfollowed, Action<Edge<V, E>> onnotfollowed)
+ {
+ HashSet<V> seen = new HashSet<V>();
+ seen.Add(start);
+ //If we do not first set visit = null, the compiler will complain at visit(end)
+ //that visit is uninitialized
+ Visitor visit = null;
+ visit = delegate(V v, V parent, bool atRoot)
+ {
+ before(v);
+ HashDictionary<V, E> adjacent;
+ if (graph.Find(v, out adjacent))
+ foreach (KeyValuePair<V, E> p in adjacent)
+ {
+ V end = p.Key;
+ Edge<V, E> e = new Edge<V, E>(v, end, p.Value);
+ if (!seen.FindOrAdd(ref end))
+ {
+ onfollow(e);
+ visit(end, v, false);
+ onfollowed(e);
+ }
+ else
+ {
+ if (!atRoot && !parent.Equals(end))
+ onnotfollowed(e);
+ }
+ }
+ after(v);
+ };
+ visit(start, default(V), true);
+ }
+
+ public void PriorityFirstTraverse(bool accumulated, V start, EdgeAction<V, E, W> act)
+ {
+ if (!graph.Contains(start))
+ throw new ArgumentException("Graph does not contain start");
+ IPriorityQueue<W> fringe = new IntervalHeap<W>();
+ HashDictionary<V, IPriorityQueueHandle<W>> seen = new HashDictionary<V, IPriorityQueueHandle<W>>();
+ HashDictionary<IPriorityQueueHandle<W>, Edge<V, E>> bestedge = new HashDictionary<IPriorityQueueHandle<W>, Edge<V, E>>();
+
+ IPriorityQueueHandle<W> h = null;
+ V current;
+ W currentdist;
+ while (!fringe.IsEmpty || seen.Count == 0)
+ {
+ if (seen.Count == 0)
+ {
+ seen.Add(start, h);
+ current = start;
+ currentdist = default(W);
+ }
+ else
+ {
+ currentdist = fringe.DeleteMin(out h);
+ Edge<V, E> e = bestedge[h];
+ if (!act(e, currentdist))
+ break;
+ bestedge.Remove(h);
+ current = e.end;
+ }
+ HashDictionary<V, E> adjacentnodes;
+ if (graph.Find(current, out adjacentnodes))
+ foreach (KeyValuePair<V, E> adjacent in adjacentnodes)
+ {
+ V end = adjacent.Key;
+ E edgedata = adjacent.Value;
+ W dist = weight.Weight(edgedata), olddist;
+ if (accumulated && !current.Equals(start)) dist = weight.Add(currentdist, weight.Weight(edgedata));
+ if (!seen.Find(end, out h))
+ {
+ h = null;
+ fringe.Add(ref h, dist);
+ seen[end] = h;
+ bestedge[h] = new Edge<V, E>(current, end, edgedata);
+ }
+ else if (fringe.Find(h, out olddist) && dist.CompareTo(olddist) < 0)
+ {
+ fringe[h] = dist;
+ bestedge[h] = new Edge<V, E>(current, end, edgedata);
+ }
+ }
+ }
+ }
+
+ public W Distance(V start, V end)
+ {
+ W dist = default(W);
+ bool found = false;
+ PriorityFirstTraverse(true, start, delegate(Edge<V, E> e, W w)
+ {
+ if (end.Equals(e.end)) { dist = w; found = true; return false; }
+ else return true;
+ });
+ if (found)
+ return dist;
+ throw new ArgumentException(String.Format("No path from {0} to {1}", start, end));
+ }
+
+
+ public ICollectionValue<Edge<V, E>> ShortestPath(V start, V end)
+ {
+ HashDictionary<V, Edge<V, E>> backtrack = new HashDictionary<V, Edge<V, E>>();
+ PriorityFirstTraverse(true, start, delegate(Edge<V, E> e, W w) { backtrack[e.end] = e; return !end.Equals(e.end); });
+ ArrayList<Edge<V, E>> path = new ArrayList<Edge<V, E>>();
+ Edge<V, E> edge;
+ V v = end;
+ while (backtrack.Find(v, out edge))
+ {
+ path.Add(edge);
+ v = edge.start;
+ }
+ if (path.IsEmpty)
+ throw new ArgumentException(String.Format("No path from {0} to {1}", start, end));
+ path.Reverse();
+ return path;
+ }
+
+ /// <summary>
+ /// NB: assume connected, throw exception if not
+ /// </summary>
+ /// <typeparam name="W"></typeparam>
+ /// <param name="edgeWeight"></param>
+ /// <returns></returns>
+ public IGraph<V, E, W> MinimumSpanningTree(out V start)
+ {
+ ArrayList<Edge<V, E>> edges = new ArrayList<Edge<V, E>>();
+ start = default(V);
+ foreach (V v in graph.Keys)
+ { start = v; break; }
+ PriorityFirstTraverse(false, start, delegate(Edge<V, E> e, W w) { edges.Add(e); return true; });
+ if (edges.Count != graph.Count - 1)
+ throw new ArgumentException("Graph not connected");
+ return new HashGraph<V, E, W>(weight, edges);
+ }
+
+ public ICollectionValue<Edge<V, E>> ApproximateMWPM()
+ {
+ //Assume graph complete and even number of vertices
+ HashGraph<V, E, W> clone = new HashGraph<V, E, W>(weight, Edges());
+ ArrayList<Edge<V, E>> evenpath = new ArrayList<Edge<V, E>>();
+ ArrayList<Edge<V, E>> oddpath = new ArrayList<Edge<V, E>>();
+ V start = default(V);
+ foreach (V v in clone.Vertices()) { start = v; break; }
+ V current = start;
+ W evenweight, oddweight;
+ evenweight = oddweight = default(W);
+ bool even = true;
+ while (clone.VertexCount > 0)
+ {
+ V bestvertex = default(V);
+ E bestedge = default(E);
+ W bestweight = default(W);
+ if (clone.VertexCount == 1)
+ {
+ bestvertex = start;
+ bestedge = graph[current][start];
+ bestweight = weight.Weight(bestedge);
+ }
+ else
+ {
+ bool first = true;
+ foreach (KeyValuePair<V, E> p in clone.graph[current])
+ {
+ W thisweight = weight.Weight(p.Value);
+ if (first || bestweight.CompareTo(thisweight) > 0)
+ {
+ bestvertex = p.Key;
+ bestweight = thisweight;
+ bestedge = p.Value;
+ }
+ first = false;
+ }
+ }
+ clone.RemoveVertex(current);
+ //Console.WriteLine("-* {0} / {1} / {2}", bestvertex, bestweight, tour.Count);
+ if (even)
+ {
+ evenweight = evenpath.Count < 1 ? bestweight : weight.Add(evenweight, bestweight);
+ evenpath.Add(new Edge<V, E>(current, bestvertex, bestedge));
+ }
+ else
+ {
+ oddweight = oddpath.Count < 1 ? bestweight : weight.Add(oddweight, bestweight);
+ oddpath.Add(new Edge<V, E>(current, bestvertex, bestedge));
+ }
+ current = bestvertex;
+ even = !even;
+ }
+ //Console.WriteLine("Totalweights: even: {0} and odd: {1}", evenweight, oddweight);
+ return evenweight.CompareTo(oddweight) < 0 ? evenpath : oddpath;
+ }
+
+ /// <summary>
+ /// The construction is performed as follows:
+ /// Start at some vertex. Greedily construct a path starting there by
+ /// following edges at random until no more unused edges are available
+ /// from the current node, which must be the start node. Then follow
+ /// the path constructed so far and whenever we meet a vertex with
+ /// unused edges, construct a path from there greedily as above,
+ /// inserting into the path in front of us.
+ ///
+ /// The algorithm will use constant time for each vertex added
+ /// to the path and
+ ///
+ /// Illustrates use of views as a safe version of listnode pointers
+ /// and hashed linked lists for choosing some item in constant time combined
+ /// with (expected) constant time remove.
+ /// </summary>
+ /// <returns></returns>
+ public IList<V> EulerTour()
+ {
+ bool debug = false;
+ //Assert connected and all degrees even. (Connected is checked at the end)
+ string fmt = "Graph does not have a closed Euler tour: vertex {0} has odd degree {1}";
+ foreach (KeyValuePair<V, HashDictionary<V, E>> adj in graph)
+ if (adj.Value.Count % 2 != 0)
+ throw new ArgumentException(String.Format(fmt, adj.Key, adj.Value.Count));
+
+ LinkedList<V> path = new LinkedList<V>();
+ //Clone the graph data to keep track of used edges.
+ HashDictionary<V, HashedArrayList<V>> edges = new HashDictionary<V, HashedArrayList<V>>();
+ V start = default(V);
+ HashedArrayList<V> adjacent = null;
+ foreach (KeyValuePair<V, HashDictionary<V, E>> p in graph)
+ {
+ adjacent = new HashedArrayList<V>();
+ adjacent.AddAll(p.Value.Keys);
+ start = p.Key;
+ edges.Add(start, adjacent);
+ }
+
+ path.Add(start);
+ IList<V> view = path.View(0, 1);
+ while (adjacent.Count > 0)
+ {
+ V current = view[0];
+ if (debug) Console.WriteLine("==> {0}", current);
+ //Augment the path (randomly) until we return here and all edges
+ while (adjacent.Count > 0)
+ {
+ if (debug) Console.WriteLine(" => {0}, {1}", current, path.Count);
+ V next = adjacent.RemoveFirst();
+ view.Add(next);
+ if (debug) Console.WriteLine("EDGE: " + current + "->" + next);
+ if (!edges[next].Remove(current))
+ Console.WriteLine("Bad");
+ current = next;
+ adjacent = edges[current];
+ }
+ //When we get here, the view contains a closed path, i.e.
+ //view[view.Count-1] == view[0] and we have followed all edges from view[0]
+ //We slide forward along the rest of the path constructed so far and stop at the
+ //first vertex with still unfollwed edges.
+ while (view.Offset < path.Count - 1 && adjacent.Count == 0)
+ {
+ view.Slide(1, 1);
+ if (debug) Console.WriteLine(" -> {0}, {1}", view[0], path.Count);
+ adjacent = edges[view[0]];
+ }
+ }
+ if (path.Count <= edges.Count)
+ throw new ArgumentException("Graph was not connected");
+ return path;
+ }
+
+ /// <summary>
+ /// The purpose of this struct is to be able to create and add new,
+ /// synthetic vertices to a graph.
+ /// </summary>
+ struct Vplus : IEquatable<Vplus>
+ {
+ internal readonly V vertex; internal readonly int id;
+ static SCG.IEqualityComparer<V> vequalityComparer = EqualityComparer<V>.Default;
+ internal Vplus(V v) { vertex = v; id = 0; }
+ internal Vplus(int i) { vertex = default(V); id = i; }
+ //We should override Equals and GetHashCode
+
+ public override string ToString()
+ { return id == 0 ? String.Format("real({0})", vertex) : String.Format("fake({0})", id); }
+
+ public override bool Equals(object obj) { throw new NotImplementedException(); }
+
+ public bool Equals(Vplus other) { return vequalityComparer.Equals(vertex, other.vertex) && id == other.id; }
+
+ public override int GetHashCode() { return vequalityComparer.GetHashCode(vertex) + id; }
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ /// <returns></returns>
+ public IDirectedCollectionValue<V> ApproximateTSP2()
+ {
+ /* Construct a minimum spanning tree for the graph */
+ V root;
+ IGraph<V, E, W> tree = MinimumSpanningTree(out root);
+
+ //Console.WriteLine("========= Matching of odd vertices of mst =========");
+ ArrayList<V> oddvertices = new ArrayList<V>();
+ foreach (V v in tree.Vertices())
+ if (tree.Adjacent(v).Count % 2 != 0)
+ oddvertices.Add(v);
+
+ ICollectionValue<Edge<V, E>> matching = SubGraph(oddvertices).ApproximateMWPM();
+
+ //Console.WriteLine("========= Fuse matching and tree =========");
+ //We must split the edges of the matching with fake temporary vertices
+ //since the matching and the tree may have common edges
+
+ HashGraph<Vplus, E, W> fused = new HashGraph<Vplus, E, W>(weight);
+ foreach (Edge<V, E> e in tree.Edges())
+ fused.AddEdge(new Vplus(e.start), new Vplus(e.end), e.edgedata);
+ int fakeid = 1;
+ foreach (Edge<V, E> e in matching)
+ {
+ Vplus fakevertex = new Vplus(fakeid++);
+ fused.AddEdge(new Vplus(e.start), fakevertex, e.edgedata);
+ fused.AddEdge(fakevertex, new Vplus(e.end), e.edgedata);
+ }
+ fused.Print(Console.Out);
+
+ //Console.WriteLine("========= Remove fake vertices and perform shortcuts =========");
+ IList<Vplus> fusedtour = fused.EulerTour();
+ HashSet<V> seen = new HashSet<V>();
+ IList<V> tour = new ArrayList<V>();
+
+ foreach (Vplus vplus in fused.EulerTour())
+ {
+ V v = vplus.vertex;
+ if (vplus.id == 0 && !seen.FindOrAdd(ref v))
+ tour.Add(v);
+ }
+ return tour;
+ }
+
+ /// <summary>
+ /// (Refer to the litterature, Vazirani)
+ ///
+ /// (Describe: MST+Euler+shortcuts)
+ /// </summary>
+ /// <returns></returns>
+ [UsedBy("testTSP")]
+ public IDirectedCollectionValue<V> ApproximateTSP()
+ {
+ /* Construct a minimum spanning tree for the graph */
+ V root;
+ IGraph<V, E, W> tree = MinimumSpanningTree(out root);
+
+ /* (Virtually) double all edges of MST and construct an Euler tour of the vertices*/
+ LinkedList<V> tour = new LinkedList<V>();
+ tour.Add(root);
+ tour.Add(root);
+ IList<V> view = tour.View(1, 1);
+
+ Action<Edge<V, E>> onfollow = delegate(Edge<V, E> e)
+ {
+ //slide the view until it points to the last copy of e.start
+ while (!view[0].Equals(e.start))
+ view.Slide(1);
+ //then insert two copies of e.end and slide the view one backwards
+ view.InsertFirst(e.end);
+ view.InsertFirst(e.end);
+ view.Slide(1, 1);
+ };
+
+ tree.TraverseVertices(false, root, onfollow);
+
+ /* Finally, slide along the Euler tour and shortcut by removing vertices already seen*/
+ HashSet<V> seen = new HashSet<V>();
+ view = tour.View(0, tour.Count);
+ while (view.Offset < tour.Count - 1)
+ {
+ V v = view[0];
+ if (seen.FindOrAdd(ref v))
+ view.RemoveFirst();
+ else
+ view.Slide(1, view.Count - 1);
+ }
+ return tour;
+ }
+
+ public void Print(System.IO.TextWriter output)
+ {
+ output.WriteLine("Graph has {0} vertices, {1} edges, {2} components", graph.Count, edgecount, ComponentCount);
+ foreach (KeyValuePair<V, HashDictionary<V, E>> p in graph)
+ {
+ output.Write(" {0} -> ", p.Key);
+ foreach (KeyValuePair<V, E> p2 in p.Value)
+ output.Write("{1} (data {2}), ", p.Key, p2.Key, p2.Value);
+ output.WriteLine();
+ }
+ }
+ }
+
+/// <summary>
+/// A weight on a graph that assigns the weight 1 to every edge.
+/// </summary>
+/// <typeparam name="E">(Ignored) type of edgedata</typeparam>
+ class CountWeight<E> : IWeight<E, int>
+ {
+ public int Weight(E edgedata) { return 1; }
+
+ public int Add(int w1, int w2) { return w1 + w2; }
+ }
+
+/// <summary>
+/// A weight on an IGraph<V,int> that uses the value of the edgedata as the weight value.
+/// </summary>
+ class IntWeight : IWeight<int, int>
+ {
+
+ public int Weight(int edgedata) { return edgedata; }
+
+ public int Add(int w1, int w2) { return w1 + w2; }
+
+ }
+
+/// <summary>
+/// A weight on an IGraph<V,double> that uses the value of the edgedata as the weight value.
+/// </summary>
+ class DoubleWeight : IWeight<double, double>
+ {
+
+ public double Weight(double edgedata) { return edgedata; }
+
+ public double Add(double w1, double w2) { return w1 + w2; }
+
+ }
+
+/// <summary>
+/// Attribute used for marking which examples use a particuler graph method
+/// </summary>
+ class UsedByAttribute : Attribute
+ {
+ string[] tests;
+ internal UsedByAttribute(params string[] tests) { this.tests = tests; }
+
+ public override string ToString()
+ {
+ System.Text.StringBuilder sb = new System.Text.StringBuilder();
+ for (int i = 0; i < tests.Length; i++)
+ {
+ if (i > 0)
+ sb.Append(", ");
+ sb.Append(tests[i]);
+ }
+ return sb.ToString();
+ }
+ }
+
+/// <summary>
+/// Attribute for marking example methods with a description
+/// </summary>
+ class ExampleDescriptionAttribute : Attribute
+ {
+ string text;
+ internal ExampleDescriptionAttribute(string text) { this.text = text; }
+
+ public override string ToString() { return text; }
+ }
+
+/// <summary>
+/// A selection of test cases
+/// </summary>
+ class Test
+ {
+ static SCG.IEnumerable<Edge<int, int>> Grid(int n)
+ {
+ Random ran = new Random(1717);
+ for (int i = 1; i <= n; i++)
+ {
+ for (int j = 1; j <= n; j++)
+ {
+ yield return new Edge<int, int>(1000 * i + j, 1000 * (i + 1) + j, ran.Next(1, 100));
+ yield return new Edge<int, int>(1000 * i + j, 1000 * i + j + 1, ran.Next(1, 100));
+ }
+ }
+ }
+
+ static SCG.IEnumerable<Edge<string, int>> Snake(int n)
+ {
+ for (int i = 1; i <= n; i++)
+ {
+ yield return new Edge<string, int>("U" + i, "L" + i, 1);
+ yield return new Edge<string, int>("U" + i, "U" + (i + 1), i % 2 == 0 ? 1 : 10);
+ yield return new Edge<string, int>("L" + i, "L" + (i + 1), i % 2 == 0 ? 10 : 1);
+ }
+ }
+
+ /// <summary>
+ /// Create the edges of a forest of complete binary trees.
+ /// </summary>
+ /// <param name="treeCount">Number of trees</param>
+ /// <param name="height">Height of trees</param>
+ /// <returns></returns>
+ static SCG.IEnumerable<Edge<string, int>> Forest(int treeCount, int height)
+ {
+ for (int i = 0; i < treeCount; i++)
+ {
+ IList<string> q = new ArrayList<string>();
+ string root = String.Format("[{0}]", i);
+ int lmax = height + root.Length;
+ q.Add(root);
+ while (!q.IsEmpty)
+ {
+ string s = q.Remove();
+ string s2 = s + "L";
+ if (s2.Length < lmax)
+ q.Add(s2);
+ yield return new Edge<string, int>(s, s2, 0);
+ s2 = s + "R";
+ if (s2.Length < lmax)
+ q.Add(s2);
+ yield return new Edge<string, int>(s, s2, 0);
+ }
+ }
+ }
+
+ /// <summary>
+ /// Create edges of a graph correspondingto a "wheel" shape: the ecnter and equidistant
+ /// points around the perimeter. The edgedata and edge weights are the euclidean distances.
+ /// </summary>
+ /// <param name="complete">True means the graph will be complete, false that the graph
+ /// will have edges for the spokes and between neighboring perimeter vetices.</param>
+ /// <param name="n">The number of perimeter vertices, must be at least 3.</param>
+ /// <returns>An enumerable with the edges</returns>
+ static SCG.IEnumerable<Edge<string, double>> Wheel(bool complete, int n)
+ {
+ if (n < 3)
+ throw new ArgumentOutOfRangeException("n must be at least 3");
+ string center = "C";
+ string[] perimeter = new string[n];
+ for (int i = 0; i < n; i++)
+ {
+ perimeter[i] = "P" + i;
+ yield return new Edge<string, double>(perimeter[i], center, 1);
+ }
+ if (complete)
+ for (int i = 0; i < n - 1; i++)
+ for (int j = i + 1; j < n; j++)
+ yield return new Edge<string, double>(perimeter[i], perimeter[j], 2 * Math.Sin((j - i) * Math.PI / n));
+ else
+ {
+ for (int i = 0; i < n - 1; i++)
+ yield return new Edge<string, double>(perimeter[i], perimeter[i + 1], 2 * Math.Sin(Math.PI / n));
+ yield return new Edge<string, double>(perimeter[n - 1], perimeter[0], 2 * Math.Sin(Math.PI / n));
+ }
+ }
+
+
+ /// <summary>
+ /// []
+ /// </summary>
+ [ExampleDescription("Basic BFS and DFS using TraverseVertices method")]
+ static void test1()
+ {
+ IGraph<int, int, int> g = new HashGraph<int, int, int>(new CountWeight<int>(), Grid(3));
+ Console.WriteLine("Edge count: {0}", g.Edges().Count);
+ Console.WriteLine("BFS:");
+ g.TraverseVertices(true, 1001, delegate(Edge<int, int> e) { Console.WriteLine(e); });
+ Console.WriteLine("DFS:");
+ g.TraverseVertices(false, 1001, delegate(Edge<int, int> e) { Console.WriteLine(e); });
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ [ExampleDescription("Component methods")]
+ static void testCOMP()
+ {
+ IGraph<string, int, int> g = new HashGraph<string, int, int>(new CountWeight<int>(), Forest(2, 2));
+ Console.WriteLine("Forest has: Vertices: {0}, Edges: {1}, Components: {2}", g.VertexCount, g.EdgeCount, g.ComponentCount);
+ //g.Print(Console.Out);
+ foreach (KeyValuePair<string, IGraph<string, int, int>> comp in g.Components())
+ {
+ Console.WriteLine("Component of {0}:", comp.Key);
+ comp.Value.Print(Console.Out);
+ }
+ }
+
+ //TODO: remove?
+ static void test3()
+ {
+ HashGraph<int, int, int> g = new HashGraph<int, int, int>(new CountWeight<int>(), Grid(5));
+ g.Print(Console.Out);
+ //EdgeWeight<int, IntWeight> weight = delegate(int i) { return i; };
+ Console.WriteLine("========= PFS accum =========");
+ g.PriorityFirstTraverse(
+ true,
+ 2002,
+ delegate(Edge<int, int> e, int d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
+ Console.WriteLine("========= PFS not accum =========");
+ g.PriorityFirstTraverse(
+ false,
+ 2002,
+ delegate(Edge<int, int> e, int d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
+ Console.WriteLine("========= MST =========");
+ int root;
+ g.MinimumSpanningTree(out root).Print(Console.Out);
+ Console.WriteLine("========= SP =========");
+ foreach (Edge<int, int> edge in g.ShortestPath(1001, 5005))
+ Console.WriteLine(edge);
+ }
+
+ static void test4()
+ {
+ IGraph<string, int, int> g = new HashGraph<string, int, int>(new IntWeight(), Snake(5));
+ Console.WriteLine("Edge count: {0}", g.Edges().Count);
+ Console.WriteLine("========= PFS =========");
+ g.PriorityFirstTraverse(false,
+ "U3",
+ delegate(Edge<string, int> e, int d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
+ Console.WriteLine("========= MST =========");
+ string root;
+ IGraph<string, int, int> mst = g.MinimumSpanningTree(out root);
+ mst.Print(Console.Out);
+ Console.WriteLine("DFS:");
+ mst.TraverseVertices(false, root, delegate(Edge<string, int> e) { Console.WriteLine(e); });
+ Console.WriteLine("ATSP:");
+ int first = 0;
+ foreach (string s in g.ApproximateTSP())
+ {
+ Console.Write((first++ == 0 ? "" : " -> ") + s);
+ }
+ }
+
+ /// <summary>
+ /// This example examines the two variants of a priority-first search:
+ /// with accumulated weights, leading to shortest paths from start;
+ /// with non-acumulated weights, leading to a minimum spanning tree.
+ /// </summary>
+ [ExampleDescription("Priority-first-search with and without accumulated weights")]
+ static void testPFS()
+ {
+ IGraph<string, double, double> g = new HashGraph<string, double, double>(new DoubleWeight(), Wheel(false, 10));
+ g.Print(Console.Out);
+ Console.WriteLine("========= PFS non-accumulated weights (-> MST) =========");
+ g.PriorityFirstTraverse(false,
+ "P0",
+ delegate(Edge<string, double> e, double d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
+ Console.WriteLine("========= PFS accumulated weights (-> Shortst paths from start) =========");
+ g.PriorityFirstTraverse(true,
+ "P0",
+ delegate(Edge<string, double> e, double d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
+ }
+
+ /// <summary>
+ ///
+ ///
+ /// (Refer to Vazirani, or do that where ApproximateTSP is implemented)
+ ///
+ /// Note that the tour created is not optimal. [Describe why]
+ /// </summary>
+ [ExampleDescription("Approximate TSP")]
+ static void testTSP()
+ {
+ IGraph<string, double, double> g = new HashGraph<string, double, double>(new DoubleWeight(), Wheel(true, 10));
+ //g.Print(Console.Out);
+ Console.WriteLine("========= MST =========");
+ string root;
+ IGraph<string, double, double> mst = g.MinimumSpanningTree(out root);
+ mst.TraverseVertices(false,
+ root,
+ delegate(Edge<string, double> e) { Console.WriteLine("Edge: {0} -> {1}", e.start, e.end); });
+ Console.WriteLine("========= Approximate TSP =========");
+ int first = 0;
+ foreach (string s in g.ApproximateTSP())
+ {
+ Console.Write((first++ == 0 ? "" : " -> ") + s);
+ }
+ }
+
+ /// <summary>
+ ///
+ ///
+ /// (Refer to Vazirani, or do that where ApproximateTSP is implemented)
+ ///
+ /// Note that the tour created is not optimal. [Describe why]
+ /// </summary>
+ [ExampleDescription("Approximate TSP2")]
+ static void testTSP2()
+ {
+ HashGraph<string, double, double> g = new HashGraph<string, double, double>(new DoubleWeight(), Wheel(true, 20));
+
+ foreach (string s in g.ApproximateTSP2())
+ Console.WriteLine("# " + s);
+ //g.Print(Console.Out);
+ /*
+ Console.WriteLine("========= MST =========");
+ string root;
+ IGraph<string, double, double> mst = g.MinimumSpanningTree(out root);
+ mst.TraverseVertices(false,
+ root,
+ delegate(Edge<string, double> e) { Console.WriteLine("Edge: {0} -> {1}", e.start, e.end); });
+ ArrayList<string> oddvertices = new ArrayList<string>();
+ foreach (string v in mst.Vertices())
+ if (mst.Adjacent(v).Count % 2 != 0)
+ oddvertices.Add(v);
+
+ Console.WriteLine("========= Matching of odd vertices of mst =========");
+ ICollectionValue<Edge<string, double>> matching = g.SubGraph(oddvertices).ApproximateMWPM();
+
+ Console.WriteLine("========= Add matching to mst =========");
+ //We must split the edges of the matchin with fake temporary vertices
+ //(For a general vertex type, we would have to augment it to Pair<V,int>
+ int fake = 0;
+ foreach (Edge<string, double> e in matching)
+ {
+ string fakevertex = "_" + (fake++);
+ mst.AddEdge(e.start, fakevertex, 0);
+ mst.AddEdge(fakevertex, e.end, e.edgedata);
+ }
+ //mst.Print(Console.Out);
+
+ IList<string> tour = mst.EulerTour(), view = tour.View(1, tour.Count - 1);
+
+ //Remove fake vertices
+ while (view.Count > 0)
+ if (view[0].StartsWith("_"))
+ view.RemoveFirst();
+ else
+ view.Slide(1, view.Count - 1);
+
+ Console.WriteLine("========= Approximate TSP 2 =========");
+ //Short cut
+ view = tour.View(1, tour.Count - 1);
+ HashSet<string> seen = new HashSet<string>();
+
+ while (view.Count > 0)
+ {
+ string s = view[0];
+ if (seen.FindOrAdd(ref s))
+ view.RemoveFirst();
+ else
+ view.Slide(1, view.Count - 1);
+ }
+
+ foreach (string s in tour)
+ Console.WriteLine(". " + s);*/
+ }
+
+ /// <summary>
+ ///
+ /// </summary>
+ static void testEuler()
+ {
+ HashGraph<string, double, double> g = new HashGraph<string, double, double>(new DoubleWeight(), Wheel(true, 6));
+ foreach (string s in g.EulerTour())
+ Console.Write(s + " ");
+ Console.WriteLine();
+ }
+
+ /// <summary>
+ /// An articulation point in a graph is a vertex, whose removal will
+ /// disconnect the graph (or its component). This example uses the
+ /// extended DepthFirstSearch method to compute articulation points
+ /// of a graph.
+ ///
+ /// (Refer to Sedgewick. )
+ ///
+ /// Each vertex is given an index in traversal order.
+ /// For each vertex, we compute the least index reachable by going downwards
+ /// in the DFS tree and then following a single non-dfs edge.
+ ///
+ /// Since we cannot store the DFS indices in the vertices without changing the
+ /// (assumed given) vertex type, V, we remember the indices in a V->int
+ /// hash dictionary, index. The "least reachable" values are then stored in an
+ /// array keyed by the index.
+ ///
+ /// The root of the search is an articulation point if it has more than one
+ /// outgoing DFS edges. Other articulation points are non-root vertices, va,
+ /// with an outgoing DFS edge, where the the least reachable index of the other
+ /// vertex is greater or equal to the index of va.
+ /// </summary>
+ [ExampleDescription("Using the advanced DFS to compute articulation points")]
+ static void testDFS()
+ {
+ HashGraph<string, int, int> g = new HashGraph<string, int, int>(new IntWeight());
+ g.AddEdge("A", "B", 0);
+ g.AddEdge("A", "E", 0);
+ g.AddEdge("B", "E", 0);
+ g.AddEdge("B", "C", 0);
+ g.AddEdge("B", "H", 0);
+ g.AddEdge("H", "I", 0);
+ g.AddEdge("B", "D", 0);
+ g.AddEdge("C", "D", 0);
+ g.AddEdge("C", "F", 0);
+ g.AddEdge("C", "G", 0);
+ g.AddEdge("F", "G", 0);
+
+ HashDictionary<string, int> index = new HashDictionary<string, int>();
+ int[] leastIndexReachableFrom = new int[g.VertexCount];
+ int nextindex = 0;
+ int outgoingFromRoot = 0;
+ Action<string> beforevertex = delegate(string v)
+ {
+ int i = (index[v] = nextindex++);
+ leastIndexReachableFrom[i] = i;
+ };
+ Action<string> aftervertex = delegate(string v)
+ {
+ int i = index[v];
+ if (i == 0 && outgoingFromRoot > 1)
+ Console.WriteLine("Articulation point: {0} ({1}>1 outgoing DFS edges from start)",
+ v, outgoingFromRoot);
+ };
+ Action<Edge<string, int>> onfollow = delegate(Edge<string, int> e)
+ {
+ };
+ Action<Edge<string, int>> onfollowed = delegate(Edge<string, int> e)
+ {
+ int startind = index[e.start], endind = index[e.end];
+ if (startind == 0)
+ outgoingFromRoot++;
+ else
+ {
+ int leastIndexReachable = leastIndexReachableFrom[endind];
+ if (leastIndexReachable >= startind)
+ Console.WriteLine("Articulation point: {0} (least index reachable via {3} is {1} >= this index {2})",
+ e.start, leastIndexReachable, startind, e);
+ if (leastIndexReachableFrom[startind] > leastIndexReachable)
+ leastIndexReachableFrom[startind] = leastIndexReachable;
+ }
+ };
+ Action<Edge<string, int>> onnotfollowed = delegate(Edge<string, int> e)
+ {
+ int startind = index[e.start], endind = index[e.end];
+ if (leastIndexReachableFrom[startind] > endind)
+ leastIndexReachableFrom[startind] = endind;
+ };
+
+ string root = "C";
+ g.DepthFirstSearch(root, beforevertex, aftervertex, onfollow, onfollowed, onnotfollowed);
+ Console.WriteLine("Edges:");
+ foreach (Edge<string, int> e in g.Edges())
+ Console.WriteLine("/ {0}", e);
+ }
+
+ static void Main(String[] args)
+ {
+ if (args.Length != 1)
+ {
+ Console.WriteLine("Usage: Graph.exe testno");
+ System.Reflection.MethodInfo[] mis = typeof(Test).GetMethods(
+ System.Reflection.BindingFlags.Static | System.Reflection.BindingFlags.NonPublic);
+ foreach (System.Reflection.MethodInfo mi in mis)
+ {
+ if (mi.GetParameters().Length == 0 && mi.ReturnType == typeof(void) && mi.Name.StartsWith("test"))
+ {
+ object[] attrs = mi.GetCustomAttributes(typeof(ExampleDescriptionAttribute), false);
+ Console.WriteLine(" {0} : {1}", mi.Name.Substring(4), attrs.Length > 0 ? attrs[0] : "");
+ }
+ }
+ }
+ else
+ {
+ string testMethodName = String.Format("test{0}", args[0]);
+
+ System.Reflection.MethodInfo mi = typeof(Test).GetMethod(testMethodName,
+ System.Reflection.BindingFlags.Static | System.Reflection.BindingFlags.NonPublic);
+
+ if (mi == null)
+ Console.WriteLine("No such testmethod, {0}", testMethodName);
+ else
+ {
+ object[] attrs = mi.GetCustomAttributes(typeof(ExampleDescriptionAttribute), false);
+ Console.WriteLine("============================== {0}() ==================================", testMethodName);
+ Console.WriteLine("Description: {0}", attrs.Length > 0 ? attrs[0] : "None");
+ Console.WriteLine("===========================================================================");
+ mi.Invoke(null, null);
+ }
+ }
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/HashCodes.cs b/mcs/class/Mono.C5/UserGuideExamples/HashCodes.cs new file mode 100644 index 00000000000..40938d3291c --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/HashCodes.cs @@ -0,0 +1,106 @@ +/*
+ 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: hash codes, good and bad 2005-02-28
+
+// Compile with
+// csc /r:C5.dll HashCodes.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace MyHashCodesTest {
+ class MyTest {
+ public static void Main(String[] args) {
+ int count = int.Parse(args[0]);
+ {
+ Console.Write("Good hash function: ");
+ Timer t = new Timer();
+ HashSet<int> good
+ = MakeRandom(count, new GoodIntegerEqualityComparer());
+ Console.WriteLine("({0} sec, {1} items)", t.Check(), good.Count);
+ ISortedDictionary<int,int> bcd = good.BucketCostDistribution();
+ foreach (KeyValuePair<int,int> entry in bcd)
+ Console.WriteLine("{0,7} bucket(s) with cost {1,5}",
+ entry.Value, entry.Key);
+ }
+ {
+ Console.Write("Bad hash function: ");
+ Timer t = new Timer();
+ HashSet<int> bad = MakeRandom(count, new BadIntegerEqualityComparer());
+ Console.WriteLine("({0} sec, {1} items)", t.Check(), bad.Count);
+ ISortedDictionary<int,int> bcd = bad.BucketCostDistribution();
+ foreach (KeyValuePair<int,int> entry in bcd)
+ Console.WriteLine("{0,7} bucket(s) with cost {1,5}",
+ entry.Value, entry.Key);
+ }
+ }
+
+ private static readonly C5Random rnd = new C5Random();
+
+ public static HashSet<int> MakeRandom(int count,
+ SCG.IEqualityComparer<int> eqc) {
+ HashSet<int> res;
+ if (eqc == null)
+ res = new HashSet<int>();
+ else
+ res = new HashSet<int>(eqc);
+ for (int i=0; i<count; i++)
+ res.Add(rnd.Next(1000000));
+ return res;
+ }
+
+ private class BadIntegerEqualityComparer : SCG.IEqualityComparer<int> {
+ public bool Equals(int i1, int i2) {
+ return i1 == i2;
+ }
+ public int GetHashCode(int i) {
+ return i % 7;
+ }
+ }
+
+ private class GoodIntegerEqualityComparer : SCG.IEqualityComparer<int> {
+ public bool Equals(int i1, int i2) {
+ return i1 == i2;
+ }
+ public int GetHashCode(int i) {
+ return i;
+ }
+ }
+ }
+
+ // Crude timing utility
+
+ public class Timer {
+ private DateTime start;
+
+ public Timer() {
+ start = DateTime.Now;
+ }
+
+ public double Check() {
+ TimeSpan dur = DateTime.Now - start;
+ return dur.TotalSeconds;
+ }
+ }
+}
+
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Jobqueue.cs b/mcs/class/Mono.C5/UserGuideExamples/Jobqueue.cs new file mode 100644 index 00000000000..15944f702be --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Jobqueue.cs @@ -0,0 +1,147 @@ +/*
+ 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: job queue 2004-11-22
+
+// Compile with
+// csc /r:C5.dll Anagrams.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+class MyJobQueueTest {
+ public static void Main(String[] args) {
+ JobQueue jq = new JobQueue();
+ // One user submits three jobs at time=27
+ Rid rid1 = jq.Submit(new Ip("62.150.83.11"), 27),
+ rid2 = jq.Submit(new Ip("62.150.83.11"), 27),
+ rid3 = jq.Submit(new Ip("62.150.83.11"), 27);
+ // One job is executed
+ jq.ExecuteOne();
+ // Another user submits two jobs at time=55
+ Rid rid4 = jq.Submit(new Ip("130.225.17.5"), 55),
+ rid5 = jq.Submit(new Ip("130.225.17.5"), 55);
+ // One more job is executed
+ jq.ExecuteOne();
+ // The first user tries to cancel his first and last job
+ jq.Cancel(rid1);
+ jq.Cancel(rid3);
+ // The remaining jobs are executed
+ while (jq.ExecuteOne() != null) { }
+ }
+}
+
+class JobQueue {
+ private readonly IPriorityQueue<Job> jobQueue;
+ private readonly IDictionary<Rid,IPriorityQueueHandle<Job>> jobs;
+ private readonly HashBag<Ip> userJobs;
+
+ public JobQueue() {
+ this.jobQueue = new IntervalHeap<Job>();
+ this.jobs = new HashDictionary<Rid,IPriorityQueueHandle<Job>>();
+ this.userJobs = new HashBag<Ip>();
+ }
+
+ public Rid Submit(Ip ip, int time) {
+ int jobCount = userJobs.ContainsCount(ip);
+ Rid rid = new Rid();
+ Job job = new Job(rid, ip, time + 60 * jobCount);
+ IPriorityQueueHandle<Job> h = null;
+ jobQueue.Add(ref h, job);
+ userJobs.Add(ip);
+ jobs.Add(rid, h);
+ Console.WriteLine("Submitted {0}", job);
+ return rid;
+ }
+
+ public Job ExecuteOne() {
+ if (!jobQueue.IsEmpty) {
+ Job job = jobQueue.DeleteMin();
+ userJobs.Remove(job.ip);
+ jobs.Remove(job.rid);
+ Console.WriteLine("Executed {0}", job);
+ return job;
+ } else
+ return null;
+ }
+
+ public void Cancel(Rid rid) {
+ IPriorityQueueHandle<Job> h;
+ if (jobs.Remove(rid, out h)) {
+ Job job = jobQueue.Delete(h);
+ userJobs.Remove(job.ip);
+ Console.WriteLine("Cancelled {0}", job);
+ }
+ }
+}
+
+class Job : IComparable<Job> {
+ public readonly Rid rid;
+ public readonly Ip ip;
+ public readonly int time;
+
+ public Job(Rid rid, Ip ip, int time) {
+ this.rid = rid;
+ this.ip = ip;
+ this.time = time;
+ }
+
+ public int CompareTo(Job that) {
+ return this.time - that.time;
+ }
+
+ public override String ToString() {
+ return rid.ToString();
+ }
+}
+
+class Rid {
+ private readonly int ridNumber;
+ private static int nextRid = 1;
+ public Rid() {
+ ridNumber = nextRid++;
+ }
+ public override String ToString() {
+ return "rid=" + ridNumber;
+ }
+}
+
+class Ip {
+ public readonly String ipString;
+
+ public Ip(String ipString) {
+ this.ipString = ipString;
+ }
+
+ public override int GetHashCode() {
+ return ipString.GetHashCode();
+ }
+
+ public override bool Equals(Object that) {
+ return
+ that != null
+ && that is Ip
+ && this.ipString.Equals(((Ip)that).ipString);
+ }
+}
+
+
diff --git a/mcs/class/Mono.C5/UserGuideExamples/KeywordRecognition.cs b/mcs/class/Mono.C5/UserGuideExamples/KeywordRecognition.cs new file mode 100644 index 00000000000..3758383a2f8 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/KeywordRecognition.cs @@ -0,0 +1,177 @@ +/*
+ 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: Keyword recognition 2004-12-20
+
+// Compile with
+// csc /r:C5.dll KeywordRecognition.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace KeywordRecognition {
+
+class KeywordRecognition {
+ // Array of 77 keywords:
+
+ static readonly String[] keywordArray =
+ { "abstract", "as", "base", "bool", "break", "byte", "case", "catch",
+ "char", "checked", "class", "const", "continue", "decimal", "default",
+ "delegate", "do", "double", "else", "enum", "event", "explicit",
+ "extern", "false", "finally", "fixed", "float", "for", "foreach",
+ "goto", "if", "implicit", "in", "int", "interface", "internal", "is",
+ "lock", "long", "namespace", "new", "null", "object", "operator",
+ "out", "override", "params", "private", "protected", "public",
+ "readonly", "ref", "return", "sbyte", "sealed", "short", "sizeof",
+ "stackalloc", "static", "string", "struct", "switch", "this", "throw",
+ "true", "try", "typeof", "uint", "ulong", "unchecked", "unsafe",
+ "ushort", "using", "virtual", "void", "volatile", "while" };
+
+ private static readonly ICollection<String> kw1;
+
+ private static readonly ICollection<String> kw2;
+
+ private static readonly ICollection<String> kw3;
+
+ private static readonly SCG.IDictionary<String,bool> kw4 =
+ new SCG.Dictionary<String,bool>();
+
+
+ class SC : SCG.IComparer<string>
+ {
+ public int Compare(string a, string b)
+ {
+ return StringComparer.InvariantCulture.Compare(a,b);
+ }
+ }
+
+ class SH : SCG.IEqualityComparer<string>
+ {
+ public int GetHashCode(string item)
+ {
+ return item.GetHashCode();
+ }
+
+ public bool Equals(string i1, string i2)
+ {
+ return i1 == null ? i2 == null : i1.Equals(i2,StringComparison.InvariantCulture);
+ }
+ }
+
+ static KeywordRecognition() {
+ kw1 = new HashSet<String>();
+ kw1.AddAll<string>(keywordArray);
+ kw2 = new TreeSet<String>(new SC());
+ kw2.AddAll<string>(keywordArray);
+ kw3 = new SortedArray<String>(new SC());
+ kw3.AddAll<string>(keywordArray);
+ kw4 = new SCG.Dictionary<String,bool>();
+ foreach (String keyword in keywordArray)
+ kw4.Add(keyword, false);
+ }
+
+ public static bool IsKeyword1(String s) {
+ return kw1.Contains(s);
+ }
+
+ public static bool IsKeyword2(String s) {
+ return kw2.Contains(s);
+ }
+
+ public static bool IsKeyword3(String s) {
+ return kw3.Contains(s);
+ }
+
+ public static bool IsKeyword4(String s) {
+ return kw4.ContainsKey(s);
+ }
+
+ public static bool IsKeyword5(String s) {
+ return Array.BinarySearch(keywordArray, s) >= 0;
+ }
+
+ public static void Main(String[] args) {
+ if (args.Length != 2)
+ Console.WriteLine("Usage: KeywordRecognition <iterations> <word>\n");
+ else {
+ int count = int.Parse(args[0]);
+ String id = args[1];
+
+ {
+ Console.Write("HashSet.Contains ");
+ Timer t = new Timer();
+ for (int i=0; i<count; i++)
+ IsKeyword1(id);
+ Console.WriteLine(t.Check());
+ }
+
+ {
+ Console.Write("TreeSet.Contains ");
+ Timer t = new Timer();
+ for (int i=0; i<count; i++)
+ IsKeyword2(id);
+ Console.WriteLine(t.Check());
+ }
+
+ {
+ Console.Write("SortedArray.Contains ");
+ Timer t = new Timer();
+ for (int i=0; i<count; i++)
+ IsKeyword3(id);
+ Console.WriteLine(t.Check());
+ }
+
+ {
+ Console.Write("SCG.Dictionary.ContainsKey ");
+ Timer t = new Timer();
+ for (int i=0; i<count; i++)
+ IsKeyword4(id);
+ Console.WriteLine(t.Check());
+ }
+
+ {
+ Console.Write("Array.BinarySearch ");
+ Timer t = new Timer();
+ for (int i=0; i<count; i++)
+ IsKeyword5(id);
+ Console.WriteLine(t.Check());
+ }
+ }
+ }
+}
+
+// Crude timing utility ----------------------------------------
+
+public class Timer {
+ private DateTime start;
+
+ public Timer() {
+ start = DateTime.Now;
+ }
+
+ public double Check() {
+ TimeSpan dur = DateTime.Now - start;
+ return dur.TotalSeconds;
+ }
+}
+
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/ListPatterns.cs b/mcs/class/Mono.C5/UserGuideExamples/ListPatterns.cs new file mode 100644 index 00000000000..f980ce6e55f --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/ListPatterns.cs @@ -0,0 +1,141 @@ +/*
+ 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: ListPatterns.cs for pattern chapter
+
+// Compile with
+// csc /r:C5.dll ListPatterns.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace ListPatterns {
+ class ListPatterns {
+ public static void Main(String[] args) {
+ IList<int> list = new ArrayList<int>();
+ list.AddAll(new int[] { 23, 29, 31, 37, 41, 43, 47, 53 });
+ // Reversing and swapping
+ Console.WriteLine(list);
+ list.Reverse();
+ Console.WriteLine(list);
+ ReverseInterval(list, 2, 3);
+ Console.WriteLine(list);
+ SwapInitialFinal(list, 2);
+ Console.WriteLine(list);
+ // Clearing all or part of list
+ list.CollectionCleared
+ += delegate(Object c, ClearedEventArgs eargs) {
+ ClearedRangeEventArgs ceargs = eargs as ClearedRangeEventArgs;
+ if (ceargs != null)
+ Console.WriteLine("Cleared [{0}..{1}]",
+ ceargs.Start, ceargs.Start+ceargs.Count-1);
+ };
+ RemoveSublist1(list, 1, 2);
+ Console.WriteLine(list);
+ RemoveSublist2(list, 1, 2);
+ Console.WriteLine(list);
+ RemoveTail1(list, 3);
+ Console.WriteLine(list);
+ RemoveTail2(list, 2);
+ Console.WriteLine(list);
+ }
+
+ // Reverse list[i..i+n-1]
+
+ public static void ReverseInterval<T>(IList<T> list, int i, int n) {
+ list.View(i,n).Reverse();
+ }
+
+ // Swap list[0..i-1] with list[i..Count-1]
+
+ public static void SwapInitialFinal<T>(IList<T> list, int i) {
+ list.View(0,i).Reverse();
+ list.View(i,list.Count-i).Reverse();
+ list.Reverse();
+ }
+
+ // Remove sublist of a list
+
+ public static void RemoveSublist1<T>(IList<T> list, int i, int n) {
+ list.RemoveInterval(i, n);
+ }
+
+ public static void RemoveSublist2<T>(IList<T> list, int i, int n) {
+ list.View(i, n). Clear();
+ }
+
+
+ // Remove tail of a list
+
+ public static void RemoveTail1<T>(IList<T> list, int i) {
+ list.RemoveInterval(i, list.Count-i);
+ }
+
+ public static void RemoveTail2<T>(IList<T> list, int i) {
+ list.View(i, list.Count-i).Clear();
+ }
+
+ // Pattern for finding and using first (leftmost) x in list
+
+ private static void PatFirst<T>(IList<T> list, T x) {
+ int j = list.IndexOf(x);
+ if (j >= 0) {
+ // x is a position j in list
+ } else {
+ // x is not in list
+ }
+ }
+
+ // Pattern for finding and using last (rightmost) x in list
+
+ private static void PatLast<T>(IList<T> list, T x) {
+ int j = list.LastIndexOf(x);
+ if (j >= 0) {
+ // x is at position j in list
+ } else {
+ // x is not in list
+ }
+ }
+
+ // Pattern for finding and using first (leftmost) x in list[i..i+n-1]
+
+ private static void PatFirstSublist<T>(IList<T> list, T x, int i, int n) {
+ int j = list.View(i,n).IndexOf(x);
+ if (j >= 0) {
+ // x is at position j+i in list
+ } else {
+ // x is not in list[i..i+n-1]
+ }
+ }
+
+ // Pattern for finding and using last (rightmost) x in list[i..i+n-1]
+
+ private static void PatLastSublist<T>(IList<T> list, T x, int i, int n) {
+ int j = list.View(i,n).LastIndexOf(x);
+ if (j >= 0) {
+ // x is at position j+i in list
+ } else {
+ // x is not in list[i..i+n-1]
+ }
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Locking.cs b/mcs/class/Mono.C5/UserGuideExamples/Locking.cs new file mode 100644 index 00000000000..30365596407 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Locking.cs @@ -0,0 +1,97 @@ +// C5 example: locking 2005-11-07
+
+// Compile with
+// csc /r:C5.dll Locking.cs
+
+using System;
+using System.Threading;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace Locking {
+ class Locking {
+ static ArrayList<int> coll = new ArrayList<int>();
+ // static SCG.List<int> coll = new SCG.List<int>();
+ static readonly int count = 1000;
+
+ public static void Main(String[] args) {
+ Console.WriteLine("Adding and removing without locking:");
+ RunTwoThreads(delegate { AddAndRemove(15000); });
+ Console.WriteLine("coll has {0} items, should be 0", coll.Count);
+
+ coll = new ArrayList<int>();
+ Console.WriteLine("Adding and removing with locking:");
+ RunTwoThreads(delegate { SafeAddAndRemove(15000); });
+ Console.WriteLine("coll has {0} items, should be 0", coll.Count);
+
+ Console.WriteLine("Moving items without locking:");
+ ArrayList<int> from, to;
+ from = new ArrayList<int>();
+ to = new ArrayList<int>();
+ for (int i=0; i<count; i++)
+ from.Add(i);
+ RunTwoThreads(delegate { while (!from.IsEmpty) Move(from, to); });
+ Console.WriteLine("coll has {0} items, should be {1}", to.Count, count);
+
+ Console.WriteLine("Moving items with locking:");
+ from = new ArrayList<int>();
+ to = new ArrayList<int>();
+ for (int i=0; i<count; i++)
+ from.Add(i);
+ RunTwoThreads(delegate { while (!from.IsEmpty) SafeMove(from, to); });
+ Console.WriteLine("coll has {0} items, should be {1}", to.Count, count);
+ }
+
+ public static void RunTwoThreads(Act run) {
+ Thread t1 = new Thread(new ThreadStart(run)),
+ t2 = new Thread(new ThreadStart(run));
+ t1.Start(); t2.Start();
+ t1.Join(); t2.Join();
+ }
+
+ // Concurrently adding to and removing from an arraylist
+
+ public static void AddAndRemove(int count) {
+ for (int i=0; i<count; i++)
+ coll.Add(i);
+ for (int i=0; i<count; i++)
+ coll.Remove(i);
+ }
+
+ private static readonly Object sync = new Object();
+
+ public static void SafeAddAndRemove(int count) {
+ for (int i=0; i<count; i++)
+ lock (sync)
+ coll.Add(i);
+ for (int i=0; i<count; i++)
+ lock (sync)
+ coll.Remove(i);
+ }
+
+ public static void SafeAdd<T>(IExtensible<T> coll, T x) {
+ lock (sync) {
+ coll.Add(x);
+ }
+ }
+
+ public static void Move<T>(ICollection<T> from, ICollection<T> to) {
+ if (!from.IsEmpty) {
+ T x = from.Choose();
+ Thread.Sleep(0); // yield processor to other threads
+ from.Remove(x);
+ to.Add(x);
+ }
+ }
+
+ public static void SafeMove<T>(ICollection<T> from, ICollection<T> to) {
+ lock (sync)
+ if (!from.IsEmpty) {
+ T x = from.Choose();
+ Thread.Sleep(0); // yield processor to other threads
+ from.Remove(x);
+ to.Add(x);
+ }
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Makefile b/mcs/class/Mono.C5/UserGuideExamples/Makefile new file mode 100644 index 00000000000..a2db8fc60fd --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Makefile @@ -0,0 +1,27 @@ +# Makefile for C5 book examples
+
+USERGUIDEFILES= Anagrams.cs Antipatterns.cs CollectionSanity.cs EventPatterns.cs \
+ Fileindex.cs GConvexHull.cs GNfaToDfa.cs GettingStarted.cs \
+ Graph.cs Graphcopy.cs HashCodes.cs Jobqueue.cs \
+ KeywordRecognition.cs ListPatterns.cs ListPatterns.cs \
+ Locking.cs MultiDictionary.cs PointLocation.cs \
+ RandomSelection.cs ReadOnlyPatterns.cs Sets.cs \
+ SortedIterationPatterns.cs SortedIterationPatterns.cs \
+ SortingPermutation.cs Toposort.cs ViewPatterns.cs WrappedArray.cs
+
+all: c5examples.zip
+
+c5examples.zip: ${USERGUIDEFILES}
+ rm -f C5.examples.zip
+ zip C5.examples.zip ${USERGUIDEFILES}
+
+clean:
+ rm -f C5.examples.zip
+ rm -f *.dot
+ rm -f *.exe
+ rm -f *.ps
+ rm -f *.eps
+
+.SUFFIXES :
+.SUFFIXES : .cs
+
diff --git a/mcs/class/Mono.C5/UserGuideExamples/MultiCollection.cs b/mcs/class/Mono.C5/UserGuideExamples/MultiCollection.cs new file mode 100644 index 00000000000..32ec13ae7d0 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/MultiCollection.cs @@ -0,0 +1,131 @@ +/*
+ 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.
+*/
+
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace MultiCollection
+{
+ class BasicCollectionValue<T> : CollectionValueBase<T>, ICollectionValue<T>
+ {
+ SCG.IEnumerable<T> enumerable;
+ Fun<T> chooser;
+ int count;
+ //TODO: add delegate for checking validity!
+
+ public BasicCollectionValue(SCG.IEnumerable<T> e, Fun<T> chooser, int c) { enumerable = e; count = c; this.chooser = chooser; }
+
+ public override int Count { get { return count; } }
+
+ public override Speed CountSpeed { get { return Speed.Constant; } }
+
+ public override bool IsEmpty { get { return count == 0; } }
+
+ public override T Choose() { return chooser(); }
+
+ public override System.Collections.Generic.IEnumerator<T> GetEnumerator()
+ {
+ return enumerable.GetEnumerator();
+ }
+ }
+
+ interface IMultiCollection<K, V>
+ {
+ SCG.IEqualityComparer<K> KeyEqualityComparer { get;}
+ SCG.IEqualityComparer<V> ValueEqualityComparer { get;}
+ bool Add(K k, V v);
+ bool Remove(K k, V v);
+ ICollectionValue<V> this[K k] { get;}
+ ICollectionValue<K> Keys { get;}
+ SCG.IEnumerable<V> Values { get;}
+
+ }
+
+ class BasicMultiCollection<K, V, W, U> : IMultiCollection<K, V>//: IDictionary<K, W>
+ where W : ICollection<V>, new()
+ where U : IDictionary<K, W>, new()
+ {
+ U dict = new U();
+
+ public SCG.IEqualityComparer<K> KeyEqualityComparer { get { return EqualityComparer<K>.Default; } }
+
+ public SCG.IEqualityComparer<V> ValueEqualityComparer { get { return EqualityComparer<V>.Default; } } //TODO: depends on W!
+
+ public bool Add(K k, V v)
+ {
+ W w;
+ if (!dict.Find(k, out w))
+ dict.Add(k,w = new W());
+ return w.Add(v);
+ }
+
+ public bool Remove(K k, V v)
+ {
+ W w;
+ if (dict.Find(k, out w) && w.Remove(v))
+ {
+ if (w.Count == 0)
+ dict.Remove(k);
+ return true;
+ }
+ return false;
+ }
+
+ public ICollectionValue<V> this[K k] { get { return dict[k]; } }
+
+ public ICollectionValue<K> Keys { get { return dict.Keys; } }
+
+ public SCG.IEnumerable<V> Values
+ {
+ get
+ {
+ foreach (W w in dict.Values)
+ foreach (V v in w)
+ yield return v;
+ }
+ }
+ }
+
+ class WordIndex : BasicMultiCollection<string,int,HashSet<int>,HashDictionary<string,HashSet<int>>>
+ {
+ }
+
+ class MyTest
+ {
+ public static void Main(String[] args)
+ {
+ WordIndex wi = new WordIndex();
+ wi.Add("ja", 2);
+ wi.Add("nej", 4);
+ wi.Add("ja", 7);
+ foreach (string s in wi.Keys)
+ {
+ Console.WriteLine(s + " -->");
+ foreach (int line in wi[s])
+ {
+ Console.WriteLine(" " + line);
+ }
+ }
+ }
+ }
+}
\ No newline at end of file diff --git a/mcs/class/Mono.C5/UserGuideExamples/MultiDictionary.cs b/mcs/class/Mono.C5/UserGuideExamples/MultiDictionary.cs new file mode 100644 index 00000000000..22fad233345 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/MultiDictionary.cs @@ -0,0 +1,308 @@ +/*
+ 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: 2006-01-29
+
+// Compile with
+// csc /r:C5.dll MultiDictionary.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace MultiDictionaries {
+
+ using MultiDictionary2;
+
+ class MyTest {
+ public static void Main(String[] args) {
+ MultiHashDictionary<int,String> mdict = new MultiHashDictionary<int,String>();
+ mdict.Add(2, "to");
+ mdict.Add(2, "deux");
+ mdict.Add(2, "two");
+ mdict.Add(20, "tyve");
+ mdict.Add(20, "twenty");
+ Console.WriteLine(mdict);
+ Console.WriteLine("mdict.Count is {0}", mdict.Count);
+ Console.WriteLine("mdict.Count (keys) is {0}",
+ ((IDictionary<int,ICollection<String>>)mdict).Count);
+ Console.WriteLine("mdict[2].Count is {0}", mdict[2].Count);
+ mdict.Remove(20, "tyve");
+ mdict.Remove(20, "twenty");
+ Console.WriteLine(mdict);
+ Console.WriteLine("mdict.Count is {0}", mdict.Count);
+ ICollection<String> zwei = new HashSet<String>();
+ zwei.Add("zwei");
+ mdict[2] = zwei;
+ mdict[-2] = zwei;
+ Console.WriteLine(mdict);
+ Console.WriteLine("mdict.Count is {0}", mdict.Count);
+ zwei.Add("kaksi");
+ Console.WriteLine(mdict);
+ Console.WriteLine("mdict.Count is {0}", mdict.Count);
+ ICollection<String> empty = new HashSet<String>();
+ mdict[0] = empty;
+ Console.WriteLine(mdict);
+ Console.WriteLine("mdict.Count is {0}", mdict.Count);
+ Console.WriteLine("mdict contains key 0: {0}", mdict.Contains(0));
+ mdict.Remove(-2);
+ Console.WriteLine(mdict);
+ Console.WriteLine("mdict.Count is {0}", mdict.Count);
+ zwei.Remove("kaksi");
+ Console.WriteLine(mdict);
+ Console.WriteLine("mdict.Count is {0}", mdict.Count);
+ zwei.Clear();
+ Console.WriteLine(mdict);
+ Console.WriteLine("mdict.Count is {0}", mdict.Count);
+ }
+ }
+}
+
+namespace MultiDictionary1 {
+ // Here we implement a multivalued dictionary as a hash dictionary
+ // from keys to value collections. The value collections may have set
+ // or bag semantics.
+
+ // The value collections are externally modifiable (as in Peter
+ // Golde's PowerCollections library), and therefore:
+ //
+ // * A value collection associated with a key may be null or
+ // non-empty. Hence for correct semantics, the Contains(k) method
+ // must check that the value collection associated with a key is
+ // non-null and non-empty.
+ //
+ // * A value collection may be shared between two or more keys.
+ //
+
+ // A C5 hash dictionary each of whose keys map to a collection of values.
+
+ public class MultiHashDictionary<K,V> : HashDictionary<K, ICollection<V>> {
+
+ // Return total count of values associated with keys. This basic
+ // implementation simply sums over all value collections, and so
+ // is a linear-time operation in the total number of values.
+
+ public new virtual int Count {
+ get {
+ int count = 0;
+ foreach (KeyValuePair<K,ICollection<V>> entry in this)
+ if (entry.Value != null)
+ count += entry.Value.Count;
+ return count;
+ }
+ }
+
+ public override Speed CountSpeed {
+ get { return Speed.Linear; }
+ }
+
+ // Add a (key,value) pair
+
+ public virtual void Add(K k, V v) {
+ ICollection<V> values;
+ if (!base.Find(k, out values) || values == null) {
+ values = new HashSet<V>();
+ Add(k, values);
+ }
+ values.Add(v);
+ }
+
+ // Remove a single (key,value) pair, if present; return true if
+ // anything was removed, else false
+
+ public virtual bool Remove(K k, V v) {
+ ICollection<V> values;
+ if (base.Find(k, out values) && values != null) {
+ if (values.Remove(v)) {
+ if (values.IsEmpty)
+ base.Remove(k);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ // Determine whether key k is associated with a value
+
+ public override bool Contains(K k) {
+ ICollection<V> values;
+ return Find(k, out values) && values != null && !values.IsEmpty;
+ }
+
+ // Determine whether each key in ks is associated with a value
+
+ public override bool ContainsAll<U>(SCG.IEnumerable<U> ks) {
+ foreach (K k in ks)
+ if (!Contains(k))
+ return false;
+ return true;
+ }
+
+ // Get or set the value collection associated with key k
+
+ public override ICollection<V> this[K k] {
+ get {
+ ICollection<V> values;
+ return base.Find(k, out values) && values != null ? values : new HashSet<V>();
+ }
+ set {
+ base[k] = value;
+ }
+ }
+
+ // Inherited from base class HashDictionary<K,ICollection<V>>:
+
+ // Add(K k, ICollection<V> values)
+ // AddAll(IEnumerable<KeyValuePair<K,ICollection<V>>> kvs)
+ // Clear
+ // Clone
+ // Find(K k, out ICollection<V> values)
+ // Find(ref K k, out ICollection<V> values)
+ // FindOrAdd(K k, ref ICollection<V> values)
+ // Remove(K k)
+ // Remove(K k, out ICollection<V> values)
+ // Update(K k, ICollection<V> values)
+ // Update(K k, ICollection<V> values, out ICollection<V> oldValues)
+ // UpdateOrAdd(K k, ICollection<V> values)
+ // UpdateOrAdd(K k, ICollection<V> values, out ICollection<V> oldValues)
+ }
+}
+
+
+namespace MultiDictionary2 {
+ // Here we implement a multivalued dictionary as a hash dictionary
+ // from keys to value collections. The value collections may have
+ // set or bag semantics. This version uses event listeners to make
+ // the Count operation constant time.
+
+ // * To avoid recomputing the total number of values for the Count
+ // property, one may cache it and then use event listeners on the
+ // value collections to keep the cached count updated. In turn, this
+ // requires such event listeners on the dictionary also.
+
+ // A C5 hash dictionary each of whose keys map to a collection of values.
+
+ public class MultiHashDictionary<K,V> : HashDictionary<K, ICollection<V>> {
+ private int count = 0; // Cached value count, updated by events only
+
+ private void IncrementCount(Object sender, ItemCountEventArgs<V> args) {
+ count += args.Count;
+ }
+
+ private void DecrementCount(Object sender, ItemCountEventArgs<V> args) {
+ count -= args.Count;
+ }
+
+ private void ClearedCount(Object sender, ClearedEventArgs args) {
+ count -= args.Count;
+ }
+
+ public MultiHashDictionary() {
+ ItemsAdded +=
+ delegate(Object sender, ItemCountEventArgs<KeyValuePair<K,ICollection<V>>> args) {
+ ICollection<V> values = args.Item.Value;
+ if (values != null) {
+ count += values.Count;
+ values.ItemsAdded += IncrementCount;
+ values.ItemsRemoved += DecrementCount;
+ values.CollectionCleared += ClearedCount;
+ }
+ };
+ ItemsRemoved +=
+ delegate(Object sender, ItemCountEventArgs<KeyValuePair<K,ICollection<V>>> args) {
+ ICollection<V> values = args.Item.Value;
+ if (values != null) {
+ count -= values.Count;
+ values.ItemsAdded -= IncrementCount;
+ values.ItemsRemoved -= DecrementCount;
+ values.CollectionCleared -= ClearedCount;
+ }
+ };
+ }
+
+ // Return total count of values associated with keys.
+
+ public new virtual int Count {
+ get {
+ return count;
+ }
+ }
+
+ public override Speed CountSpeed {
+ get { return Speed.Constant; }
+ }
+
+ // Add a (key,value) pair
+
+ public virtual void Add(K k, V v) {
+ ICollection<V> values;
+ if (!base.Find(k, out values) || values == null) {
+ values = new HashSet<V>();
+ Add(k, values);
+ }
+ values.Add(v);
+ }
+
+ // Remove a single (key,value) pair, if present; return true if
+ // anything was removed, else false
+
+ public virtual bool Remove(K k, V v) {
+ ICollection<V> values;
+ if (base.Find(k, out values) && values != null) {
+ if (values.Remove(v)) {
+ if (values.IsEmpty)
+ base.Remove(k);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ // Determine whether key k is associated with a value
+
+ public override bool Contains(K k) {
+ ICollection<V> values;
+ return Find(k, out values) && values != null && !values.IsEmpty;
+ }
+
+ // Determine whether each key in ks is associated with a value
+
+ public override bool ContainsAll<U>(SCG.IEnumerable<U> ks) {
+ foreach (K k in ks)
+ if (!Contains(k))
+ return false;
+ return true;
+ }
+
+ // Get or set the value collection associated with key k
+
+ public override ICollection<V> this[K k] {
+ get {
+ ICollection<V> values;
+ return base.Find(k, out values) && values != null ? values : new HashSet<V>();
+ }
+ set {
+ base[k] = value;
+ }
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/PointLocation.cs b/mcs/class/Mono.C5/UserGuideExamples/PointLocation.cs new file mode 100644 index 00000000000..88f24aa91db --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/PointLocation.cs @@ -0,0 +1,774 @@ +/*
+ 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.
+*/
+
+using System;
+using System.Diagnostics;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace PointLocation
+{
+ //public enum Site { Cell,Edge,Outside}
+ /// <summary>
+ /// A line segment with associated data of type T for the cell
+ /// to its right respectively left.
+ /// </summary>
+ public struct Edge<T>
+ {
+ public double xs, ys, xe, ye;
+
+ public T right, left;
+
+ public Edge(double xs, double ys, double xe, double ye, T right, T left)
+ {
+ this.xs = xs;
+ this.ys = ys;
+ this.xe = xe;
+ this.ye = ye;
+ this.right = right;
+ this.left = left;
+ }
+
+
+ public T Cell(bool upper)
+ {
+ return (DoubleComparer.StaticCompare(xs, xe) < 0) == upper ? left : right;
+ }
+
+
+ public override string ToString()
+ {
+ return String.Format("[({0:G5};{1:G5})->({2:G5};{3:G5})/R:{4} L:{5}]", xs, ys, xe, ye, right, left);
+ }
+ }
+
+
+
+ /// <summary>
+ /// A data structure for point location in a plane divided into
+ /// cells by edges. This is the classical use of persistent trees
+ /// by Sarnak and Tarjan [?]. See de Berg et al for alternatives.
+ ///
+ /// The internal data is an outer sorted dictionary that maps each
+ /// x coordinate of an endpoint of some edge to an inner sorted set
+ /// of the edges crossing or touching the vertical line at that x
+ /// coordinate, the edges being ordered by their y coordinates
+ /// to the immediate right of x. Lookup of a point (x,y) is done by
+ /// finding the predecessor of x cell the outer dictionary and then locating
+ /// the edges above and below (x,y) by searching in the inner sorted set.
+ ///
+ /// The creation of the inner sorted sets is done by maintaining a
+ /// (persistent) tree of edges, inserting and deleting edges according
+ /// to a horzontal sweep of the edges while saving a snapshot of the
+ /// inner tree in the outer dictionary at each new x coordinate.
+ ///
+ /// If there are n edges, there will be 2n updates to the inner tree,
+ /// and in the worst case, the inner tree will have size Omega(n) for
+ /// Omega(n) snapshots. We will use O(n*logn) time and O(n) space for
+ /// sorting the endpoints. If we use a nodecopying persistent inner tree,
+ /// we will use O(n) space and time for building the data structure proper.
+ /// If we use a pathcopy persistent tree, we will use O(n*logn) time and
+ /// space for the data struicture. Finally, if we use a non-persistent
+ /// tree with a full copy for snapshot, we may use up to O(n^2) space and
+ /// time for building the datastructure.
+ ///
+ /// Lookup will take O(logn) time in any case, but taking the memory
+ /// hierarchy into consideration, a low space use is very beneficial
+ /// for large problems.
+ ///
+ /// The code assumes that the given set of edges is correct, in particular
+ /// that they do not touch at interior points (e.g. cross or coincide).
+ /// </summary>
+
+ public class PointLocator<T>
+ {
+ private TreeDictionary<double,ISorted<Edge<T>>> htree;
+
+ private EdgeComparer<T> lc = new EdgeComparer<T>();
+
+ private SCG.IComparer<EndPoint> epc = new EndPoint(0, 0, true, 0);
+
+ private DoubleComparer dc = new DoubleComparer();
+
+ private TreeDictionary<EndPoint,Edge<T>> endpoints;
+
+ private int count;
+
+ private bool built = false;
+
+ public PointLocator()
+ {
+ //htree = new TreeDictionary<double,TreeSet<Edge<T>>>(dc);
+ endpoints = new TreeDictionary<EndPoint,Edge<T>>(epc);
+ }
+
+ public PointLocator(SCG.IEnumerable<Edge<T>> edges)
+ {
+ //htree = new TreeDictionary<double,TreeSet<Edge<T>>>(dc);
+ endpoints = new TreeDictionary<EndPoint,Edge<T>>(epc);
+ foreach (Edge<T> edge in edges)
+ add(edge);
+ }
+
+ private void add(Edge<T> edge)
+ {
+ int c = DoubleComparer.StaticCompare(edge.xs, edge.xe);
+
+ if (c == 0)
+ return;
+
+ endpoints.Add(new EndPoint(edge.xs, edge.ys, c < 0, count), edge);
+ endpoints.Add(new EndPoint(edge.xe, edge.ye, c > 0, count++), edge);
+ }
+
+ public void Add(Edge<T> edge)
+ {
+ if (built)
+ throw new InvalidOperationException("PointLocator static when built");
+ add(edge);
+ }
+
+ public void AddAll(SCG.IEnumerable<Edge<T>> edges)
+ {
+ if (built)
+ throw new InvalidOperationException("PointLocator static when built");
+
+ foreach (Edge<T> edge in edges)
+ add(edge);
+ }
+
+ public void Build()
+ {
+ //htree.Clear();
+ htree = new TreeDictionary<double,ISorted<Edge<T>>>(dc);
+
+ TreeSet<Edge<T>> vtree = new TreeSet<Edge<T>>(lc);
+ double lastx = Double.NegativeInfinity;
+
+ foreach (KeyValuePair<EndPoint,Edge<T>> p in endpoints)
+ {
+ if (dc.Compare(p.Key.x,lastx)>0)
+ {
+ //Put an empty snapshot at -infinity!
+ htree[lastx] = (ISorted<Edge<T>>)(vtree.Snapshot());
+ lc.X = lastx = p.Key.x;
+ lc.compareToRight = false;
+ }
+
+ if (p.Key.start)
+ {
+ if (!lc.compareToRight)
+ lc.compareToRight = true;
+ Debug.Assert(vtree.Check());
+ bool chk = vtree.Add(p.Value);
+ Debug.Assert(vtree.Check());
+
+ Debug.Assert(chk,"edge was not added!",""+p.Value);
+ }
+ else
+ {
+ Debug.Assert(!lc.compareToRight);
+
+ Debug.Assert(vtree.Check("C"));
+
+ bool chk = vtree.Remove(p.Value);
+ Debug.Assert(vtree.Check("D"));
+
+ Debug.Assert(chk,"edge was not removed!",""+p.Value);
+ }
+ }
+ lc.compareToRight = true;
+
+ htree[lastx] = (TreeSet<Edge<T>>)(vtree.Snapshot());
+ built = true;
+ }
+
+
+ /*public void Clear()
+ {
+ endpoints.Clear();
+ htree.Clear();
+ }*/
+ /// <summary>
+ /// Find the cell, if any, containing (x,y).
+ /// </summary>
+ /// <param name="x">x coordinate of point</param>
+ /// <param name="y">y coordinate of point</param>
+ /// <param name="below">Associate data of cell according to edge below</param>
+ /// <param name="above">Associate data of cell according to edge above</param>
+ /// <returns>True if point is inside some cell</returns>
+ public bool Place(double x, double y, out T cell)
+ {
+ if (!built)
+ throw new InvalidOperationException("PointLocator must be built first");
+
+ KeyValuePair<double,ISorted<Edge<T>>> p = htree.WeakPredecessor(x);
+
+ //if (DoubleComparer.StaticCompare(cell.key,x)==0)
+ //Just note it, we have thrown away the vertical edges!
+ Edge<T> low, high;
+ bool lval, hval;
+ PointComparer<T> c = new PointComparer<T>(x, y);
+
+ //Return value true here means we are at an edge.
+ //But note that if x is in htree.Keys, we may be at a
+ //vertical edge even if the return value is false here.
+ //Therefore we do not attempt to sort out completely the case
+ //where (x,y) is on an edge or even on several edges,
+ //and just deliver some cell it is in.
+ p.Value.Cut(c, out low, out lval, out high, out hval);
+ if (!lval || !hval)
+ {
+ cell = default(T);
+ return false;
+ }
+ else
+ {
+ cell = low.Cell(true);//high.Cell(false);
+ return true;
+ }
+ }
+
+ public void Place(double x, double y, out T upper, out bool hval, out T lower, out bool lval)
+ {
+ if (!built)
+ throw new InvalidOperationException("PointLocator must be built first");
+
+ KeyValuePair<double,ISorted<Edge<T>>> p = htree.WeakPredecessor(x);
+
+ //if (DoubleComparer.StaticCompare(cell.key,x)==0)
+ //Just note it, we have thrown away the vertical edges!
+ Edge<T> low, high;
+ PointComparer<T> c = new PointComparer<T>(x, y);
+
+ //Return value true here means we are at an edge.
+ //But note that if x is in htree.Keys, we may be at a
+ //vertical edge even if the return value is false here.
+ //Therefore we do not attempt to sort out completely the case
+ //where (x,y) is on an edge or even on several edges,
+ //and just deliver some cell it is in.
+ p.Value.Cut(c, out low, out lval, out high, out hval);
+ upper = hval ? high.Cell(false) : default(T);
+ lower = lval ? low.Cell(true) : default(T);
+ return;
+ }
+
+ public void Test(double x, double y)
+ {
+ T cell;
+
+ if (Place(x, y, out cell))
+ Console.WriteLine("({0}; {1}): <- {2} ", x, y, cell);
+ else
+ Console.WriteLine("({0}; {1}): -", x, y);
+ }
+
+ /// <summary>
+ /// Endpoint of an edge with ordering/comparison according to x
+ /// coordinates with arbitration by the id field.
+ /// The client is assumed to keep the ids unique.
+ /// </summary>
+ public /*private*/ struct EndPoint: SCG.IComparer<EndPoint>
+ {
+ public double x, y;
+
+ public bool start;
+
+ private int id;
+
+
+ public EndPoint(double x, double y, bool left, int id)
+ {
+ this.x = x;this.y = y;this.start = left;this.id = id;
+ }
+
+
+ public int Compare(EndPoint a, EndPoint b)
+ {
+ int c = DoubleComparer.StaticCompare(a.x, b.x);
+
+ return c != 0 ? c : (a.start && !b.start) ? 1 : (!a.start && b.start) ? -1 : a.id < b.id ? -1 : a.id > b.id ? 1 : 0;
+ }
+ }
+ }
+
+ /// <summary>
+ /// Compare two doubles with tolerance.
+ /// </summary>
+ class DoubleComparer: SCG.IComparer<double>
+ {
+ private const double eps = 1E-10;
+
+ public int Compare(double a, double b)
+ {
+ return a > b + eps ? 1 : a < b - eps ? -1 : 0;
+ }
+
+ public static int StaticCompare(double a, double b)
+ {
+ return a > b + eps ? 1 : a < b - eps ? -1 : 0;
+ }
+ }
+
+ /// <summary>
+ /// Compare a given point (x,y) to edges: is the point above, at or below
+ /// the edge. Assumes edges not vertical.
+ /// </summary>
+ class PointComparer<T>: IComparable<Edge<T>>
+ {
+ private double x, y;
+
+ public PointComparer(double x, double y)
+ {
+ this.x = x; this.y = y;
+ }
+
+ public int CompareTo(Edge<T> a)
+ {
+ double ya = (a.ye - a.ys) / (a.xe - a.xs) * (x - a.xs) + a.ys;
+
+ return DoubleComparer.StaticCompare(y, ya);
+ }
+
+ public bool Equals(Edge<T> a) { return CompareTo(a) == 0; }
+ }
+
+ /// <summary>
+ /// Compare two edges at a given x coordinate:
+ /// Compares the y-coordinate to the immediate right of x of the two edges.
+ /// Assumes edges to be compared are not vertical.
+ /// </summary>
+ class EdgeComparer<T>: SCG.IComparer<Edge<T>>
+ {
+ private double x;
+
+ public bool compareToRight = true;
+
+ public double X { get { return x; } set { x = value; } }
+
+ public int Compare(Edge<T> line1, Edge<T> line2)
+ {
+ double a1 = (line1.ye - line1.ys) / (line1.xe - line1.xs);
+ double a2 = (line2.ye - line2.ys) / (line2.xe - line2.xs);
+ double ya = a1 * (x - line1.xs) + line1.ys;
+ double yb = a2 * (x - line2.xs) + line2.ys;
+ int c = DoubleComparer.StaticCompare(ya, yb);
+
+ return c != 0 ? c : (compareToRight ? 1 : -1) * DoubleComparer.StaticCompare(a1, a2);
+ }
+ }
+
+ namespace Test
+ {
+ public class Ugly : EnumerableBase<Edge<int>>, SCG.IEnumerable<Edge<int>>, SCG.IEnumerator<Edge<int>>
+ {
+ private int level = -1, maxlevel;
+
+ private bool leftend = false;
+
+ public Ugly(int maxlevel)
+ {
+ this.maxlevel = maxlevel;
+ }
+
+ public override SCG.IEnumerator<Edge<int>> GetEnumerator()
+ {
+ return (SCG.IEnumerator<Edge<int>>)MemberwiseClone();
+ }
+
+ public void Reset()
+ {
+ level = -1;
+ leftend = false;
+ }
+
+ public bool MoveNext()
+ {
+ if (level > maxlevel)
+ throw new InvalidOperationException();
+
+ if (leftend)
+ {
+ leftend = false;
+ return true;
+ }
+ else
+ {
+ leftend = true;
+ return ++level <= maxlevel;
+ }
+ }
+
+ public Edge<int> Current
+ {
+ get
+ {
+ if (level < 0 || level > maxlevel)
+ throw new InvalidOperationException();
+
+ double y = (level * 37) % maxlevel;
+ double deltax = leftend ? 1 : maxlevel;
+
+ if (leftend)
+ return new Edge<int>(0, y, level, y - 0.5, 0, 0);
+ else
+ return new Edge<int>(level, y - 0.5, level, y, 0, 0);
+ }
+ }
+
+
+ public void Dispose() { }
+
+#region IEnumerable Members
+
+ System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
+ {
+ throw new Exception("The method or operation is not implemented.");
+ }
+
+#endregion
+
+#region IEnumerator Members
+
+ object System.Collections.IEnumerator.Current
+ {
+ get { throw new Exception("The method or operation is not implemented."); }
+ }
+
+ void System.Collections.IEnumerator.Reset()
+ {
+ throw new Exception("The method or operation is not implemented.");
+ }
+
+#endregion
+ }
+
+ public class TestUgly
+ {
+ private Ugly ugly;
+
+ private int d;
+
+ private PointLocator<int> pointlocator;
+
+
+ public TestUgly(int d)
+ {
+ this.d = d;
+ ugly = new Ugly(d);
+ }
+
+
+ public double Traverse()
+ {
+ double xsum = 0;
+
+ foreach (Edge<int> e in ugly) xsum += e.xe;
+
+ return xsum;
+ }
+
+ public bool LookUp(int count, int seed)
+ {
+ Random random = new Random(seed);
+ bool res = false;
+
+ for (int i = 0; i < count; i++)
+ {
+ int cell;
+
+ res ^= pointlocator.Place(random.NextDouble() * d, random.NextDouble() * d, out cell);
+ }
+
+ return res;
+ }
+
+ public static void Run(string[] args)
+ {
+ int d = args.Length >= 2 ? int.Parse(args[1]) : 400;//00;
+ int repeats = args.Length >= 3 ? int.Parse(args[2]) : 10;
+ int lookups = args.Length >= 4 ? int.Parse(args[3]) : 500;//00;
+
+ new TestUgly(d).run(lookups);
+ }
+
+
+ public void run(int lookups)
+ {
+ double s = 0;
+
+ s += Traverse();
+
+ pointlocator = new PointLocator<int>(ugly);
+ pointlocator.Build();
+
+ LookUp(lookups, 567);
+ }
+ }
+
+ public class Lattice : EnumerableBase<Edge<string>>, SCG.IEnumerable<Edge<string>>, SCG.IEnumerator<Edge<string>>, System.Collections.IEnumerator
+ {
+ private int currenti = -1, currentj = 0, currentid = 0;
+
+ private bool currenthoriz = true;
+
+ private int maxi, maxj;
+
+ private double a11 = 1, a21 = -1, a12 = 1, a22 = 1;
+
+ public Lattice(int maxi, int maxj, double a11, double a21, double a12, double a22)
+ {
+ this.maxi = maxi;
+ this.maxj = maxj;
+ this.a11 = a11;
+ this.a12 = a12;
+ this.a21 = a21;
+ this.a22 = a22;
+ }
+
+ public Lattice(int maxi, int maxj)
+ {
+ this.maxi = maxi;
+ this.maxj = maxj;
+ }
+
+ public override SCG.IEnumerator<Edge<string>> GetEnumerator()
+ {
+ return (SCG.IEnumerator<Edge<string>>)MemberwiseClone();
+ }
+
+ public void Reset()
+ {
+ currenti = -1;
+ currentj = 0;
+ currentid = -1;
+ currenthoriz = true;
+ }
+
+ public bool MoveNext()
+ {
+ currentid++;
+ if (currenthoriz)
+ {
+ if (++currenti >= maxi)
+ {
+ if (currentj >= maxj)
+ return false;
+
+ currenti = 0;
+ currenthoriz = false;
+ }
+
+ return true;
+ }
+ else
+ {
+ if (++currenti > maxi)
+ {
+ currenti = 0;
+ currenthoriz = true;
+ if (++currentj > maxj)
+ return false;
+ }
+
+ return true;
+ }
+ }
+
+
+ private string i2l(int i)
+ {
+ int ls = 0, j = i;
+
+ do { ls++; j = j / 26 - 1; } while (j >= 0);
+
+ char[] res = new char[ls];
+
+ while (ls > 0) { res[--ls] = (char)(65 + i % 26); i = i / 26 - 1; }
+
+ //res[0]--;
+ return new String(res);
+ }
+
+
+ private string fmtid(int i, int j)
+ {
+ return "";//cell + ";" + cell;
+ /*if (cell < 0 || cell < 0 || cell >= maxi || cell >= maxj)
+ return "Outside";
+
+ return String.Format("{0}{1}", i2l(cell), cell);*/
+ }
+
+
+ public Edge<string> Current
+ {
+ get
+ {
+ if (currenti >= maxi && currentj >= maxj)
+ throw new InvalidOperationException();
+
+ double xs = currenti * a11 + currentj * a12;
+ double ys = currenti * a21 + currentj * a22;
+ double deltax = currenthoriz ? a11 : a12;
+ double deltay = currenthoriz ? a21 : a22;
+ string r = fmtid(currenti, currenthoriz ? currentj - 1 : currentj);
+ string l = fmtid(currenthoriz ? currenti : currenti - 1, currentj);
+
+ return new Edge<string>(xs, ys, xs + deltax, ys + deltay, r, l);
+ }
+ }
+
+
+ public void Dispose() { }
+
+#region IEnumerable Members
+
+ System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
+ {
+ throw new Exception("The method or operation is not implemented.");
+ }
+
+#endregion
+
+#region IEnumerator Members
+
+ object System.Collections.IEnumerator.Current
+ {
+ get { throw new Exception("The method or operation is not implemented."); }
+ }
+
+ bool System.Collections.IEnumerator.MoveNext()
+ {
+ throw new Exception("The method or operation is not implemented.");
+ }
+
+ void System.Collections.IEnumerator.Reset()
+ {
+ throw new Exception("The method or operation is not implemented.");
+ }
+
+#endregion
+ }
+
+ public class TestLattice
+ {
+ private Lattice lattice;
+
+ private int d;
+
+ private PointLocator<string> pointlocator;
+
+
+ public TestLattice(int d)
+ {
+ this.d = d;
+ lattice = new Lattice(d, d, 1, 0, 0, 1);
+ }
+
+ public TestLattice(int d, double shear)
+ {
+ this.d = d;
+ lattice = new Lattice(d, d, 1, 0, shear, 1);
+ }
+
+ public double Traverse()
+ {
+ double xsum = 0;
+
+ foreach (Edge<string> e in lattice) xsum += e.xe;
+
+ return xsum;
+ }
+
+
+ public bool LookUp(int count, int seed)
+ {
+ Random random = new Random(seed);
+ bool res = false;
+
+ for (int i = 0; i < count; i++)
+ {
+ string cell;
+
+ res ^= pointlocator.Place(random.NextDouble() * d, random.NextDouble() * d, out cell);
+ }
+
+ return res;
+ }
+
+
+ public static void Run()
+ {
+ int d = 200;
+ int repeats = 2;
+ int lookups = 50000;
+ TestLattice tl = null;
+
+ Console.WriteLine("TestLattice Run({0}), means over {1} repeats:", d, repeats);
+ tl = new TestLattice(d, 0.000001);
+
+ tl.Traverse();
+
+ tl.pointlocator = new PointLocator<string>();
+
+ tl.pointlocator.AddAll(tl.lattice);
+
+ tl.pointlocator.Build();
+
+ tl.LookUp(lookups, 567);
+ }
+
+
+ public void BasicRun()
+ {
+ pointlocator.Test(-0.5, -0.5);
+ pointlocator.Test(-0.5, 0.5);
+ pointlocator.Test(-0.5, 1.5);
+ pointlocator.Test(0.5, -0.5);
+ pointlocator.Test(0.5, 0.5);
+ pointlocator.Test(0.5, 1.5);
+ pointlocator.Test(1.5, -0.5);
+ pointlocator.Test(1.5, 0.5);
+ pointlocator.Test(1.5, 1.5);
+ pointlocator.Test(1.5, 4.99);
+ pointlocator.Test(1.5, 5);
+ pointlocator.Test(1.5, 5.01);
+ pointlocator.Test(1.99, 4.99);
+ pointlocator.Test(1.99, 5);
+ pointlocator.Test(1.99, 5.01);
+ pointlocator.Test(2, 4.99);
+ pointlocator.Test(2, 5);
+ pointlocator.Test(2, 5.01);
+ pointlocator.Test(2.01, 4.99);
+ pointlocator.Test(2.01, 5);
+ pointlocator.Test(2.01, 5.01);
+ }
+ }
+ }
+
+ public class TestPointLocation {
+ public static void Main(String[] args) {
+ Test.TestUgly.Run(new String[0]);
+ }
+ }
+}
+
diff --git a/mcs/class/Mono.C5/UserGuideExamples/RandomSelection.cs b/mcs/class/Mono.C5/UserGuideExamples/RandomSelection.cs new file mode 100644 index 00000000000..8049758ad67 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/RandomSelection.cs @@ -0,0 +1,86 @@ +/*
+ 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: RandomSelection.cs for pattern chapter
+
+// Compile with
+// csc /r:C5.dll RandomSelection.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace RandomSelection {
+ class RandomSelection {
+ public static void Main(String[] args) {
+ ArrayList<int> list = new ArrayList<int>(), copy1, copy2;
+ list.AddAll(new int[] { 2, 3, 5, 7, 11, 13, 17, 19 });
+ copy1 = (ArrayList<int>)list.Clone();
+ copy2 = (ArrayList<int>)list.Clone();
+ const int N = 7;
+ Console.WriteLine("-- With replacement:");
+ foreach (int x in RandomWith(list, N))
+ Console.Write("{0} ", x);
+ Console.WriteLine("\n-- Without replacement:");
+ foreach (int x in RandomWithout1(copy1, N))
+ Console.Write("{0} ", x);
+ Console.WriteLine("\n-- Without replacement:");
+ foreach (int x in RandomWithout2(copy2, N))
+ Console.Write("{0} ", x);
+ Console.WriteLine();
+ }
+
+ private static readonly C5Random rnd = new C5Random();
+
+ // Select N random items from coll, with replacement.
+ // Does not modify the given list.
+
+ public static SCG.IEnumerable<T> RandomWith<T>(IIndexed<T> coll, int N) {
+ for (int i=N; i>0; i--) {
+ T x = coll[rnd.Next(coll.Count)];
+ yield return x;
+ }
+ }
+
+ // Select N random items from list, without replacement.
+ // Modifies the given list.
+
+ public static SCG.IEnumerable<T> RandomWithout1<T>(IList<T> list, int N) {
+ list.Shuffle(rnd);
+ foreach (T x in list.View(0, N))
+ yield return x;
+ }
+
+ // Select N random items from list, without replacement.
+ // Faster when list is efficiently indexable and modifiable.
+ // Modifies the given list.
+
+ public static SCG.IEnumerable<T> RandomWithout2<T>(ArrayList<T> list, int N) {
+ for (int i=N; i>0; i--) {
+ int j = rnd.Next(list.Count);
+ T x = list[j], replacement = list.RemoveLast();
+ if (j < list.Count)
+ list[j] = replacement;
+ yield return x;
+ }
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/ReadOnlyPatterns.cs b/mcs/class/Mono.C5/UserGuideExamples/ReadOnlyPatterns.cs new file mode 100644 index 00000000000..feb3cf12ec8 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/ReadOnlyPatterns.cs @@ -0,0 +1,96 @@ +/*
+ 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: ReadOnlyPatterns.cs for pattern chapter
+
+// Compile with
+// csc /r:C5.dll ReadOnlyPatterns.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace ReadOnlyPatterns {
+ class ReadOnlyPatterns {
+ public static void Main(String[] args) {
+ GuardHashSet<int>();
+ GuardTreeSet<int>();
+ GuardList<int>();
+ GuardHashDictionary<int,int>();
+ GuardSortedDictionary<int,int>();
+ }
+
+ // Read-only access to a hash-based collection
+
+ static void GuardHashSet<T>() {
+ ICollection<T> coll = new HashSet<T>();
+ DoWork(new GuardedCollection<T>(coll));
+ }
+
+ static void DoWork<T>(ICollection<T> gcoll) {
+ // Use gcoll ...
+ }
+
+ // Read-only access to an indexed sorted collection
+
+ static void GuardTreeSet<T>() {
+ IIndexedSorted<T> coll = new TreeSet<T>();
+ DoWork(new GuardedIndexedSorted<T>(coll));
+ }
+
+ static void DoWork<T>(IIndexedSorted<T> gcoll) {
+ // Use gcoll ...
+ }
+
+ // Read-only access to a list
+
+ static void GuardList<T>() {
+ IList<T> coll = new ArrayList<T>();
+ DoWork(new GuardedList<T>(coll));
+ }
+
+ static void DoWork<T>(IList<T> gcoll) {
+ // Use gcoll ...
+ }
+
+ // Read-only access to a dictionary
+
+ static void GuardHashDictionary<K,V>() {
+ IDictionary<K,V> dict = new HashDictionary<K,V>();
+ DoWork(new GuardedDictionary<K,V>(dict));
+ }
+
+ static void DoWork<K,V>(IDictionary<K,V> gdict) {
+ // Use gdict ...
+ }
+
+ // Read-only access to a sorted dictionary
+
+ static void GuardSortedDictionary<K,V>() {
+ ISortedDictionary<K,V> dict = new TreeDictionary<K,V>();
+ DoWork(new GuardedSortedDictionary<K,V>(dict));
+ }
+
+ static void DoWork<K,V>(ISortedDictionary<K,V> gdict) {
+ // Use gdict ...
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Sets.cs b/mcs/class/Mono.C5/UserGuideExamples/Sets.cs new file mode 100644 index 00000000000..0ddbeef7a06 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Sets.cs @@ -0,0 +1,175 @@ +/*
+ 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: functional sets 2004-12-21
+
+// Compile with
+// csc /r:C5.dll Sets.cs
+
+using System;
+using System.Text;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace Sets {
+ // The class of sets with item type T, implemented as a subclass of
+ // HashSet<T> but with functional infix operators * + - that compute
+ // intersection, union and difference functionally. That is, they
+ // create a new set object instead of modifying an existing one.
+ // The hasher is automatically created so that it is appropriate for
+ // T. In particular, this is true when T has the form Set<W> for
+ // some W, since Set<W> implements ICollectionValue<W>.
+
+ public class Set<T> : HashSet<T> {
+ public Set(SCG.IEnumerable<T> enm) : base() {
+ AddAll(enm);
+ }
+
+ public Set(params T[] elems) : this((SCG.IEnumerable<T>)elems) { }
+
+ // Set union (+), difference (-), and intersection (*):
+
+ public static Set<T> operator +(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set+Set");
+ else {
+ Set<T> res = new Set<T>(s1);
+ res.AddAll(s2);
+ return res;
+ }
+ }
+
+ public static Set<T> operator -(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set-Set");
+ else {
+ Set<T> res = new Set<T>(s1);
+ res.RemoveAll(s2);
+ return res;
+ }
+ }
+
+ public static Set<T> operator *(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set*Set");
+ else {
+ Set<T> res = new Set<T>(s1);
+ res.RetainAll(s2);
+ return res;
+ }
+ }
+
+ // Equality of sets; take care to avoid infinite loops
+
+ public static bool operator ==(Set<T> s1, Set<T> s2) {
+ return EqualityComparer<Set<T>>.Default.Equals(s1, s2);
+ }
+
+ public static bool operator !=(Set<T> s1, Set<T> s2) {
+ return !(s1 == s2);
+ }
+
+ public override bool Equals(Object that) {
+ return this == (that as Set<T>);
+ }
+
+ public override int GetHashCode() {
+ return EqualityComparer<Set<T>>.Default.GetHashCode(this);
+ }
+
+ // Subset (<=) and superset (>=) relation:
+
+ public static bool operator <=(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set<=Set");
+ else
+ return s1.ContainsAll(s2);
+ }
+
+ public static bool operator >=(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set>=Set");
+ else
+ return s2.ContainsAll(s1);
+ }
+
+ public override String ToString() {
+ StringBuilder sb = new StringBuilder();
+ sb.Append("{");
+ bool first = true;
+ foreach (T x in this) {
+ if (!first)
+ sb.Append(",");
+ sb.Append(x);
+ first = false;
+ }
+ sb.Append("}");
+ return sb.ToString();
+ }
+ }
+
+ class MyTest {
+ public static void Main(String[] args) {
+ Set<int> s1 = new Set<int>(2, 3, 5, 7, 11);
+ Set<int> s2 = new Set<int>(2, 4, 6, 8, 10);
+ Console.WriteLine("s1 + s2 = {0}", s1 + s2);
+ Console.WriteLine("s1 * s2 = {0}", s1 * s2);
+ Console.WriteLine("s1 - s2 = {0}", s1 - s2);
+ Console.WriteLine("s1 - s1 = {0}", s1 - s1);
+ Console.WriteLine("s1 + s1 == s1 is {0}", s1 + s1 == s1);
+ Console.WriteLine("s1 * s1 == s1 is {0}", s1 * s1 == s1);
+ Set<Set<int>> ss1 = new Set<Set<int>>(s1, s2, s1 + s2);
+ Console.WriteLine("ss1 = {0}", ss1);
+ Console.WriteLine("IntersectionClose(ss1) = {0}", IntersectionClose(ss1));
+ Set<Set<int>> ss2 =
+ new Set<Set<int>>(new Set<int>(2, 3), new Set<int>(1, 3), new Set<int>(1, 2));
+ Console.WriteLine("ss2 = {0}", ss2);
+ Console.WriteLine("IntersectionClose(ss2) = {0}", IntersectionClose(ss2));
+ }
+
+ // Given a set SS of sets of Integers, compute its intersection
+ // closure, that is, the least set TT such that SS is a subset of TT
+ // and such that for any two sets t1 and t2 in TT, their
+ // intersection is also in TT.
+
+ // For instance, if SS is {{2,3}, {1,3}, {1,2}},
+ // then TT is {{2,3}, {1,3}, {1,2}, {3}, {2}, {1}, {}}.
+
+ // Both the argument and the result is a Set<Set<int>>
+
+ static Set<Set<T>> IntersectionClose<T>(Set<Set<T>> ss) {
+ IQueue<Set<T>> worklist = new CircularQueue<Set<T>>();
+ foreach (Set<T> s in ss)
+ worklist.Enqueue(s);
+ HashSet<Set<T>> tt = new HashSet<Set<T>>();
+ while (worklist.Count != 0) {
+ Set<T> s = worklist.Dequeue();
+ foreach (Set<T> t in tt) {
+ Set<T> ts = t * s;
+ if (!tt.Contains(ts))
+ worklist.Enqueue(ts);
+ }
+ tt.Add(s);
+ }
+ return new Set<Set<T>>((SCG.IEnumerable<Set<T>>)tt);
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/SortedIterationPatterns.cs b/mcs/class/Mono.C5/UserGuideExamples/SortedIterationPatterns.cs new file mode 100644 index 00000000000..5bfe072e3a5 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/SortedIterationPatterns.cs @@ -0,0 +1,247 @@ +/*
+ 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: SortedIterationPatterns.cs for pattern chapter
+
+// Compile with
+// csc /r:C5.dll SortedIterationPatterns.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace SortedIterationPatterns {
+ class SortedIterationPatterns {
+ public static void Main(String[] args) {
+ ISorted<int> sorted = new TreeSet<int>();
+ sorted.AddAll(new int[] { 23, 29, 31, 37, 41, 43, 47, 53 });
+ Console.WriteLine(sorted);
+ if (args.Length == 1) {
+ int n = int.Parse(args[0]);
+ int res;
+ if (Predecessor(sorted, n, out res))
+ Console.WriteLine("{0} has predecessor {1}", n, res);
+ if (WeakPredecessor(sorted, n, out res))
+ Console.WriteLine("{0} has weak predecessor {1}", n, res);
+ if (Successor(sorted, n, out res))
+ Console.WriteLine("{0} has successor {1}", n, res);
+ if (WeakSuccessor(sorted, n, out res))
+ Console.WriteLine("{0} has weak successor {1}", n, res);
+ }
+ IterBeginEnd(sorted);
+ IterBeginEndBackwards(sorted);
+ IterIncExc(sorted, 29, 47);
+ IterIncExcBackwards(sorted, 29, 47);
+ IterIncEnd(sorted, 29);
+ IterBeginExc(sorted, 47);
+ IterIncInc(sorted, 29, 47);
+ IterBeginInc(sorted, 47);
+ IterExcExc(sorted, 29, 47);
+ IterExcEnd(sorted, 29);
+ IterExcInc(sorted, 29, 47);
+ }
+
+ // --- Predecessor and successor patterns --------------------
+
+ // Find weak successor of y in coll, or return false
+
+ public static bool WeakSuccessor<T>(ISorted<T> coll, T y, out T ySucc)
+ where T : IComparable<T>
+ {
+ T yPred;
+ bool hasPred, hasSucc,
+ hasY = coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);
+ if (hasY)
+ ySucc = y;
+ return hasY || hasSucc;
+ }
+
+ // Find weak predecessor of y in coll, or return false
+
+ public static bool WeakPredecessor<T>(ISorted<T> coll, T y, out T yPred)
+ where T : IComparable<T>
+ {
+ T ySucc;
+ bool hasPred, hasSucc,
+ hasY = coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);
+ if (hasY)
+ yPred = y;
+ return hasY || hasPred;
+ }
+
+ // Find (strict) successor of y in coll, or return false
+
+ public static bool Successor<T>(ISorted<T> coll, T y, out T ySucc)
+ where T : IComparable<T>
+ {
+ bool hasPred, hasSucc;
+ T yPred;
+ coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);
+ return hasSucc;
+ }
+
+ // Find (strict) predecessor of y in coll, or return false
+
+ public static bool Predecessor<T>(ISorted<T> coll, T y, out T yPred)
+ where T : IComparable<T>
+ {
+ bool hasPred, hasSucc;
+ T ySucc;
+ coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);
+ return hasPred;
+ }
+
+ // --- Sorted iteration patterns -----------------------------
+
+ // Iterate over all items
+
+ public static void IterBeginEnd<T>(ISorted<T> coll) {
+ foreach (T x in coll) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over all items, backwards
+
+ public static void IterBeginEndBackwards<T>(ISorted<T> coll) {
+ foreach (T x in coll.Backwards()) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over [x1,x2[
+
+ public static void IterIncExc<T>(ISorted<T> coll, T x1, T x2) {
+ foreach (T x in coll.RangeFromTo(x1, x2)) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over [x1,x2[, backwards
+
+ public static void IterIncExcBackwards<T>(ISorted<T> coll, T x1, T x2) {
+ foreach (T x in coll.RangeFromTo(x1, x2).Backwards()) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over [x1...]
+
+ public static void IterIncEnd<T>(ISorted<T> coll, T x1) {
+ foreach (T x in coll.RangeFrom(x1)) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over [...x2[
+
+ public static void IterBeginExc<T>(ISorted<T> coll, T x2) {
+ foreach (T x in coll.RangeTo(x2)) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over [x1...x2]
+
+ public static void IterIncInc<T>(ISorted<T> coll, T x1, T x2)
+ where T : IComparable<T>
+ {
+ T x2Succ;
+ bool x2HasSucc = Successor(coll, x2, out x2Succ);
+ IDirectedEnumerable<T> range =
+ x2HasSucc ? coll.RangeFromTo(x1, x2Succ) : coll.RangeFrom(x1);
+ foreach (T x in range) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over [...x2]
+
+ public static void IterBeginInc<T>(ISorted<T> coll, T x2)
+ where T : IComparable<T>
+ {
+ T x2Succ;
+ bool x2HasSucc = Successor(coll, x2, out x2Succ);
+ IDirectedEnumerable<T> range =
+ x2HasSucc ? coll.RangeTo(x2Succ) : coll.RangeAll();
+ foreach (T x in range) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over ]x1...x2[
+
+ public static void IterExcExc<T>(ISorted<T> coll, T x1, T x2)
+ where T : IComparable<T>
+ {
+ T x1Succ;
+ bool x1HasSucc = Successor(coll, x1, out x1Succ);
+ IDirectedEnumerable<T> range =
+ x1HasSucc ? coll.RangeFromTo(x1Succ, x2) : new ArrayList<T>();
+ foreach (T x in range) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over ]x1...]
+
+ public static void IterExcEnd<T>(ISorted<T> coll, T x1)
+ where T : IComparable<T>
+ {
+ T x1Succ;
+ bool x1HasSucc = Successor(coll, x1, out x1Succ);
+ IDirectedEnumerable<T> range =
+ x1HasSucc ? coll.RangeFrom(x1Succ) : new ArrayList<T>();
+ foreach (T x in range) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ // Iterate over ]x1...x2]
+
+ public static void IterExcInc<T>(ISorted<T> coll, T x1, T x2)
+ where T : IComparable<T>
+ {
+ T x1Succ, x2Succ;
+ bool x1HasSucc = Successor(coll, x1, out x1Succ),
+ x2HasSucc = Successor(coll, x2, out x2Succ);
+ IDirectedEnumerable<T> range =
+ x1HasSucc ? (x2HasSucc ? coll.RangeFromTo(x1Succ, x2Succ)
+ : coll.RangeFrom(x1Succ))
+ : new ArrayList<T>();
+ foreach (T x in range) {
+ Console.Write("{0} ", x);
+ }
+ Console.WriteLine();
+ }
+
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/SortingPermutation.cs b/mcs/class/Mono.C5/UserGuideExamples/SortingPermutation.cs new file mode 100644 index 00000000000..83c135012b7 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/SortingPermutation.cs @@ -0,0 +1,80 @@ +// C5 example
+// 2004-11
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace SortingPermutation
+{
+ class MyTest
+ {
+ public static void Main(String[] args)
+ {
+ String[] cities =
+ { "Tokyo", "Beijing", "Hangzhou", "Kyoto", "Beijing", "Copenhagen", "Seattle" };
+ IList<String> alst = new ArrayList<String>();
+ alst.AddAll<String>(cities);
+ foreach (int i in MySort.GetPermutation1(alst))
+ Console.Write("{0} ", i);
+ Console.WriteLine();
+ IList<String> llst = new LinkedList<String>();
+ llst.AddAll<String>(cities);
+ foreach (int i in MySort.GetPermutation2(llst))
+ Console.Write("{0} ", i);
+ Console.WriteLine();
+ Console.WriteLine("The rank of the cities:");
+ ArrayList<int> res = MySort.GetPermutation1(MySort.GetPermutation2(llst));
+ foreach (int i in res)
+ Console.Write("{0} ", i);
+ Console.WriteLine();
+ }
+ }
+
+ class MySort
+ {
+ // Fast for array lists and similar, but not stable; slow for linked lists
+
+ public static ArrayList<int> GetPermutation1<T>(IList<T> lst)
+ where T : IComparable<T>
+ {
+ ArrayList<int> res = new ArrayList<int>(lst.Count);
+ for (int i = 0; i < lst.Count; i++)
+ res.Add(i);
+ res.Sort(new DelegateComparer<int>
+ (delegate(int i, int j) { return lst[i].CompareTo(lst[j]); }));
+ return res;
+ }
+
+ // Stable and fairly fast both for array lists and linked lists,
+ // but does copy the collection's items.
+
+ public static ArrayList<int> GetPermutation2<T>(IList<T> lst)
+ where T : IComparable<T>
+ {
+ int i = 0;
+ IList<KeyValuePair<T, int>> zipList =
+ lst.Map<KeyValuePair<T, int>>
+ (delegate(T x) { return new KeyValuePair<T, int>(x, i++); });
+ zipList.Sort(new KeyValueComparer<T>(lst));
+ ArrayList<int> res = new ArrayList<int>(lst.Count);
+ foreach (KeyValuePair<T, int> p in zipList)
+ res.Add(p.Value);
+ return res;
+ }
+
+ private class KeyValueComparer<T> : SCG.IComparer<KeyValuePair<T, int>>
+ where T : IComparable<T>
+ {
+ private readonly IList<T> lst;
+ public KeyValueComparer(IList<T> lst)
+ {
+ this.lst = lst;
+ }
+ public int Compare(KeyValuePair<T, int> p1, KeyValuePair<T, int> p2)
+ {
+ return p1.Key.CompareTo(p2.Key);
+ }
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/TestSortedArray.cs b/mcs/class/Mono.C5/UserGuideExamples/TestSortedArray.cs new file mode 100644 index 00000000000..15a814b4bc0 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/TestSortedArray.cs @@ -0,0 +1,37 @@ +/*
+ 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: anagrams 2004-12-08
+
+// Compile with
+// csc /r:C5.dll TestSortedArray.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace TestSortedArray {
+ class TestSortedArray {
+ public static void Main(String[] args) {
+ SortedArray<Object> sarr = new SortedArray<Object>();
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/ThisFun.cs b/mcs/class/Mono.C5/UserGuideExamples/ThisFun.cs new file mode 100644 index 00000000000..1fd29f1c122 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/ThisFun.cs @@ -0,0 +1,46 @@ +// Experiment: implicit conversion of indexer to function
+// sestoft@dina.kvl.dk * 2005-11-08
+
+using System;
+using C5;
+
+class MyFunTest {
+ public static void Main(String[] args) {
+ FooBar fb = new FooBar();
+ IList<int> list = new LinkedList<int>();
+ list.AddAll(new int[] { 2, 3, 5, 7, 11 });
+ list.Map<double>(fb).Apply(Console.WriteLine);
+ list.Apply(fb);
+ }
+}
+
+class FooBar {
+ public double this[int x] {
+ get {
+ Console.WriteLine(x);
+ return x + 1.5;
+ }
+ }
+
+ public Fun<int,double> Fun {
+ get {
+ return delegate(int x) { return this[x]; };
+ }
+ }
+
+ public Act<int> Act {
+ get {
+ return delegate(int x) { double junk = this[x]; };
+ }
+ }
+
+ public static implicit operator Fun<int,double>(FooBar fb) {
+ return delegate(int x) { return fb[x]; };
+ }
+
+ public static implicit operator Act<int>(FooBar fb) {
+ return delegate(int x) { double junk = fb[x]; };
+ }
+}
+
+
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Toposort.cs b/mcs/class/Mono.C5/UserGuideExamples/Toposort.cs new file mode 100644 index 00000000000..e078f6a5bee --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Toposort.cs @@ -0,0 +1,139 @@ +/*
+ 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]; }
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/TreeTraversal.cs b/mcs/class/Mono.C5/UserGuideExamples/TreeTraversal.cs new file mode 100644 index 00000000000..0fbc2478aec --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/TreeTraversal.cs @@ -0,0 +1,107 @@ +// C5 example
+// 2004-11-09
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace TreeTraversal
+{
+ class MyTest
+ {
+ public static void Main(String[] args)
+ {
+ Tree<int> t = MakeTree(1, 15);
+ Act<int> act = delegate(int val) { Console.Write("{0} ", val); };
+ Console.WriteLine("Depth-first:");
+ Tree<int>.DepthFirst(t, act);
+ Console.WriteLine("\nBreadth-first:");
+ Tree<int>.BreadthFirst(t, act);
+ Console.WriteLine("\nDepth-first:");
+ Tree<int>.Traverse(t, act, new ArrayList<Tree<int>>());
+ Console.WriteLine("\nBreadth-first:");
+ Tree<int>.Traverse(t, act, new LinkedList<Tree<int>>());
+ Console.WriteLine();
+ }
+
+ // Build n-node tree with root numbered b and other nodes numbered b+1..b+n
+ public static Tree<int> MakeTree(int b, int n)
+ {
+ if (n == 0)
+ return null;
+ else
+ {
+ int k = n / 2;
+ Tree<int> t1 = MakeTree(b + 1, k), t2 = MakeTree(b + k + 1, n - 1 - k);
+ return new Tree<int>(b, t1, t2);
+ }
+ }
+ }
+
+ class Tree<T>
+ {
+ private T val;
+ private Tree<T> t1, t2;
+ public Tree(T val) : this(val, null, null) { }
+ public Tree(T val, Tree<T> t1, Tree<T> t2)
+ {
+ this.val = val; this.t1 = t1; this.t2 = t2;
+ }
+
+ public static void DepthFirst(Tree<T> t, Act<T> act)
+ {
+ IStack<Tree<T>> work = new ArrayList<Tree<T>>();
+ work.Push(t);
+ while (!work.IsEmpty)
+ {
+ Tree<T> cur = work.Pop();
+ if (cur != null)
+ {
+ work.Push(cur.t2);
+ work.Push(cur.t1);
+ act(cur.val);
+ }
+ }
+ }
+
+ public static void BreadthFirst(Tree<T> t, Act<T> act)
+ {
+ IQueue<Tree<T>> work = new CircularQueue<Tree<T>>();
+ work.Enqueue(t);
+ while (!work.IsEmpty)
+ {
+ Tree<T> cur = work.Dequeue();
+ if (cur != null)
+ {
+ work.Enqueue(cur.t1);
+ work.Enqueue(cur.t2);
+ act(cur.val);
+ }
+ }
+ }
+
+ public static void Traverse(Tree<T> t, Act<T> act, IList<Tree<T>> work)
+ {
+ work.Clear();
+ work.Add(t);
+ while (!work.IsEmpty)
+ {
+ Tree<T> cur = work.Remove();
+ if (cur != null)
+ {
+ if (work.FIFO)
+ {
+ work.Add(cur.t1);
+ work.Add(cur.t2);
+ }
+ else
+ {
+ work.Add(cur.t2);
+ work.Add(cur.t1);
+ }
+ act(cur.val);
+ }
+ }
+ }
+ }
+}
\ No newline at end of file diff --git a/mcs/class/Mono.C5/UserGuideExamples/Try.cs b/mcs/class/Mono.C5/UserGuideExamples/Try.cs new file mode 100644 index 00000000000..6617ffad48d --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Try.cs @@ -0,0 +1,64 @@ +/*
+ 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: various tests 2005-01-01
+
+// Compile with
+// csc /r:C5.dll Try.cs
+
+using System;
+using System.Text;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace Try
+{
+ class MyTest
+ {
+ public static void Main()
+ {
+ IList<bool> list = new ArrayList<bool>();
+ list.AddAll(new bool[] { false, false, true, true, false });
+ list.CollectionCleared
+ += delegate(Object coll, ClearedEventArgs args) {
+ ClearedRangeEventArgs crargs = args as ClearedRangeEventArgs;
+ if (crargs != null) {
+ Console.WriteLine("Cleared {0} to {1}",
+ crargs.Start, crargs.Start+crargs.Count-1);
+ } else {
+ Console.WriteLine("Cleared {0} items", args.Count);
+ }
+ };
+ list.RemoveInterval(2, 2);
+ HashSet<int> hash = new HashSet<int>();
+ hash.ItemsRemoved
+ += delegate {
+ Console.WriteLine("Item was removed");
+ };
+ hash.ItemsAdded
+ += delegate {
+ Console.WriteLine("Item was added");
+ };
+ hash.UpdateOrAdd(2);
+ hash.UpdateOrAdd(2);
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/UserGuideExamples.csproj b/mcs/class/Mono.C5/UserGuideExamples/UserGuideExamples.csproj new file mode 100644 index 00000000000..f2559711fd9 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/UserGuideExamples.csproj @@ -0,0 +1,90 @@ +<?xml version="1.0" encoding="utf-8"?>
+<Project DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+ <PropertyGroup>
+ <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+ <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+ <ProductVersion>8.0.50727</ProductVersion>
+ <SchemaVersion>2.0</SchemaVersion>
+ <ProjectGuid>{B2A29FF2-A5C5-4F07-8CE7-FF5D744D7562}</ProjectGuid>
+ <OutputType>Library</OutputType>
+ <RootNamespace>UserGuideExamples</RootNamespace>
+ <AssemblyName>UserGuideExamples</AssemblyName>
+ <WarningLevel>4</WarningLevel>
+ <StartupObject>
+ </StartupObject>
+ </PropertyGroup>
+ <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+ <DebugSymbols>true</DebugSymbols>
+ <DebugType>full</DebugType>
+ <Optimize>false</Optimize>
+ <OutputPath>.\bin\Debug\</OutputPath>
+ <DefineConstants>DEBUG;TRACE</DefineConstants>
+ </PropertyGroup>
+ <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+ <DebugSymbols>false</DebugSymbols>
+ <Optimize>true</Optimize>
+ <OutputPath>.\bin\Release\</OutputPath>
+ <DefineConstants>TRACE</DefineConstants>
+ </PropertyGroup>
+ <ItemGroup>
+ <Compile Include="AnagramHashBag.cs" />
+ <Compile Include="Anagrams.cs" />
+ <Compile Include="AnagramStrings.cs" />
+ <Compile Include="AnagramTreeBag.cs" />
+ <Compile Include="Antipatterns.cs" />
+ <Compile Include="Cloning.cs" />
+ <Compile Include="CollectionCollection.cs" />
+ <Compile Include="CollectionSanity.cs" />
+ <Compile Include="EventPatterns.cs" />
+ <Compile Include="GettingStarted.cs" />
+ <Compile Include="Graph.cs" />
+ <Compile Include="Fileindex.cs" />
+ <Compile Include="GCHForm.cs">
+ <SubType>Form</SubType>
+ </Compile>
+ <Compile Include="GConvexHull.cs" />
+ <Compile Include="GNfaToDfa.cs" />
+ <Compile Include="HashCodes.cs" />
+ <Compile Include="Jobqueue.cs" />
+ <Compile Include="KeywordRecognition.cs" />
+ <Compile Include="ListPatterns.cs" />
+ <Compile Include="Locking.cs" />
+ <Compile Include="MultiCollection.cs" />
+ <Compile Include="MultiDictionary.cs" />
+ <Compile Include="PointLocation.cs" />
+ <Compile Include="RandomSelection.cs" />
+ <Compile Include="ReadOnlyPatterns.cs" />
+ <Compile Include="Sets.cs" />
+ <Compile Include="SortedIterationPatterns.cs" />
+ <Compile Include="SortingPermutation.cs" />
+ <Compile Include="TestSortedArray.cs" />
+ <Compile Include="ThisFun.cs" />
+ <Compile Include="Toposort.cs" />
+ <Compile Include="TreeTraversal.cs" />
+ <Compile Include="Try.cs" />
+ <Compile Include="ViewPatterns.cs" />
+ <Compile Include="Views.cs" />
+ <Compile Include="WrappedArray.cs" />
+ </ItemGroup>
+ <ItemGroup>
+ <EmbeddedResource Include="GCHForm.resx">
+ <DependentUpon>GCHForm.cs</DependentUpon>
+ </EmbeddedResource>
+ </ItemGroup>
+ <ItemGroup>
+ <ProjectReference Include="..\C5\C5.csproj">
+ <Project>{D70489CD-ABDA-48FF-BD1E-BE3F7495BE71}</Project>
+ <Package>{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</Package>
+ <Name>C5</Name>
+ </ProjectReference>
+ </ItemGroup>
+ <ItemGroup>
+ <None Include="Makefile" />
+ </ItemGroup>
+ <ItemGroup>
+ <Reference Include="System" />
+ <Reference Include="System.Drawing" />
+ <Reference Include="System.Windows.Forms" />
+ </ItemGroup>
+ <Import Project="$(MSBuildBinPath)\Microsoft.CSHARP.Targets" />
+</Project>
\ No newline at end of file diff --git a/mcs/class/Mono.C5/UserGuideExamples/ViewPatterns.cs b/mcs/class/Mono.C5/UserGuideExamples/ViewPatterns.cs new file mode 100644 index 00000000000..c1330ed6f10 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/ViewPatterns.cs @@ -0,0 +1,340 @@ +/*
+ 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: ViewPatterns 2005-07-22
+
+// Compile with
+// csc /r:C5.dll ViewPatterns.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace ViewPatterns {
+ class Views {
+ public static void Main(String[] args) {
+ IList<char> lst = new ArrayList<char>();
+ lst.AddAll<char>(new char[] { 'a', 'b', 'c', 'd' });
+ IList<char> v1 = lst.View(1, 1);
+ Console.WriteLine("v1 = {0}", v1);
+ InsertBeforeFirst(v1, '<', 'b');
+ InsertAfterFirst(v1, '>', 'b');
+ Console.WriteLine("v1 = {0}", v1);
+ char x;
+ if (SequencePredecessor(v1, 'b', out x))
+ Console.WriteLine("Predecessor of b is " + x);
+ if (SequenceSuccessor(v1, 'b', out x))
+ Console.WriteLine("Successor of b is " + x);
+ if (!SequencePredecessor(v1, 'c', out x))
+ Console.WriteLine("c has no predecessor");
+ if (!SequenceSuccessor(v1, 'a', out x))
+ Console.WriteLine("a has no successor");
+ IList<char> lst2 = new ArrayList<char>();
+ lst2.AddAll<char>(new char[] { 'a', 'b', 'c', 'A', 'a', 'd', 'a' });
+ foreach (int i in IndexesOf(lst2, 'a'))
+ Console.Write("{0} ", i);
+ Console.WriteLine();
+ foreach (int i in ReverseIndexesOf(lst2, 'a'))
+ Console.Write("{0} ", i);
+ Console.WriteLine();
+ Console.WriteLine(lst2);
+ IList<char> view = lst2.View(2,0);
+ InsertAtView(lst2, view, 'y');
+ Console.WriteLine(lst2);
+ InsertIntoView(view, 'x');
+ Console.WriteLine(lst2);
+ }
+
+ // --- Patterns for zero-item views -----------------------------
+
+ // Number of items before zero-item view
+
+ public static int ItemsBefore<T>(IList<T> view) {
+ return view.Offset;
+ }
+
+ // Number of items after zero-item view
+
+ public static int ItemsAfter<T>(IList<T> view) {
+ return view.Underlying.Count - view.Offset;
+ }
+
+ // Move (zero-item) view one item to the left
+
+ public static void MoveLeft<T>(IList<T> view) {
+ // One of these:
+ view.Slide(-1);
+ view.TrySlide(-1);
+ }
+
+ // Move (zero-item) view one item to the right
+
+ public static void MoveRight<T>(IList<T> view) {
+ // One of these:
+ view.Slide(+1);
+ view.TrySlide(+1);
+ }
+
+ // Test whether (zero-item) view is at beginning of list
+
+ public static bool AtBeginning<T>(IList<T> view) {
+ return view.Offset == 0;
+ }
+
+ // Test whether (zero-item) view is at end of list
+
+ public static bool AtEnd<T>(IList<T> view) {
+ return view.Offset == view.Underlying.Count;
+ }
+
+ // Insert x into zero-item view and into underlying list
+
+ public static void InsertIntoView<T>(IList<T> view, T x) {
+ view.Add(x);
+ }
+
+ // Insert x into list at zero-item view
+
+ public static void InsertAtView<T>(IList<T> list, IList<T> view, T x) {
+ list.Insert(view, x);
+ }
+
+ // Delete the item before zero-item view
+
+ public static void DeleteBefore<T>(IList<T> view) {
+ view.Slide(-1,1).RemoveFirst();
+ }
+
+ // Delete the item after zero-item view
+
+ public static void DeleteAfter<T>(IList<T> view) {
+ view.Slide(0,1).RemoveFirst();
+ }
+
+ // Get the zero-item view at left endpoint. Succeeds on all lists
+ // and valid views.
+
+ public static IList<T> LeftEndView<T>(IList<T> list) {
+ return list.View(0,0);
+ }
+
+ // Get the zero-item view at right endpoint. Succeeds on all
+ // lists and valid views.
+
+ public static IList<T> RightEndView<T>(IList<T> list) {
+ return list.View(list.Count,0);
+ }
+
+
+ // --- Patterns for one-item views ------------------------------
+
+ // Find the sequence predecessor x of y; or throw exception
+
+ public static T SequencePredecessor<T>(IList<T> list, T y) {
+ return list.ViewOf(y).Slide(-1)[0];
+ }
+
+ // Find the sequence predecessor x of y; or return false
+
+ public static bool SequencePredecessor<T>(IList<T> list, T y, out T x) {
+ IList<T> view = list.ViewOf(y);
+ bool ok = view != null && view.TrySlide(-1);
+ x = ok ? view[0] : default(T);
+ return ok;
+ }
+
+ // Find the sequence successor x of y; or throw exception
+
+ public static T SequenceSuccessor<T>(IList<T> list, T y) {
+ return list.ViewOf(y).Slide(+1)[0];
+ }
+
+ // Find the sequence successor x of y; or return false
+
+ public static bool SequenceSuccessor<T>(IList<T> list, T y, out T x) {
+ IList<T> view = list.ViewOf(y);
+ bool ok = view != null && view.TrySlide(+1);
+ x = ok ? view[0] : default(T);
+ return ok;
+ }
+
+ // Insert x into list after first occurrence of y (or throw
+ // NullReferenceException).
+
+ public static void InsertAfterFirst<T>(IList<T> list, T x, T y) {
+ list.Insert(list.ViewOf(y), x);
+ }
+
+ // Insert x into list before first occurrence of y (or throw
+ // NullReferenceException)
+
+ public static void InsertBeforeFirst<T>(IList<T> list, T x, T y) {
+ list.Insert(list.ViewOf(y).Slide(0, 0), x);
+ }
+
+ // Insert x into list after last occurrence of y (or throw
+ // NullReferenceException).
+
+ public static void InsertAfterLast<T>(IList<T> list, T x, T y) {
+ list.Insert(list.LastViewOf(y), x);
+ }
+
+ // Insert x into list before last occurrence of y (or throw
+ // NullReferenceException)
+
+ public static void InsertBeforeLast<T>(IList<T> list, T x, T y) {
+ list.Insert(list.LastViewOf(y).Slide(0, 0), x);
+ }
+
+ // Same meaning as InsertBeforeFirst on a proper list, but not on
+ // a view
+
+ public static void InsertBeforeFirstAlt<T>(IList<T> list, T x, T y) {
+ list.ViewOf(y).InsertFirst(x);
+ }
+
+ // Delete the sequence predecessor of first y; or throw exception
+
+ public static T RemovePredecessorOfFirst<T>(IList<T> list, T y) {
+ return list.ViewOf(y).Slide(-1).Remove();
+ }
+
+ // Delete the sequence successor of first y; or throw exception
+
+ public static T RemoveSuccessorOfFirst<T>(IList<T> list, T y) {
+ return list.ViewOf(y).Slide(+1).Remove();
+ }
+
+ // --- Other view patterns --------------------------------------
+
+ // Replace the first occurrence of each x from xs by y in list:
+
+ public static void ReplaceXsByY<T>(HashedLinkedList<T> list, T[] xs, T y) {
+ foreach (T x in xs) {
+ using (IList<T> view = list.ViewOf(x)) {
+ if (view != null) {
+ view.Remove();
+ view.Add(y);
+ }
+ }
+ }
+ }
+
+ // Get index in underlying list of view's left end
+
+ public static int LeftEndIndex<T>(IList<T> view) {
+ return view.Offset;
+ }
+
+ // Get index in underlying list of view's right end
+
+ public static int RightEndIndex<T>(IList<T> view) {
+ return view.Offset + view.Count;
+ }
+
+ // Test whether views overlap
+
+ public static bool Overlap<T>(IList<T> u, IList<T> w) {
+ if (u.Underlying == null || u.Underlying != w.Underlying)
+ throw new ArgumentException("views must have same underlying list");
+ else
+ return u.Offset < w.Offset+w.Count && w.Offset < u.Offset+u.Count;
+ }
+
+ // Find the length of the overlap between two views
+
+ public static int OverlapLength<T>(IList<T> u, IList<T> w) {
+ if (Overlap(u, w))
+ return Math.Min(u.Offset+u.Count, w.Offset+w.Count)
+ - Math.Max(u.Offset, w.Offset);
+ else
+ return -1; // No overlap
+ }
+
+ // Test whether view u contains view v
+
+ public static bool ContainsView<T>(IList<T> u, IList<T> w) {
+ if (u.Underlying == null || u.Underlying != w.Underlying)
+ throw new ArgumentException("views must have same underlying list");
+ else
+ if (w.Count > 0)
+ return u.Offset <= w.Offset && w.Offset+w.Count <= u.Offset+u.Count;
+ else
+ return u.Offset < w.Offset && w.Offset < u.Offset+u.Count;
+ }
+
+ // Test whether views u and v have (or are) the same underlying list
+
+ public static bool SameUnderlying<T>(IList<T> u, IList<T> w) {
+ return (u.Underlying ?? u) == (w.Underlying ?? w);
+ }
+
+ // Find the index of the first item that satisfies p
+
+ public static int FindFirstIndex<T>(IList<T> list, Fun<T,bool> p) {
+ using (IList<T> view = list.View(0, 0)) {
+ while (view.TrySlide(0, 1)) {
+ if (p(view.First))
+ return view.Offset;
+ view.Slide(+1, 0);
+ }
+ }
+ return -1;
+ }
+
+ // Find the index of the last item that satisfies p
+
+ public static int FindLastIndex<T>(IList<T> list, Fun<T,bool> p) {
+ using (IList<T> view = list.View(list.Count, 0)) {
+ while (view.TrySlide(-1, 1)) {
+ if (p(view.First))
+ return view.Offset;
+ }
+ }
+ return -1;
+ }
+
+ // Yield indexes of all items equal to x, in list order:
+
+ public static SCG.IEnumerable<int> IndexesOf<T>(IList<T> list, T x) {
+ IList<T> tail = list.View(0, list.Count);
+ tail = tail.ViewOf(x);
+ while (tail != null) {
+ yield return tail.Offset;
+ tail = tail.Slide(+1,0).Span(list);
+ tail = tail.ViewOf(x);
+ }
+ }
+
+ // Yield indexes of items equal to x, in reverse list order.
+
+ public static SCG.IEnumerable<int> ReverseIndexesOf<T>(IList<T> list, T x) {
+ IList<T> head = list.View(0, list.Count);
+ head = head.LastViewOf(x);
+ while (head != null) {
+ yield return head.Offset;
+ head = list.Span(head.Slide(0,0));
+ head = head.LastViewOf(x);
+ }
+ }
+
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/Views.cs b/mcs/class/Mono.C5/UserGuideExamples/Views.cs new file mode 100644 index 00000000000..6cf96bf1291 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/Views.cs @@ -0,0 +1,160 @@ +/*
+ 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: Views 2004-12-29 OBSOLETE
+
+// Compile with
+// csc /r:C5.dll Views.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace Views {
+ class Views {
+ public static void Main(String[] args) {
+ IList<char> lst = new LinkedList<char>();
+ lst.AddAll<char>(new char[] { 'a', 'b', 'c', 'd' });
+ IList<char>
+ A = lst.View(0, 2),
+ B = lst.View(2, 0),
+ C = lst.View(2, 1),
+ D = lst.View(3, 1),
+ E = lst.View(4, 0),
+ F = lst.View(1, 2),
+ G = lst.View(0, 4);
+ IList<char>[] views = { A, B, C, D, E, F, G };
+ Console.WriteLine("ABCDEFG overlaps with:");
+ foreach (IList<char> u in views) {
+ foreach (IList<char> w in views)
+ Console.Write(Overlap(u, w) ? '+' : '-');
+ Console.WriteLine();
+ }
+ Console.WriteLine("ABCDEFG overlap length:");
+ foreach (IList<char> u in views) {
+ foreach (IList<char> w in views) {
+ int len = OverlapLength(u, w);
+ Console.Write(len >= 0 ? String.Format("{0}", len) : " ");
+ }
+ Console.WriteLine();
+ }
+ Console.WriteLine("ABCDEFG contained in:");
+ foreach (IList<char> u in views) {
+ foreach (IList<char> w in views)
+ Console.Write(ContainsView(u, w) ? '+' : '-');
+ Console.WriteLine();
+ }
+ }
+
+ public static int LeftEndIndex<T>(IList<T> u) {
+ return u.Offset;
+ }
+
+ public static int RightEndIndex<T>(IList<T> u) {
+ return u.Offset+u.Count;
+ }
+
+ public static bool Overlap<T>(IList<T> u, IList<T> w) {
+ if (u.Underlying == null || u.Underlying != w.Underlying)
+ throw new ArgumentException("views must have same underlying list");
+ else
+ return u.Offset < w.Offset+w.Count && w.Offset < u.Offset+u.Count;
+ }
+
+ public static int OverlapLength<T>(IList<T> u, IList<T> w) {
+ if (Overlap(u, w))
+ return Math.Min(u.Offset+u.Count, w.Offset+w.Count)
+ - Math.Max(u.Offset, w.Offset);
+ else
+ return -1; // No overlap
+ }
+
+ public static bool ContainsView<T>(IList<T> u, IList<T> w) {
+ if (u.Underlying == null || u.Underlying != w.Underlying)
+ throw new ArgumentException("views must have same underlying list");
+ else
+ if (w.Count > 0)
+ return u.Offset <= w.Offset && w.Offset+w.Count <= u.Offset+u.Count;
+ else
+ return u.Offset < w.Offset && w.Offset < u.Offset+u.Count;
+ }
+
+ public static bool SameUnderlying<T>(IList<T> u, IList<T> w) {
+ return (u.Underlying ?? u) == (w.Underlying ?? w);
+ }
+
+ // Replace the first occurrence of each x from xs by y in list:
+
+ public static void ReplaceXsByY<T>(HashedLinkedList<T> list, T[] xs, T y) {
+ foreach (T x in xs) {
+ using (IList<T> view = list.ViewOf(x)) {
+ if (view != null) {
+ view.Remove();
+ view.Add(y);
+ }
+ }
+ }
+ }
+
+ // Find first item that satisfies p
+
+ public static bool Find<T>(IList<T> list, Fun<T,bool> p, out T res) {
+ IList<T> view = list.View(0, 0);
+ while (view.Offset < list.Count) {
+ view.Slide(+1, 1);
+ if (p(view.First)) {
+ res = view.First;
+ return true;
+ }
+ }
+ res = default(T);
+ return false;
+ }
+
+ // Or, using that the list is enumerable:
+
+ public static bool Find1<T>(IList<T> list, Fun<T,bool> p, out T res) {
+ foreach (T x in list) {
+ if (p(x)) {
+ res = x;
+ return true;
+ }
+ }
+ res = default(T);
+ return false;
+ }
+
+ // Find last item that satisfies p
+
+ public static bool FindLast<T>(IList<T> list, Fun<T,bool> p, out T res) {
+ IList<T> view = list.View(list.Count, 0);
+ while (view.Offset > 0) {
+ view.Slide(-1, 1);
+ if (p(view.First)) {
+ res = view.First;
+ return true;
+ }
+ }
+ res = default(T);
+ return false;
+ }
+ }
+}
diff --git a/mcs/class/Mono.C5/UserGuideExamples/WrappedArray.cs b/mcs/class/Mono.C5/UserGuideExamples/WrappedArray.cs new file mode 100644 index 00000000000..398b9bf5b44 --- /dev/null +++ b/mcs/class/Mono.C5/UserGuideExamples/WrappedArray.cs @@ -0,0 +1,191 @@ +/*
+ 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: WrappedArray 2005-07-21
+
+// Compile with
+// csc /r:C5.dll WrappedArray.cs
+
+using System;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace WrappedArray {
+ class WrappedArray {
+ public static void Main(String[] args) {
+ }
+
+
+ // System.Array.Exists
+
+ public static bool Exists<T>(T[] arr, Fun<T,bool> p) {
+ return new WrappedArray<T>(arr).Exists(p);
+ }
+
+ // System.Array.TrueForAll
+
+ public static bool TrueForAll<T>(T[] arr, Fun<T,bool> p) {
+ return new WrappedArray<T>(arr).All(p);
+ }
+
+ // System.Array.Find(T[], Predicate)
+ // This loses the valuable bool returned by C5 Find.
+
+ public static T Find<T>(T[] arr, Fun<T,bool> p) {
+ T res;
+ new WrappedArray<T>(arr).Find(p, out res);
+ return res;
+ }
+
+ // System.Array.FindAll(T[], Predicate)
+
+ public static T[] FindAll<T>(T[] arr, Fun<T,bool> p) {
+ return new WrappedArray<T>(arr).FindAll(p).ToArray();
+ }
+
+ // System.Array.FindIndex(T[], Predicate)
+
+ public static int FindIndex<T>(T[] arr, Fun<T,bool> p) {
+ return new WrappedArray<T>(arr).FindIndex(p);
+ }
+
+ // System.Array.FindIndex(T[], int, Predicate)
+
+ public static int FindIndex<T>(T[] arr, int i, Fun<T,bool> p) {
+ int j = new WrappedArray<T>(arr).View(i,arr.Length-i).FindIndex(p);
+ return j < 0 ? j : j+i;
+ }
+
+ // System.Array.FindIndex(T[], int, int, Predicate)
+
+ public static int FindIndex<T>(T[] arr, int i, int n, Fun<T,bool> p) {
+ int j = new WrappedArray<T>(arr).View(i,n).FindIndex(p);
+ return j < 0 ? j : j+i;
+ }
+
+ // System.Array.FindLast(T[], Predicate)
+ // This loses the valuable bool returned by C5 Find.
+
+ public static T FindLast<T>(T[] arr, Fun<T,bool> p) {
+ T res;
+ new WrappedArray<T>(arr).FindLast(p, out res);
+ return res;
+ }
+
+ // System.Array.FindLastIndex(T[], Predicate)
+
+ public static int FindLastIndex<T>(T[] arr, Fun<T,bool> p) {
+ return new WrappedArray<T>(arr).FindIndex(p);
+ }
+
+ // System.Array.FindLastIndex(T[], int, Predicate)
+
+ public static int FindLastIndex<T>(T[] arr, int i, Fun<T,bool> p) {
+ int j = new WrappedArray<T>(arr).View(i,arr.Length-i).FindIndex(p);
+ return j < 0 ? j : j+i;
+ }
+
+ // System.Array.FindLastIndex(T[], int, int, Predicate)
+
+ public static int FindLastIndex<T>(T[] arr, int i, int n, Fun<T,bool> p) {
+ int j = new WrappedArray<T>(arr).View(i,n).FindIndex(p);
+ return j < 0 ? j : j+i;
+ }
+
+ // System.Array.ForEach(T[], Action)
+
+ public static void ForEach<T>(T[] arr, Act<T> act) {
+ new WrappedArray<T>(arr).Apply(act);
+ }
+
+ // System.Array.IndexOf(T[], T)
+
+ public static int IndexOf<T>(T[] arr, T x) {
+ int j = new WrappedArray<T>(arr).IndexOf(x);
+ return j < 0 ? -1 : j;
+ }
+
+ // System.Array.IndexOf(T[], T, int)
+
+ public static int IndexOf<T>(T[] arr, T x, int i) {
+ int j = new WrappedArray<T>(arr).View(i, arr.Length-i).IndexOf(x);
+ return j < 0 ? -1 : j+i;
+ }
+
+ // System.Array.IndexOf(T[], T, int, int)
+
+ public static int IndexOf<T>(T[] arr, T x, int i, int n) {
+ int j = new WrappedArray<T>(arr).View(i, n).IndexOf(x);
+ return j < 0 ? -1 : j+i;
+ }
+
+ // System.Array.LastIndexOf(T[], T)
+
+ public static int LastIndexOf<T>(T[] arr, T x) {
+ int j = new WrappedArray<T>(arr).LastIndexOf(x);
+ return j < 0 ? -1 : j;
+ }
+
+ // System.Array.LastIndexOf(T[], T, int)
+
+ public static int LastIndexOf<T>(T[] arr, T x, int i) {
+ int j = new WrappedArray<T>(arr).View(i, arr.Length-i).LastIndexOf(x);
+ return j < 0 ? -1 : j+i;
+ }
+
+ // System.Array.LastIndexOf(T[], T, int, int)
+
+ public static int LastIndexOf<T>(T[] arr, T x, int i, int n) {
+ int j = new WrappedArray<T>(arr).View(i, n).LastIndexOf(x);
+ return j < 0 ? -1 : j+i;
+ }
+
+ // System.Array.Sort(T[])
+
+ public static void Sort<T>(T[] arr) {
+ new WrappedArray<T>(arr).Sort();
+ }
+
+ // System.Array.Sort(T[], int, int)
+
+ public static void Sort<T>(T[] arr, int i, int n) {
+ new WrappedArray<T>(arr).View(i, n).Sort();
+ }
+
+ // System.Array.Sort(T[], SCG.IComparer<T>)
+
+ public static void Sort<T>(T[] arr, SCG.IComparer<T> cmp) {
+ new WrappedArray<T>(arr).Sort(cmp);
+ }
+
+ // System.Array.Sort(T[], int, int, SCG.IComparer<T>)
+
+ public static void Sort<T>(T[] arr, int i, int n, SCG.IComparer<T> cmp) {
+ new WrappedArray<T>(arr).View(i, n).Sort(cmp);
+ }
+
+ // System.Array.Sort(T[], Comparison)
+
+ public static void Sort<T>(T[] arr, Comparison<T> csn) {
+ new WrappedArray<T>(arr).Sort(new DelegateComparer<T>(csn));
+ }
+ }
+}
|