1 # This file is part of NIT ( http://www.nitlanguage.org ).
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
11 # Memory-efficient Cartesian products on heterogeneous collections.
13 # This module is a proof-of-concept to propose memory-efficient views on collections.
15 # This is a specific alternative to `combinations`, that focuses only highly efficient
16 # Cartesian products between collections of different types.
18 # Collection[Int] X Collection[String] -> Collection[(Int,String)]
20 # However, in Nit, there in no native *tuple* type.
21 # So we need a first building block, a pair.
24 # A simple read-only pair of two elements `e` and `f`.
26 # The first element of the pair
29 # The second element of the pair
32 # The parenthesized notation.
35 # var p = new Pair[Int, String](1, "hello")
36 # assert p.to_s == "(1,hello)"
45 # Untyped pair equality.
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)
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
60 redef fun hash
do return e
.hash
* 13 + f
.hash
* 27 # Magic numbers are magic!
63 # A view of a Cartesian-product collection over two collections.
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.
69 # However the view is memory-efficient and the pairs are created only when needed.
71 # A simple Cartesian product
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
80 # Note: because it is a view, changes on the base collections are reflected on the view.
82 # E.g. c12 is a view on c1 and c2, so if c1 changes, then c12 "changes".
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
89 # Cartesian objects are collections, so can be used to build another Cartesian object.
91 # var c3 = [1000..2000[
92 # var c123 = new Cartesian[Pair[Int,String],Int](c12, c3)
93 # assert c123.length == 4000
96 # All methods of Collection are inherited, it is so great!
98 # E.g. search elements?
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
107 class Cartesian[E
, F
]
108 super Collection[Pair[E
,F
]]
110 # The first collection
111 var ce
: Collection[E
]
113 # The second collection
114 var cf
: Collection[F
]
116 redef fun length
do return ce
.length
* cf
.length
# optional, but so efficient...
118 redef fun iterator
do return new CartesianIterator[E
,F
](self)
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
)
125 # An iterator over a `Cartesian`-product collection.
126 class CartesianIterator[E
,F
]
127 super Iterator[Pair[E
,F
]]
129 # The associated Cartesian-product collection.
130 var collection
: Cartesian[E
,F
]
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
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
141 # Initialize each iterator
142 ice
= collection
.ce
.iterator
143 icf
= collection
.cf
.iterator
146 redef fun is_ok
do return ice
.is_ok
and icf
.is_ok
149 # We lazily create the pair here
152 res
= new Pair[E
,F
](ice
.item
, icf
.item
)
158 # Cached pair created by `item` and cleared by `next`.
159 private var item_cache
: nullable Pair[E
,F
] = null
162 # Next item in the second iterator
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
173 # First member of `item`.
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
178 # Second member of `item`.
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