[bb] Container: hash table by octothorpe [ 1+ years ago ]

Started by BlitzBot, June 29, 2017, 00:28:42

Previous topic - Next topic

BlitzBot

Title : Container: hash table
Author : octothorpe
Posted : 1+ years ago

Description : This library makes it painless to add many independant hash table containers for many different types of objects. This is done by storing Handle()s to your objects. Each container should hold objects of only one type.  For more information on containers, an example of how to use them, and a tutorial, <a href="../Community/posts8333.html?topic=53352" target="_blank">click here</a>.

A hash table (or map, or dictionary) is similar to an array, but you refer to elements with a key$ instead of an index%.  You also don't have to worry about the size of the container.

This library is dependant upon <a href="codearcs0d6f.html?code=1438" >Container: double-linked list</a>

For an example of how to use this library, scroll down to the test() function at the very bottom.  This code will run standalone if you uncomment the line at the top which runs the test code.
Please post bugs or feature requests in comments.
Fundamentals

hash_new.hashC()
- create a new hash
hash_destroy(our_hash.hashC)
- delete a hash and all of its elements

Standard Operations

hash_set(our_hash.hashC, key$, value)
- set a key-value pair in a hash
hash_exists(our_hash.hashC, key$)
- check to see if a key exists in a hash
hash_delete(our_hash.hashC, key$)
- delete a key-value pair in a hash, returning the value
hash_get(our_hash.hashC, key$)
- get a value from a hash by its key$
hash_count(our_hash.hashC)
- return the number of elements in the hash

Iterators

; for item.type = each our_hash
it.hashC_iter = hash_iterator_begin(our_hash)
while hash_iterator_next(it)
key$      = hash_iterator_get_key$(it)
item.type = object.type(hash_iterator_get_value(it))
; do stuff with key$ and item
wend


Convenience

hash_get_list.listC(our_hash.hashC, key$)
- get a list from a hash by its key$, autovivifying (for hashes-of-lists)
---

The Code [/i]

Code :
Code (blitzbasic) Select
;test_hashC()

; ------------------------------------------------------------------------------
;= TO DO
; ------------------------------------------------------------------------------
; iterator sanity checking (try to catch problems which might be caused by deleting elements while iterating)
; replace hashCucket[] array with a vectorC so hashes aren't all forced to share the same number of buckets?

; ------------------------------------------------------------------------------
;= CHANGE LOG
; ------------------------------------------------------------------------------
; 12/11/2005 - iterator sample usage for quick copying and pasting
; 06/11/2005 - new() for forwards compatibility
; 06/11/2005 - dropped humpBack notation in favour of under_score
; 06/11/2005 - sexy new hash_get_list() function for hashes-of-lists
; 03/11/2005 - renamed class from hashType
; 02/11/2005 - iterators now treat null hash objects as empty hashes
; 02/11/2005 - added hash_destroy, iterators

; ------------------------------------------------------------------------------
;= INCLUDES
; ------------------------------------------------------------------------------
include "listC.bb" ; http://blitzbasic.com/codearcs/codearcs.php?code=1438

; ------------------------------------------------------------------------------
;= CONSTANTS
; ------------------------------------------------------------------------------
const HASH_MAX_BUCKETS = 512
; more buckets will make lookups faster in crowded hashes, but will use more memory
; theoretically, overhead memory usage is (buckets * 16 bytes)

; ------------------------------------------------------------------------------
;= TYPES
; ------------------------------------------------------------------------------
type hashC
field bucket.listC[HASH_MAX_BUCKETS-1]          ; a list of hashC_elems
field elements%
end type

type hashC_elem
field key$
field value
end type

type hashC_iter
field hash.hashC
field current_bucket%
field current_node.listC_node
field next_node.listC_node                      ; keep track of this so we can safely delete the current_node
end type

; ------------------------------------------------------------------------------
;= FUNDAMENTAL
; ------------------------------------------------------------------------------

; ------------------------------------------------------------------------------
function hash_new.hashC()
; create a new hash

return new hashC
end function

; ------------------------------------------------------------------------------
function hash_destroy(our_hash.hashC)
; delete a hash and all of its elements

if our_hash = null then runtimeerror("not a valid hashC: null")

; loop through each bucket
for bucket_index% = 0 to HASH_MAX_BUCKETS-1
local this_element_list.listC = our_hashucket[bucket_index]

if this_element_list <> null then
; loop through each node in each bucket's list
local this_node.listC_node = this_element_listfirst_node
while this_node <> null
; destroy the element
delete object.hashC_elem(this_nodevalue)
; advance to next node in list
this_node = this_node
ext_node
wend
; destroy the bucket
list_destroy(this_element_list)
endif
next
; destroy the hash
delete our_hash
end function

