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 `Collection`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.
21 # The filters methods return a view bounded on the original collection.
22 # Filters can be chained to build complex virtual collections.
24 # FIXME: Fix vocabulary (lazy/view/filter)
25 # FIXME: Maybe the name of the method should indicate that the method is 'lazy' (or is a filter).
28 redef interface Collection[E
]
29 # Filter: sort with ComparableSorter.
30 # SEE: `sort_with` for details
31 # REQUIRE: self isa Iterator[Comparable]
33 # assert [1,3,2].sort_filter.to_a == [1,2,3]
34 fun sort_filter
: Collection[E
]
36 assert self isa Collection[Comparable]
37 var sorter
= new ComparableSorter[Comparable]
43 # Filter: sort with a given `sorter`.
44 # Important: require O(n) memory.
45 fun sort_with
(sorter
: AbstractSorter[E
]): Collection[E
]
52 # Filter: reject duplicates.
53 # Elements already seen are rejected.
55 # Important: rely on `==` and `hash`
56 # Important: require O(m) in memory, where m is the total number of uniq items.
58 # assert [1,2,1,1,1,3,2].uniq.to_a == [1,2,3]
60 # REQUIRE: self isa Iterator[Object]
61 fun uniq
: Collection[E
]
63 assert self isa Collection[Object]
64 return new PipeUniq[E
](self)
67 # Filter: reject continuous sequences of duplicates
69 # Important: rely on `==`.
71 # assert [1,2,1,1,1,3,2].seq_uniq.to_a == [1,2,1,3,2]
72 fun seq_uniq
: Collection[E
]
74 return new PipeSeqUniq[E
](self)
77 # The view of two combined collections.
79 # assert ([1..20[ + [20..40[).to_a == ([1..40[).to_a
80 fun +(other
: Collection[E
]): Collection[E
]
82 return new PipeJoin[E
](self, other
)
85 # Alternate each item with `e`.
87 # assert [1,2,3].alternate(0).to_a == [1,0,2,0,3]
88 fun alternate
(e
: E
): Collection[E
]
90 return new PipeAlternate[E
](self, e
)
93 # Filter: reject a given `item`.
95 # assert [1,1,2,1,3].skip(1).to_a == [2,3]
96 fun skip
(item
: E
): Collection[E
]
98 return new PipeSkip[E
](self, item
)
101 # Filter: keep only the first `length` items.
103 # assert [1,2,3,4,5].head(2).to_a == [1,2]
104 fun head
(length
: Int): Collection[E
]
106 return new PipeHead[E
](self, length
)
109 # Filter: reject the first `length` items.
111 # assert [1,2,3,4,5].skip_head(2).to_a == [3,4,5]
113 # ENSURE: self == return
114 fun skip_head
(length
: Int): Collection[E
]
116 return new PipeSkipHead[E
](self, length
)
119 # Filter: keep only the last `length` items.
121 # assert [1,2,3,4,5].tail(2).to_a == [4,5]
123 # Important: require O(length) in memory
124 fun tail
(length
: Int): Collection[E
]
126 return new PipeTail[E
](self, length
)
129 # Filter: reject the last `length` items.
131 # assert [1,2,3,4,5].skip_tail(2).to_a == [1,2,3]
133 # Important: require O(length) in memory
134 fun skip_tail
(length
: Int): Collection[E
]
136 return new PipeSkipTail[E
](self, length
)
140 ### Specific private collection and iterator classes
142 private class PipeUniq[E
]
144 var source
: Collection[E
]
145 redef fun iterator
do return new PipeUniqIterator[E
](source
.iterator
)
148 private class PipeUniqIterator[E
]
151 var source
: Iterator[E
]
153 var seen
= new HashSet[Object] # FIXME HashSet[E]
155 redef fun is_ok
do return source
.is_ok
157 redef fun item
do return source
.item
161 self.seen
.add
(self.item
.as(Object))
163 while source
.is_ok
and self.seen
.has
(source
.item
.as(Object)) do
169 private class PipeSeqUniq[E
]
171 var source
: Collection[E
]
172 redef fun iterator
do return new PipeSeqUniqIterator[E
](source
.iterator
)
175 private class PipeSeqUniqIterator[E
]
178 var source
: Iterator[E
]
180 redef fun is_ok
do return source
.is_ok
182 redef fun item
do return source
.item
188 while source
.is_ok
and seen
== source
.item
do
194 private class PipeJoin[E
]
196 var source1
: Collection[E
]
197 var source2
: Collection[E
]
198 redef fun iterator
do return new PipeJoinIterator[E
](source1
.iterator
, source2
.iterator
)
201 private class PipeJoinIterator[E
]
203 var source1
: Iterator[E
]
204 var source2
: Iterator[E
]
208 return source1
.is_ok
or source2
.is_ok
213 if source1
.is_ok
then return source1
.item
else return source2
.item
218 if source1
.is_ok
then source1
.next
else source2
.next
222 private class PipeAlternate[E
]
224 var source
: Collection[E
]
226 redef fun iterator
do return new PipeAlternateIterator[E
](source
.iterator
, odd_item
)
229 private class PipeAlternateIterator[E
]
232 var source
: Iterator[E
]
236 redef fun is_ok
do return source
.is_ok
256 private class PipeSkip[E
]
258 var source
: Collection[E
]
260 redef fun iterator
do return new PipeSkipIterator[E
](source
.iterator
, skip_item
)
263 private class PipeSkipIterator[E
]
267 var source
: Iterator[E
]
270 init(source
: Iterator[E
], skip_item
: E
)
273 self.skip_item
= skip_item
280 while source
.is_ok
and source
.item
== skip_item
do source
.next
283 redef fun is_ok
do return source
.is_ok
285 redef fun item
do return source
.item
294 private class PipeHead[E
]
296 var source
: Collection[E
]
298 redef fun iterator
do return new PipeHeadIterator[E
](source
.iterator
, pipe_length
)
301 private class PipeHeadIterator[E
]
304 var source
: Iterator[E
]
308 redef fun is_ok
do return length
> 0 and source
.is_ok
310 redef fun item
do return source
.item
319 private class PipeSkipHead[E
]
321 var source
: Collection[E
]
325 var res
= source
.iterator
326 var length
= pipe_length
327 while length
> 0 and res
.is_ok
do
335 private class PipeTail[E
]
337 var source
: Collection[E
]
341 var lasts
= new List[E
]
342 var res
= source
.iterator
343 var length
= pipe_length
345 while lasts
.length
>= length
do lasts
.shift
349 return lasts
.iterator
353 private class PipeSkipTail[E
]
355 var source
: Collection[E
]
357 redef fun iterator
do return new PipeSkipTailIterator[E
](source
.iterator
, pipe_length
)
360 private class PipeSkipTailIterator[E
]
363 var source
: Iterator[E
]
367 var lasts
= new List[E
]
369 init(source
: Iterator[E
], length
: Int)
373 var lasts
= self.lasts
374 while source
.is_ok
and lasts
.length
< length
do
375 lasts
.push
(source
.item
)
380 redef fun is_ok
do return source
.is_ok
382 redef fun item
do return lasts
.first
387 lasts
.push
(source
.item
)