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 # [1,3,2].sort_filter #=> [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.
46 # REQUIRE: self isa Iterator[Object]
47 # FIXME: AbstractSorter[E] is refused
48 fun sort_with
(sorter
: AbstractSorter[Object]): Collection[E
]
50 assert self isa Collection[Object]
56 # Filter: reject duplicates.
57 # Elements already seen are rejected.
59 # Important: rely on `==` and `hash`
60 # Important: require O(m) in memory, where m is the total number of uniq items.
62 # [1,2,1,1,1,3,2].uniq #=> [1,2,3]
64 # REQUIRE: self isa Iterator[Object]
65 fun uniq
: Collection[E
]
67 assert self isa Collection[Object]
68 return new PipeUniq[E
](self)
71 # Filter: reject continuous sequences of duplicates
73 # Important: rely on `==`.
75 # [1,2,1,1,1,3,2].seq_uniq #=> [1,2,1,3,2]
76 fun seq_uniq
: Collection[E
]
78 return new PipeSeqUniq[E
](self)
81 # The view of two combined collections.
83 # ([1..20[ + [20..40[) #=> [1..40[
84 fun +(other
: Collection[E
]): Collection[E
]
86 return new PipeJoin[E
](self, other
)
89 # Alternate each item with `e`.
91 # [1,2,3].alternate(0) #=> [1,0,2,0,3]
92 fun alternate
(e
: E
): Collection[E
]
94 return new PipeAlternate[E
](self, e
)
97 # Filter: reject a given `item`.
99 # [1,1,2,1,3].skip(1) #=> [2,3]
100 fun skip
(item
: E
): Collection[E
]
102 return new PipeSkip[E
](self, item
)
105 # Filter: keep only the first `length` items.
107 # [1,2,3,4,5].head(2) #=> [1,2]
108 fun head
(length
: Int): Collection[E
]
110 return new PipeHead[E
](self, length
)
113 # Filter: reject the first `length` items.
115 # [1,2,3,4,5].skip_head(2) #=> [3,4,5]
117 # ENSURE: self == return
118 fun skip_head
(length
: Int): Collection[E
]
120 return new PipeSkipHead[E
](self, length
)
123 # Filter: keep only the last `length` items.
125 # [1,2,3,4,5].tail(2) #=> [4,5]
127 # Important: require O(length) in memory
128 fun tail
(length
: Int): Collection[E
]
130 return new PipeTail[E
](self, length
)
133 # Filter: reject the last `length` items.
135 # [1,2,3,4,5].skip_tail(2) #=> [1,2,3]
137 # Important: require O(length) in memory
138 fun skip_tail
(length
: Int): Collection[E
]
140 return new PipeSkipTail[E
](self, length
)
144 ### Specific private collection and iterator classes
146 private class PipeUniq[E
]
147 super NaiveCollection[E
]
148 var source
: Collection[E
]
149 redef fun iterator
do return new PipeUniqIterator[E
](source
.iterator
)
152 private class PipeUniqIterator[E
]
155 var source
: Iterator[E
]
157 var seen
= new HashSet[Object] # FIXME HashSet[E]
159 redef fun is_ok
do return source
.is_ok
161 redef fun item
do return source
.item
165 self.seen
.add
(self.item
.as(Object))
167 while source
.is_ok
and self.seen
.has
(source
.item
.as(Object)) do
173 private class PipeSeqUniq[E
]
174 super NaiveCollection[E
]
175 var source
: Collection[E
]
176 redef fun iterator
do return new PipeSeqUniqIterator[E
](source
.iterator
)
179 private class PipeSeqUniqIterator[E
]
182 var source
: Iterator[E
]
184 redef fun is_ok
do return source
.is_ok
186 redef fun item
do return source
.item
192 while source
.is_ok
and seen
== source
.item
do
198 private class PipeJoin[E
]
199 super NaiveCollection[E
]
200 var source1
: Collection[E
]
201 var source2
: Collection[E
]
202 redef fun iterator
do return new PipeJoinIterator[E
](source1
.iterator
, source2
.iterator
)
205 private class PipeJoinIterator[E
]
207 var source1
: Iterator[E
]
208 var source2
: Iterator[E
]
212 return source1
.is_ok
or source2
.is_ok
217 if source1
.is_ok
then return source1
.item
else return source2
.item
222 if source1
.is_ok
then source1
.next
else source2
.next
226 private class PipeAlternate[E
]
227 super NaiveCollection[E
]
228 var source
: Collection[E
]
230 redef fun iterator
do return new PipeAlternateIterator[E
](source
.iterator
, odd_item
)
233 private class PipeAlternateIterator[E
]
236 var source
: Iterator[E
]
240 redef fun is_ok
do return source
.is_ok
260 private class PipeSkip[E
]
261 super NaiveCollection[E
]
262 var source
: Collection[E
]
264 redef fun iterator
do return new PipeSkipIterator[E
](source
.iterator
, skip_item
)
267 private class PipeSkipIterator[E
]
268 super NaiveCollection[E
]
271 var source
: Iterator[E
]
274 init(source
: Iterator[E
], skip_item
: E
)
277 self.skip_item
= skip_item
284 while source
.is_ok
and source
.item
== skip_item
do source
.next
287 redef fun is_ok
do return source
.is_ok
289 redef fun item
do return source
.item
298 private class PipeHead[E
]
299 super NaiveCollection[E
]
300 var source
: Collection[E
]
302 redef fun iterator
do return new PipeHeadIterator[E
](source
.iterator
, pipe_length
)
305 private class PipeHeadIterator[E
]
308 var source
: Iterator[E
]
312 redef fun is_ok
do return length
> 0 and source
.is_ok
314 redef fun item
do return source
.item
323 private class PipeSkipHead[E
]
324 super NaiveCollection[E
]
325 var source
: Collection[E
]
329 var res
= source
.iterator
330 var length
= pipe_length
331 while length
> 0 and res
.is_ok
do
339 private class PipeTail[E
]
340 super NaiveCollection[E
]
341 var source
: Collection[E
]
345 var lasts
= new List[E
]
346 var res
= source
.iterator
347 var length
= pipe_length
349 while lasts
.length
>= length
do lasts
.shift
353 return lasts
.iterator
357 private class PipeSkipTail[E
]
358 super NaiveCollection[E
]
359 var source
: Collection[E
]
361 redef fun iterator
do return new PipeSkipTailIterator[E
](source
.iterator
, pipe_length
)
364 private class PipeSkipTailIterator[E
]
367 var source
: Iterator[E
]
371 var lasts
= new List[E
]
373 init(source
: Iterator[E
], length
: Int)
377 var lasts
= self.lasts
378 while source
.is_ok
and lasts
.length
< length
do
379 lasts
.push
(source
.item
)
384 redef fun is_ok
do return source
.is_ok
386 redef fun item
do return lasts
.first
391 lasts
.push
(source
.item
)