containers/ hashtable.bi

Summary
containers/ hashtable.bi
LicenseCopyright © 2009, FreeBASIC Extended Library Development Group
ext
Macros
FBEXT_DECLARE_HASHTABLE
Types
HashTableIterator(type)This is a prototype for a subroutine for iterating through a hashtable.
fbext_HashTable(T_)Simple to use but powerful HashTable overloaded for all built-in numerical types.
Functions
constructorDefines an initial size for the hashtable.
InsertInserts a value into the hashtable.
FindSearches for a key in the table.
FindSearches for a value in the table and returns its key.
ForEachIterates through the table calling the passed subroutine with each key pair.
RemoveSearches for a key in the table and removes it.
Properties
CountReturns the number of key pairs in the table.
Examples
Basic Usage of the HashTable Class
Using HashTable with UDTs
Simple HashTable Iterator example

License

Copyright © 2009, FreeBASIC Extended Library Development Group

Distributed under the FreeBASIC Extended Library Group license.  See accompanying file LICENSE.txt or copy at http://code.google.com- /p- /fb-extended-lib- /wiki- /License

ext

Summary
Macros
FBEXT_DECLARE_HASHTABLE
Types
HashTableIterator(type)This is a prototype for a subroutine for iterating through a hashtable.

Macros

FBEXT_DECLARE_HASHTABLE

Types

HashTableIterator(type)

type fbext_HashTableIterator(
   T_
) as sub ( byref key as const string, byval value as fbext_TypeName(T_) ptr )

This is a prototype for a subroutine for iterating through a hashtable.

fbext_HashTable(T_)

Simple to use but powerful HashTable overloaded for all built-in numerical types.

Notes

This class also supports UDTs.  The requirements for UDTs are:

  • A default constructor.
  • Operator let.
  • Operator = (equality).  If you are experiencing a large number of collisions, you should increase the size of the hashtable.

See Also

Basic Usage of the HashTable Class | Using HashTable with UDTs

Summary
Functions
constructorDefines an initial size for the hashtable.
InsertInserts a value into the hashtable.
FindSearches for a key in the table.
FindSearches for a value in the table and returns its key.
ForEachIterates through the table calling the passed subroutine with each key pair.
RemoveSearches for a key in the table and removes it.
Properties
CountReturns the number of key pairs in the table.
Examples
Basic Usage of the HashTable Class
Using HashTable with UDTs
Simple HashTable Iterator example

Functions

constructor

declare constructor (byval minsize as ext.SizeType)

Defines an initial size for the hashtable.  When necessary the HashTable will expand itself to ensure enough room for proper operation.

Parameters

minsizethe MINIMUM size of table to create, the actual table size could be larger.

Insert

declare sub Insert (byref key_ as string,
byref value as fbext_TypeName(T_))

Inserts a value into the hashtable.

Parameters

key_the string key to associate with the value.
valuethe value to insert into the table.

Usage

It is very important that you REMOVE a value with a key that would overlap another.  If the key is already located in the table, the value will NOT be overwritten.

Find

declare function Find (byref key_ as string) as fbext_TypeName(T_) ptr

Searches for a key in the table.

Parameters

key_the key to search for.

Returns

A pointer to value associated with the passed key.  This value is NOT removed from the table.

Find

declare function Find (byref value as const fbext_TypeName(T_)) as string

Searches for a value in the table and returns its key.

Parameters

valuethe value to search for.

Returns

String containing the key associated with a value or “” if the value was not found.

ForEach

declare sub ForEach (byval iter as fbext_HashTableIterator(T_))

Iterates through the table calling the passed subroutine with each key pair.

Parameters

iterthe address of the subroutine to call, this subroutine is of the type HashTableIterator(type).

Notes

You may freely change the value passed to the subroutine, but you may not change the key.  To change the key you must remove the current key from the table and insert a new one.

See Also

Simple HashTable Iterator example

Remove

