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 # 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.
23 # A simple read-only pair of two elements `e` and `f`.
25 # The first element of the pair
28 # The second element of the pair
31 # The parenthesized notation.
34 # var p = new Pair[Int, String](1, "hello")
35 # assert p.to_s == "(1,hello)"
44 # Untyped pair equality.
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)
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
59 redef fun hash
do return e
.hash
* 13 + f
.hash
* 27 # Magic numbers are magic!
62 # A view of a Cartesian-product collection over two collections.
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.
68 # However the view is memory-efficient and the pairs are created only when needed.
70 # A simple Cartesian product
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
79 # Note: because it is a view, changes on the base collections are reflected on the view.
81 # E.g. c12 is a view on c1 and c2, so if c1 changes, then c12 "changes".
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
88 # Cartesian objects are collections, so can be used to build another Cartesian object.
90 # var c3 = [1000..2000[
91 # var c123 = new Cartesian[Pair[Int,String],Int](c12, c3)
92 # assert c123.length == 4000
95 # All methods of Collection are inherited, it is so great!
97 # E.g. search elements?
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
106 class Cartesian[E
, F
]
107 super Collection[Pair[E
,F
]]
109 # The first collection
110 var ce
: Collection[E
]
112 # The second collection
113 var cf
: Collection[F
]
115 redef fun length
do return ce
.length
* cf
.length
# optional, but so efficient...
117 redef fun iterator
do return new CartesianIterator[E
,F
](self)
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
)
124 # An iterator over a `Cartesian`-product collection.
125 class CartesianIterator[E
,F
]
126 super Iterator[Pair[E
,F
]]
128 # The associated Cartesian-product collection.
129 var collection
: Cartesian[E
,F
]
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
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
140 # Initialize each iterator
141 ice
= collection
.ce
.iterator
142 icf
= collection
.cf
.iterator
145 redef fun is_ok
do return ice
.is_ok
and icf
.is_ok
148 # We lazily create the pair here
151 res
= new Pair[E
,F
](ice
.item
, icf
.item
)
157 # Cached pair created by `item` and cleared by `next`.
158 private var item_cache
: nullable Pair[E
,F
] = null
161 # Next item in the second iterator
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
172 # First member of `item`.
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
177 # Second member of `item`.
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