Dictionary, SortedList

Previous topic - Next topic

Kitty Hello

Here's an improved version of the Dictionary and a Sorted List for strings. I'll include that into the GLBasic Samples folder, because it's very handy, okay?
Code (glbasic) Select

// --------------------------------- //
// Project: T_Dictionary
// Start: Friday, August 16, 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


TYPE TSortedSet
keys$[]

// ------------------------------------------ //
//! Get string at given key
// ------------------------------------------ //
FUNCTION isSet%: key$
LOCAL i% = _index(key$, FALSE)
IF i>=0 THEN RETURN TRUE
RETURN FALSE
ENDFUNCTION

// ------------------------------------------ //
//! Set string at given key
// ------------------------------------------ //
FUNCTION insert%: key$
_index(key$, TRUE)
ENDFUNCTION

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

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

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

self.keys$[up] = name$
RETURN up
ENDIF
RETURN -1
ENDFUNCTION
ENDTYPE



Test program
Code (glbasic) Select

LOCAL sose AS TSortedSet

sose.insert("cat")
sose.insert("mouse")
sose.insert("dog")
sose.insert("bird")
STDOUT "isset dog " + sose.isSet("dog") + "\n"
STDOUT "isset rat " + sose.isSet("rat") + "\n"
FOREACH k$ IN sose.keys$[]
STDOUT "-" + k$ + "\n"
NEXT

STDOUT "------------------\n"

LOCAL dict AS TDictionary

dict.set("cats", 5)
dict.set("mice", 7)
dict.set("dogs", "many")
dict.set("birds", "any")
STDOUT "dogs: " + dict.get$("dogs") + "\n"
STDOUT "rats: " + dict.get$("rats") + "\n"
FOREACH p IN dict.pairs[]
STDOUT "-" + p.key$ + " = " + p.val$ + "\n"
NEXT
KEYWAIT



Here's the output
Code (glbasic) Select

isset dog 1
isset rat 0
-bird
-cat
-dog
-mouse
------------------
dogs: many
rats:
-birds = any
-cats = 5
-dogs = many
-mice = 7


bigsofty

Handy, thanks Gernot!  :good:
Cheers,

Ian.

"It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration."
(E. W. Dijkstra)

SnooPI

Yes Bigsofty, it's very interesting, thanks Gernot  :)

Schranz0r

I like those Stuff! :)
Can you put this into the examples?
I <3 DGArray's :D

PC:
AMD Ryzen 7 3800X 16@4.5GHz, 16GB Corsair Vengeance LPX DDR4-3200 RAM, ASUS Dual GeForce RTX™ 3060 OC Edition 12GB GDDR6, Windows 11 Pro 64Bit, MSi Tomahawk B350 Mainboard