declare sub Remove (byref key_ as string)

Searches for a key in the table and removes it.

Parameters

key_the key to search for.

Properties

Count

declare property Count ( ) as SizeType

Returns the number of key pairs in the table.

Examples

Basic Usage of the HashTable Class

# include once "ext/containers/hashtable.bi"

using ext

var myHT = HashTable(single)(16)

print "Count before insertion: " & myHT.count

print !"Inserting \"One\" as 1.0"
myHT.insert("One", 1.0)

print !"Inserting \"Two\" as 2.0"
myHT.insert("Two", 2.0)

print !"Inserting \"Three\" as 3.0"
myHT.insert("Three", 3.0)

print !"Inserting \"Tacos\" as 4.2"
myHT.insert("Tacos", 4.2)

print !"Inserting \"FBEXT\" as 5.6"
myHT.insert("FBEXT", 5.6)

print "Count after insertion: " & myHT.count

print "One: " & *(myHT.find("One"))

print "Removing Tacos"
myHT.remove("Tacos")

print "Two: " & *(myHT.find("Two"))

print "Removing Three"
myHT.remove("Three")

print "FBEXT: " & *(myHT.find("FBEXT"))

print "Count after 2 removes: " & myHT.count

Using HashTable with UDTs

# include once "ext/containers/hashtable.bi"

type UDT
   x as integer
   y as integer
   declare constructor( ) 'Required by ext.HashTable
   declare operator let( byref t as UDT ) 'Required by ext.HashTable
end type

constructor UDT( )
   x = 0
   y = 0
end constructor

'This operator is only used by the Find by value and return the key method,
'so if you are not using that method you can safely make this operator simply
'return 0
operator = ( byref lhs as UDT, byref rhs as UDT ) as integer 'Required by ext.HashTable
  return iif( (lhs.x + lhs.y) = ( rhs.x + rhs.y ), ext.true, ext.false )
end operator

operator UDT.let( byref t as UDT )
   this.x = t.x
   this.y = t.y
end operator

namespace ext 'must be declared within ext's namespace
fbext_Instanciate( fbExt_HashTable, ((UDT)) )
end namespace

dim as FBEXT_HASHTABLE(UDT) MyUDTHT(10)

dim as UDT t1, t2, t3

t1.x = 42  : t1.y = 12
t2.x = 134 : t2.y = 1
t3.x = 0   : t3.y = 396

MyUDTHT.Insert("First One", t1)
MyUDTHT.Insert("Third One", t3)
MyUDTHT.Insert("Ext Rocks", t2)

print MyUDTHT.Find("Ext Rocks")->x 'prints 134

Simple HashTable Iterator example

# include once "ext/containers/hashtable.bi"

declare sub MyIterator ( byref key as const string, byval value as integer ptr )

var MyHT = FBEXT_HASHTABLE(integer)(10)

for n as integer = 1 to 10
  MyHT.Insert("Number: " & n, n)
next

MyHT.ForEach( @MyIterator )

sub MyIterator ( byref key as const string, byval value as integer ptr )

  print !"\"" & key & !"\" => " & *value

end sub
type fbext_HashTableIterator(
   T_
) as sub ( byref key as const string, byval value as fbext_TypeName(T_) ptr )
This is a prototype for a subroutine for iterating through a hashtable.
declare constructor (byval minsize as ext.SizeType)
Defines an initial size for the hashtable.
declare sub Insert (byref key_ as string,
byref value as fbext_TypeName(T_))
Inserts a value into the hashtable.
declare function Find (byref key_ as string) as fbext_TypeName(T_) ptr
Searches for a key in the table.
declare sub ForEach (byval iter as fbext_HashTableIterator(T_))
Iterates through the table calling the passed subroutine with each key pair.
declare sub Remove (byref key_ as string)
Searches for a key in the table and removes it.
declare property Count ( ) as SizeType
Returns the number of key pairs in the table.