1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Pipelined filters and operations on iterators.
17 # This module enhances `Iterator` with some methods that enable a pipeline-like programing.
18 # The processing of elements in a pipeline is done trough connected filters that are implemented with reasonable memory constraints.
21 redef interface Iterator[E
]
22 # Filter: sort with `default_comparator`.
23 # SEE: `sort_with` for details
24 # REQUIRE: self isa Iterator[Comparable]
26 # assert [1,3,2].iterator.sort.to_a == [1,2,3]
29 assert self isa Iterator[Comparable]
31 default_comparator
.sort
(a
)
35 # Filter: sort with a given `comparator`.
36 # Important: require O(n) memory.
38 # assert ["a", "c", "b"].iterator.sort_with(alpha_comparator).to_a == ["a", "b", "c"]
39 fun sort_with
(comparator
: Comparator): Iterator[E
]
46 # Filter: reject duplicates.
47 # Elements already seen are rejected.
49 # Important: rely on `==` and `hash`
50 # Important: require O(m) in memory, where m is the total number of uniq items.
52 # assert [1,2,1,1,1,3,2].iterator.uniq.to_a == [1,2,3]
54 # REQUIRE: self isa Iterator[Object]
57 assert self isa Iterator[Object]
58 return new PipeUniq[E
](self)
61 # Filter: reject continuous sequences of duplicates
63 # Important: rely on `==`.
65 # assert [1,2,1,1,1,3,2].iterator.seq_uniq.to_a == [1,2,1,3,2]
66 fun seq_uniq
: Iterator[E
]
68 return new PipeSeqUniq[E
](self)
71 # Combine two iterators.
73 # When the first iterator is terminated, the second is started.
75 # assert ([1..20[.iterator + [20..40[.iterator).to_a == ([1..40[).to_a
78 fun +(other
: Iterator[E
]): Iterator[E
]
80 return new PipeJoin[E
](self, other
)
83 # Alternate each item with `e`.
85 # assert [1,2,3].iterator.alternate(0).to_a == [1,0,2,0,3]
86 fun alternate
(e
: E
): Iterator[E
]
88 return new PipeAlternate[E
](self, e
)
91 # Filter: reject a given `item`.
93 # assert [1,1,2,1,3].iterator.skip(1).to_a == [2,3]
94 fun skip
(item
: E
): Iterator[E
]
96 return new PipeSkip[E
](self, item
)
99 # Filter: keep only the first `length` items.
101 # This filter does not always consume `self'.
103 # var i = [1,2,3,4,5].iterator
104 # assert i.head(2).to_a == [1,2]
105 # assert i.to_a == [3,4,5]
106 fun head
(length
: Int): Iterator[E
]
108 return new PipeHead[E
](self, length
)
111 # Filter: reject the first `length` items.
113 # assert [1,2,3,4,5].iterator.skip_head(2).to_a == [3,4,5]
115 # ENSURE: self == return
116 fun skip_head
(length
: Int): Iterator[E
]
118 while length
> 0 and self.is_ok
do
125 # Filter: keep only the last `length` items.
127 # assert [1,2,3,4,5].iterator.tail(2).to_a == [4,5]
129 # Important: require O(length) in memory
130 fun tail
(length
: Int): Iterator[E
]
132 var lasts
= new List[E
]
134 while lasts
.length
>= length
do lasts
.shift
135 lasts
.push
(self.item
)
138 return lasts
.iterator
141 # Filter: reject the last `length` items.
143 # assert [1,2,3,4,5].iterator.skip_tail(2).to_a == [1,2,3]
145 # Important: require O(length) in memory
146 fun skip_tail
(length
: Int): Iterator[E
]
148 return new PipeSkipTail[E
](self, length
)
151 # Filter: reject items that does not meet some criteria.
153 # class IsEvenFunction
154 # super Function[Int, Bool]
155 # redef fun apply(i) do return i % 2 == 0
157 # assert [1,2,3,4,8].iterator.select(new IsEvenFunction).to_a == [2,4,8]
158 fun select
(predicate
: Function[E
, Bool]): Iterator[E
]
160 return new PipeSelect[E
](self, predicate
)
164 # Concatenates a sequence of iterators.
166 # Wraps an iterator of sub-iterators and iterates over the elements of the
170 # var i: Iterator[Int]
171 # var empty = new Array[Int]
173 # i = new Iterator2[Int]([
174 # [1, 2, 3].iterator,
178 # assert i.to_a == [1, 2, 3, 4, 5]
180 # i = new Iterator2[Int]([
185 # assert i.to_a == [42]
192 # The inner iterator over sub-iterators.
193 var inner
: Iterator[Iterator[E
]]
197 var i
= current_iterator
198 if i
!= null then i
.finish
203 var i
= current_iterator
204 if i
== null then return false
210 var i
= current_iterator
217 var i
= current_iterator
224 var i
= current_iterator
225 if i
!= null then i
.start
228 private var previous_iterator
: nullable Iterator[E
] = null
230 private fun current_iterator
: nullable Iterator[E
]
232 if previous_iterator
== null then
233 # Get the first sub-iterator.
235 previous_iterator
= inner
.item
236 previous_iterator
.start
242 # Get the first sub-iterator that has a current item.
243 while inner
.is_ok
and not previous_iterator
.is_ok
do
244 previous_iterator
.finish
245 previous_iterator
= inner
.item
246 previous_iterator
.start
249 return previous_iterator
253 # Wraps an iterator to skip nulls.
256 # var i: Iterator[Int]
258 # i = new NullSkipper[Int]([null, 1, null, 2, null: nullable Int].iterator)
259 # assert i.to_a == [1, 2]
261 # i = new NullSkipper[Int]([1, null, 2, 3: nullable Int].iterator)
262 # assert i.to_a == [1, 2, 3]
264 class NullSkipper[E
: Object]
267 # The inner iterator.
268 var inner
: Iterator[nullable E
]
270 redef fun finish
do inner
.finish
279 return inner
.item
.as(E
)
287 private fun skip_nulls
do
288 while inner
.is_ok
and inner
.item
== null do inner
.next
292 # Interface that reify a function.
293 # Concrete subclasses must implements the `apply` method.
295 # This interface helps to manipulate function-like objects.
297 # The main usage it as a transformation; that takes an argument and produce a result.
298 # See `map` for example.
300 # Another usage is as a predicate, with `Function[E, Bool]`.
301 # See `Iterator::select` for example.
303 # Function with more than one argument can be reified with some uncurification.
304 # Eg. `Function[ARG1, Function[ARG2, RES]]`.
306 # NOTE: Nit is not a functionnal language, this class is a very basic way to
307 # simulate the reification of a simple function.
308 interface Function[FROM, TO]
309 # How an element is mapped to another one.
310 fun apply
(e
: FROM): TO is abstract
312 # Filter: produce an iterator which each element is transformed.
314 # var i = [1,2,3].iterator
315 # assert fun_to_s.map(i).to_a == ["1", "2", "3"]
317 # Note: because there is no generic method in Nit (yet?),
318 # there is no way to have a better API.
319 # eg. with the Iterator as receiver and the function as argument.
320 # (see `Iterator::select`)
321 fun map
(i
: Iterator[FROM]): Iterator[TO]
323 return new PipeMap[FROM, TO](i
, self)
327 private class FunctionToS
328 super Function[Object, String]
329 redef fun apply
(e
) do return e
.to_s
332 ### Specific private iterator classes
334 private class PipeUniq[E
]
337 var source
: Iterator[E
]
339 var seen
= new HashSet[Object] # FIXME HashSet[E]
341 redef fun is_ok
do return source
.is_ok
343 redef fun item
do return source
.item
347 self.seen
.add
(self.item
.as(Object))
349 while source
.is_ok
and self.seen
.has
(source
.item
.as(Object)) do
355 private class PipeSeqUniq[E
]
358 var source
: Iterator[E
]
360 redef fun is_ok
do return source
.is_ok
362 redef fun item
do return source
.item
368 while source
.is_ok
and seen
== source
.item
do
374 private class PipeJoin[E
]
376 var source1
: Iterator[E
]
377 var source2
: Iterator[E
]
381 return source1
.is_ok
or source2
.is_ok
386 if source1
.is_ok
then return source1
.item
else return source2
.item
391 if source1
.is_ok
then source1
.next
else source2
.next
395 private class PipeAlternate[E
]
398 var source
: Iterator[E
]
402 redef fun is_ok
do return source
.is_ok
422 private class PipeSkip[E
]
425 var source
: Iterator[E
]
432 while source
.is_ok
and source
.item
== skip_item
do source
.next
435 redef fun is_ok
do return source
.is_ok
437 redef fun item
do return source
.item
446 private class PipeHead[E
]
449 var source
: Iterator[E
]
453 redef fun is_ok
do return length
> 0 and source
.is_ok
455 redef fun item
do return source
.item
464 private class PipeSkipTail[E
]
467 var source
: Iterator[E
]
471 var lasts
= new List[E
]
475 var lasts
= self.lasts
476 while source
.is_ok
and lasts
.length
< length
do
477 lasts
.push
(source
.item
)
482 redef fun is_ok
do return source
.is_ok
484 redef fun item
do return lasts
.first
489 lasts
.push
(source
.item
)
494 private class PipeSelect[E
]
497 var source
: Iterator[E
]
499 var predicate
: Function[E
, Bool]
505 while source
.is_ok
and not predicate
.apply
(source
.item
) do source
.next
508 redef fun is_ok
do return source
.is_ok
510 redef fun item
do return source
.item
519 private class PipeMap[E
, F
]
522 var source
: Iterator[E
]
523 var function
: Function[E
, F
]
525 var item_cache
: nullable F
= null
526 var item_cached
= false
528 redef fun is_ok
do return source
.is_ok
531 if item_cached
then return item_cache
532 item_cache
= function
.apply
(source
.item
)
543 # Stateless singleton that reify to the `to_s` method.
545 # assert fun_to_s.apply(5) == "5"
546 fun fun_to_s
: Function[Object, String] do return once
new FunctionToS