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