Author Topic: Dictionary / Hash list  (Read 3970 times)

Offline Slydog

  • Prof. Inline
  • *****
  • Posts: 932
  • KodeSource
    • View Profile
    • KodeSource
Dictionary / Hash list
« on: 2012-Apr-24 »
Here's a quick dictionary / hash library I created when first starting with GLBasic.
I have never used it (changed my mind!), and I don't think it was ever tested.
It was created for simplicity, and perhaps should not be used too much in your main game loop.
I haven't tested it so I don't know if it works, or how fast it is:

Oh, and it only works for storing numerical values (floats) against a string. 
It could easily be update for strings.
Code: (glbasic) [Select]
//==============================================================================
//  D I C T I O N A R Y
//==============================================================================
TYPE TDictionaryItem
name$
value
ENDTYPE

TYPE TDictionary
table[] AS TDictionaryItem

FUNCTION Clear:
DIM self.table[0]
ENDFUNCTION

FUNCTION Add: name$, value
// If 'name$' already exists, call 'Set' instead
IF self.Exists(name$)
self.Set(name$, value)
RETURN
ENDIF

LOCAL item AS TDictionaryItem
item.name$ = name$
item.value = value
DIMPUSH self.table[], item
ENDFUNCTION

FUNCTION Get: name$, defaultValue=-1
LOCAL rv# = defaultValue

FOREACH item IN self.table[]
IF item.name$ = name$
rv = item.value
BREAK
ENDIF
NEXT

RETURN rv
ENDFUNCTION

FUNCTION Set%: name$, value
// If the 'name$' doesn't exist in the table, call 'Add' instead
IF NOT self.Exists(name$)
self.Add(name$, value)
RETURN
ENDIF

FOREACH item IN self.table[]
IF item.name$ = name$
item.value = value
BREAK
ENDIF
NEXT
ENDFUNCTION

FUNCTION Exists%: name$
FOREACH item IN self.table[]
IF item.name$ = name$
RETURN TRUE
ENDIF
NEXT
RETURN FALSE
ENDFUNCTION

ENDTYPE

Usage:
Code: (glbasic) [Select]
GLOBAL salaries AS TDictionary
salaries.Clear()
salaries.Add("Peter", 49000)
salaries.Add("Paul", 58000)
salaries.Add("Mary", 63000)
DEBUG "Paul makes $" + salaries.Get("Paul") + " per year\n"

salaries.Set("Paul", 67000)
DEBUG "Paul now makes $" + salaries.Get("Paul") + " per year\n"

IF NOT salaries.Exists("Slydog") THEN DEBUG "Slydog doesn't exist in employee table"
« Last Edit: 2012-Apr-25 by Slydog »
My current project (WIP) :: TwistedMaze <<  [Updated: 2015-11-25]

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10759
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
Re: Dictionary / Hash list
« Reply #1 on: 2012-Apr-24 »
Many thanks. Very useful.

Here is an update. It's a string-string dictionary with sorted arrays for faster searching:
Code: (glbasic) [Select]
// --------------------------------- //
// Project: Glosses
// Start: Thursday, August 15, 2019
// IDE Version: 16.252

TYPE T_DictionaryPair
key$
val$
ENDTYPE

TYPE TDictionary
pairs[] AS T_DictionaryPair

// ------------------------------------------ //
//! Get string at given key
// ------------------------------------------ //
FUNCTION get$: key$
LOCAL i% = _index(key$, FALSE)
IF i>=0 THEN RETURN self.pairs[i].val$
RETURN ""
ENDFUNCTION

// ------------------------------------------ //
//! Set string at given key
// ------------------------------------------ //
FUNCTION set: key$, val$
LOCAL i% = _index(key$, TRUE)
self.pairs[i].val$ = val$
ENDFUNCTION

// ------------------------------------------ //
//! Get index in pairs[] for given string
// ------------------------------------------ //
FUNCTION _index%: BYREF name$, create%=TRUE
LOCAL up%, dn%, mid%
up=0; dn=LEN(self.pairs[])-1
WHILE up < dn
mid = (up+dn) / 2
IF self.pairs[mid].key$ > name$
dn=MAX(mid-1, up)
ELSE
IF self.pairs[mid].key$ < name$
up=MIN(dn, mid+1)
ELSE
RETURN mid // not bigger, not smaller, guess what!?
ENDIF
ENDIF
WEND

IF LEN(self.pairs[]) AND self.pairs[up].key$ = name$ THEN RETURN up

// not found. But must be at [up].
IF create%
dn = LEN(self.pairs[]) // one below last
REDIM self.pairs[dn+1]
FOR mid = dn TO up+1 STEP -1
self.pairs[mid] = self.pairs[mid-1]
NEXT
IF dn>0 AND self.pairs[up].key$ < name$ THEN up=up+1

ALIAS where AS self.pairs[up]
where.key$ = name$
where.val$ = ""
RETURN up
ENDIF
RETURN -1
ENDFUNCTION
ENDTYPE
« Last Edit: 2019-Aug-15 by Kitty Hello »

Offline 8bitBoss

  • Mc. Print
  • *
  • Posts: 15
  • May the force be with you
    • View Profile
    • http://astutekitsune.tumblr.com
Re: Dictionary / Hash list
« Reply #2 on: 2012-Apr-25 »
Dude, this is a great idea!
One of my feature requests were dictionaries but I didn't think about crafting them myself. I will borrow your idea and see what I can come up with  :good:
i7 2700k
16GB DDR3 RAM
GeForce GTX 560 Ti
Windows 7 Ultimate 64Bit