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