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
20 # Simple way to store an `HashMap[K, Array[V]]`
22 # Unlike standard HashMap, MultiHashMap provides a new
23 # empty array on the first access on a unknown key.
25 # var m = new MultiHashMap[String, Char]
26 # assert not m.has_key("four")
31 # assert m.has_key("four")
32 # assert m["four"] == ['i', 'i', 'i', 'i']
33 # assert m["zzz"] == new Array[Char]
34 class MultiHashMap[K
, V
]
35 super HashMap[K
, Array[V
]]
37 # Add `v` to the array associated with `k`.
38 # If there is no array associated, then create it.
39 fun add_one
(k
: K
, v
: V
)
41 var x
= self.get_or_null
(k
)
49 redef fun provide_default_value
(key
) do
50 var res
= new Array[V
]
56 # Simple way to store an `HashMap[K1, HashMap[K2, V]]`
59 # var hm2 = new HashMap2[Int, String, Float]
62 # assert hm2[1, "one"] == 1.0
63 # assert hm2[2, "not-two"] == null
65 class HashMap2[K1, K2, V
]
67 private var level1
= new HashMap[K1, HashMap[K2, V
]]
69 # Return the value associated to the keys `k1` and `k2`.
70 # Return `null` if no such a value.
71 fun [](k1
: K1, k2
: K2): nullable V
73 var level1
= self.level1
74 var level2
= level1
.get_or_null
(k1
)
75 if level2
== null then return null
76 return level2
.get_or_null
(k2
)
79 # Set `v` the value associated to the keys `k1` and `k2`.
80 fun []=(k1
: K1, k2
: K2, v
: V
)
82 var level1
= self.level1
83 var level2
= level1
.get_or_null
(k1
)
84 if level2
== null then
85 level2
= new HashMap[K2, V
]
91 # Remove the item at `k1` and `k2`
92 fun remove_at
(k1
: K1, k2
: K2)
94 var level1
= self.level1
95 var level2
= level1
.get_or_null
(k1
)
96 if level2
== null then return
97 level2
.keys
.remove
(k2
)
100 # Is there a value at `k1, k2`?
101 fun has
(k1
: K1, k2
: K2): Bool
103 if not level1
.keys
.has
(k1
) then return false
104 return level1
[k1
].keys
.has
(k2
)
108 fun clear
do level1
.clear
111 # Simple way to store an `HashMap[K1, HashMap[K2, HashMap[K3, V]]]`
114 # var hm3 = new HashMap3[Int, String, Int, Float]
115 # hm3[1, "one", 11] = 1.0
116 # hm3[2, "two", 22] = 2.0
117 # assert hm3[1, "one", 11] == 1.0
118 # assert hm3[2, "not-two", 22] == null
120 class HashMap3[K1, K2, K3, V
]
122 private var level1
= new HashMap[K1, HashMap2[K2, K3, V
]]
124 # Return the value associated to the keys `k1`, `k2`, and `k3`.
125 # Return `null` if no such a value.
126 fun [](k1
: K1, k2
: K2, k3
: K3): nullable V
128 var level1
= self.level1
129 var level2
= level1
.get_or_null
(k1
)
130 if level2
== null then return null
131 return level2
[k2
, k3
]
134 # Set `v` the value associated to the keys `k1`, `k2`, and `k3`.
135 fun []=(k1
: K1, k2
: K2, k3
: K3, v
: V
)
137 var level1
= self.level1
138 var level2
= level1
.get_or_null
(k1
)
139 if level2
== null then
140 level2
= new HashMap2[K2, K3, V
]
146 # Remove the item at `k1`, `k2` and `k3`
147 fun remove_at
(k1
: K1, k2
: K2, k3
: K3)
149 var level1
= self.level1
150 var level2
= level1
.get_or_null
(k1
)
151 if level2
== null then return
152 level2
.remove_at
(k2
, k3
)
155 # Is there a value at `k1, k2, k3`?
156 fun has
(k1
: K1, k2
: K2, k3
: K3): Bool
158 if not level1
.keys
.has
(k1
) then return false
159 return level1
[k1
].has
(k2
, k3
)
163 fun clear
do level1
.clear
166 # A map with a default value.
169 # var dm = new DefaultMap[String, Int](10)
170 # assert dm["a"] == 10
173 # The default value is used when the key is not present.
174 # And getting a default value does not register the key.
177 # assert dm["a"] == 10
178 # assert dm.length == 0
179 # assert dm.has_key("a") == false
182 # It also means that removed key retrieve the default value.
186 # assert dm["a"] == 2
187 # dm.keys.remove("a")
188 # assert dm["a"] == 10
191 # Warning: the default value is used as is, so using mutable object might
192 # cause side-effects.
195 # var dma = new DefaultMap[String, Array[Int]](new Array[Int])
198 # assert dma["a"] == [65]
199 # assert dma.default == [65]
200 # assert dma["c"] == [65]
203 # assert dma["b"] == [65, 66]
204 # assert dma.default == [65]
206 class DefaultMap[K
, V
]
212 redef fun provide_default_value
(key
) do return default
215 # An unrolled linked list
217 # A sequence implemented as a linked list of arrays.
219 # This data structure is similar to the `List` but it can benefit from
220 # better cache performance, lower data overhead for the nodes metadata and
221 # it spares the GC to allocate many small nodes.
222 class UnrolledList[E
]
225 # Desired capacity for each nodes
227 # By default at `32`, it can be increased for very large lists.
229 # It can be modified anytime, but newly created nodes may still be assigned
230 # the same capacity of old nodes when created by `insert`.
231 var nodes_length
= 32 is writable
233 private var head_node
: UnrolledNode[E
] = new UnrolledNode[E
](nodes_length
)
235 private var tail_node
: UnrolledNode[E
] = head_node
241 head_node
= new UnrolledNode[E
](nodes_length
)
242 tail_node
= head_node
246 # Out parameter of `node_at`
247 private var index_within_node
= 0
249 private fun node_at
(index
: Int): UnrolledNode[E
]
251 assert index
>= 0 and index
< length
254 while index
>= node
.length
do
256 node
= node
.next
.as(not null)
259 index_within_node
= index
263 private fun insert_node
(node
: UnrolledNode[E
], prev
, next
: nullable UnrolledNode[E
])
267 else head_node
= node
271 else tail_node
= node
279 var node
= node_at
(index
)
280 index
= index_within_node
+ node
.head_index
281 return node
.items
[index
]
284 redef fun []=(index
, value
)
286 var node
= node_at
(index
)
287 index
= index_within_node
+ node
.head_index
288 node
.items
[index
] = value
294 if not node
.full
then
295 if node
.tail_index
< node
.capacity
then
296 # There's room at the tail
299 # Move everything over by `d`
300 assert node
.head_index
> 0
301 var d
= node
.head_index
/ 2 + 1
302 node
.move_head
(node
.length
, d
)
303 for i
in d
.times
do node
.items
[node
.tail_index
- i
] = null
305 node
.tail_index
+= -d
+1
307 node
.items
[node
.tail_index-1
] = item
310 node
= new UnrolledNode[E
](nodes_length
)
311 insert_node
(node
, tail_node
, null)
318 redef fun unshift
(item
)
321 if not node
.full
then
322 if node
.head_index
> 0 then
323 # There's room at the head
326 # Move everything over by `d`
327 assert node
.tail_index
< node
.capacity
328 var d
= (node
.capacity-node
.tail_index
) / 2 + 1
330 for i
in d
.times
do node
.items
[node
.head_index
+i
] = null
331 node
.head_index
+= d-1
334 node
.items
[node
.head_index
] = item
337 node
= new UnrolledNode[E
](nodes_length
)
338 insert_node
(node
, null, head_node
)
339 node
.head_index
= node
.capacity-1
340 node
.tail_index
= node
.capacity
341 node
.items
[node
.capacity-1
] = item
351 while node
.length
== 0 do
353 var nullable_node
= node
.prev
354 assert is_not_empty
: nullable_node
!= null
357 self.tail_node
= node
360 var item
= node
.items
[node
.tail_index-1
]
371 while node
.length
== 0 do
373 var nullable_node
= node
.next
374 assert is_not_empty
: nullable_node
!= null
377 self.head_node
= node
380 var item
= node
.items
[node
.head_index
]
386 redef fun insert
(item
, index
)
388 if index
== length
then
393 var node
= node_at
(index
)
394 index
= index_within_node
396 # Move half to a new node
397 var new_node
= new UnrolledNode[E
](nodes_length
.max
(node
.capacity
))
399 # Plug in the new node
400 var next_node
= node
.next
401 insert_node
(new_node
, node
, next_node
)
403 # Move items at and after `index` to the new node
404 var to_displace
= node
.length-index
405 var offset
= (new_node
.capacity-to_displace
)/2
406 for i
in [0..to_displace
[ do
407 new_node
.items
[offset
+i
] = node
.items
[index
+i
]
408 node
.items
[index
+i
] = null
410 new_node
.head_index
= offset
411 new_node
.tail_index
= offset
+ to_displace
412 node
.tail_index
-= to_displace
415 if index
> node
.capacity
/ 2 then
416 new_node
.items
[offset-1
] = item
417 new_node
.head_index
-= 1
419 node
.items
[node
.head_index
+index
] = item
423 if node
.tail_index
< node
.capacity
then
424 # Move items towards the tail
425 node
.move_tail
(index
, 1)
427 node
.items
[node
.head_index
+ index
] = item
429 # Move items towards the head
430 node
.move_head
(index
, 1)
431 node
.items
[node
.head_index
+ index-1
] = item
438 redef fun remove_at
(index
)
440 var node
= node_at
(index
)
441 index
= index_within_node
+ node
.head_index
443 # Shift left all the elements after `index`
444 for i
in [index
+1 .. node
.tail_index
[ do
445 node
.items
[i-1
] = node
.items
[i
]
448 node
.items
[node
.tail_index
] = null
452 var next_node
= node
.next
453 var prev_node
= node
.prev
454 if node
.is_empty
and (next_node
!= null or prev_node
!= null) then
455 # Empty and non-head or tail node, delete
456 if next_node
!= null then
457 next_node
.prev
= node
.prev
458 else tail_node
= prev_node
.as(not null)
460 if prev_node
!= null then
461 prev_node
.next
= node
.next
462 else head_node
= next_node
.as(not null)
466 redef fun iterator
do return new UnrolledIterator[E
](self)
469 # Node composing an `UnrolledList`
471 # Stores the elements in the `items` array. The elements in the `items` array
472 # begin at `head_index` and end right before `tail_index`. The data is contiguous,
473 # but there can be empty cells at the beginning and the end of the array.
474 private class UnrolledNode[E
]
476 var prev
: nullable UnrolledNode[E
] = null
478 var next
: nullable UnrolledNode[E
] = null
480 # Desired length of `items`
483 # `Array` of items in this node, filled with `null`
484 var items
= new Array[nullable E
].filled_with
(null, capacity
) is lazy
486 # Index of the first element in `items`
489 # Index after the last element in `items`
492 fun length
: Int do return tail_index
- head_index
494 fun full
: Bool do return length
== capacity
496 fun is_empty
: Bool do return tail_index
== head_index
498 # Move towards the head all elements before `index` of `displace` cells
499 fun move_tail
(index
, displace
: Int)
501 for i
in [tail_index-1
..head_index
+index
].step
(-1) do
502 items
[i
+displace
] = items
[i
]
506 # Move towards the tail all elements at and after `index` of `displace` cells
507 fun move_head
(index
, displace
: Int)
509 for i
in [head_index
..head_index
+index
[ do
510 items
[i-displace
] = items
[i
]
515 private class UnrolledIterator[E
]
516 super IndexedIterator[E
]
518 var list
: UnrolledList[E
]
520 var node
: nullable UnrolledNode[E
] = list
.head_node
is lazy
522 # Index of the current `item`
525 # Index within the current `node`
526 var index_in_node
: Int = node
.head_index
is lazy
528 redef fun item
do return node
.items
[index_in_node
]
530 redef fun is_ok
do return index
< list
.length
537 if index_in_node
>= node
.tail_index
then
539 if node
!= null then index_in_node
= node
.head_index
544 # Keep track of the best elements according to a distance value.
547 # var bests = new BestDistance[String](5)
548 # bests.update(10, "Too big")
549 # assert bests.best_items.is_empty
550 # bests.update(5, "Just fine")
551 # bests.update(5, "Another one")
552 # assert bests.best_items.has_exactly(["Just fine", "Another one"])
553 # bests.update(2, "A better one")
554 # bests.update(4, "Not good enough")
555 # assert bests.best_distance == 2
556 # assert bests.best_items.has_exactly(["A better one"])
558 class BestDistance[E
]
559 # Current smallest distance
560 var best_distance
: Int is writable
562 # Known elements with the smallest distance
563 var best_items
= new Set[E
] is writable
565 # Register a `candidate` with a `distance`
567 # * To high, it is ignored.
568 # * Equal to the current best, it is added
569 # * Better that them, is is the new best element
571 # Return `true` if the candidate is kept (alone or with other)
572 # returns `false` if the candidate is ignored.
573 fun update
(distance
: Int, candidate
: E
): Bool
575 if distance
> best_distance
then return false
576 if distance
< best_distance
then
577 best_distance
= distance
580 best_items
.add candidate