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