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
10 The above copyright notice and this permission notice shall be included in
\r
11 all copies or substantial portions of the Software.
\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
22 // C5 example: SortedIterationPatterns.cs for pattern chapter
\r
25 // csc /r:C5.dll SortedIterationPatterns.cs
\r
29 using SCG = System.Collections.Generic;
\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
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
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
62 // --- Predecessor and successor patterns --------------------
\r
64 // Find weak successor of y in coll, or return false
\r
66 public static bool WeakSuccessor<T>(ISorted<T> coll, T y, out T ySucc)
\r
67 where T : IComparable<T>
\r
70 bool hasPred, hasSucc,
\r
71 hasY = coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);
\r
74 return hasY || hasSucc;
\r
77 // Find weak predecessor of y in coll, or return false
\r
79 public static bool WeakPredecessor<T>(ISorted<T> coll, T y, out T yPred)
\r
80 where T : IComparable<T>
\r
83 bool hasPred, hasSucc,
\r
84 hasY = coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);
\r
87 return hasY || hasPred;
\r
90 // Find (strict) successor of y in coll, or return false
\r
92 public static bool Successor<T>(ISorted<T> coll, T y, out T ySucc)
\r
93 where T : IComparable<T>
\r
95 bool hasPred, hasSucc;
\r
97 coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);
\r
101 // Find (strict) predecessor of y in coll, or return false
\r
103 public static bool Predecessor<T>(ISorted<T> coll, T y, out T yPred)
\r
104 where T : IComparable<T>
\r
106 bool hasPred, hasSucc;
\r
108 coll.Cut(y, out yPred, out hasPred, out ySucc, out hasSucc);
\r
112 // --- Sorted iteration patterns -----------------------------
\r
114 // Iterate over all items
\r
116 public static void IterBeginEnd<T>(ISorted<T> coll) {
\r
117 foreach (T x in coll) {
\r
118 Console.Write("{0} ", x);
\r
120 Console.WriteLine();
\r
123 // Iterate over all items, backwards
\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
129 Console.WriteLine();
\r
132 // Iterate over [x1,x2[
\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
138 Console.WriteLine();
\r
141 // Iterate over [x1,x2[, backwards
\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
147 Console.WriteLine();
\r
150 // Iterate over [x1...]
\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
156 Console.WriteLine();
\r
159 // Iterate over [...x2[
\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
165 Console.WriteLine();
\r
168 // Iterate over [x1...x2]
\r
170 public static void IterIncInc<T>(ISorted<T> coll, T x1, T x2)
\r
171 where T : IComparable<T>
\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
180 Console.WriteLine();
\r
183 // Iterate over [...x2]
\r
185 public static void IterBeginInc<T>(ISorted<T> coll, T x2)
\r
186 where T : IComparable<T>
\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
195 Console.WriteLine();
\r
198 // Iterate over ]x1...x2[
\r
200 public static void IterExcExc<T>(ISorted<T> coll, T x1, T x2)
\r
201 where T : IComparable<T>
\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
210 Console.WriteLine();
\r
213 // Iterate over ]x1...]
\r
215 public static void IterExcEnd<T>(ISorted<T> coll, T x1)
\r
216 where T : IComparable<T>
\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
225 Console.WriteLine();
\r
228 // Iterate over ]x1...x2]
\r
230 public static void IterExcInc<T>(ISorted<T> coll, T x1, T x2)
\r
231 where T : IComparable<T>
\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
243 Console.WriteLine();
\r