lib/cartesian.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # This file is free software, which comes along with NIT.  This software is
   4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   5 # without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   6 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
   7 # is kept unaltered, and a notification of the changes is added.
   8 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
   9 # another product.
  10
  11 # Cartesian products on heterogeneous collections.
  12 #
  13 # This module is a proof-of-concept to propose memory-efficient views on collections.
  14 #
  15 # This is a specific alternative to `combinations`, that focuses only highly efficient
  16 # Cartesian products between collections of different types.
  17 #
  18 #    Collection[Int] X Collection[String] -> Collection[(Int,String)]
  19 #
  20 # However, in Nit, there in no native *tuple* type.
  21 # So we need a first building block, a pair.
  22
  23 # A simple read-only pair of two elements `e` and `f`.
  24 class Pair[E, F]
  25         # The first element of the pair
  26         var e: E
  27
  28         # The second element of the pair
  29         var f: F
  30
  31         # The parenthesized notation.
  32         #
  33         # ~~~
  34         # var p = new Pair[Int, String](1, "hello")
  35         # assert p.to_s == "(1,hello)"
  36         # ~~~
  37         redef fun to_s
  38         do
  39                 var es = e or else ""
  40                 var fs = f or else ""
  41                 return "({es},{fs})"
  42         end
  43
  44         # Untyped pair equality.
  45         #
  46         # ~~~
  47         # var p1 = new Pair[Object, Object](1, 2)
  48         # var p2 = new Pair[Int, Int](1, 2)
  49         # var p3 = new Pair[Int, Int](1, 3)
  50         #
  51         # assert p1 == p2
  52         # assert p2 != p3
  53         # ~~~
  54         #
  55         # Untyped because we want that `p1 == p2` above.
  56         # So the method just ignores the real types of `E` and `F`.
  57         redef fun ==(o) do return o isa Pair[nullable Object, nullable Object] and e == o.e and f == o.f
  58
  59         redef fun hash do return e.hash * 13 + f.hash * 27 # Magic numbers are magic!
  60 end
  61
  62 # A view of a Cartesian-product collection over two collections.
  63 #
  64 # A Cartesian product over two collections is just a collection of pairs.
  65 # Therefore, this view *contains* all the pairs of elements constructed by associating each
  66 # element of the first collection to each element of the second collection.
  67 #
  68 # However the view is memory-efficient and the pairs are created only when needed.
  69 #
  70 # A simple Cartesian product
  71 # ~~~~
  72 # var c1 = [1,2]
  73 # var c2 = ["a","b","c"]
  74 # var c12 = new Cartesian[Int,String](c1, c2)
  75 # assert c12.length    == 6
  76 # assert c12.join(";") == "(1,a);(1,b);(1,c);(2,a);(2,b);(2,c)" # All the 6 pairs
  77 # ~~~~
  78 #
  79 # Note: because it is a view, changes on the base collections are reflected on the view.
  80 #
  81 # E.g. c12 is a view on c1 and c2, so if c1 changes, then c12 "changes".
  82 # ~~~~
  83 # assert c2.pop        == "c"
  84 # assert c12.length    == 4
  85 # assert c12.join(";") == "(1,a);(1,b);(2,a);(2,b)" # All the 4 remaining pairs
  86 # ~~~~
  87 #
  88 # Cartesian objects are collections, so can be used to build another Cartesian object.
  89 # ~~~~
  90 # var c3 = [1000..2000[
  91 # var c123 = new Cartesian[Pair[Int,String],Int](c12, c3)
  92 # assert c123.length   == 4000
  93 # ~~~~
  94 #
  95 # All methods of Collection are inherited, it is so great!
  96 #
  97 # E.g. search elements?
  98 # ~~~~
  99 # var p12 = new Pair[Int,String](2,"b")
 100 # assert c12.has(p12)      == true
 101 # var p123 = new Pair[Pair[Int, String], Int](p12, 1500)
 102 # var p123bis = new Pair[Pair[Int, String], Int](p12, 0)
 103 # assert c123.has(p123)    == true
 104 # assert c123.has(p123bis) == false
 105 # ~~~~
 106 class Cartesian[E, F]
 107         super Collection[Pair[E,F]]
 108
 109         # The first collection
 110         var ce: Collection[E]
 111
 112         # The second collection
 113         var cf: Collection[F]
 114
 115         redef fun length do return ce.length * cf.length # optional, but so efficient...
 116
 117         redef fun iterator do return new CartesianIterator[E,F](self)
 118
 119         # Returns a new Cartesian where the first collection is the second.
 120         # Because the full collection is virtual, the operation is cheap!
 121         fun swap: Cartesian[F, E] do return new Cartesian[F, E](cf, ce)
 122 end
 123
 124 # An iterator over a `Cartesian`-product collection.
 125 class CartesianIterator[E,F]
 126         super Iterator[Pair[E,F]]
 127
 128         # The associated Cartesian-product collection.
 129         var collection: Cartesian[E,F]
 130
 131         # The iterator over the first collection of the Cartesian product.
 132         # Will be used only once.
 133         private var ice: Iterator[E] is noinit
 134
 135         # The iterator over the second collection of the Cartesian product.
 136         # Will be used once for each element of the first collection.
 137         private var icf: Iterator[F] is noinit
 138
 139         init do
 140                 # Initialize each iterator
 141                 ice = collection.ce.iterator
 142                 icf = collection.cf.iterator
 143         end
 144
 145         redef fun is_ok do return ice.is_ok and icf.is_ok
 146
 147         redef fun item do
 148                 # We lazily create the pair here
 149                 var res = item_cache
 150                 if res == null then
 151                         res = new Pair[E,F](ice.item, icf.item)
 152                         item_cache = res
 153                 end
 154                 return res
 155         end
 156
 157         # Cached pair created by `item` and cleared by `next`.
 158         private var item_cache: nullable Pair[E,F] = null
 159
 160         redef fun next do
 161                 # Next item in the second iterator
 162                 icf.next
 163                 if not icf.is_ok then
 164                         # If it is over, then reset it and advance the first iterator
 165                         icf = collection.cf.iterator
 166                         ice.next
 167                 end
 168                 # Reset the cache
 169                 item_cache = null
 170         end
 171
 172         # First member of `item`.
 173         #
 174         # This method shortcut the allocation of a `Pair`, thus should be more time and memory efficient.
 175         fun item_e: E do return ice.item
 176
 177         # Second member of `item`.
 178         #
 179         # This method shortcut the allocation of a `Pair`, thus should be more time and memory efficient.
 180         fun item_f: E do return icf.item
 181 end