lib/standard/collection/hash_collection.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2009 Jean Privat <jean@pryen.org>
   4 #
   5 # This file is free software, which comes along with NIT.  This software is
   6 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   7 # without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   8 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
   9 # is kept unaltered, and a notification of the changes is added.
  10 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
  11 # another product.
  12
  13 # Introduce `HashMap` and `HashSet`.
  14 module hash_collection
  15
  16 import array
  17
  18 redef class Map[K, V]
  19         # Get a `HashMap[K, V]` as default implementation
  20         new do return new HashMap[K, V]
  21 end
  22
  23 # A HashCollection is an array of HashNode[K] indexed by the K hash value
  24 private abstract class HashCollection[K]
  25         type N: HashNode[K]
  26
  27         var array: nullable NativeArray[nullable N] = null # Used to store items
  28         var capacity: Int = 0 # Size of _array
  29         var the_length: Int = 0 # Number of items in the map
  30
  31         var first_item: nullable N = null # First added item (used to visit items in nice order)
  32         var last_item: nullable N = null # Last added item (same)
  33
  34         # The last key accessed (used for cache)
  35         var last_accessed_key: nullable K = null
  36
  37         # The last node accessed (used for cache)
  38         var last_accessed_node: nullable N = null
  39
  40         # Return the index of the key k
  41         fun index_at(k: K): Int
  42         do
  43                 if k == null then return 0
  44
  45                 var i = k.hash % _capacity
  46                 if i < 0 then i = - i
  47                 return i
  48         end
  49
  50         # Return the node associated with the key
  51         fun node_at(k: K): nullable N
  52         do
  53                 # cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
  54                 if k.is_same_instance(_last_accessed_key) then return _last_accessed_node
  55
  56                 var res = node_at_idx(index_at(k), k)
  57                 _last_accessed_key = k
  58                 _last_accessed_node = res
  59                 return res
  60         end
  61
  62         # Return the node associated with the key (but with the index already known)
  63         fun node_at_idx(i: Int, k: K): nullable N
  64         do
  65                 var c = _array[i]
  66                 while c != null do
  67                         var ck = c._key
  68                         if ck.is_same_instance(k) or ck == k then # FIXME prefilter because the compiler is not smart enought yet
  69                                 break
  70                         end
  71                         c = c._next_in_bucklet
  72                 end
  73                 return c
  74         end
  75
  76         # Add a new node at a given index
  77         fun store(index: Int, node: N)
  78         do
  79                 # Store the item in the list
  80                 if _first_item == null then
  81                         _first_item = node
  82                 else
  83                         _last_item._next_item = node
  84                 end
  85                 node._prev_item = _last_item
  86                 node._next_item = null
  87                 _last_item = node
  88
  89                 # Then store it in the array
  90                 var next = _array[index]
  91                 _array[index] = node
  92                 node._next_in_bucklet = next
  93                 if next != null then next._prev_in_bucklet = node
  94
  95                 _last_accessed_key = node._key
  96                 _last_accessed_node = node
  97
  98                 # Enlarge if needed
  99                 var l = _the_length
 100                 _the_length = l + 1
 101
 102                 # Magic values determined empirically
 103                 # We do not want to enlarge too much
 104                 # We also want a odd capacity so that the modulo is more distributive
 105                 l = (l + 5) * 2 + 1
 106                 if l >= _capacity then
 107                         enlarge(l * 3 / 2 + 1)
 108                 end
 109         end
 110
 111         # Remove the node assosiated with the key
 112         fun remove_node(k: K)
 113         do
 114                 var i = index_at(k)
 115                 var node = node_at_idx(i, k)
 116                 if node == null then return
 117
 118                 # Remove the item in the list
 119                 var prev = node._prev_item
 120                 var next = node._next_item
 121                 if prev != null then
 122                         prev._next_item = next
 123                 else
 124                         _first_item = next
 125                 end
 126                 if next != null then
 127                         next._prev_item = prev
 128                 else
 129                         _last_item = prev
 130                 end
 131
 132                 # Remove the item in the array
 133                 _the_length -= 1
 134                 prev = node._prev_in_bucklet
 135                 next = node._next_in_bucklet
 136                 if prev != null then
 137                         prev._next_in_bucklet = next
 138                 else
 139                         _array[i] = next
 140                 end
 141                 if next != null then
 142                         next._prev_in_bucklet = prev
 143                 end
 144
 145                 _last_accessed_key = null
 146         end
 147
 148         # Clear the whole structure
 149         fun raz
 150         do
 151                 var i = _capacity - 1
 152                 while i >= 0 do
 153                         _array[i] = null
 154                         i -= 1
 155                 end
 156                 _the_length = 0
 157                 _first_item = null
 158                 _last_item = null
 159                 _last_accessed_key = null
 160         end
 161
 162         # Force a capacity
 163         fun enlarge(cap: Int)
 164         do
 165                 var old_cap = _capacity
 166                 # get a new capacity
 167                 if cap < _the_length + 1 then cap = _the_length + 1
 168                 if cap <= _capacity then return
 169                 _capacity = cap
 170                 _last_accessed_key = null
 171
 172                 # get a new array
 173                 var new_array = new NativeArray[nullable N](cap)
 174                 _array = new_array
 175
 176                 # clean the new array
 177                 var i = cap - 1
 178                 while i >=0 do
 179                         new_array[i] = null
 180                         i -= 1
 181                 end
 182
 183                 if _capacity <= old_cap then return
 184
 185                 # Reput items in the array
 186                 var node = _first_item
 187                 while node != null do
 188                         var index = index_at(node._key)
 189                         # Then store it in the array
 190                         var next = new_array[index]
 191                         new_array[index] = node
 192                         node._prev_in_bucklet = null
 193                         node._next_in_bucklet = next
 194                         if next != null then next._prev_in_bucklet = node
 195                         node = node._next_item
 196                 end
 197         end
 198 end
 199
 200 private abstract class HashNode[K]
 201         var key: K
 202         type N: HashNode[K]
 203         var next_item: nullable N = null
 204         var prev_item: nullable N = null
 205         var prev_in_bucklet: nullable N = null
 206         var next_in_bucklet: nullable N = null
 207 end
 208
 209 # A `Map` implemented with a hash table.
 210 #
 211 # ~~~
 212 # var map = new HashMap[nullable String, Int]
 213 # map[null] = 0
 214 # map["one"] = 1
 215 # map["two"] = 2
 216 #
 217 # assert map[null] == 0
 218 # assert map["one"] == 1
 219 # assert map.keys.has("two")
 220 # assert map.values.length == 3
 221 # ~~~
 222 class HashMap[K, V]
 223         super Map[K, V]
 224         super HashCollection[K]
 225
 226         redef type N: HashMapNode[K, V] is fixed
 227
 228         redef fun [](key)
 229         do
 230                 var c = node_at(key)
 231                 if c == null then
 232                         return provide_default_value(key)
 233                 else
 234                         return c._value
 235                 end
 236         end
 237
 238         redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
 239
 240         redef fun length do return _the_length
 241
 242         redef fun is_empty do return _the_length == 0
 243
 244         redef fun []=(key, v)
 245         do
 246                 var i = index_at(key)
 247                 var c = node_at_idx(i, key)
 248                 if c != null then
 249                         c._key = key
 250                         c._value = v
 251                 else
 252                         store(i, new HashMapNode[K, V](key, v))
 253                 end
 254         end
 255
 256         redef fun clear do raz
 257
 258         init
 259         do
 260                 _capacity = 0
 261                 _the_length = 0
 262                 enlarge(0)
 263         end
 264
 265         redef var keys: RemovableCollection[K] = new HashMapKeys[K, V](self)
 266         redef var values: RemovableCollection[V] = new HashMapValues[K, V](self)
 267 end
 268
 269 # View of the keys of a HashMap
 270 private class HashMapKeys[K, V]
 271         super RemovableCollection[K]
 272         # The original map
 273         var map: HashMap[K, V]
 274
 275         redef fun count(k) do if self.has(k) then return 1 else return 0
 276         redef fun first do return self.map._first_item._key
 277         redef fun has(k) do return self.map.node_at(k) != null
 278         redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
 279         redef fun is_empty do return self.map.is_empty
 280         redef fun length do return self.map.length
 281
 282         redef fun iterator do return new MapKeysIterator[K, V](self.map.iterator)
 283
 284         redef fun clear do self.map.clear
 285
 286         redef fun remove(key) do self.map.remove_node(key)
 287         redef fun remove_all(key) do self.map.remove_node(key)
 288 end
 289
 290 # View of the values of a Map
 291 private class HashMapValues[K, V]
 292         super RemovableCollection[V]
 293         # The original map
 294         var map: HashMap[K, V]
 295
 296         redef fun count(item)
 297         do
 298                 var nb = 0
 299                 var c = self.map._first_item
 300                 while c != null do
 301                         if c._value == item then nb += 1
 302                         c = c._next_item
 303                 end
 304                 return nb
 305         end
 306         redef fun first do return self.map._first_item._value
 307
 308         redef fun has(item)
 309         do
 310                 var c = self.map._first_item
 311                 while c != null do
 312                         if c._value == item then return true
 313                         c = c._next_item
 314                 end
 315                 return false
 316         end
 317
 318         redef fun has_only(item)
 319         do
 320                 var c = self.map._first_item
 321                 while c != null do
 322                         if c._value != item then return false
 323                         c = c._next_item
 324                 end
 325                 return true
 326         end
 327
 328         redef fun is_empty do return self.map.is_empty
 329         redef fun length do return self.map.length
 330
 331         redef fun iterator do return new MapValuesIterator[K, V](self.map.iterator)
 332
 333         redef fun clear do self.map.clear
 334
 335         redef fun remove(item)
 336         do
 337                 var map = self.map
 338                 var c = map._first_item
 339                 while c != null do
 340                         if c._value == item then
 341                                 map.remove_node(c._key)
 342                                 return
 343                         end
 344                         c = c._next_item
 345                 end
 346         end
 347
 348         redef fun remove_all(item)
 349         do
 350                 var map = self.map
 351                 var c = map._first_item
 352                 while c != null do
 353                         if c._value == item then
 354                                 map.remove_node(c._key)
 355                         end
 356                         c = c._next_item
 357                 end
 358         end
 359 end
 360
 361 private class HashMapNode[K, V]
 362         super HashNode[K]
 363         redef type N: HashMapNode[K, V]
 364         var value: V
 365 end
 366
 367 # A `MapIterator` over a `HashMap`.
 368 class HashMapIterator[K, V]
 369         super MapIterator[K, V]
 370         redef fun is_ok do return _node != null
 371
 372         redef fun item
 373         do
 374                 assert is_ok
 375                 return _node._value
 376         end
 377
 378         #redef fun item=(value)
 379         #do
 380         #       assert is_ok
 381         #       _node.second = value
 382         #end
 383
 384         redef fun key
 385         do
 386                 assert is_ok
 387                 return _node._key
 388         end
 389
 390         redef fun next
 391         do
 392                 assert is_ok
 393                 _node = _node._next_item
 394         end
 395
 396         # The map to iterate on
 397         private var map: HashMap[K, V]
 398
 399         # The current node
 400         private var node: nullable HashMapNode[K, V] = null
 401
 402         init
 403         do
 404                 _map = map
 405                 _node = _map._first_item
 406         end
 407 end
 408
 409 # A `Set` implemented with a hash table.
 410 # Keys of such a map cannot be null and require a working `hash` method
 411 class HashSet[E: Object]
 412         super Set[E]
 413         super HashCollection[E]
 414
 415         redef type N: HashSetNode[E] is fixed
 416
 417         redef fun length do return _the_length
 418
 419         redef fun is_empty do return _the_length == 0
 420
 421         redef fun first
 422         do
 423                 assert _the_length > 0
 424                 return _first_item._key
 425         end
 426
 427         redef fun has(item)
 428         do
 429                 return node_at(item) != null
 430         end
 431
 432         redef fun add(item)
 433         do
 434                 var i = index_at(item)
 435                 var c = node_at_idx(i, item)
 436                 if c != null then
 437                         c._key = item
 438                 else
 439                         store(i,new HashSetNode[E](item))
 440                 end
 441         end
 442
 443         redef fun remove(item) do remove_node(item)
 444
 445         redef fun clear do raz
 446
 447         redef fun iterator do return new HashSetIterator[E](self)
 448
 449         init
 450         do
 451                 _capacity = 0
 452                 _the_length = 0
 453                 enlarge(0)
 454         end
 455
 456         # Build a list filled with the items of `coll`.
 457         init from(coll: Collection[E]) do
 458                 init
 459                 add_all(coll)
 460         end
 461
 462         redef fun new_set do return new HashSet[E]
 463 end
 464
 465 private class HashSetNode[E: Object]
 466         super HashNode[E]
 467         redef type N: HashSetNode[E]
 468 end
 469
 470 private class HashSetIterator[E: Object]
 471         super Iterator[E]
 472         redef fun is_ok do return _node != null
 473
 474         redef fun item
 475         do
 476                 assert is_ok
 477                 return _node._key
 478         end
 479
 480         redef fun next
 481         do
 482                 assert is_ok
 483                 _node = _node._next_item
 484         end
 485
 486         # The set to iterate on
 487         var set: HashSet[E]
 488
 489         # The position in the internal map storage
 490         var node: nullable HashSetNode[E] = null
 491
 492         init
 493         do
 494                 _node = _set._first_item
 495         end
 496 end
 497