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 enhance `Iterator`s with some methods that enable a
18 # pipeline-like programing that offers the manupulation of
19 # collections trough connected filters with reasonable memory constraints.
22 redef interface Iterator[E
]
23 # Filter: sort with `default_comparator`.
24 # SEE: `sort_with` for details
25 # REQUIRE: self isa Iterator[Comparable]
27 # assert [1,3,2].iterator.sort.to_a == [1,2,3]
30 assert self isa Iterator[Comparable]
32 default_comparator
.sort
(a
)
36 # Filter: sort with a given `comparator`.
37 # Important: require O(n) memory.
38 fun sort_with
(comparator
: Comparator[E
]): Iterator[E
]
45 # Filter: reject duplicates.
46 # Elements already seen are rejected.
48 # Important: rely on `==` and `hash`
49 # Important: require O(m) in memory, where m is the total number of uniq items.
51 # assert [1,2,1,1,1,3,2].iterator.uniq.to_a == [1,2,3]
53 # REQUIRE: self isa Iterator[Object]
56 assert self isa Iterator[Object]
57 return new PipeUniq[E
](self)
60 # Filter: reject continuous sequences of duplicates
62 # Important: rely on `==`.
64 # assert [1,2,1,1,1,3,2].iterator.seq_uniq.to_a == [1,2,1,3,2]
65 fun seq_uniq
: Iterator[E
]
67 return new PipeSeqUniq[E
](self)
70 # Combine two iterators.
72 # When the first iterator is terminated, the second is started.
74 # assert ([1..20[.iterator + [20..40[.iterator).to_a == ([1..40[).to_a
75 fun +(other
: Iterator[E
]): Iterator[E
]
77 return new PipeJoin[E
](self, other
)
80 # Alternate each item with `e`.
82 # assert [1,2,3].iterator.alternate(0).to_a == [1,0,2,0,3]
83 fun alternate
(e
: E
): Iterator[E
]
85 return new PipeAlternate[E
](self, e
)
88 # Filter: reject a given `item`.
90 # assert [1,1,2,1,3].iterator.skip(1).to_a == [2,3]
91 fun skip
(item
: E
): Iterator[E
]
93 return new PipeSkip[E
](self, item
)
96 # Filter: keep only the first `length` items.
98 # This filter does not always consume `self'.
100 # var i = [1,2,3,4,5].iterator
101 # assert i.head(2).to_a == [1,2]
102 # assert i.to_a == [3,4,5]
103 fun head
(length
: Int): Iterator[E
]
105 return new PipeHead[E
](self, length
)
108 # Filter: reject the first `length` items.
110 # assert [1,2,3,4,5].iterator.skip_head(2).to_a == [3,4,5]
112 # ENSURE: self == return
113 fun skip_head
(length
: Int): Iterator[E
]
115 while length
> 0 and self.is_ok
do
122 # Filter: keep only the last `length` items.
124 # assert [1,2,3,4,5].iterator.tail(2).to_a == [4,5]
126 # Important: require O(length) in memory
127 fun tail
(length
: Int): Iterator[E
]
129 var lasts
= new List[E
]
131 while lasts
.length
>= length
do lasts
.shift
132 lasts
.push
(self.item
)
135 return lasts
.iterator
138 # Filter: reject the last `length` items.
140 # assert [1,2,3,4,5].iterator.skip_tail(2).to_a == [1,2,3]
142 # Important: require O(length) in memory
143 fun skip_tail
(length
: Int): Iterator[E
]
145 return new PipeSkipTail[E
](self, length
)
148 # Filter: reject items that does not meet some criteria.
150 # class IsEvenFunction
151 # super Function[Int, Bool]
152 # redef fun apply(i) do return i % 2 == 0
154 # assert [1,2,3,4,8].iterator.select(new IsEvenFunction).to_a == [2,4,8]
155 fun select
(predicate
: Function[E
, Bool]): Iterator[E
]
157 return new PipeSelect[E
](self, predicate
)
161 # Interface that reify a function.
162 # Concrete subclasses must implements the `apply` method.
164 # This interface helps to manipulate function-like objects.
166 # The main usage it as a transformation; that takes an argument and produce a result.
167 # See `map` for example.
169 # Another usage is as a predicate, with `Function[E, Bool]`.
170 # See `Iterator::select` for example.
172 # Function with more than one argument can be reified with some uncurification.
173 # Eg. `Function[ARG1, Function[ARG2, RES]]`.
175 # NOTE: Nit is not a functionnal language, this class is a very basic way to
176 # simulate the reification of a simple function.
177 interface Function[FROM, TO]
178 # How an element is mapped to another one.
179 fun apply
(e
: FROM): TO is abstract
181 # Filter: produce an iterator which each element is transformed.
183 # var i = [1,2,3].iterator
184 # assert fun_to_s.map(i).to_a == ["1", "2", "3"]
186 # Note: because there is no generic method in Nit (yet?),
187 # there is no way to have a better API.
188 # eg. with the Iterator as receiver and the function as argument.
189 # (see `Iterator::select`)
190 fun map
(i
: Iterator[FROM]): Iterator[TO]
192 return new PipeMap[FROM, TO](i
, self)
196 private class FunctionToS
197 super Function[Object, String]
198 redef fun apply
(e
) do return e
.to_s
201 ### Specific private iterator classes
203 private class PipeUniq[E
]
206 var source
: Iterator[E
]
208 var seen
= new HashSet[Object] # FIXME HashSet[E]
210 redef fun is_ok
do return source
.is_ok
212 redef fun item
do return source
.item
216 self.seen
.add
(self.item
.as(Object))
218 while source
.is_ok
and self.seen
.has
(source
.item
.as(Object)) do
224 private class PipeSeqUniq[E
]
227 var source
: Iterator[E
]
229 redef fun is_ok
do return source
.is_ok
231 redef fun item
do return source
.item
237 while source
.is_ok
and seen
== source
.item
do
243 private class PipeJoin[E
]
245 var source1
: Iterator[E
]
246 var source2
: Iterator[E
]
250 return source1
.is_ok
or source2
.is_ok
255 if source1
.is_ok
then return source1
.item
else return source2
.item
260 if source1
.is_ok
then source1
.next
else source2
.next
264 private class PipeAlternate[E
]
267 var source
: Iterator[E
]
271 redef fun is_ok
do return source
.is_ok
291 private class PipeSkip[E
]
294 var source
: Iterator[E
]
301 while source
.is_ok
and source
.item
== skip_item
do source
.next
304 redef fun is_ok
do return source
.is_ok
306 redef fun item
do return source
.item
315 private class PipeHead[E
]
318 var source
: Iterator[E
]
322 redef fun is_ok
do return length
> 0 and source
.is_ok
324 redef fun item
do return source
.item
333 private class PipeSkipTail[E
]
336 var source
: Iterator[E
]
340 var lasts
= new List[E
]
344 var lasts
= self.lasts
345 while source
.is_ok
and lasts
.length
< length
do
346 lasts
.push
(source
.item
)
351 redef fun is_ok
do return source
.is_ok
353 redef fun item
do return lasts
.first
358 lasts
.push
(source
.item
)
363 private class PipeSelect[E
]
366 var source
: Iterator[E
]
368 var predicate
: Function[E
, Bool]
374 while source
.is_ok
and not predicate
.apply
(source
.item
) do source
.next
377 redef fun is_ok
do return source
.is_ok
379 redef fun item
do return source
.item
388 private class PipeMap[E
, F
]
391 var source
: Iterator[E
]
392 var function
: Function[E
, F
]
394 var item_cache
: nullable F
= null
395 var item_cached
= false
397 redef fun is_ok
do return source
.is_ok
400 if item_cached
then return item_cache
401 item_cache
= function
.apply
(source
.item
)
412 # Stateless singleton that reify to the `to_s` method.
414 # assert fun_to_s.apply(5) == "5"
415 fun fun_to_s
: Function[Object, String] do return once
new FunctionToS