1 package frost.collections
2
3 ====================================================================================================
4 Returns a collection of objects one at a time. `Iterator`s are valid `for` loop targets.
5 ====================================================================================================
6 interface Iterator<T> {
7 @private
8 class FilterIterator<T> : Iterator<T> {
9 def base:Iterator<T>
10
11 def filter:(T)=>(Bit)
12
13 var _done:Bit
14
15 var nextValue:T?
16
17 init(base:Iterator<T>, filter:(T)=>(Bit)) {
18 self.base := base
19 self.filter := filter
20 getNext()
21 }
22
23 method getNext() {
24 do {
25 if base.done {
26 _done := true
27 return
28 }
29 nextValue := base.next()
30 }
31 while !filter(nextValue!)
32 }
33
34 @override
35 function get_done():Bit {
36 return _done
37 }
38
39 @override
40 method next():T {
41 def result := nextValue!
42 getNext()
43 return result
44 }
45 }
46
47 @private
48 class RangeIterator<T> : Iterator<T> {
49 def base:Iterator<T>
50
51 var current:Int
52
53 def end:Int?
54
55 def step:Int
56
57 var pending:T?
58
59 var _done := false
60
61 @pre(step > 0)
62 init(base:Iterator<T>, start:Int?, end:Int?, inclusive:Bit, step:Int) {
63 self.base := base
64 if start !== null {
65 for i in 0 .. start {
66 if !base.done {
67 base.next()
68 }
69 }
70 current := start
71 }
72 else {
73 current := 0
74 }
75 if end !== null {
76 if inclusive {
77 self.end := end + 1
78 }
79 else {
80 self.end := end
81 }
82 }
83 self.step := step
84 if !base.done {
85 pending := base.next()
86 }
87 else {
88 _done := true
89 }
90 }
91
92 @override
93 function get_done():Bit {
94 return _done
95 }
96
97 @override
98 method next():T {
99 def result := pending!
100 for i in 0 .. step {
101 current += 1
102 _done := (end !== null & current >= end) | base.done
103 if _done {
104 pending := null
105 break
106 }
107 pending := base.next()
108 }
109 return result
110 }
111 }
112
113 @private
114 class MapIterator<T, U> : Iterator<U> {
115 def base:Iterator<T>
116
117 def map:(T)=&>(U)
118
119 init(base:Iterator<T>, map:(T)=&>(U)) {
120 self.base := base
121 self.map := map
122 }
123
124 @override
125 function get_done():Bit {
126 return base.done
127 }
128
129 @override
130 method next():U {
131 return map(base.next())
132 }
133 }
134
135 @private
136 class EnumerationIterator<T> : Iterator<(Int, T)> {
137 def base:Iterator<T>
138
139 var index := -1
140
141 init(base:Iterator<T>) {
142 self.base := base
143 }
144
145 @override
146 function get_done():Bit {
147 return base.done
148 }
149
150 @override
151 method next():(Int, T) {
152 index += 1
153 return (index, base.next())
154 }
155 }
156
157 ================================================================================================
158 True if this iterator has no more elements to return.
159 ================================================================================================
160 property done:Bit
161
162 ================================================================================================
163 Returns an iterator which reads from this iterator and returns `(index, value)` tuples. For
164 example,
165
166 -- testcase IteratorEnumeration(Simple)
167 for (i, v) in ["A", "B", "C"].iterator.enumeration {
168 Console.printLine("\{i}: \{v}")
169 }
170
171 will display:
172
173 0: A
174 1: B
175 2: C
176 ================================================================================================
177 property enumeration:Iterator<(Int, T)>
178
179 function get_done():Bit
180
181 ================================================================================================
182 Returns the next element from the iterator.
183 ================================================================================================
184 @pre(!done)
185 method next():T
186
187 ================================================================================================
188 Scans through the `Iterator` until the end, returning the number of elements traversed over.
189 ================================================================================================
190 @default
191 @post(get_done())
192 method count():Int {
193 var result := 0
194 while !done {
195 next()
196 result += 1
197 }
198 return result
199 }
200
201 ================================================================================================
202 Returns a new `Iterator` which reads from this `Iterator`, returning `(index, value)` tuples.
203 For example, `["Hello", "Bonjour"].iterator.enumeration` returns an `Iterator<(Int, String)>`
204 which produces `(0, "Hello")` followed by `(1, "Bonjour")`. As the new `Iterator` internally
205 reads from this `Iterator`, you should not interact with an `Iterator` after calling
206 `enumeration` on it.
207 ================================================================================================
208 @default
209 function get_enumeration():Iterator<(Int, T)> {
210 return EnumerationIterator<T>(self)
211 }
212
213 ================================================================================================
214 Returns a new `Iterator` which reads from this `Iterator`, skipping over values which do not
215 match the predicate. As the new `Iterator` internally reads from this `Iterator`, you should not
216 interact with an `Iterator` after calling `filter` on it.
217 ================================================================================================
218 @default
219 function filter(predicate:(T)=>(Bit)):Iterator<T> {
220 return FilterIterator<T>(self, predicate)
221 }
222
223 ================================================================================================
224 Returns an `Iterator` which traverses a subrange of this `Iterator`. As the new `Iterator`
225 internally reads from this `Iterator`, you should not interact with an `Iterator` after calling
226 `range` on it.
227
228 Example:
229
230 -- testcase IteratorRangeIndex
231 base[..10].map(x => x * x)
232
233 This produces an iterator which squares the first ten numbers produced by the base iterator.
234
235 The range iterator will never read past the end of the base iterator. If the base iterator does
236 not produce enough elements to finish the range, iteration will simply end at that point.
237 ================================================================================================
238 @default
239 @pre(range.min == null | range.min! >= 0 & range.max == null | range.max! >= 0)
240 function [](range:Range<Int?>):Iterator<T> {
241 return RangeIterator<T>(self, range.min, range.max, range.inclusive, 1)
242 }
243
244 ================================================================================================
245 As [\[\](Range<Int?>)], but additionally handles a `step`.
246
247 Example:
248
249 -- testcase IteratorSteppedRangeIndex
250 for v in arr.iterator[1.. by 2] {
251 Console.printLine(v)
252 }
253
254 This will loop over every odd-numbered element in `arr`.
255 ================================================================================================
256 @default
257 @pre(range.start == null | range.start! >= 0 & range.end == null |
258 range.end! >= 0 & range.step > 0)
259 function [](range:SteppedRange<Int?, Int>):Iterator<T> {
260 return RangeIterator<T>(self, range.start, range.end, range.inclusive, range.step)
261 }
262
263 ================================================================================================
264 Scans through the `Iterator` until the end, collecting all of the traversed elements into an
265 `Array`.
266 ================================================================================================
267 @default
268 @post(done)
269 method all():Array<T> {
270 def result := Array<T>()
271 for v in self {
272 result.add(v)
273 }
274 return result
275 }
276
277 ================================================================================================
278 Scans through the `Iterator` until the end, calling the specified method on each object
279 returned.
280
281 For example, to call a method named `process` on each word in a string:
282
283 -- testcase IteratorApply(StringProcess)
284 def words := "This will do something with the words in this string".find(/\w+/)
285 words.map(m => m.groups[0]).apply(process)
286 ================================================================================================
287 @default
288 @post(done)
289 method apply(m:(T)=&>()) {
290 for v in self {
291 m(v)
292 }
293 }
294
295 ================================================================================================
296 Successively applies a binary function to 'fold' the elements returned by the iterator down to a
297 single value. For instance, if we have an `Iterator<Int64>` and fold it using the binary
298 function [Int64.+(Int64)], as in:
299
300 -- testcase IteratorFold
301 iter.fold(Int.+)
302
303 this would add the first and second elements returned by the iterator together, and
304 then add the sum of the first two elements to the third, and so forth until all of the elements
305 had been added together.
306
307 Similarly, we could fold using [Int64.max(Int64)] to find the biggest number returned by the
308 iterator, [Int64.*(Int64)] to get the product of all of the numbers returned by the iterator,
309 etc.
310
311 If the iterator returns only a single element, the result of `fold` is this single element and
312 the function `f` is never called. This variant of `fold` may not be called on an iterator with
313 no remaining elements because the result would be undefined. After calling `fold`, there will be
314 no more elements remaining.
315
316 @param f a binary function to combine elements of the iterator
317 @returns the result of combining all elements from the iterator
318 @see fold((T, T)=>(T), T)
319 ================================================================================================
320 @default
321 @pre(!done)
322 @post(done)
323 method fold(f:(T, T)=>(T)):T {
324 var result := next()
325 while !done {
326 result := f(result, next())
327 }
328 return result
329 }
330
331 ================================================================================================
332 As [fold((T, T)=>(T))], but additionally takes a starting value for the fold operation. The
333 starting value is folded into the first element, the result is then folded into the second
334 element, etc. This allows `fold` to be well-defined even on an empty iterator: folding an empty
335 iterator simply returns the start value.
336
337 @param f a binary function to combine elements of the iterator
338 @param start the starting value for the fold
339 @returns the result of combining all elements from the iterator
340 @see fold((T, T)=>(T))
341 ================================================================================================
342 @default
343 @post(done)
344 method fold(f:(T, T)=>(T), start:T):T {
345 var result := start
346 while !done {
347 result := f(result, next())
348 }
349 return result
350 }
351
352 ================================================================================================
353 Returns a new iterator which reads from this iterator and applies a method to transform the
354 results. For instance,
355
356 File("/tmp/example").lines().map(line => line.length)
357
358 is an iterator which produces the length of each line in a file.
359 ================================================================================================
360 @default
361 method map<U>(f:(T)=&>(U)):Iterator<U> {
362 return MapIterator<T, U>(self, f)
363 }
364 }
365