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 index accessed
  31         var _last_accessed_index: Int = -1
  32
  33         # The last key accessed
  34         var _last_accessed_key: nullable K = null
  35
  36         # Return the index of the k element
  37         fun index_at(k: K): Int
  38         do
  39                 var arr = _array
  40
  41                 # Fisrt step: look in the last indexed elt
  42                 if k == _last_accessed_key then return _last_accessed_index
  43
  44                 # Compute the base position of the key
  45                 var base = k.hash % _capacity
  46                 if base < 0 then base = - base
  47
  48                 # Look for the key in the array
  49                 var cur = base
  50                 loop
  51                         var c = arr[cur]
  52                         if c == null or c._key == k then # REAL equals
  53                                 _last_accessed_index = cur
  54                                 _last_accessed_key = k
  55                                 return cur
  56                         end
  57                         cur -= 1
  58                         if cur < 0 then cur = _capacity - 1
  59                         assert no_loop: cur != base
  60                         if false then break # FIXME remove once unreach loop exits are in c_src
  61                 end
  62                 abort #FIXME remove once unreach loop exits are in c_src
  63         end
  64
  65         # Return the node assosiated with the key
  66         fun node_at(k: K): nullable N
  67         do
  68                 var res = node_at_idx(index_at(k), k)
  69                 return res
  70         end
  71
  72         # Return the node assosiated with the key (but with the index already known)
  73         fun node_at_idx(i: Int, k: K): nullable N
  74         do
  75                 return _array[i]
  76         end
  77
  78         # Add a new node (should be free)
  79         fun store(index: Int, node: N)
  80         do
  81                 # Store the item in the list
  82                 if _first_item == null then
  83                         _first_item = node
  84                 else
  85                         _last_item._next_item = node
  86                 end
  87                 node._prev_item = _last_item
  88                 node._next_item = null
  89                 _last_item = node
  90                 # Then store it in the array
  91                 assert _array[index] == null
  92                 _array[index] = node
  93                 var l = _length
  94                 _length = l + 1
  95                 l = (l + 5) * 150 / 100
  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 = _array[i]
 106                 if node == null then return
 107                 # Remove the item in the list
 108                 var prev = node._prev_item
 109                 var next = node._next_item
 110                 if prev != null then
 111                         prev._next_item = next
 112                 else
 113                         _first_item = next
 114                 end
 115                 if next != null then
 116                         next._prev_item = prev
 117                 else
 118                         _last_item = prev
 119                 end
 120                 # Remove the item in the array
 121                 _array[i] = null
 122                 _length -= 1
 123                 # Now replaces things before if needed
 124                 loop
 125                         i -= 1
 126                         if i < 0 then
 127                                 i = _capacity - 1
 128                         end
 129                         var n = _array[i]
 130                         if n == null then
 131                                 return
 132                         end
 133                         var i2 = index_at(n._key)
 134                         if i != i2 then
 135                                 _array[i] = null
 136                                 assert _array[i2] == null
 137                                 _array[i2] = n
 138                         end
 139                 end
 140         end
 141
 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         fun enlarge(cap: Int)
 156         do
 157                 var old_cap = _capacity
 158                 # get a new capacity
 159                 if cap < _length + 1 then cap = _length + 1
 160                 if cap <= _capacity then return
 161                 _capacity = cap
 162                 _last_accessed_key = null
 163
 164                 # get a new array
 165                 var new_array = calloc_array(cap)
 166                 _array = new_array
 167
 168                 # clean the new array
 169                 var i = cap - 1
 170                 while i >=0 do
 171                         new_array[i] = null
 172                         i -= 1
 173                 end
 174
 175                 if _capacity <= old_cap then return
 176
 177                 # Reput items in the array
 178                 var node = _first_item
 179                 while node != null do
 180                         var ind = index_at(node._key)
 181                         assert new_array[ind] == null
 182                         new_array[ind] = node
 183                         node = node._next_item
 184                 end
 185                 _last_accessed_key = null
 186         end
 187 end
 188
 189 private class HashNode[K]
 190         var _key: K
 191         type N: HashNode[K]
 192         readable writable var _next_item: nullable N = null
 193         readable writable var _prev_item: nullable N = null
 194         init(k: K)
 195         do
 196                 _key = k
 197         end
 198 end
 199
 200 class HashMap[K, 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                 assert key != null
 270                 var i = index_at(key)
 271                 var c = node_at_idx(i, key)
 272                 if c != null then
 273                         c._key = key
 274                         c._value = v
 275                 else
 276                         store(i, new HashMapNode[K, V](key, v))
 277                 end
 278         end
 279
 280         redef fun remove(item)
 281         do
 282                 var c = _first_item
 283                 while c != null do
 284                         if c._value == item then
 285                                 remove_node(c._key)
 286                                 return
 287                         end
 288                         c = c._next_item
 289                 end
 290         end
 291
 292         redef fun remove_at(key) do remove_node(key)
 293
 294         redef fun clear do raz
 295
 296         init
 297         do
 298                 _capacity = 0
 299                 _length = 0
 300                 enlarge(0)
 301         end
 302 end
 303
 304 class HashMapNode[K, V]
 305 special HashNode[K]
 306         redef type N: HashMapNode[K, V]
 307         var _value: V
 308
 309         init(k: K, v: V)
 310         do
 311                 super(k)
 312                 _value = v
 313         end
 314 end
 315
 316 class HashMapIterator[K, V]
 317 special MapIterator[K, V]
 318         redef fun is_ok do return _node != null
 319
 320         redef fun item
 321         do
 322                 assert is_ok
 323                 return _node._value
 324         end
 325
 326         #redef fun item=(value)
 327         #do
 328         #       assert is_ok
 329         #       _node.second = value
 330         #end
 331
 332         redef fun key
 333         do
 334                 assert is_ok
 335                 return _node._key
 336         end
 337
 338         redef fun next
 339         do
 340                 assert is_ok
 341                 _node = _node._next_item
 342         end
 343
 344         # The map to iterate on
 345         var _map: HashMap[K, V]
 346
 347         # The current node
 348         var _node: nullable HashMapNode[K, V]
 349
 350         init(map: HashMap[K, V])
 351         do
 352                 _map = map
 353                 _node = map.first_item
 354         end
 355 end
 356
 357 class HashSet[E]
 358 special Set[E]
 359 special HashCollection[E, HashSetNode[E], E]
 360
 361         redef fun is_empty do return _length == 0
 362
 363         redef fun first
 364         do
 365                 assert _length > 0
 366                 return _first_item._key
 367         end
 368
 369         redef fun has(item)
 370         do
 371                 return node_at(item) != null
 372         end
 373
 374         redef fun add(item)
 375         do
 376                 var i = index_at(item)
 377                 var c = node_at_idx(i, item)
 378                 if c != null then
 379                         c._key = item
 380                 else
 381                         store(i,new HashSetNode[E](item))
 382                 end
 383         end
 384
 385         redef fun remove(item) do remove_node(item)
 386
 387         redef fun clear do raz
 388
 389         redef fun iterator do return new HashSetIterator[E](self)
 390
 391         init
 392         do
 393                 _capacity = 0
 394                 _length = 0
 395                 enlarge(0)
 396         end
 397 end
 398
 399 class HashSetNode[E]
 400 special HashNode[E]
 401         redef type N: HashSetNode[E]
 402
 403         init(e: E)
 404         do
 405                 _key = e
 406         end
 407 end
 408
 409 class HashSetIterator[E]
 410 special Iterator[E]
 411         redef fun is_ok do return _node != null
 412
 413         redef fun item
 414         do
 415                 assert is_ok
 416                 return _node._key
 417         end
 418
 419         redef fun next
 420         do
 421                 assert is_ok
 422                 _node = _node._next_item
 423         end
 424
 425         # The set to iterate on
 426         var _set: HashSet[E]
 427
 428         # The position in the internal map storage
 429         var _node: nullable HashSetNode[E]
 430
 431         init(set: HashSet[E])
 432         do
 433                 _set = set
 434                 _node = set._first_item
 435         end
 436 end
 437