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                 while true do
  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                 while true do
 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 first
 189         do
 190                 assert _length > 0
 191                 return _first_item.second
 192         end
 193
 194         redef fun is_empty do return _length == 0
 195
 196         redef fun count(item)
 197         do
 198                 var nb = 0
 199                 var i = 0
 200                 while i < _capacity do
 201                         var c = _array[i]
 202                         if c != null and c.second == item then nb += 1
 203                         i += 1
 204                 end
 205                 return nb
 206         end
 207
 208         redef fun has(item)
 209         do
 210                 var i = 0
 211                 while i < _capacity do
 212                         var c = _array[i]
 213                         if c != null and c.second == item then return true
 214                         i += 1
 215                 end
 216                 return false
 217         end
 218
 219         redef fun has_only(item)
 220         do
 221                 var i = 0
 222                 while i < _capacity do
 223                         var c = _array[i]
 224                         if c != null and c.second != item then return false
 225                         i += 1
 226                 end
 227                 return true
 228         end
 229
 230         redef fun []=(key, v)
 231         do
 232                 assert key != null
 233                 var i = index_at(key)
 234                 var c = _array[i]
 235                 if c != null then
 236                         c.first = key
 237                         c.second = v
 238                 else
 239                         store(i, new HashMapNode[K, V](key, v))
 240                 end
 241         end
 242
 243         redef fun remove(item)
 244         do
 245                 var i = 0
 246                 while i < _capacity do
 247                         var c = _array[i]
 248                         if c != null and c.second == item then
 249                                 remove_index(i)
 250                                 return
 251                         end
 252                         i += 1
 253                 end
 254         end
 255
 256         redef fun remove_at(key) do remove_index(index_at(key))
 257
 258         redef fun clear do raz
 259
 260         redef fun couple_at(key) do return _array[index_at(key)]
 261
 262         init
 263         do
 264                 _capacity = 0
 265                 _length = 0
 266                 enlarge(0)
 267         end
 268 end
 269
 270 class HashMapNode[K, V]
 271 special Couple[K, V]
 272 special HashNode[K]
 273         redef fun key do return first
 274         redef type N: HashMapNode[K, V]
 275
 276         init(k: K, v: V)
 277         do
 278                 first = k
 279                 second = v
 280         end
 281 end
 282
 283 class HashMapIterator[K, V]
 284 special MapIterator[K, V]
 285         redef fun is_ok do return _node != null
 286
 287         redef fun item
 288         do
 289                 assert is_ok
 290                 return _node.second
 291         end
 292
 293         #redef fun item=(value)
 294         #do
 295         #       assert is_ok
 296         #       _node.second = value
 297         #end
 298
 299         redef fun key
 300         do
 301                 assert is_ok
 302                 return _node.first
 303         end
 304
 305         redef fun next
 306         do
 307                 assert is_ok
 308                 _node = _node.next_item
 309         end
 310
 311         # The map to iterate on
 312         var _map: HashMap[K, V]
 313
 314         # The current node
 315         var _node: nullable HashMapNode[K, V]
 316
 317         init(map: HashMap[K, V])
 318         do
 319                 _map = map
 320                 _node = map.first_item
 321         end
 322 end
 323
 324 class HashSet[E]
 325 special Set[E]
 326 special HashCollection[E, HashSetNode[E], E]
 327
 328         redef fun is_empty do return _length == 0
 329
 330         redef fun first
 331         do
 332                 assert _length > 0
 333                 return _first_item.key
 334         end
 335
 336         redef fun has(item)
 337         do
 338                 return _array[index_at(item)] != null
 339         end
 340
 341         redef fun add(item)
 342         do
 343                 var i = index_at(item)
 344                 var c = _array[i]
 345                 if c != null then
 346                         c.key = item
 347                 else
 348                         store(i,new HashSetNode[E](item))
 349                 end
 350         end
 351
 352         redef fun remove(item) do remove_index(index_at(item))
 353
 354         redef fun clear do raz
 355
 356         redef fun iterator do return new HashSetIterator[E](self)
 357
 358         init
 359         do
 360                 _capacity = 0
 361                 _length = 0
 362                 enlarge(0)
 363         end
 364 end
 365
 366 class HashSetNode[E]
 367 special HashNode[E]
 368         redef type N: HashSetNode[E]
 369
 370         redef readable writable var _key: E
 371
 372         init(e: E)
 373         do
 374                 _key = e
 375         end
 376 end
 377
 378 class HashSetIterator[E]
 379 special Iterator[E]
 380         redef fun is_ok do return _node != null
 381
 382         redef fun item
 383         do
 384                 assert is_ok
 385                 return _node.key
 386         end
 387
 388         redef fun next
 389         do
 390                 assert is_ok
 391                 _node = _node.next_item
 392         end
 393
 394         # The set to iterate on
 395         var _set: HashSet[E]
 396
 397         # The position in the internal map storage
 398         var _node: nullable HashSetNode[E]
 399
 400         init(set: HashSet[E])
 401         do
 402                 _set = set
 403                 _node = set.first_item
 404         end
 405 end
 406