Here's an integer associative array class I use in a few projects. It is a way to map one integer to another using a hash table. Adapted from the Aurora class that maps integers to strings. Feel free to adapt and use in your Emergence projects.
usage:
CIntAssoc test
test.Create()
test.Add(999,54545)
test.Add(123,14150)
print test.Lookup(999)
The source file:
autodefine "off"
$include "CIntAssoc.inc"
SUB CIntAssoc::CIntAssoc()
m_pHashTable = NULL
m_nHashTableSize = 17
m_nCount = 0
m_pFreeList = NULL
m_pBlocks = NULL
m_nBlockSize = 10
m_ListPlex = NULL
Endsub
SUB CIntAssoc::_CIntAssoc()
RemoveAll()
Endsub
SUB CIntAssoc::GetCount(),int
return m_nCount
Endsub
SUB CIntAssoc::Add(int key,int value)
UINT nHash:nHash = 0
POINTER pAssoc
pAssoc = GetAssocAt(key, nHash)
if (pAssoc = NULL)
IF (m_pHashTable = NULL)
InitHashTable(m_nHashTableSize)
ENDIF
'// it doesn't exist, add a new Association
pAssoc = NewAssoc()
#<IAssoc>pAssoc.nHashValue = nHash
#<IAssoc>pAssoc.key = key
'#<IAssoc>pAssoc.#<STRING>key = key
'// put into hash table
#<IAssoc>pAssoc.pNext = #<POINTER>m_pHashTable[nHash]
#<POINTER>m_pHashTable[nHash] = pAssoc
endif
#<IAssoc>pAssoc.value = value
'return pAssoc->value; // return new reference
RETURN 0
Endsub
SUB CIntAssoc::Create(OPT hashtablesize=17 as int,OPT blocksize=10 as int),int
if(blocksize > 0)
m_pHashTable = NULL
m_nHashTableSize = hashtablesize
m_nCount = 0
m_pFreeList = NULL
m_pBlocks = NULL
m_nBlockSize = BlockSize
m_ListPlex = ListCreate
return 1
endif
return 0
Endsub
SUB CIntAssoc::Free()
RemoveAll()
Endsub
SUB CIntAssoc::GetStartAssoc(),uint
IF m_nCount > 0 THEN RETURN -1
RETURN 0
Endsub
SUB CIntAssoc::GetNextAssoc(rNextPosition as uint BYREF),pointer
UINT nBucket
POINTER pAssocRet:pAssocRet = rNextPosition + 0
if (pAssocRet = -1)
'// find the first association
for nBucket = 0 TO m_nHashTableSize-1
pAssocRet = #<POINTER>m_pHashTable[nBucket]
if (pAssocRet <> NULL)
breakfor
endif
next nBucket
ENDIF
'// find next association
POINTER pAssocNext
pAssocNext = #<IAssoc>pAssocRet.pNext
if pAssocNext = NULL
'// go to next bucket
for nBucket = #<IAssoc>pAssocRet.nHashValue + 1 TO m_nHashTableSize-1
pAssocNext = #<POINTER>m_pHashTable[nBucket]
if pAssocNext <> NULL
breakfor
endif
next nBucket
endif
rNextPosition = pAssocNext+0
'// fill in return data
'rKey = pAssocRet->key;
'rValue = pAssocRet->value;
RETURN pAssocRet
Endsub
SUB CIntAssoc::GetKey(pAssoc as pointer),int
IF(pAssoc <> NULL)
RETURN #<IAssoc>pAssoc.key
ENDIF
Return 0
Endsub
SUB CIntAssoc::GetValue(pAssoc as pointer),int
IF(pAssoc <> NULL)
RETURN #<IAssoc>pAssoc.value
ENDIF
Return 0
Endsub
SUB CIntAssoc::Lookup(int key),int
UINT nHash:nHash = 0
POINTER pAssoc:pAssoc = GetAssocAt(key, nHash)
if (pAssoc = NULL)
return 0
endif
RETURN #<IAssoc>pAssoc.value
Endsub
SUB CIntAssoc::Remove(key as int),int
if (m_pHashTable = NULL) THEN return FALSE
POINTER ppAssocPrev
ppAssocPrev = &#<POINTER>m_pHashTable[HashKey(key) % m_nHashTableSize]
POINTER pAssoc
pAssoc = #<POINTER>ppAssocPrev
WHILE pAssoc <> NULL
if #<IAssoc>pAssoc.key = key
#<POINTER>ppAssocPrev = #<IAssoc>pAssoc.pNext
FreeAssoc(pAssoc)
return TRUE
endif
ppAssocPrev = &#<IAssoc>pAssoc.pNext
pAssoc = #<IAssoc>pAssoc.pNext
ENDWHILE
return FALSE
Endsub
SUB CIntAssoc::RemoveAll()
UINT nHash
POINTER pAssoc
if (m_pHashTable <> NULL)
for nHash = 0 to m_nHashTableSize - 1
'DebugPrint("Hash = " + str$(nHash))
pAssoc = #<POINTER>m_pHashTable[nHash]
WHILE pAssoc <> NULL
IF #<IAssoc>pAssoc.key <> 0
'DebugPrint(" Key:" + #<IAssoc>pAssoc.#<STRING>key)
'DELETE #<IAssoc>pAssoc.key
'DELETE #<IAssoc>pAssoc.value
ENDIF
pAssoc = #<IAssoc>pAssoc.pNext
ENDWHILE
next nHash
delete m_pHashTable
m_pHashTable = NULL
endif
m_nCount = 0
m_pFreeList = NULL
ListRemoveAll(m_ListPlex,TRUE)
m_ListPlex = NULL
Endsub
SUB CIntAssoc::InitHashTable(uint nHashSize, OPT bAllocNow=TRUE as int)
'//
'// Used to force allocation of a hash table or to override the default
'// hash table size of (which is fairly small)
if (m_pHashTable <> NULL)
'// free hash table
delete m_pHashTable
m_pHashTable = NULL
endif
if (bAllocNow)
m_pHashTable = new(UINT, nHashSize)
ENDIF
m_nHashTableSize = nHashSize
RETURN
Endsub
SUB CIntAssoc::NewAssoc(), pointer
POINTER pAssoc:pAssoc = NULL
POINTER newBlock:newBlock = NULL
INT i
if(1)
if (m_pFreeList = NULL)
'// add another block
pAssoc = ListAdd(m_ListPlex,new(CHAR,m_nBlockSize * LEN(IAssoc)))
'// chain them into free list
'// free in reverse order to make it easier to debug
pAssoc += (m_nBlockSize - 1) * LEN(IAssoc)
for i = m_nBlockSize-1 TO 0 STEP -1
#<IAssoc>pAssoc.pNext = m_pFreeList
m_pFreeList = pAssoc
pAssoc -= LEN(IAssoc)
next i
endif
pAssoc = m_pFreeList
m_pFreeList = #<IAssoc>m_pFreeList.pNext
m_nCount++
#<IAssoc>pAssoc.key = 0
#<IAssoc>pAssoc.value = 0
#<IAssoc>pAssoc.nHashValue = 0
endif
return pAssoc
Endsub
SUB CIntAssoc::GetAssocAt(key as int, nHash as uint BYREF),pointer
nHash = key % m_nHashTableSize
'DebugPrint("GetAssocAt nHash = "+str$(nHash))
if (m_pHashTable = NULL) then return NULL
'// see if it exists
POINTER pAssoc
pAssoc = #<POINTER>m_pHashTable[nHash]
WHILE pAssoc <> NULL
IF (#<IAssoc>pAssoc.key <> 0) AND (#<IAssoc>pAssoc.key = key) THEN return pAssoc
pAssoc = #<IAssoc>pAssoc.pNext
ENDWHILE
return NULL
Endsub
SUB CIntAssoc::HashKey(key as int),uint
UINT nHash:nHash = key
return nHash
Endsub
SUB CIntAssoc::FreeAssoc(pointer pAssoc)
#<IAssoc>pAssoc.pNext = m_pFreeList
m_pFreeList = pAssoc
m_nCount--
'// if no more elements, cleanup completely
if (m_nCount = 0)
Free()
endif
Endsub
The include file:
TYPE IAssoc
POINTER pNext
UINT nHashValue
INT key
INT value
ENDTYPE
Class CIntAssoc
Declare CIntAssoc()
Declare _CIntAssoc()
Declare Add(int key,int value)
Declare Create(OPT hashtablesize=17 as int,OPT blocksize=10 as int),int
Declare Free()
Declare GetStartAssoc(),uint
Declare GetNextAssoc(rNextPosition as uint BYREF),pointer
Declare GetKey(pAssoc as pointer),int
Declare GetValue(pAssoc as pointer),int
Declare Lookup(int key),int
Declare Remove(key as int),int
Declare RemoveAll()
Declare InitHashTable(uint nHashSize, OPT bAllocNow=TRUE as int)
Declare NewAssoc(), pointer
Declare GetAssocAt(key as int, nHash as uint BYREF),pointer
Declare HashKey(key as int),uint
Declare FreeAssoc(pointer pAssoc)
Declare GetCount(),int
Protected
POINTER m_pHashTable
UINT m_nHashTableSize
int m_nCount
POINTER m_pFreeList
POINTER m_pBlocks
int m_nBlockSize
POINTER m_ListPlex
Endclass
Notes:
The hash is generated by the remainder of the integer key with the hash table size. For large key ranges increase the hash table size for more speed if needed.
The class can also be used to map an integer to a pointer, which is useful for associating data with control or menu id's
pointer pData
pData = store.Lookup(menuid)
Add the source file to your project, and include the include file in any source file you are using the class in.
Paul,