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