Dictionary, SortedList

[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! 

[SnooPI]

Yes Bigsofty, it's very interesting, thanks Gernot 

[Schranz0r]

I like those Stuff!
Can you put this into the examples?