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 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.
  19 module pipeline
  20
  21 redef interface Iterator[E]
  22         # Filter: sort with `default_comparator`.
  23         # SEE: `sort_with` for details
  24         # REQUIRE: self isa Iterator[Comparable]
  25         #
  26         #     assert [1,3,2].iterator.sort.to_a      ==  [1,2,3]
  27         fun sort: Iterator[E]
  28         do
  29                 assert self isa Iterator[Comparable]
  30                 var a = self.to_a
  31                 default_comparator.sort(a)
  32                 return a.iterator
  33         end
  34
  35         # Filter: sort with a given `comparator`.
  36         # Important: require O(n) memory.
  37         #
  38         #    assert ["a", "c", "b"].iterator.sort_with(alpha_comparator).to_a  == ["a", "b", "c"]
  39         fun sort_with(comparator: Comparator): Iterator[E]
  40         do
  41                 var a = self.to_a
  42                 comparator.sort(a)
  43                 return a.iterator
  44         end
  45
  46         # Filter: reject duplicates.
  47         # Elements already seen are rejected.
  48         #
  49         # Important: rely on `==` and `hash`
  50         # Important: require O(m) in memory, where m is the total number of uniq items.
  51         #
  52         #     assert [1,2,1,1,1,3,2].iterator.uniq.to_a      ==  [1,2,3]
  53         #
  54         # REQUIRE: self isa Iterator[Object]
  55         fun uniq: Iterator[E]
  56         do
  57                 assert self isa Iterator[Object]
  58                 return new PipeUniq[E](self)
  59         end
  60
  61         # Filter: reject continuous sequences of duplicates
  62         #
  63         # Important: rely on `==`.
  64         #
  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]
  67         do
  68                 return new PipeSeqUniq[E](self)
  69         end
  70
  71         # Combine two iterators.
  72         #
  73         # When the first iterator is terminated, the second is started.
  74         #
  75         #     assert ([1..20[.iterator + [20..40[.iterator).to_a             ==  ([1..40[).to_a
  76         fun +(other: Iterator[E]): Iterator[E]
  77         do
  78                 return new PipeJoin[E](self, other)
  79         end
  80
  81         # Alternate each item with `e`.
  82         #
  83         #    assert [1,2,3].iterator.alternate(0).to_a               ==  [1,0,2,0,3]
  84         fun alternate(e: E): Iterator[E]
  85         do
  86                 return new PipeAlternate[E](self, e)
  87         end
  88
  89         # Filter: reject a given `item`.
  90         #
  91         #    assert [1,1,2,1,3].iterator.skip(1).to_a                ==  [2,3]
  92         fun skip(item: E): Iterator[E]
  93         do
  94                 return new PipeSkip[E](self, item)
  95         end
  96
  97         # Filter: keep only the first `length` items.
  98         #
  99         # This filter does not always consume `self'.
 100         #
 101         #     var i = [1,2,3,4,5].iterator
 102         #     assert i.head(2).to_a   == [1,2]
 103         #     assert i.to_a           == [3,4,5]
 104         fun head(length: Int): Iterator[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].iterator.skip_head(2).to_a          ==  [3,4,5]
 112         #
 113         # ENSURE: self == return
 114         fun skip_head(length: Int): Iterator[E]
 115         do
 116                 while length > 0 and self.is_ok do
 117                         length -= 1
 118                         self.next
 119                 end
 120                 return self
 121         end
 122
 123         # Filter: keep only the last `length` items.
 124         #
 125         #     assert [1,2,3,4,5].iterator.tail(2).to_a       ==  [4,5]
 126         #
 127         # Important: require O(length) in memory
 128         fun tail(length: Int): Iterator[E]
 129         do
 130                 var lasts = new List[E]
 131                 while self.is_ok do
 132                         while lasts.length >= length do lasts.shift
 133                         lasts.push(self.item)
 134                         self.next
 135                 end
 136                 return lasts.iterator
 137         end
 138
 139         # Filter: reject the last `length` items.
 140         #
 141         #     assert [1,2,3,4,5].iterator.skip_tail(2).to_a          ==  [1,2,3]
 142         #
 143         # Important: require O(length) in memory
 144         fun skip_tail(length: Int): Iterator[E]
 145         do
 146                 return new PipeSkipTail[E](self, length)
 147         end
 148
 149         # Filter: reject items that does not meet some criteria.
 150         #
 151         #     class IsEvenFunction
 152         #       super Function[Int, Bool]
 153         #       redef fun apply(i) do return i % 2 == 0
 154         #     end
 155         #     assert [1,2,3,4,8].iterator.select(new IsEvenFunction).to_a  == [2,4,8]
 156         fun select(predicate: Function[E, Bool]): Iterator[E]
 157         do
 158                 return new PipeSelect[E](self, predicate)
 159         end
 160 end
 161
 162 # Wraps an iterator to skip nulls.
 163 #
 164 # ~~~nit
 165 # var i: Iterator[Int]
 166 #
 167 # i = new NullSkipper[Int]([null, 1, null, 2, null: nullable Int].iterator)
 168 # assert i.to_a == [1, 2]
 169 #
 170 # i = new NullSkipper[Int]([1, null, 2, 3: nullable Int].iterator)
 171 # assert i.to_a == [1, 2, 3]
 172 # ~~~
 173 class NullSkipper[E: Object]
 174         super Iterator[E]
 175
 176         # The inner iterator.
 177         var inner: Iterator[nullable E]
 178
 179         redef fun finish do inner.finish
 180
 181         redef fun is_ok do
 182                 skip_nulls
 183                 return inner.is_ok
 184         end
 185
 186         redef fun item do
 187                 skip_nulls
 188                 return inner.item.as(E)
 189         end
 190
 191         redef fun next do
 192                 inner.next
 193                 skip_nulls
 194         end
 195
 196         private fun skip_nulls do
 197                 while inner.is_ok and inner.item == null do inner.next
 198         end
 199 end
 200
 201 # Interface that reify a function.
 202 # Concrete subclasses must implements the `apply` method.
 203 #
 204 # This interface helps to manipulate function-like objects.
 205 #
 206 # The main usage it as a transformation; that takes an argument and produce a result.
 207 # See `map` for example.
 208 #
 209 # Another usage is as a predicate, with `Function[E, Bool]`.
 210 # See `Iterator::select` for example.
 211 #
 212 # Function with more than one argument can be reified with some uncurification.
 213 # Eg. `Function[ARG1, Function[ARG2, RES]]`.
 214 #
 215 # NOTE: Nit is not a functionnal language, this class is a very basic way to
 216 # simulate the reification of a simple function.
 217 interface Function[FROM, TO]
 218         # How an element is mapped to another one.
 219         fun apply(e: FROM): TO is abstract
 220
 221         # Filter: produce an iterator which each element is transformed.
 222         #
 223         #     var i = [1,2,3].iterator
 224         #     assert fun_to_s.map(i).to_a  == ["1", "2", "3"]
 225         #
 226         # Note: because there is no generic method in Nit (yet?),
 227         # there is no way to have a better API.
 228         # eg. with the Iterator as receiver and the function as argument.
 229         # (see `Iterator::select`)
 230         fun map(i: Iterator[FROM]): Iterator[TO]
 231         do
 232                 return new PipeMap[FROM, TO](i, self)
 233         end
 234 end
 235
 236 private class FunctionToS
 237         super Function[Object, String]
 238         redef fun apply(e) do return e.to_s
 239 end
 240
 241 ### Specific private iterator classes
 242
 243 private class PipeUniq[E]
 244         super Iterator[E]
 245
 246         var source: Iterator[E]
 247
 248         var seen = new HashSet[Object] # FIXME HashSet[E]
 249
 250         redef fun is_ok do return source.is_ok
 251
 252         redef fun item do return source.item
 253
 254         redef fun next
 255         do
 256                 self.seen.add(self.item.as(Object))
 257                 source.next
 258                 while source.is_ok and self.seen.has(source.item.as(Object)) do
 259                         source.next
 260                 end
 261         end
 262 end
 263
 264 private class PipeSeqUniq[E]
 265         super Iterator[E]
 266
 267         var source: Iterator[E]
 268
 269         redef fun is_ok do return source.is_ok
 270
 271         redef fun item do return source.item
 272
 273         redef fun next
 274         do
 275                 var seen = self.item
 276                 source.next
 277                 while source.is_ok and seen == source.item do
 278                         source.next
 279                 end
 280         end
 281 end
 282
 283 private class PipeJoin[E]
 284         super Iterator[E]
 285         var source1: Iterator[E]
 286         var source2: Iterator[E]
 287
 288         redef fun is_ok
 289         do
 290                 return source1.is_ok or source2.is_ok
 291         end
 292
 293         redef fun item
 294         do
 295                 if source1.is_ok then return source1.item else return source2.item
 296         end
 297
 298         redef fun next
 299         do
 300                 if source1.is_ok then source1.next else source2.next
 301         end
 302 end
 303
 304 private class PipeAlternate[E]
 305         super Iterator[E]
 306
 307         var source: Iterator[E]
 308         var odd_item: E
 309         var odd = true
 310
 311         redef fun is_ok do return source.is_ok
 312
 313         redef fun item
 314         do
 315                 if odd then
 316                         return source.item
 317                 else
 318                         return odd_item
 319                 end
 320         end
 321
 322         redef fun next
 323         do
 324                 if odd then
 325                         source.next
 326                 end
 327                 odd = not odd
 328         end
 329 end
 330
 331 private class PipeSkip[E]
 332         super Iterator[E]
 333
 334         var source: Iterator[E]
 335         var skip_item: E
 336
 337         init do do_skip
 338
 339         fun do_skip
 340         do
 341                 while source.is_ok and source.item == skip_item do source.next
 342         end
 343
 344         redef fun is_ok do return source.is_ok
 345
 346         redef fun item do return source.item
 347
 348         redef fun next
 349         do
 350                 source.next
 351                 do_skip
 352         end
 353 end
 354
 355 private class PipeHead[E]
 356         super Iterator[E]
 357
 358         var source: Iterator[E]
 359
 360         var length: Int
 361
 362         redef fun is_ok do return length > 0 and source.is_ok
 363
 364         redef fun item do return source.item
 365
 366         redef fun next
 367         do
 368                 length -= 1
 369                 source.next
 370         end
 371 end
 372
 373 private class PipeSkipTail[E]
 374         super Iterator[E]
 375
 376         var source: Iterator[E]
 377
 378         var length: Int
 379
 380         var lasts = new List[E]
 381
 382         init
 383         do
 384                 var lasts = self.lasts
 385                 while source.is_ok and lasts.length < length do
 386                         lasts.push(source.item)
 387                         source.next
 388                 end
 389         end
 390
 391         redef fun is_ok do return source.is_ok
 392
 393         redef fun item do return lasts.first
 394
 395         redef fun next
 396         do
 397                 lasts.shift
 398                 lasts.push(source.item)
 399                 source.next
 400         end
 401 end
 402
 403 private class PipeSelect[E]
 404         super Iterator[E]
 405
 406         var source: Iterator[E]
 407
 408         var predicate: Function[E, Bool]
 409
 410         init do do_skip
 411
 412         fun do_skip
 413         do
 414                 while source.is_ok and not predicate.apply(source.item) do source.next
 415         end
 416
 417         redef fun is_ok do return source.is_ok
 418
 419         redef fun item do return source.item
 420
 421         redef fun next
 422         do
 423                 source.next
 424                 do_skip
 425         end
 426 end
 427
 428 private class PipeMap[E, F]
 429         super Iterator[F]
 430
 431         var source: Iterator[E]
 432         var function: Function[E, F]
 433
 434         var item_cache: nullable F = null
 435         var item_cached = false
 436
 437         redef fun is_ok do return source.is_ok
 438
 439         redef fun item do
 440                 if item_cached then return item_cache
 441                 item_cache = function.apply(source.item)
 442                 item_cached = true
 443                 return item_cache
 444         end
 445
 446         redef fun next do
 447                 source.next
 448                 item_cached = false
 449         end
 450 end
 451
 452 # Stateless singleton that reify to the `to_s` method.
 453 #
 454 #     assert fun_to_s.apply(5)  == "5"
 455 fun fun_to_s: Function[Object, String] do return once new FunctionToS