mcs/class/Mono.C5/UserGuideExamples/SortedIterationPatterns.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: SortedIterationPatterns.cs for pattern chapter\r
  23 \r
  24 // Compile with \r
  25 //   csc /r:C5.dll SortedIterationPatterns.cs \r
  26 \r
  27 using System;\r
  28 using C5;\r
  29 using SCG = System.Collections.Generic;\r
  30 \r
  31 namespace SortedIterationPatterns {\r
  32   class SortedIterationPatterns {\r
  33     public static void Main(String[] args) {\r
  34       ISorted<int> sorted = new TreeSet<int>();\r
  35       sorted.AddAll(new int[] { 23, 29, 31, 37, 41, 43, 47, 53 });\r
  36       Console.WriteLine(sorted);\r
  37       if (args.Length == 1) { \r
  38         int n = int.Parse(args[0]);\r
  39         int res;\r
  40         if (Predecessor(sorted, n, out res))\r
  41           Console.WriteLine("{0} has predecessor {1}", n, res);\r
  42         if (WeakPredecessor(sorted, n, out res))\r
  43           Console.WriteLine("{0} has weak predecessor {1}", n, res);\r
  44         if (Successor(sorted, n, out res))\r
  45           Console.WriteLine("{0} has successor {1}", n, res);\r
  46         if (WeakSuccessor(sorted, n, out res))\r
  47           Console.WriteLine("{0} has weak successor {1}", n, res);\r
  48       }\r
  49       IterBeginEnd(sorted);\r
  50       IterBeginEndBackwards(sorted);\r
  51       IterIncExc(sorted, 29, 47);\r
  52       IterIncExcBackwards(sorted, 29, 47);\r
  53       IterIncEnd(sorted, 29);\r
  54       IterBeginExc(sorted, 47);\r
  55       IterIncInc(sorted, 29, 47);\r
  56       IterBeginInc(sorted, 47);\r
  57       IterExcExc(sorted, 29, 47);\r
  58       IterExcEnd(sorted, 29);\r
  59       IterExcInc(sorted, 29, 47);\r
  60     }\r
  61 \r
  62     // --- Predecessor and successor patterns --------------------\r
  63 \r
  64     // Find weak successor of y in coll, or return false\r
  65 \r
  66     public static bool WeakSuccessor<T>(ISorted<T> coll, T y, out T ySucc) \r
  67       where T : IComparable<T>\r
  68     {\r
  69       T yPred;\r
  70       bool hasPred, hasSucc, \r
  71         hasY = coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);\r
  72       if (hasY)\r
  73         ySucc = y;\r
  74       return hasY || hasSucc;\r
  75     }\r
  76 \r
  77     // Find weak predecessor of y in coll, or return false\r
  78 \r
  79     public static bool WeakPredecessor<T>(ISorted<T> coll, T y, out T yPred) \r
  80       where T : IComparable<T>\r
  81     {\r
  82       T ySucc;\r
  83       bool hasPred, hasSucc, \r
  84         hasY = coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);\r
  85       if (hasY) \r
  86         yPred = y;\r
  87       return hasY || hasPred;\r
  88     }\r
  89 \r
  90     // Find (strict) successor of y in coll, or return false\r
  91 \r
  92     public static bool Successor<T>(ISorted<T> coll, T y, out T ySucc) \r
  93       where T : IComparable<T>\r
  94     {\r
  95       bool hasPred, hasSucc;\r
  96       T yPred;\r
  97       coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);\r
  98       return hasSucc;\r
  99     }\r
 100 \r
 101     // Find (strict) predecessor of y in coll, or return false\r
 102 \r
 103     public static bool Predecessor<T>(ISorted<T> coll, T y, out T yPred) \r
 104       where T : IComparable<T>\r
 105     {\r
 106       bool hasPred, hasSucc;\r
 107       T ySucc;\r
 108       coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);\r
 109       return hasPred;\r
 110     }\r
 111 \r
 112     // --- Sorted iteration patterns -----------------------------\r
 113 \r
 114     // Iterate over all items\r
 115     \r
 116     public static void IterBeginEnd<T>(ISorted<T> coll) {\r
 117       foreach (T x in coll) { \r
 118         Console.Write("{0} ", x);\r
 119       }\r
 120       Console.WriteLine();\r
 121     }\r
 122 \r
 123     // Iterate over all items, backwards\r
 124     \r
 125     public static void IterBeginEndBackwards<T>(ISorted<T> coll) {\r
 126       foreach (T x in coll.Backwards()) { \r
 127         Console.Write("{0} ", x);\r
 128       }\r
 129       Console.WriteLine();\r
 130     }\r
 131 \r
 132     // Iterate over [x1,x2[\r
 133     \r
 134     public static void IterIncExc<T>(ISorted<T> coll, T x1, T x2) {\r
 135       foreach (T x in coll.RangeFromTo(x1, x2)) { \r
 136         Console.Write("{0} ", x);\r
 137       }\r
 138       Console.WriteLine();\r
 139     }\r
 140 \r
 141     // Iterate over [x1,x2[, backwards\r
 142     \r
 143     public static void IterIncExcBackwards<T>(ISorted<T> coll, T x1, T x2) {\r
 144       foreach (T x in coll.RangeFromTo(x1, x2).Backwards()) { \r
 145         Console.Write("{0} ", x);\r
 146       }\r
 147       Console.WriteLine();\r
 148     }\r
 149 \r
 150     // Iterate over [x1...]\r
 151     \r
 152     public static void IterIncEnd<T>(ISorted<T> coll, T x1) {\r
 153       foreach (T x in coll.RangeFrom(x1)) { \r
 154         Console.Write("{0} ", x);\r
 155       }\r
 156       Console.WriteLine();\r
 157     }\r
 158 \r
 159     // Iterate over [...x2[\r
 160     \r
 161     public static void IterBeginExc<T>(ISorted<T> coll, T x2) {\r
 162       foreach (T x in coll.RangeTo(x2)) { \r
 163         Console.Write("{0} ", x);\r
 164       }\r
 165       Console.WriteLine();\r
 166     }\r
 167 \r
 168     // Iterate over [x1...x2]\r
 169     \r
 170     public static void IterIncInc<T>(ISorted<T> coll, T x1, T x2) \r
 171       where T : IComparable<T>\r
 172     {\r
 173       T x2Succ; \r
 174       bool x2HasSucc = Successor(coll, x2, out x2Succ);\r
 175       IDirectedEnumerable<T> range = \r
 176         x2HasSucc ? coll.RangeFromTo(x1, x2Succ) : coll.RangeFrom(x1);\r
 177       foreach (T x in range) {\r
 178         Console.Write("{0} ", x);\r
 179       } \r
 180       Console.WriteLine();\r
 181     }\r
 182 \r
 183     // Iterate over [...x2]\r
 184     \r
 185     public static void IterBeginInc<T>(ISorted<T> coll, T x2) \r
 186       where T : IComparable<T>\r
 187     {\r
 188       T x2Succ; \r
 189       bool x2HasSucc = Successor(coll, x2, out x2Succ);\r
 190       IDirectedEnumerable<T> range = \r
 191         x2HasSucc ? coll.RangeTo(x2Succ) : coll.RangeAll();\r
 192       foreach (T x in range) {\r
 193         Console.Write("{0} ", x);\r
 194       } \r
 195       Console.WriteLine();\r
 196     }\r
 197 \r
 198     // Iterate over ]x1...x2[\r
 199     \r
 200     public static void IterExcExc<T>(ISorted<T> coll, T x1, T x2)\r
 201       where T : IComparable<T>\r
 202     {\r
 203       T x1Succ;\r
 204       bool x1HasSucc = Successor(coll, x1, out x1Succ);\r
 205       IDirectedEnumerable<T> range = \r
 206         x1HasSucc ? coll.RangeFromTo(x1Succ, x2) : new ArrayList<T>();\r
 207       foreach (T x in range) {\r
 208         Console.Write("{0} ", x);\r
 209       } \r
 210       Console.WriteLine();\r
 211     }\r
 212 \r
 213     // Iterate over ]x1...]\r
 214     \r
 215     public static void IterExcEnd<T>(ISorted<T> coll, T x1) \r
 216       where T : IComparable<T>\r
 217     {\r
 218       T x1Succ;\r
 219       bool x1HasSucc = Successor(coll, x1, out x1Succ);\r
 220       IDirectedEnumerable<T> range = \r
 221         x1HasSucc ? coll.RangeFrom(x1Succ) : new ArrayList<T>();\r
 222       foreach (T x in range) {\r
 223         Console.Write("{0} ", x);\r
 224       } \r
 225       Console.WriteLine();\r
 226     }\r
 227 \r
 228     // Iterate over ]x1...x2]\r
 229     \r
 230     public static void IterExcInc<T>(ISorted<T> coll, T x1, T x2) \r
 231       where T : IComparable<T>\r
 232     {\r
 233       T x1Succ, x2Succ;\r
 234       bool x1HasSucc = Successor(coll, x1, out x1Succ),\r
 235            x2HasSucc = Successor(coll, x2, out x2Succ);\r
 236       IDirectedEnumerable<T> range = \r
 237         x1HasSucc ? (x2HasSucc ? coll.RangeFromTo(x1Succ, x2Succ) \r
 238                                : coll.RangeFrom(x1Succ))\r
 239                   : new ArrayList<T>();\r
 240       foreach (T x in range) {\r
 241         Console.Write("{0} ", x);\r
 242       } \r
 243       Console.WriteLine();\r
 244     }\r
 245 \r
 246   }\r
 247 }\r