### Author Topic: Dictionary, SortedList  (Read 950 times)

#### Kitty Hello

• code monkey
• Prof. Inline
• Posts: 10816
• here on my island the sea says 'hello'
##### 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.252TYPE T_DictionaryPair key\$ val\$ENDTYPETYPE 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 ENDFUNCTIONENDTYPETYPE 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 ENDFUNCTIONENDTYPE`

Test program
Code: (glbasic) [Select]
`LOCAL sose AS TSortedSetsose.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"NEXTSTDOUT "------------------\n"LOCAL dict AS TDictionarydict.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"NEXTKEYWAIT`

Here's the output
Code: (glbasic) [Select]
`isset dog 1isset rat 0-bird-cat-dog-mouse------------------dogs: manyrats:-birds = any-cats = 5-dogs = many-mice = 7`

#### bigsofty

• Community Developer
• Prof. Inline
• Posts: 2750
##### Re: Dictionary, SortedList
« Reply #1 on: 2021-Feb-05 »
Handy, thanks Gernot!
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

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