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