2 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
3 Permission is hereby granted, free of charge, to any person obtaining a copy
4 of this software and associated documentation files (the "Software"), to deal
5 in the Software without restriction, including without limitation the rights
6 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7 copies of the Software, and to permit persons to whom the Software is
8 furnished to do so, subject to the following conditions:
10 The above copyright notice and this permission notice shall be included in
11 all copies or substantial portions of the Software.
13 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 // C5 example: Views 2004-12-29 OBSOLETE
25 // csc /r:C5.dll Views.cs
29 using SCG = System.Collections.Generic;
33 public static void Main(String[] args) {
34 IList<char> lst = new LinkedList<char>();
35 lst.AddAll<char>(new char[] { 'a', 'b', 'c', 'd' });
44 IList<char>[] views = { A, B, C, D, E, F, G };
45 Console.WriteLine("ABCDEFG overlaps with:");
46 foreach (IList<char> u in views) {
47 foreach (IList<char> w in views)
48 Console.Write(Overlap(u, w) ? '+' : '-');
51 Console.WriteLine("ABCDEFG overlap length:");
52 foreach (IList<char> u in views) {
53 foreach (IList<char> w in views) {
54 int len = OverlapLength(u, w);
55 Console.Write(len >= 0 ? String.Format("{0}", len) : " ");
59 Console.WriteLine("ABCDEFG contained in:");
60 foreach (IList<char> u in views) {
61 foreach (IList<char> w in views)
62 Console.Write(ContainsView(u, w) ? '+' : '-');
67 public static int LeftEndIndex<T>(IList<T> u) {
71 public static int RightEndIndex<T>(IList<T> u) {
72 return u.Offset+u.Count;
75 public static bool Overlap<T>(IList<T> u, IList<T> w) {
76 if (u.Underlying == null || u.Underlying != w.Underlying)
77 throw new ArgumentException("views must have same underlying list");
79 return u.Offset < w.Offset+w.Count && w.Offset < u.Offset+u.Count;
82 public static int OverlapLength<T>(IList<T> u, IList<T> w) {
84 return Math.Min(u.Offset+u.Count, w.Offset+w.Count)
85 - Math.Max(u.Offset, w.Offset);
87 return -1; // No overlap
90 public static bool ContainsView<T>(IList<T> u, IList<T> w) {
91 if (u.Underlying == null || u.Underlying != w.Underlying)
92 throw new ArgumentException("views must have same underlying list");
95 return u.Offset <= w.Offset && w.Offset+w.Count <= u.Offset+u.Count;
97 return u.Offset < w.Offset && w.Offset < u.Offset+u.Count;
100 public static bool SameUnderlying<T>(IList<T> u, IList<T> w) {
101 return (u.Underlying ?? u) == (w.Underlying ?? w);
104 // Replace the first occurrence of each x from xs by y in list:
106 public static void ReplaceXsByY<T>(HashedLinkedList<T> list, T[] xs, T y) {
107 foreach (T x in xs) {
108 using (IList<T> view = list.ViewOf(x)) {
117 // Find first item that satisfies p
119 public static bool Find<T>(IList<T> list, Fun<T,bool> p, out T res) {
120 IList<T> view = list.View(0, 0);
121 while (view.Offset < list.Count) {
132 // Or, using that the list is enumerable:
134 public static bool Find1<T>(IList<T> list, Fun<T,bool> p, out T res) {
135 foreach (T x in list) {
145 // Find last item that satisfies p
147 public static bool FindLast<T>(IList<T> list, Fun<T,bool> p, out T res) {
148 IList<T> view = list.View(list.Count, 0);
149 while (view.Offset > 0) {