1 # This file is part of NIT ( http://www.nitlanguage.org ).
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
7 # http://www.apache.org/licenses/LICENSE-2.0
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.
15 # Highly specific, but useful, collections-related classes.
16 module more_collections
is serialize
21 # Simple way to store an `HashMap[K, Array[V]]`
23 # Unlike standard HashMap, MultiHashMap provides a new
24 # empty array on the first access on a unknown key.
26 # var m = new MultiHashMap[String, Char]
27 # assert not m.has_key("four")
32 # assert m.has_key("four")
33 # assert m["four"] == ['i', 'i', 'i', 'i']
34 # assert m["zzz"] == new Array[Char]
35 class MultiHashMap[K
, V
]
36 super HashMap[K
, Array[V
]]
38 # Add `v` to the array associated with `k`.
40 # If there is no array associated, then create it.
42 # For the inverse operation, see `remove_one`.
45 # var m = new MultiHashMap[String, Char]
46 # m.add_one("four", 'i')
47 # m.add_one("four", 'i')
48 # m.add_one("four", 'i')
49 # m.add_one("four", 'i')
50 # assert m.has_key("four")
51 # assert m["four"] == ['i', 'i', 'i', 'i']
53 fun add_one
(k
: K
, v
: V
)
55 var x
= self.get_or_null
(k
)
63 redef fun provide_default_value
(key
) do
64 var res
= new Array[V
]
69 # Remove an occurrence of `v` from the array associated with `k`.
71 # If the associated array does not contain `v`, do nothing. If the
72 # associated array only contain one element and this element is `v`, remove
75 # In a nutshell, does the inverse operation of `add_one`.
78 # var m = new MultiHashMap[String, Char]
79 # m["four"] = ['4', 'i', 'i', 'i', 'i']
80 # m.remove_one("four", 'i')
81 # assert m["four"] == ['4', 'i', 'i', 'i']
83 # m = new MultiHashMap[String, Char]
84 # m.add_one("one", '1')
85 # m.remove_one("one", '?')
86 # assert m["one"] == ['1']
87 # m.remove_one("one", '1')
88 # assert not m.has_key("one")
89 # assert m["one"] == new Array[Char]
91 # m = new MultiHashMap[String, Char]
92 # m.add_one("one", '1')
93 # m.remove_one("two", '2')
94 # assert not m.has_key("two")
95 # assert m["one"] == ['1']
96 # assert m["two"] == new Array[Char]
98 fun remove_one
(k
: K
, v
: V
)
100 var x
= get_or_null
(k
)
103 if x
.is_empty
then keys
.remove
(k
)
107 # Search the values in `pe.greaters` from the most smaller elements that have a value.
109 # Elements without values are ignored.
111 # Basically, values defined in nearest greater elements of `pe` are inherited.
114 # var pos = new POSet[String]
115 # pos.add_chain(["E", "D", "C", "B", "A"])
116 # pos.add_chain(["D", "X", "B"])
118 # var map = new MultiHashMap[String, String]
119 # map["A"].append(["a", "1"])
120 # map["C"].append(["c", "2"])
121 # map["X"].append(["x", "2"])
124 # assert map.lookup_joined_values(pos["B"]).has_exactly(["a", "1"])
125 # assert map.lookup_joined_values(pos["C"]).has_exactly(["c", "2"])
126 # assert map.lookup_joined_values(pos["D"]).has_exactly(["c", "x", "2"])
128 fun lookup_joined_values
(pe
: POSetElement[K
]): Set[V
]
131 for k
in pe
.poset
.select_smallest
(filter_keys
(pe
.greaters
)) do res
.add_all
self[k
]
137 # Simple way to store an `HashMap[K1, HashMap[K2, V]]`
140 # var hm2 = new HashMap2[Int, String, Float]
141 # hm2[1, "one"] = 1.0
142 # hm2[2, "two"] = 2.0
143 # assert hm2[1, "one"] == 1.0
144 # assert hm2[2, "not-two"] == null
146 class HashMap2[K1, K2, V
]
148 private var level1
= new HashMap[K1, HashMap[K2, V
]]
150 # Return the value associated to the keys `k1` and `k2`.
151 # Return `null` if no such a value.
152 fun [](k1
: K1, k2
: K2): nullable V
154 var level1
= self.level1
155 var level2
= level1
.get_or_null
(k1
)
156 if level2
== null then return null
157 return level2
.get_or_null
(k2
)
160 # Set `v` the value associated to the keys `k1` and `k2`.
161 fun []=(k1
: K1, k2
: K2, v
: V
)
163 var level1
= self.level1
164 var level2
= level1
.get_or_null
(k1
)
165 if level2
== null then
166 level2
= new HashMap[K2, V
]
172 # Remove the item at `k1` and `k2`
173 fun remove_at
(k1
: K1, k2
: K2)
175 var level1
= self.level1
176 var level2
= level1
.get_or_null
(k1
)
177 if level2
== null then return
178 level2
.keys
.remove
(k2
)
181 # Is there a value at `k1, k2`?
182 fun has
(k1
: K1, k2
: K2): Bool
184 if not level1
.keys
.has
(k1
) then return false
185 return level1
[k1
].keys
.has
(k2
)
189 fun clear
do level1
.clear
192 # Simple way to store an `HashMap[K1, HashMap[K2, HashMap[K3, V]]]`
195 # var hm3 = new HashMap3[Int, String, Int, Float]
196 # hm3[1, "one", 11] = 1.0
197 # hm3[2, "two", 22] = 2.0
198 # assert hm3[1, "one", 11] == 1.0
199 # assert hm3[2, "not-two", 22] == null
201 class HashMap3[K1, K2, K3, V
]
203 private var level1
= new HashMap[K1, HashMap2[K2, K3, V
]]
205 # Return the value associated to the keys `k1`, `k2`, and `k3`.
206 # Return `null` if no such a value.
207 fun [](k1
: K1, k2
: K2, k3
: K3): nullable V
209 var level1
= self.level1
210 var level2
= level1
.get_or_null
(k1
)
211 if level2
== null then return null
212 return level2
[k2
, k3
]
215 # Set `v` the value associated to the keys `k1`, `k2`, and `k3`.
216 fun []=(k1
: K1, k2
: K2, k3
: K3, v
: V
)
218 var level1
= self.level1
219 var level2
= level1
.get_or_null
(k1
)
220 if level2
== null then
221 level2
= new HashMap2[K2, K3, V
]
227 # Remove the item at `k1`, `k2` and `k3`
228 fun remove_at
(k1
: K1, k2
: K2, k3
: K3)
230 var level1
= self.level1
231 var level2
= level1
.get_or_null
(k1
)
232 if level2
== null then return
233 level2
.remove_at
(k2
, k3
)
236 # Is there a value at `k1, k2, k3`?
237 fun has
(k1
: K1, k2
: K2, k3
: K3): Bool
239 if not level1
.keys
.has
(k1
) then return false
240 return level1
[k1
].has
(k2
, k3
)
244 fun clear
do level1
.clear
247 # Simple way to store an `HashMap[K1, HashMap[K2, HashMap[K3, HashMap[K4, V]]]]`
250 # var hm4 = new HashMap4[Int, String, Int, String, Float]
251 # hm4[1, "one", 11, "un"] = 1.0
252 # hm4[2, "two", 22, "deux"] = 2.0
253 # assert hm4[1, "one", 11, "un"] == 1.0
254 # assert hm4[2, "not-two", 22, "deux"] == null
256 class HashMap4[K1, K2, K3, K4, V
]
258 private var level1
= new HashMap[K1, HashMap3[K2, K3, K4, V
]]
260 # Return the value associated to the keys `k1`, `k2`, `k3` and `k4`.
261 # Return `null` if no such a value.
262 fun [](k1
: K1, k2
: K2, k3
: K3, k4
: K4): nullable V
264 var level1
= self.level1
265 var level2
= level1
.get_or_null
(k1
)
266 if level2
== null then return null
267 return level2
[k2
, k3
, k4
]
270 # Set `v` the value associated to the keys `k1`, `k2`, `k3` and `k4`.
271 fun []=(k1
: K1, k2
: K2, k3
: K3, k4
: K4, v
: V
)
273 var level1
= self.level1
274 var level2
= level1
.get_or_null
(k1
)
275 if level2
== null then
276 level2
= new HashMap3[K2, K3, K4, V
]
279 level2
[k2
, k3
, k4
] = v
282 # Remove the item at `k1`, `k2`, `k3` and `k4`
283 fun remove_at
(k1
: K1, k2
: K2, k3
: K3, k4
: K4)
285 var level1
= self.level1
286 var level2
= level1
.get_or_null
(k1
)
287 if level2
== null then return
288 level2
.remove_at
(k2
, k3
, k4
)
291 # Is there a value at `k1, k2, k3, k4`?
292 fun has
(k1
: K1, k2
: K2, k3
: K3, k4
: K4): Bool
294 if not level1
.keys
.has
(k1
) then return false
295 return level1
[k1
].has
(k2
, k3
, k4
)
299 fun clear
do level1
.clear
302 # A map with a default value.
305 # var dm = new DefaultMap[String, Int](10)
306 # assert dm["a"] == 10
309 # The default value is used when the key is not present.
310 # And getting a default value does not register the key.
313 # assert dm["a"] == 10
314 # assert dm.length == 0
315 # assert dm.has_key("a") == false
318 # It also means that removed key retrieve the default value.
322 # assert dm["a"] == 2
323 # dm.keys.remove("a")
324 # assert dm["a"] == 10
327 # Warning: the default value is used as is, so using mutable object might
328 # cause side-effects.
331 # var dma = new DefaultMap[String, Array[Int]](new Array[Int])
334 # assert dma["a"] == [65]
335 # assert dma.default == [65]
336 # assert dma["c"] == [65]
339 # assert dma["b"] == [65, 66]
340 # assert dma.default == [65]
342 class DefaultMap[K
, V
]
348 redef fun provide_default_value
(key
) do return default
351 # An unrolled linked list
353 # A sequence implemented as a linked list of arrays.
355 # This data structure is similar to the `List` but it can benefit from
356 # better cache performance, lower data overhead for the nodes metadata and
357 # it spares the GC to allocate many small nodes.
358 class UnrolledList[E
]
361 # Desired capacity for each nodes
363 # By default at `32`, it can be increased for very large lists.
365 # It can be modified anytime, but newly created nodes may still be assigned
366 # the same capacity of old nodes when created by `insert`.
367 var nodes_length
= 32 is writable
369 private var head_node
: UnrolledNode[E
] = new UnrolledNode[E
](nodes_length
)
371 private var tail_node
: UnrolledNode[E
] = head_node
377 head_node
= new UnrolledNode[E
](nodes_length
)
378 tail_node
= head_node
382 # Out parameter of `node_at`
383 private var index_within_node
= 0
385 private fun node_at
(index
: Int): UnrolledNode[E
]
387 assert index
>= 0 and index
< length
390 while index
>= node
.length
do
392 node
= node
.next
.as(not null)
395 index_within_node
= index
399 private fun insert_node
(node
: UnrolledNode[E
], prev
, next
: nullable UnrolledNode[E
])
403 else head_node
= node
407 else tail_node
= node
415 var node
= node_at
(index
)
416 index
= index_within_node
+ node
.head_index
417 return node
.items
[index
]
420 redef fun []=(index
, value
)
422 var node
= node_at
(index
)
423 index
= index_within_node
+ node
.head_index
424 node
.items
[index
] = value
430 if not node
.full
then
431 if node
.tail_index
< node
.capacity
then
432 # There's room at the tail
435 # Move everything over by `d`
436 assert node
.head_index
> 0
437 var d
= node
.head_index
/ 2 + 1
438 node
.move_head
(node
.length
, d
)
439 for i
in d
.times
do node
.items
[node
.tail_index
- i
] = null
441 node
.tail_index
+= -d
+1
443 node
.items
[node
.tail_index-1
] = item
446 node
= new UnrolledNode[E
](nodes_length
)
447 insert_node
(node
, tail_node
, null)
454 redef fun unshift
(item
)
457 if not node
.full
then
458 if node
.head_index
> 0 then
459 # There's room at the head
462 # Move everything over by `d`
463 assert node
.tail_index
< node
.capacity
464 var d
= (node
.capacity-node
.tail_index
) / 2 + 1
466 for i
in d
.times
do node
.items
[node
.head_index
+i
] = null
467 node
.head_index
+= d-1
470 node
.items
[node
.head_index
] = item
473 node
= new UnrolledNode[E
](nodes_length
)
474 insert_node
(node
, null, head_node
)
475 node
.head_index
= node
.capacity-1
476 node
.tail_index
= node
.capacity
477 node
.items
[node
.capacity-1
] = item
487 while node
.length
== 0 do
489 var nullable_node
= node
.prev
490 assert is_not_empty
: nullable_node
!= null
493 self.tail_node
= node
496 var item
= node
.items
[node
.tail_index-1
]
507 while node
.length
== 0 do
509 var nullable_node
= node
.next
510 assert is_not_empty
: nullable_node
!= null
513 self.head_node
= node
516 var item
= node
.items
[node
.head_index
]
522 redef fun insert
(item
, index
)
524 if index
== length
then
529 var node
= node_at
(index
)
530 index
= index_within_node
532 # Move half to a new node
533 var new_node
= new UnrolledNode[E
](nodes_length
.max
(node
.capacity
))
535 # Plug in the new node
536 var next_node
= node
.next
537 insert_node
(new_node
, node
, next_node
)
539 # Move items at and after `index` to the new node
540 var to_displace
= node
.length-index
541 var offset
= (new_node
.capacity-to_displace
)/2
542 for i
in [0..to_displace
[ do
543 new_node
.items
[offset
+i
] = node
.items
[index
+i
]
544 node
.items
[index
+i
] = null
546 new_node
.head_index
= offset
547 new_node
.tail_index
= offset
+ to_displace
548 node
.tail_index
-= to_displace
551 if index
> node
.capacity
/ 2 then
552 new_node
.items
[offset-1
] = item
553 new_node
.head_index
-= 1
555 node
.items
[node
.head_index
+index
] = item
559 if node
.tail_index
< node
.capacity
then
560 # Move items towards the tail
561 node
.move_tail
(index
, 1)
563 node
.items
[node
.head_index
+ index
] = item
565 # Move items towards the head
566 node
.move_head
(index
, 1)
567 node
.items
[node
.head_index
+ index-1
] = item
574 redef fun remove_at
(index
)
576 var node
= node_at
(index
)
577 index
= index_within_node
+ node
.head_index
579 # Shift left all the elements after `index`
580 for i
in [index
+1 .. node
.tail_index
[ do
581 node
.items
[i-1
] = node
.items
[i
]
584 node
.items
[node
.tail_index
] = null
588 var next_node
= node
.next
589 var prev_node
= node
.prev
590 if node
.is_empty
and (next_node
!= null or prev_node
!= null) then
591 # Empty and non-head or tail node, delete
592 if next_node
!= null then
593 next_node
.prev
= node
.prev
594 else tail_node
= prev_node
.as(not null)
596 if prev_node
!= null then
597 prev_node
.next
= node
.next
598 else head_node
= next_node
.as(not null)
602 redef fun iterator
do return new UnrolledIterator[E
](self)
605 # Node composing an `UnrolledList`
607 # Stores the elements in the `items` array. The elements in the `items` array
608 # begin at `head_index` and end right before `tail_index`. The data is contiguous,
609 # but there can be empty cells at the beginning and the end of the array.
610 private class UnrolledNode[E
]
612 var prev
: nullable UnrolledNode[E
] = null
614 var next
: nullable UnrolledNode[E
] = null
616 # Desired length of `items`
619 # `Array` of items in this node, filled with `null`
620 var items
= new Array[nullable E
].filled_with
(null, capacity
) is lazy
622 # Index of the first element in `items`
625 # Index after the last element in `items`
628 fun length
: Int do return tail_index
- head_index
630 fun full
: Bool do return length
== capacity
632 fun is_empty
: Bool do return tail_index
== head_index
634 # Move towards the head all elements before `index` of `displace` cells
635 fun move_tail
(index
, displace
: Int)
637 for i
in [tail_index-1
..head_index
+index
].step
(-1) do
638 items
[i
+displace
] = items
[i
]
642 # Move towards the tail all elements at and after `index` of `displace` cells
643 fun move_head
(index
, displace
: Int)
645 for i
in [head_index
..head_index
+index
[ do
646 items
[i-displace
] = items
[i
]
651 private class UnrolledIterator[E
]
652 super IndexedIterator[E
]
654 var list
: UnrolledList[E
]
656 var node
: nullable UnrolledNode[E
] = list
.head_node
is lazy
658 # Index of the current `item`
661 # Index within the current `node`
662 var index_in_node
: Int = node
.head_index
is lazy
664 redef fun item
do return node
.items
[index_in_node
]
666 redef fun is_ok
do return index
< list
.length
673 if index_in_node
>= node
.tail_index
then
675 if node
!= null then index_in_node
= node
.head_index
680 # Keep track of the best elements according to a distance value.
683 # var bests = new BestDistance[String](5)
684 # bests.update(10, "Too big")
685 # assert bests.best_items.is_empty
686 # bests.update(5, "Just fine")
687 # bests.update(5, "Another one")
688 # assert bests.best_items.has_exactly(["Just fine", "Another one"])
689 # bests.update(2, "A better one")
690 # bests.update(4, "Not good enough")
691 # assert bests.best_distance == 2
692 # assert bests.best_items.has_exactly(["A better one"])
694 class BestDistance[E
]
695 # Current smallest distance
696 var best_distance
: Int is writable
698 # Known elements with the smallest distance
699 var best_items
= new Set[E
] is writable
701 # Register a `candidate` with a `distance`
703 # * To high, it is ignored.
704 # * Equal to the current best, it is added
705 # * Better that them, is is the new best element
707 # Return `true` if the candidate is kept (alone or with other)
708 # returns `false` if the candidate is ignored.
709 fun update
(distance
: Int, candidate
: E
): Bool
711 if distance
> best_distance
then return false
712 if distance
< best_distance
then
713 best_distance
= distance
716 best_items
.add candidate