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

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