; ------------------------------------------------------------------------------
function hash_set(our_hash.hashC, key$, value)
; set a key-value pair in a hash

if our_hash = null then runtimeerror("not a valid hashC: null")

; find the appropriate bucket
local our_element_list.listC = hash_choose_bucket(our_hash, key$)

; look for an element with a matching key
local this_node.listC_node = our_element_listfirst_node
while this_node <> null
local this_element.hashC_elem = object.hashC_elem(this_nodevalue)

; if the keys match, update the value and return from the function
if (this_elementkey$ = key$) then
this_elementvalue = value
return
endif

; look at the next node
this_node = this_node
ext_node
wend

; if we didn't find an element to update, add a new element
local new_element.hashC_elem = new hashC_elem
new_elementkey$  = key$
new_elementvalue = value
list_push(our_element_list, handle(new_element))

; update element count
our_hashelements = our_hashelements + 1

end function

; ------------------------------------------------------------------------------
function hash_exists(our_hash.hashC, key$)
; check to see if a key exists in a hash

if our_hash = null then runtimeerror("not a valid hashC: null")

if (hash_get(our_hash, key$) > 0) then
return true
else
return false
endif

end function

; ------------------------------------------------------------------------------
function hash_delete(our_hash.hashC, key$)
; delete a key-value pair in a hash, returning the value

if our_hash = null then runtimeerror("not a valid hashC: null")

; find the appropriate bucket
local our_element_list.listC = hash_choose_bucket(our_hash, key$)

; look for an element with a matching key
local this_node.listC_node = our_element_listfirst_node
while this_node <> null
local this_element.hashC_elem = object.hashC_elem(this_nodevalue)

; if the keys match, remove this element and return the value
if (this_elementkey$ = key$) then
local value = this_elementvalue
delete this_element
list_remove_node(this_node)

; update element count
our_hashelements = our_hashelements - 1

return value
endif

; look at the next node
this_node = this_node
ext_node
wend

; if we didn't find an element to update, return 0
return 0


end function

; ------------------------------------------------------------------------------
function hash_get(our_hash.hashC, key$)
; get a value from a hash by its key$

if our_hash = null then runtimeerror("not a valid hashC: null")

; find the appropriate bucket
local our_element_list.listC = hash_choose_bucket(our_hash, key$)

; look for an element with a matching key
local this_node.listC_node = our_element_listfirst_node
while this_node <> null
local this_element.hashC_elem = object.hashC_elem(this_nodevalue)

; if the keys match, update the value and return from the function
if (this_elementkey$ = key$) then
return this_elementvalue
endif

; look at the next node
this_node = this_node
ext_node
wend

; we didn't find the key, so return 0
return 0
end function

; ------------------------------------------------------------------------------
function hash_count(our_hash.hashC)
; return the number of elements in the hash

if our_hash = null then runtimeerror("not a valid hashC: null")
return our_hashelements
end function

; ------------------------------------------------------------------------------
;= INTERNAL
; ------------------------------------------------------------------------------

; ------------------------------------------------------------------------------
function hash_choose_bucket.listC(our_hash.hashC, key$)
; return the linked list which corresponds with the key$

; find the appropriate bucket index
local bucket_index% = hash_key_to_bucket_index(key$, HASH_MAX_BUCKETS)

; make sure bucket has been initialized
if (our_hashucket[bucket_index%] = null) then
our_hashucket[bucket_index%] = list_new()
endif

return our_hashucket[bucket_index%]

end function

; ------------------------------------------------------------------------------
function hash_key_to_bucket_index%(key$, modulus%)
; come up with an index for any string, dependably coming up with the same index
; for the same string, and attempting to distribute strings evenly over the
; available indexes

local bucket_index%

local character_index
for character_index = 1 to len(key$)
local character$ = mid$(key$, character_index, 1)
bucket_index% = (bucket_index% * 123) + asc(character)            ; arbitrary math, whee!
next

; force the index to be valid (overflows might make the number negative)
bucket_index% = abs(bucket_index% mod modulus)

return bucket_index%

end function

; ------------------------------------------------------------------------------
;= ITERATORS
; ------------------------------------------------------------------------------

; sample usage

; ; for item.type = each hash
; it.hashC_iter = hash_iterator_begin(hash)
; while hash_iterator_next(it)
; key$      = hash_iterator_get_key$(it)
; item.type = object.type(hash_iterator_get_value(it))
; wend

; ------------------------------------------------------------------------------
function hash_iterator_begin.hashC_iter(our_hash.hashC)
; create a new iterator for traversing the hash
; note that elements will be returned in arbitrary order!

