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                 end
  61                 abort
  62         end
  63
  64         # Add a new node (should be free)
  65         fun store(index: Int, node: N)
  66         do
  67                 # Store the item in the list
  68                 if _first_item == null then
  69                         _first_item = node
  70                 else
  71                         _last_item.next_item = node
  72                 end
  73                 node.prev_item = _last_item
  74                 node.next_item = null
  75                 _last_item = node
  76                 # Then store it in the array
  77                 assert _array[index] == null
  78                 _array[index] = node
  79                 var l = _length
  80                 _length = l + 1
  81                 l = (l + 5) * 150 / 100
  82                 if l >= _capacity then
  83                         enlarge(l * 2)
  84                 end
  85         end
  86
  87         fun remove_index(i: Int)
  88         do
  89                 assert correct_index: i >= 0 and i < _capacity
  90                 var node = _array[i]
  91                 assert has_couple: node != null
  92                 # Remove the item in the list
  93                 var prev = node.prev_item
  94                 var next = node.next_item
  95                 if prev != null then
  96                         prev.next_item = next
  97                 else
  98                         _first_item = next
  99                 end
 100                 if next != null then
 101                         next.prev_item = prev
 102                 else
 103                         _last_item = prev
 104                 end
 105                 # Remove the item in the array
 106                 _array[i] = null
 107                 _length -= 1
 108                 # Now replaces things before if needed
 109                 loop
 110                         i -= 1
 111                         if i < 0 then
 112                                 i = _capacity - 1
 113                         end
 114                         var n = _array[i]
 115                         if n == null then
 116                                 return
 117                         end
 118                         var i2 = index_at(n.key)
 119                         if i != i2 then
 120                                 _array[i] = null
 121                                 assert _array[i2] == null
 122                                 _array[i2] = n
 123                         end
 124                 end
 125         end
 126
 127         fun raz
 128         do
 129                 var i = _capacity - 1
 130                 while i >= 0 do
 131                         _array[i] = null
 132                         i -= 1
 133                 end
 134                 _length = 0
 135                 _first_item = null
 136                 _last_item = null
 137                 _last_accessed_key = null
 138         end
 139
 140         fun enlarge(cap: Int)
 141         do
 142                 var old_cap = _capacity
 143                 # get a new capacity
 144                 # cap = cap * 130 / 100 + 5 + 1000 # /
 145                 if cap < _length + 1 then cap = _length + 1
 146                 if cap <= _capacity then return
 147                 _capacity = cap
 148                 _last_accessed_key = null
 149
 150                 # get a new array
 151                 var new_array = calloc_array(cap)
 152                 _array = new_array
 153
 154                 # clean the new array
 155                 var i = cap - 1
 156                 while i >=0 do
 157                         new_array[i] = null
 158                         i -= 1
 159                 end
 160
 161                 if _capacity <= old_cap then return
 162
 163                 # Reput items in the array
 164                 var node = _first_item
 165                 while node != null do
 166                         var ind = index_at(node.key)
 167                         assert new_array[ind] == null
 168                         new_array[ind] = node
 169                         node = node.next_item
 170                 end
 171                 _last_accessed_key = null
 172         end
 173 end
 174
 175 private class HashNode[K]
 176         fun key: K is abstract
 177         type N: HashNode[K]
 178         readable writable var _next_item: nullable N = null
 179         readable writable var _prev_item: nullable N = null
 180 end
 181
 182 class HashMap[K, V]
 183 special CoupleMap[K, V]
 184 special HashCollection[K, HashMapNode[K, V], V]
 185
 186         redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
 187
 188         redef fun iterate
 189                 !each(e: V)
 190         do
 191                 var c = _first_item
 192                 while c != null do
 193                         each(c.second)
 194                         c = c._next_item
 195                 end
 196         end
 197
 198         redef fun first
 199         do
 200                 assert _length > 0
 201                 return _first_item.second
 202         end
 203
 204         redef fun is_empty do return _length == 0
 205
 206         redef fun count(item)
 207         do
 208                 var nb = 0
 209                 var i = 0
 210                 while i < _capacity do
 211                         var c = _array[i]
 212                         if c != null and c.second == item then nb += 1
 213                         i += 1
 214                 end
 215                 return nb
 216         end
 217
 218         redef fun has(item)
 219         do
 220                 var i = 0
 221                 while i < _capacity do
 222                         var c = _array[i]
 223                         if c != null and c.second == item then return true
 224                         i += 1
 225                 end
 226                 return false
 227         end
 228
 229         redef fun has_only(item)
 230         do
 231                 var i = 0
 232                 while i < _capacity do
 233                         var c = _array[i]
 234                         if c != null and c.second != item then return false
 235                         i += 1
 236                 end
 237                 return true
 238         end
 239
 240         redef fun []=(key, v)
 241         do
 242                 assert key != null
 243                 var i = index_at(key)
 244                 var c = _array[i]
 245                 if c != null then
 246                         c.first = key
 247                         c.second = v
 248                 else
 249                         store(i, new HashMapNode[K, V](key, v))
 250                 end
 251         end
 252
 253         redef fun remove(item)
 254         do
 255                 var i = 0
 256                 while i < _capacity do
 257                         var c = _array[i]
 258                         if c != null and c.second == item then
 259                                 remove_index(i)
 260                                 return
 261                         end
 262                         i += 1
 263                 end
 264         end
 265
 266         redef fun remove_at(key) do remove_index(index_at(key))
 267
 268         redef fun clear do raz
 269
 270         redef fun couple_at(key) do return _array[index_at(key)]
 271
 272         init
 273         do
 274                 _capacity = 0
 275                 _length = 0
 276                 enlarge(0)
 277         end
 278 end
 279
 280 class HashMapNode[K, V]
 281 special Couple[K, V]
 282 special HashNode[K]
 283         redef fun key do return first
 284         redef type N: HashMapNode[K, V]
 285
 286         init(k: K, v: V)
 287         do
 288                 first = k
 289                 second = v
 290         end
 291 end
 292
 293 class HashMapIterator[K, V]
 294 special MapIterator[K, V]
 295         redef fun is_ok do return _node != null
 296
 297         redef fun item
 298         do
 299                 assert is_ok
 300                 return _node.second
 301         end
 302
 303         #redef fun item=(value)
 304         #do
 305         #       assert is_ok
 306         #       _node.second = value
 307         #end
 308
 309         redef fun key
 310         do
 311                 assert is_ok
 312                 return _node.first
 313         end
 314
 315         redef fun next
 316         do
 317                 assert is_ok
 318                 _node = _node.next_item
 319         end
 320
 321         # The map to iterate on
 322         var _map: HashMap[K, V]
 323
 324         # The current node
 325         var _node: nullable HashMapNode[K, V]
 326
 327         init(map: HashMap[K, V])
 328         do
 329                 _map = map
 330                 _node = map.first_item
 331         end
 332 end
 333
 334 class HashSet[E]
 335 special Set[E]
 336 special HashCollection[E, HashSetNode[E], E]
 337
 338         redef fun is_empty do return _length == 0
 339
 340         redef fun first
 341         do
 342                 assert _length > 0
 343                 return _first_item.key
 344         end
 345
 346         redef fun has(item)
 347         do
 348                 return _array[index_at(item)] != null
 349         end
 350
 351         redef fun add(item)
 352         do
 353                 var i = index_at(item)
 354                 var c = _array[i]
 355                 if c != null then
 356                         c.key = item
 357                 else
 358                         store(i,new HashSetNode[E](item))
 359                 end
 360         end
 361
 362         redef fun remove(item) do remove_index(index_at(item))
 363
 364         redef fun clear do raz
 365
 366         redef fun iterator do return new HashSetIterator[E](self)
 367
 368         init
 369         do
 370                 _capacity = 0
 371                 _length = 0
 372                 enlarge(0)
 373         end
 374 end
 375
 376 class HashSetNode[E]
 377 special HashNode[E]
 378         redef type N: HashSetNode[E]
 379
 380         redef readable writable var _key: E
 381
 382         init(e: E)
 383         do
 384                 _key = e
 385         end
 386 end
 387
 388 class HashSetIterator[E]
 389 special Iterator[E]
 390         redef fun is_ok do return _node != null
 391
 392         redef fun item
 393         do
 394                 assert is_ok
 395                 return _node.key
 396         end
 397
 398         redef fun next
 399         do
 400                 assert is_ok
 401                 _node = _node.next_item
 402         end
 403
 404         # The set to iterate on
 405         var _set: HashSet[E]
 406
 407         # The position in the internal map storage
 408         var _node: nullable HashSetNode[E]
 409
 410         init(set: HashSet[E])
 411         do
 412                 _set = set
 413                 _node = set.first_item
 414         end
 415 end
 416