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