it.hashC_iter = new hashC_iter
if our_hash <> null then
ithash = our_hash
itcurrent_bucket = -1
itcurrent_node = null
it
ext_node = null
endif
return it
end function

; ------------------------------------------------------------------------------
function hash_iterator_next(it.hashC_iter)
; advance the iterator to the next item in the hash

; drop out immediately if this iterator is void
if ithash = null then return false
; if we aren't already going through a bucket's list, advance until we find one
while (it
ext_node = null)
itcurrent_bucket = itcurrent_bucket + 1
; if we've run out of buckets, delete the iterator and return false
if itcurrent_bucket >= HASH_MAX_BUCKETS then
delete it
return false
endif

local bucket_list.listC = ithashucket[itcurrent_bucket]
if (bucket_list <> null) then
; try the first node of this bucket
; (if the bucket list is empty, this will be null and the next bucket will be tried,
;  otherwise the last part of this function will advance us onto this node)
it
ext_node = bucket_listfirst_node
endif
wend
; while we're in a bucket list, simply advance to the next node
itcurrent_node = it
ext_node
it
ext_node = itcurrent_node
ext_node
return true
end function

; ------------------------------------------------------------------------------
function hash_iterator_get_key$(it.hashC_iter)
; return the key of the element the iterator is currently on

local this_element.hashC_elem = object.hashC_elem(itcurrent_nodevalue)
return this_elementkey$
end function

; ------------------------------------------------------------------------------
function hash_iterator_get_value(it.hashC_iter)
; return the key of the element the iterator is currently on

local this_element.hashC_elem = object.hashC_elem(itcurrent_nodevalue)
return this_elementvalue
end function

; ------------------------------------------------------------------------------
;= CONVENIENCE
; ------------------------------------------------------------------------------

; ------------------------------------------------------------------------------
function hash_get_list.listC(our_hash.hashC, key$)
; get a list from a hash by its key$, autovivifying (for hashes-of-lists)

if our_hash = null then runtimeerror("not a valid hashC: null")

list.listC = object.listC(hash_get(our_hash, key$))
if list = null then
list = list_new()
hash_set(our_hash, key$, handle(list))
endif
return list
end function

; ------------------------------------------------------------------------------
;= TESTING
; ------------------------------------------------------------------------------
type hash_sample_type
field value$
end type
function hash_sample_type_new.hash_sample_type(value$)
i.hash_sample_type = new hash_sample_type
ivalue$ = value$
return i
end function
function test_hashC()
print "test_hashC()"

local our_hash.hashC = new hashC

hash_set(our_hash, "apples", 1)
hash_set(our_hash, "oranges", 2)
hash_set(our_hash, "bananas", 8)

print "displaying all elements..."
it.hashC_iter = hash_iterator_begin(our_hash)
while hash_iterator_next(it)
key$ = hash_iterator_get_key$(it)
value = hash_iterator_get_value(it)
print key$ + " => " + value
wend

hash_delete(our_hash, "apples")
hash_delete(our_hash, "bananas")
hash_delete(our_hash, "grapefruit")

print hash_get(our_hash, "oranges")
print hash_exists(our_hash, "oranges")
print hash_delete(our_hash, "oranges")
print hash_get(our_hash, "oranges")
print hash_exists(our_hash, "oranges")

print "displaying all elements..."
it.hashC_iter = hash_iterator_begin(our_hash)
while hash_iterator_next(it)
key$ = hash_iterator_get_key$(it)
value = hash_iterator_get_value(it)
print key$ + " => " + value
wend

hash_destroy(our_hash)

; test new hash_get_list() function
print "test new hash_get_list() function..."

local HoL.hashC = new hashC

list_push(hash_get_list(HoL, "milk"), handle(hash_sample_type_new("cow")))
list_push(hash_get_list(HoL, "milk"), handle(hash_sample_type_new("goat")))
list_push(hash_get_list(HoL, "cheese"), handle(hash_sample_type_new("gouda")))
list_push(hash_get_list(HoL, "cheese"), handle(hash_sample_type_new("edam")))
list_push(hash_get_list(HoL, "cheese"), handle(hash_sample_type_new("cheddar")))

it.hashC_iter = hash_iterator_begin(HoL)
while hash_iterator_next(it)
key$ = hash_iterator_get_key$(it)
value = hash_iterator_get_value(it)

print key$ + ":"

list_it.listC_iter = list_iterator_begin(object.listC(value))
while list_iterator_next(list_it)
i.hash_sample_type = object.hash_sample_type(list_iterator_get(list_it))

print "  " + ivalue$

wend
wend

print "press any key to exit..."
waitkey
end

end function


Comments : none...