Author Topic: Dictionary, SortedList  (Read 880 times)

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10815
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
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?
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

Offline bigsofty

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 2747
    • View Profile
Re: Dictionary, SortedList
« Reply #1 on: 2021-Feb-05 »
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)

Offline SnooPI

  • Dr. Type
  • ****
  • Posts: 415
    • View Profile
Re: Dictionary, SortedList
« Reply #2 on: 2021-Feb-13 »
Yes Bigsofty, it's very interesting, thanks Gernot  :)

Offline Schranz0r

  • Premium User :)
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 5111
  • O Rly?
    • View Profile
Re: Dictionary, SortedList
« Reply #3 on: 2021-Feb-14 »
I like those Stuff! :)
Can you put this into the examples?
I <3 DGArray's :D

PC:
AMD Ryzen 7 1700 @3.9GHz, 16GB HyperX Fury 3000MHz Ram, ASUS ROG GTX 1060 STRIX 6GB, Windows 10 Pro 64Bit, MSi Tomahawk B350 Mainboard