lib/pipeline.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   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
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   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.
  14
  15 # Pipelined filters and operations on iterators.
  16 #
  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.
  20 #
  21 # The filters methods return a view bounded on the original collection.
  22 # Filters can be chained to build complex virtual collections.
  23 #
  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).
  26 module pipeline
  27
  28 redef interface Collection[E]
  29         # Filter: sort with ComparableSorter.
  30         # SEE: `sort_with` for details
  31         # REQUIRE: self isa Iterator[Comparable]
  32         #
  33         #     assert [1,3,2].sort_filter.to_a        ==  [1,2,3]
  34         fun sort_filter: Collection[E]
  35         do
  36                 assert self isa Collection[Comparable]
  37                 var sorter = new ComparableSorter[Comparable]
  38                 var a = self.to_a
  39                 sorter.sort(a)
  40                 return a
  41         end
  42
  43         # Filter: sort with a given `sorter`.
  44         # Important: require O(n) memory.
  45         fun sort_with(sorter: AbstractSorter[E]): Collection[E]
  46         do
  47                 var a = self.to_a
  48                 sorter.sort(a)
  49                 return a
  50         end
  51
  52         # Filter: reject duplicates.
  53         # Elements already seen are rejected.
  54         #
  55         # Important: rely on `==` and `hash`
  56         # Important: require O(m) in memory, where m is the total number of uniq items.
  57         #
  58         #     assert [1,2,1,1,1,3,2].uniq.to_a       ==  [1,2,3]
  59         #
  60         # REQUIRE: self isa Iterator[Object]
  61         fun uniq: Collection[E]
  62         do
  63                 assert self isa Collection[Object]
  64                 return new PipeUniq[E](self)
  65         end
  66
  67         # Filter: reject continuous sequences of duplicates
  68         #
  69         # Important: rely on `==`.
  70         #
  71         #     assert [1,2,1,1,1,3,2].seq_uniq.to_a           ==  [1,2,1,3,2]
  72         fun seq_uniq: Collection[E]
  73         do
  74                 return new PipeSeqUniq[E](self)
  75         end
  76
  77         # The view of two combined collections.
  78         #
  79         #     assert ([1..20[ + [20..40[).to_a       ==  ([1..40[).to_a
  80         fun +(other: Collection[E]): Collection[E]
  81         do
  82                 return new PipeJoin[E](self, other)
  83         end
  84
  85         # Alternate each item with `e`.
  86         #
  87         #    assert [1,2,3].alternate(0).to_a                ==  [1,0,2,0,3]
  88         fun alternate(e: E): Collection[E]
  89         do
  90                 return new PipeAlternate[E](self, e)
  91         end
  92
  93         # Filter: reject a given `item`.
  94         #
  95         #    assert [1,1,2,1,3].skip(1).to_a                 ==  [2,3]
  96         fun skip(item: E): Collection[E]
  97         do
  98                 return new PipeSkip[E](self, item)
  99         end
 100
 101         # Filter: keep only the first `length` items.
 102         #
 103         #     assert [1,2,3,4,5].head(2).to_a        ==  [1,2]
 104         fun head(length: Int): Collection[E]
 105         do
 106                 return new PipeHead[E](self, length)
 107         end
 108
 109         # Filter: reject the first `length` items.
 110         #
 111         #     assert [1,2,3,4,5].skip_head(2).to_a           ==  [3,4,5]
 112         #
 113         # ENSURE: self == return
 114         fun skip_head(length: Int): Collection[E]
 115         do
 116                 return new PipeSkipHead[E](self, length)
 117         end
 118
 119         # Filter: keep only the last `length` items.
 120         #
 121         #     assert [1,2,3,4,5].tail(2).to_a        ==  [4,5]
 122         #
 123         # Important: require O(length) in memory
 124         fun tail(length: Int): Collection[E]
 125         do
 126                 return new PipeTail[E](self, length)
 127         end
 128
 129         # Filter: reject the last `length` items.
 130         #
 131         #     assert [1,2,3,4,5].skip_tail(2).to_a           ==  [1,2,3]
 132         #
 133         # Important: require O(length) in memory
 134         fun skip_tail(length: Int): Collection[E]
 135         do
 136                 return new PipeSkipTail[E](self, length)
 137         end
 138 end
 139
 140 ### Specific private collection and iterator classes
 141
 142 private class PipeUniq[E]
 143         super Collection[E]
 144         var source: Collection[E]
 145         redef fun iterator do return new PipeUniqIterator[E](source.iterator)
 146 end
 147
 148 private class PipeUniqIterator[E]
 149         super Iterator[E]
 150
 151         var source: Iterator[E]
 152
 153         var seen = new HashSet[Object] # FIXME HashSet[E]
 154
 155         redef fun is_ok do return source.is_ok
 156
 157         redef fun item do return source.item
 158
 159         redef fun next
 160         do
 161                 self.seen.add(self.item.as(Object))
 162                 source.next
 163                 while source.is_ok and self.seen.has(source.item.as(Object)) do
 164                         source.next
 165                 end
 166         end
 167 end
 168
 169 private class PipeSeqUniq[E]
 170         super Collection[E]
 171         var source: Collection[E]
 172         redef fun iterator do return new PipeSeqUniqIterator[E](source.iterator)
 173 end
 174
 175 private class PipeSeqUniqIterator[E]
 176         super Iterator[E]
 177
 178         var source: Iterator[E]
 179
 180         redef fun is_ok do return source.is_ok
 181
 182         redef fun item do return source.item
 183
 184         redef fun next
 185         do
 186                 var seen = self.item
 187                 source.next
 188                 while source.is_ok and seen == source.item do
 189                         source.next
 190                 end
 191         end
 192 end
 193
 194 private class PipeJoin[E]
 195         super Collection[E]
 196         var source1: Collection[E]
 197         var source2: Collection[E]
 198         redef fun iterator do return new PipeJoinIterator[E](source1.iterator, source2.iterator)
 199 end
 200
 201 private class PipeJoinIterator[E]
 202         super Iterator[E]
 203         var source1: Iterator[E]
 204         var source2: Iterator[E]
 205
 206         redef fun is_ok
 207         do
 208                 return source1.is_ok or source2.is_ok
 209         end
 210
 211         redef fun item
 212         do
 213                 if source1.is_ok then return source1.item else return source2.item
 214         end
 215
 216         redef fun next
 217         do
 218                 if source1.is_ok then source1.next else source2.next
 219         end
 220 end
 221
 222 private class PipeAlternate[E]
 223         super Collection[E]
 224         var source: Collection[E]
 225         var odd_item: E
 226         redef fun iterator do return new PipeAlternateIterator[E](source.iterator, odd_item)
 227 end
 228
 229 private class PipeAlternateIterator[E]
 230         super Iterator[E]
 231
 232         var source: Iterator[E]
 233         var odd_item: E
 234         var odd = true
 235
 236         redef fun is_ok do return source.is_ok
 237
 238         redef fun item
 239         do
 240                 if odd then
 241                         return source.item
 242                 else
 243                         return odd_item
 244                 end
 245         end
 246
 247         redef fun next
 248         do
 249                 if odd then
 250                         source.next
 251                 end
 252                 odd = not odd
 253         end
 254 end
 255
 256 private class PipeSkip[E]
 257         super Collection[E]
 258         var source: Collection[E]
 259         var skip_item: E
 260         redef fun iterator do return new PipeSkipIterator[E](source.iterator, skip_item)
 261 end
 262
 263 private class PipeSkipIterator[E]
 264         super Collection[E]
 265         super Iterator[E]
 266
 267         var source: Iterator[E]
 268         var skip_item: E
 269
 270         init(source: Iterator[E], skip_item: E)
 271         do
 272                 self.source = source
 273                 self.skip_item = skip_item
 274
 275                 do_skip
 276         end
 277
 278         fun do_skip
 279         do
 280                 while source.is_ok and source.item == skip_item do source.next
 281         end
 282
 283         redef fun is_ok do return source.is_ok
 284
 285         redef fun item do return source.item
 286
 287         redef fun next
 288         do
 289                 source.next
 290                 do_skip
 291         end
 292 end
 293
 294 private class PipeHead[E]
 295         super Collection[E]
 296         var source: Collection[E]
 297         var pipe_length: Int
 298         redef fun iterator do return new PipeHeadIterator[E](source.iterator, pipe_length)
 299 end
 300
 301 private class PipeHeadIterator[E]
 302         super Iterator[E]
 303
 304         var source: Iterator[E]
 305
 306         var length: Int
 307
 308         redef fun is_ok do return length > 0 and source.is_ok
 309
 310         redef fun item do return source.item
 311
 312         redef fun next
 313         do
 314                 length -= 1
 315                 source.next
 316         end
 317 end
 318
 319 private class PipeSkipHead[E]
 320         super Collection[E]
 321         var source: Collection[E]
 322         var pipe_length: Int
 323         redef fun iterator
 324         do
 325                 var res = source.iterator
 326                 var length = pipe_length
 327                 while length > 0 and res.is_ok do
 328                         length -= 1
 329                         res.next
 330                 end
 331                 return res
 332         end
 333 end
 334
 335 private class PipeTail[E]
 336         super Collection[E]
 337         var source: Collection[E]
 338         var pipe_length: Int
 339         redef fun iterator
 340         do
 341                 var lasts = new List[E]
 342                 var res = source.iterator
 343                 var length = pipe_length
 344                 while res.is_ok do
 345                         while lasts.length >= length do lasts.shift
 346                         lasts.push(res.item)
 347                         res.next
 348                 end
 349                 return lasts.iterator
 350         end
 351 end
 352
 353 private class PipeSkipTail[E]
 354         super Collection[E]
 355         var source: Collection[E]
 356         var pipe_length: Int
 357         redef fun iterator do return new PipeSkipTailIterator[E](source.iterator, pipe_length)
 358 end
 359
 360 private class PipeSkipTailIterator[E]
 361         super Iterator[E]
 362
 363         var source: Iterator[E]
 364
 365         var length: Int
 366
 367         var lasts = new List[E]
 368
 369         init(source: Iterator[E], length: Int)
 370         do
 371                 self.source = source
 372                 self.length = length
 373                 var lasts = self.lasts
 374                 while source.is_ok and lasts.length < length do
 375                         lasts.push(source.item)
 376                         source.next
 377                 end
 378         end
 379
 380         redef fun is_ok do return source.is_ok
 381
 382         redef fun item do return lasts.first
 383
 384         redef fun next
 385         do
 386                 lasts.shift
 387                 lasts.push(source.item)
 388                 source.next
 389         end
 390 end