mcs/class/Mono.C5/UserGuideExamples/ViewPatterns.cs

   1 /*
   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:
   9
  10  The above copyright notice and this permission notice shall be included in
  11  all copies or substantial portions of the Software.
  12
  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
  19  SOFTWARE.
  20 */
  21
  22 // C5 example: ViewPatterns 2005-07-22
  23
  24 // Compile with
  25 //   csc /r:C5.dll ViewPatterns.cs
  26
  27 using System;
  28 using C5;
  29 using SCG = System.Collections.Generic;
  30
  31 namespace ViewPatterns {
  32   class Views {
  33     public static void Main(String[] args) {
  34       IList<char> lst = new ArrayList<char>();
  35       lst.AddAll<char>(new char[] { 'a', 'b', 'c', 'd' });
  36       IList<char> v1 = lst.View(1, 1);
  37       Console.WriteLine("v1 = {0}", v1);
  38       InsertBeforeFirst(v1, '<', 'b');
  39       InsertAfterFirst(v1, '>', 'b');
  40       Console.WriteLine("v1 = {0}", v1);
  41       char x;
  42       if (SequencePredecessor(v1, 'b', out x))
  43         Console.WriteLine("Predecessor of b is " + x);
  44       if (SequenceSuccessor(v1, 'b', out x))
  45         Console.WriteLine("Successor of b is " + x);
  46       if (!SequencePredecessor(v1, 'c', out x))
  47         Console.WriteLine("c has no predecessor");
  48       if (!SequenceSuccessor(v1, 'a', out x))
  49         Console.WriteLine("a has no successor");
  50       IList<char> lst2 = new ArrayList<char>();
  51       lst2.AddAll<char>(new char[] { 'a', 'b', 'c', 'A', 'a', 'd', 'a' });
  52       foreach (int i in IndexesOf(lst2, 'a'))
  53         Console.Write("{0} ", i);
  54       Console.WriteLine();
  55       foreach (int i in ReverseIndexesOf(lst2, 'a'))
  56         Console.Write("{0} ", i);
  57       Console.WriteLine();
  58       Console.WriteLine(lst2);
  59       IList<char> view = lst2.View(2,0);
  60       InsertAtView(lst2, view, 'y');
  61       Console.WriteLine(lst2);
  62       InsertIntoView(view, 'x');
  63       Console.WriteLine(lst2);
  64     }
  65
  66     // --- Patterns for zero-item views -----------------------------
  67
  68     // Number of items before zero-item view
  69
  70     public static int ItemsBefore<T>(IList<T> view) {
  71       return view.Offset;
  72     }
  73
  74     // Number of items after zero-item view
  75
  76     public static int ItemsAfter<T>(IList<T> view) {
  77       return view.Underlying.Count - view.Offset;
  78     }
  79
  80     // Move (zero-item) view one item to the left
  81
  82     public static void MoveLeft<T>(IList<T> view) {
  83       // One of these:
  84       view.Slide(-1);
  85       view.TrySlide(-1);
  86     }
  87
  88     // Move (zero-item) view one item to the right
  89
  90     public static void MoveRight<T>(IList<T> view) {
  91       // One of these:
  92       view.Slide(+1);
  93       view.TrySlide(+1);
  94     }
  95
  96     // Test whether (zero-item) view is at beginning of list
  97
  98     public static bool AtBeginning<T>(IList<T> view) {
  99       return view.Offset == 0;
 100     }
 101
 102     // Test whether (zero-item) view is at end of list
 103
 104     public static bool AtEnd<T>(IList<T> view) {
 105       return view.Offset == view.Underlying.Count;
 106     }
 107
 108     // Insert x into zero-item view and into underlying list
 109
 110     public static void InsertIntoView<T>(IList<T> view, T x) {
 111       view.Add(x);
 112     }
 113
 114     // Insert x into list at zero-item view
 115
 116     public static void InsertAtView<T>(IList<T> list, IList<T> view, T x) {
 117       list.Insert(view, x);
 118     }
 119
 120     // Delete the item before zero-item view
 121
 122     public static void DeleteBefore<T>(IList<T> view) {
 123       view.Slide(-1,1).RemoveFirst();
 124     }
 125
 126     // Delete the item after zero-item view
 127
 128     public static void DeleteAfter<T>(IList<T> view) {
 129       view.Slide(0,1).RemoveFirst();
 130     }
 131
 132     // Get the zero-item view at left endpoint.  Succeeds on all lists
 133     // and valid views.
 134
 135     public static IList<T> LeftEndView<T>(IList<T> list) {
 136       return list.View(0,0);
 137     }
 138
 139     // Get the zero-item view at right endpoint.  Succeeds on all
 140     // lists and valid views.
 141
 142     public static IList<T> RightEndView<T>(IList<T> list) {
 143       return list.View(list.Count,0);
 144     }
 145
 146
 147     // --- Patterns for one-item views ------------------------------
 148
 149     // Find the sequence predecessor x of y; or throw exception
 150
 151     public static T SequencePredecessor<T>(IList<T> list, T y) {
 152       return list.ViewOf(y).Slide(-1)[0];
 153     }
 154
 155     // Find the sequence predecessor x of y; or return false
 156
 157     public static bool SequencePredecessor<T>(IList<T> list, T y, out T x) {
 158       IList<T> view = list.ViewOf(y);
 159       bool ok = view != null && view.TrySlide(-1);
 160       x = ok ? view[0] : default(T);
 161       return ok;
 162     }
 163
 164     // Find the sequence successor x of y; or throw exception
 165
 166     public static T SequenceSuccessor<T>(IList<T> list, T y) {
 167       return list.ViewOf(y).Slide(+1)[0];
 168     }
 169
 170     // Find the sequence successor x of y; or return false
 171
 172     public static bool SequenceSuccessor<T>(IList<T> list, T y, out T x) {
 173       IList<T> view = list.ViewOf(y);
 174       bool ok = view != null && view.TrySlide(+1);
 175       x = ok ? view[0] : default(T);
 176       return ok;
 177     }
 178
 179     // Insert x into list after first occurrence of y (or throw
 180     // NullReferenceException).
 181
 182     public static void InsertAfterFirst<T>(IList<T> list, T x, T y) {
 183       list.Insert(list.ViewOf(y), x);
 184     }
 185
 186     // Insert x into list before first occurrence of y (or throw
 187     // NullReferenceException)
 188
 189     public static void InsertBeforeFirst<T>(IList<T> list, T x, T y) {
 190       list.Insert(list.ViewOf(y).Slide(0, 0), x);
 191     }
 192
 193     // Insert x into list after last occurrence of y (or throw
 194     // NullReferenceException).
 195
 196     public static void InsertAfterLast<T>(IList<T> list, T x, T y) {
 197       list.Insert(list.LastViewOf(y), x);
 198     }
 199
 200     // Insert x into list before last occurrence of y (or throw
 201     // NullReferenceException)
 202
 203     public static void InsertBeforeLast<T>(IList<T> list, T x, T y) {
 204       list.Insert(list.LastViewOf(y).Slide(0, 0), x);
 205     }
 206
 207     // Same meaning as InsertBeforeFirst on a proper list, but not on
 208     // a view
 209
 210     public static void InsertBeforeFirstAlt<T>(IList<T> list, T x, T y) {
 211       list.ViewOf(y).InsertFirst(x);
 212     }
 213
 214     // Delete the sequence predecessor of first y; or throw exception
 215
 216     public static T RemovePredecessorOfFirst<T>(IList<T> list, T y) {
 217       return list.ViewOf(y).Slide(-1).Remove();
 218     }
 219
 220     // Delete the sequence successor of first y; or throw exception
 221
 222     public static T RemoveSuccessorOfFirst<T>(IList<T> list, T y) {
 223       return list.ViewOf(y).Slide(+1).Remove();
 224     }
 225
 226     // --- Other view patterns --------------------------------------
 227
 228     // Replace the first occurrence of each x from xs by y in list:
 229
 230     public static void ReplaceXsByY<T>(HashedLinkedList<T> list, T[] xs, T y) {
 231       foreach (T x in xs) {
 232         using (IList<T> view = list.ViewOf(x)) {
 233           if (view != null) {
 234             view.Remove();
 235             view.Add(y);
 236           }
 237         }
 238       }
 239     }
 240
 241     // Get index in underlying list of view's left end
 242
 243     public static int LeftEndIndex<T>(IList<T> view) {
 244       return view.Offset;
 245     }
 246
 247     // Get index in underlying list of view's right end
 248
 249     public static int RightEndIndex<T>(IList<T> view) {
 250       return view.Offset + view.Count;
 251     }
 252
 253     // Test whether views overlap
 254
 255     public static bool Overlap<T>(IList<T> u, IList<T> w) {
 256       if (u.Underlying == null || u.Underlying != w.Underlying)
 257         throw new ArgumentException("views must have same underlying list");
 258       else
 259         return u.Offset < w.Offset+w.Count && w.Offset < u.Offset+u.Count;
 260     }
 261
 262     // Find the length of the overlap between two views
 263
 264     public static int OverlapLength<T>(IList<T> u, IList<T> w) {
 265       if (Overlap(u, w))
 266         return Math.Min(u.Offset+u.Count, w.Offset+w.Count)
 267              - Math.Max(u.Offset, w.Offset);
 268       else
 269         return -1; // No overlap
 270     }
 271
 272     // Test whether view u contains view v
 273
 274     public static bool ContainsView<T>(IList<T> u, IList<T> w) {
 275       if (u.Underlying == null || u.Underlying != w.Underlying)
 276         throw new ArgumentException("views must have same underlying list");
 277       else
 278         if (w.Count > 0)
 279           return u.Offset <= w.Offset && w.Offset+w.Count <= u.Offset+u.Count;
 280         else
 281           return u.Offset < w.Offset && w.Offset < u.Offset+u.Count;
 282     }
 283
 284     // Test whether views u and v have (or are) the same underlying list
 285
 286     public static bool SameUnderlying<T>(IList<T> u, IList<T> w) {
 287       return (u.Underlying ?? u) == (w.Underlying ?? w);
 288     }
 289
 290     // Find the index of the first item that satisfies p
 291
 292     public static int FindFirstIndex<T>(IList<T> list, Fun<T,bool> p) {
 293       using (IList<T> view = list.View(0, 0)) {
 294         while (view.TrySlide(0, 1)) {
 295           if (p(view.First))
 296             return view.Offset;
 297           view.Slide(+1, 0);
 298         }
 299       }
 300       return -1;
 301     }
 302
 303     // Find the index of the last item that satisfies p
 304
 305     public static int FindLastIndex<T>(IList<T> list, Fun<T,bool> p) {
 306       using (IList<T> view = list.View(list.Count, 0)) {
 307         while (view.TrySlide(-1, 1)) {
 308           if (p(view.First))
 309             return view.Offset;
 310         }
 311       }
 312       return -1;
 313     }
 314
 315     // Yield indexes of all items equal to x, in list order:
 316
 317     public static SCG.IEnumerable<int> IndexesOf<T>(IList<T> list, T x) {
 318       IList<T> tail = list.View(0, list.Count);
 319       tail = tail.ViewOf(x);
 320       while (tail != null) {
 321         yield return tail.Offset;
 322         tail = tail.Slide(+1,0).Span(list);
 323         tail = tail.ViewOf(x);
 324       }
 325     }
 326
 327     // Yield indexes of items equal to x, in reverse list order.
 328
 329     public static SCG.IEnumerable<int> ReverseIndexesOf<T>(IList<T> list, T x) {
 330       IList<T> head = list.View(0, list.Count);
 331       head = head.LastViewOf(x);
 332       while (head != null) {
 333         yield return head.Offset;
 334         head = list.Span(head.Slide(0,0));
 335         head = head.LastViewOf(x);
 336       }
 337     }
 338
 339   }
 340 }