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

Offline Slydog

  • Prof. Inline
  • *****
  • Posts: 930
  • 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: 10708
  • 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