lib/standard/hash.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2008 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 # This module is about hashable things.
  14 # It introduces an hash funtion in objects.
  15 # It also introduces two classes, an Hashmap and an Hashset.
  16 package hash
  17
  18 intrude import string
  19
  20 redef class Object
  21         # The hash code of the object.
  22         # Assuming that a = b -> a.hash = b.hash
  23         ##
  24         # Without redefinition, it is the `id' of the instance.
  25         meth hash: Int do return object_id / 8
  26 end
  27
  28 redef class String
  29         redef meth hash
  30         do
  31                 # djb2 hash algorythm
  32                 var h = 5381
  33                 var i = _length - 1
  34                 var it = _items
  35                 while i >= 0 do
  36                         h = (h * 32) + h + it[i].ascii
  37                         i -= 1
  38                 end
  39                 return h
  40
  41         end
  42 end
  43
  44 redef class Int
  45         redef meth hash do return self
  46 end
  47
  48 redef class Char
  49         redef meth hash do return ascii
  50 end
  51
  52 redef class Bool
  53         redef meth hash
  54         do
  55                 if self then
  56                         return 1
  57                 else
  58                         return 0
  59                 end
  60         end
  61 end
  62
  63 # A HashCollection is an array of HashNode[K] indexed by the K hash value
  64 private class HashCollection[K: Object, N: HashNode[K], E]
  65 special Collection[E]
  66 special ArrayCapable[nullable N]
  67         attr _array: nullable NativeArray[nullable N] = null # Used to store items
  68         attr _capacity: Int = 0 # Size of _array
  69         redef readable attr _length: Int = 0 # Number of items in the map
  70
  71         readable attr _first_item: nullable N = null # First added item (used to visit items in nice order)
  72         attr _last_item: nullable N = null # Last added item (same)
  73
  74         # The last index accessed
  75         attr _last_accessed_index: Int = -1
  76
  77         # The last key accessed
  78         attr _last_accessed_key: nullable K = null
  79
  80         # Return the index of the k element
  81         meth index_at(k: K): Int
  82         do
  83                 var arr = _array
  84
  85                 # Fisrt step: look in the last indexed elt
  86                 if k == _last_accessed_key then return _last_accessed_index
  87
  88                 # Compute the base position of the key
  89                 var base = k.hash % _capacity
  90                 if base < 0 then base = - base
  91
  92                 # Look for the key in the array
  93                 var cur = base
  94                 while true do
  95                         var c = arr[cur]
  96                         if c == null or c.key == k then # REAL equals
  97                                 _last_accessed_index = cur
  98                                 _last_accessed_key = k
  99                                 return cur
 100                         end
 101                         cur -= 1
 102                         if cur < 0 then cur = _capacity - 1
 103                         assert no_loop: cur != base
 104                 end
 105                 abort
 106         end
 107
 108         # Add a new node (should be free)
 109         meth store(index: Int, node: N)
 110         do
 111                 # Store the item in the list
 112                 if _first_item == null then
 113                         _first_item = node
 114                 else
 115                         _last_item.next_item = node
 116                 end
 117                 node.prev_item = _last_item
 118                 node.next_item = null
 119                 _last_item = node
 120                 # Then store it in the array
 121                 assert _array[index] == null
 122                 _array[index] = node
 123                 var l = _length
 124                 _length = l + 1
 125                 l = (l + 5) * 150 / 100
 126                 if l >= _capacity then
 127                         enlarge(l * 2)
 128                 end
 129         end
 130
 131         meth remove_index(i: Int)
 132         do
 133                 assert correct_index: i >= 0 and i < _capacity
 134                 var node = _array[i]
 135                 assert has_couple: node != null
 136                 # Remove the item in the list
 137                 var prev = node.prev_item
 138                 var next = node.next_item
 139                 if prev != null then
 140                         prev.next_item = next
 141                 else
 142                         _first_item = next
 143                 end
 144                 if next != null then
 145                         next.prev_item = prev
 146                 else
 147                         _last_item = prev
 148                 end
 149                 # Remove the item in the array
 150                 _array[i] = null
 151                 _length -= 1
 152                 # Now replaces things before if needed
 153                 while true do
 154                         i -= 1
 155                         if i < 0 then
 156                                 i = _capacity - 1
 157                         end
 158                         var n = _array[i]
 159                         if n == null then
 160                                 return
 161                         end
 162                         var i2 = index_at(n.key)
 163                         if i != i2 then
 164                                 _array[i] = null
 165                                 assert _array[i2] == null
 166                                 _array[i2] = n
 167                         end
 168                 end
 169         end
 170
 171         meth raz
 172         do
 173                 var i = _capacity - 1
 174                 while i >= 0 do
 175                         _array[i] = null
 176                         i -= 1
 177                 end
 178                 _length = 0
 179                 _first_item = null
 180                 _last_item = null
 181                 _last_accessed_key = null
 182         end
 183
 184         meth enlarge(cap: Int)
 185         do
 186                 var old_cap = _capacity
 187                 # get a new capacity
 188                 # cap = cap * 130 / 100 + 5 + 1000 # /
 189                 if cap < _length + 1 then cap = _length + 1
 190                 if cap <= _capacity then return
 191                 _capacity = cap
 192                 _last_accessed_key = null
 193
 194                 # get a new array
 195                 var new_array = calloc_array(cap)
 196                 _array = new_array
 197
 198                 # clean the new array
 199                 var i = cap - 1
 200                 while i >=0 do
 201                         new_array[i] = null
 202                         i -= 1
 203                 end
 204
 205                 if _capacity <= old_cap then return
 206
 207                 var new_array = _array
 208                 # Reput items in the array
 209                 var node = _first_item
 210                 while node != null do
 211                         var ind = index_at(node.key)
 212                         assert new_array[ind] == null
 213                         new_array[ind] = node
 214                         node = node.next_item
 215                 end
 216                 _last_accessed_key = null
 217         end
 218 end
 219
 220 private class HashNode[K]
 221         meth key: K is abstract
 222         type N: HashNode[K]
 223         readable writable attr _next_item: nullable N = null
 224         readable writable attr _prev_item: nullable N = null
 225 end
 226
 227 class HashMap[K, V]
 228 special CoupleMap[K, V]
 229 special HashCollection[K, HashMapNode[K, V], V]
 230
 231         redef meth iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
 232
 233         redef meth first
 234         do
 235                 assert _length > 0
 236                 return _first_item.second
 237         end
 238
 239         redef meth is_empty do return _length == 0
 240
 241         redef meth count(item)
 242         do
 243                 var nb = 0
 244                 var i = 0
 245                 while i < _capacity do
 246                         var c = _array[i]
 247                         if c != null and c.second == item then nb += 1
 248                         i += 1
 249                 end
 250                 return nb
 251         end
 252
 253         redef meth has(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 return true
 259                         i += 1
 260                 end
 261                 return false
 262         end
 263
 264         redef meth has_only(item)
 265         do
 266                 var i = 0
 267                 while i < _capacity do
 268                         var c = _array[i]
 269                         if c != null and c.second != item then return false
 270                         i += 1
 271                 end
 272                 return true
 273         end
 274
 275         redef meth []=(key, v)
 276         do
 277                 assert key != null
 278                 var i = index_at(key)
 279                 var c = _array[i]
 280                 if c != null then
 281                         c.first = key
 282                         c.second = v
 283                 else
 284                         store(i, new HashMapNode[K, V](key, v))
 285                 end
 286         end
 287
 288         redef meth remove(item)
 289         do
 290                 var i = 0
 291                 while i < _capacity do
 292                         var c = _array[i]
 293                         if c != null and c.second == item then
 294                                 remove_index(i)
 295                                 return
 296                         end
 297                         i += 1
 298                 end
 299         end
 300
 301         redef meth remove_at(key) do remove_index(index_at(key))
 302
 303         redef meth clear do raz
 304
 305         redef meth couple_at(key) do return _array[index_at(key)]
 306
 307         init
 308         do
 309                 _capacity = 0
 310                 _length = 0
 311                 enlarge(0)
 312         end
 313 end
 314
 315 class HashMapNode[K, V]
 316 special Couple[K, V]
 317 special HashNode[K]
 318         redef meth key do return first
 319         redef type N: HashMapNode[K, V]
 320
 321         init(k: K, v: V)
 322         do
 323                 first = k
 324                 second = v
 325         end
 326 end
 327
 328 class HashMapIterator[K, V]
 329 special MapIterator[K, V]
 330         redef meth is_ok do return _node != null
 331
 332         redef meth item
 333         do
 334                 assert is_ok
 335                 return _node.second
 336         end
 337
 338         #redef meth item=(value)
 339         #do
 340         #       assert is_ok
 341         #       _node.second = value
 342         #end
 343
 344         redef meth key
 345         do
 346                 assert is_ok
 347                 return _node.first
 348         end
 349
 350         redef meth next
 351         do
 352                 assert is_ok
 353                 _node = _node.next_item
 354         end
 355
 356         # The map to iterate on
 357         attr _map: HashMap[K, V]
 358
 359         # The current node
 360         attr _node: nullable HashMapNode[K, V]
 361
 362         init(map: HashMap[K, V])
 363         do
 364                 _map = map
 365                 _node = map.first_item
 366         end
 367 end
 368
 369 class HashSet[E]
 370 special Set[E]
 371 special HashCollection[E, HashSetNode[E], E]
 372
 373         redef meth is_empty do return _length == 0
 374
 375         redef meth first
 376         do
 377                 assert _length > 0
 378                 return _first_item.key
 379         end
 380
 381         redef meth has(item)
 382         do
 383                 return _array[index_at(item)] != null
 384         end
 385
 386         redef meth add(item)
 387         do
 388                 var i = index_at(item)
 389                 var c = _array[i]
 390                 if c != null then
 391                         c.key = item
 392                 else
 393                         store(i,new HashSetNode[E](item))
 394                 end
 395         end
 396
 397         redef meth remove(item) do remove_index(index_at(item))
 398
 399         redef meth clear do raz
 400
 401         redef meth iterator do return new HashSetIterator[E](self)
 402
 403         init
 404         do
 405                 _capacity = 0
 406                 _length = 0
 407                 enlarge(0)
 408         end
 409 end
 410
 411 class HashSetNode[E]
 412 special HashNode[E]
 413         redef type N: HashSetNode[E]
 414
 415         redef readable writable attr _key: E
 416
 417         init(e: E)
 418         do
 419                 _key = e
 420         end
 421 end
 422
 423 class HashSetIterator[E]
 424 special Iterator[E]
 425         redef meth is_ok do return _node != null
 426
 427         redef meth item
 428         do
 429                 assert is_ok
 430                 return _node.key
 431         end
 432
 433         redef meth next
 434         do
 435                 assert is_ok
 436                 _node = _node.next_item
 437         end
 438
 439         # The set to iterate on
 440         attr _set: HashSet[E]
 441
 442         # The position in the internal map storage
 443         attr _node: nullable HashSetNode[E]
 444
 445         init(set: HashSet[E])
 446         do
 447                 _set = set
 448                 _node = set.first_item
 449         end
 450 end
 451