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