1

**Userlibs [ *.gbal] / Dictionary, SortedList**

« **on:**2021-Feb-05 »

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?

Test program

Here's the output

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