Dictionary lookup - bug fixes

One of our eagle-eyed forum members noticed a bug in our dictionary code (thanks to tsh!).  In a couple of places the code that dealt with keys was not looking for the end of the key name.  This caused problems when two keys started the same.  For example let's say we have a key "name" and another key "names of next of kin".  The second key starts with "name", and the code wasn't written to avoid a false detection of this sort.

The solution to this problem is to fully qualify the key names by adding the "~value~" tag into the detection code so that when we look for "name" we are actually looking for a match on "~key~name~value~" and not "~key~name", which would give us a false positive if we looking at any key that happened to start with "name"

Here is the fixed version of our dictionary inspector.  Enjoy!

    nomainwin
    WindowWidth = 555
    WindowHeight = 438
    dim keys$(1000)
    dim info$(10, 10)
    global dictionary$, keyCount, lastKey$
    call readDictionary

    texteditor #main.value, 175, 7, 360, 365
    listbox #main.keys, keys$(), [keySelected], 5, 7, 160, 365
    menu #main, "Key", "New", [newKey], "Delete", [deleteKey]
    menu #main, "Edit"
    open "Dictionary inspector" for window as #main
    #main "trapclose [quit]"
    #main.keys "singleclickselect"
    #main.value "!autoresize";
    call loadKeys

[main.inputLoop]   'wait here for input event
    wait

[newKey]   'ask the user for a new key
    call saveValue
    prompt "Enter a name for the key."; newKey$
    if newKey$ <> "" then
        call setValueByName newKey$, ""
        call loadKeys
        #main.keys "select "; newKey$
        #main.value "!cls";
        #main.value "!setfocus";
        call collectGarbage
        call writeDictionary
        lastKey$ = newKey$
    end if
    wait

[deleteKey]  'left for later
    notice "Delete not implemented yet."
    wait

[keySelected] 'a key in the list was selected
    call saveValue
    #main.keys "selection? selectedKey$"
    selectedValue$ = getValue$(selectedKey$)
    #main.value "!contents selectedValue$";
    lastKey$ = selectedKey$
    wait

[quit] 'End the program
    call saveValue
    close #main
    end

sub saveValue   'if the value is changed, save it
    if lastKey$ <> "" then
        #main.value "!modified? modified$";
        if modified$ = "true" then
            #main.value "!contents? saveThisValue$";
            call setValueByName lastKey$, saveThisValue$
            call collectGarbage
            call writeDictionary
        end if
    end if
end sub

function getKeys$(delimiter$)
  global keyCount
  pointer = 1
  while pointer <> 0
    'get the next key
    pointer = instr(dictionary$, "~key~", pointer)
    if pointer then
      keyPointer = pointer + 5
      pointer = instr(dictionary$, "~value~", pointer)
      key$ = mid$(dictionary$, keyPointer, pointer - keyPointer)
      if instr(keyList$, "~key~" + key$ + "~value~") = 0 then
        getKeys$ = getKeys$ + key$ + delimiter$
        keyList$ = keyList$ + "~key~" + key$
        keyCount = keyCount + 1
      end if
    end if
  wend
end function

sub writeDictionary
  open "dictionary.dat" for output as #writeDict
    print #writeDict, dictionary$
  close #writeDict
end sub

sub readDictionary
  if fileExists(DefaultDir$, "dictionary.dat") then
      open "dictionary.dat" for input as #readDict
    length = lof(#readDict)
    dictionary$ = input$(#readDict, length)
    close #readDict
  end if
end sub

sub collectGarbage
  pointer = 1
  while pointer > 0
    'get the next key
    pointer = instr(dictionary$, "~key~", pointer)
    if pointer then
      keyPointer = pointer + 5
      pointer = instr(dictionary$, "~value~", pointer)
      key$ = mid$(dictionary$, keyPointer, pointer - keyPointer)
      if instr(keyList$, "~key~" + key$ + "~value~") = 0 then
        value$ = getValue$(key$)
        newDictionary$ = "~key~" + key$ + "~value~" + value$ + newDictionary$
        keyList$ = keyList$ + "~key~" + key$ + "~value~"
      end if
    end if
  wend
  dictionary$ = newDictionary$
end sub

sub setValueByName key$, value$
  dictionary$ = "~key~"+key$+"~value~"+value$+dictionary$
end sub

function getValue$(key$)
  getValue$ = chr$(0)
  keyPosition = instr(dictionary$, "~key~"+key$+"~value~")
  if keyPosition > 0 then
    keyPosition = keyPosition + 5  'skip over key tag
    valuePosition = instr(dictionary$, "~value~",  keyPosition)
    if valuePosition > 0 then
      valuePosition = valuePosition + 7   'skip over value tag
      endPosition = instr(dictionary$, "~key~", valuePosition)
      if endPosition > 0 then
        getValue$ = mid$(dictionary$, valuePosition, endPosition - valuePosition)
      else
        getValue$ = mid$(dictionary$, valuePosition)
      end if
    end if
  end if
end function

sub loadKeys
    keyList$ = getKeys$("~")
    redim keys$(keyCount)
    for item = 1 to keyCount
      keys$(item-1) = word$(keyList$, item, "~")
    next item
    #main.keys "reload"
end sub

function fileExists(path$, filename$) ' Does file exist?
    files path$, filename$, info$(
    fileExists = val(info$(0, 0)) > 0
end function

A dictionary lookup mini application

Here is a simple demo application for our keyed lookup library in development.  It opens a window with keys on the left, and a text editor on the right.  You can add new keys and edit the values for those keys by changing text on the right.  The values are saved to the file dictionary.dat.

We will enhance this code for a couple more blog entries before we move on to some other project.  :-)

Enjoy!

    nomainwin
    WindowWidth = 555
    WindowHeight = 438
    dim keys$(1000)
    dim info$(10, 10)
    global dictionary$, keyCount, lastKey$
    call readDictionary

    texteditor #main.value, 175, 7, 360, 365
    listbox #main.keys, keys$(), [keySelected], 5, 7, 160, 365
    menu #main, "Key", "New", [newKey], "Delete", [deleteKey]
    menu #main, "Edit"
    open "Dictionary inspector" for window as #main
    #main "trapclose [quit]"
    #main.keys "singleclickselect"
    #main.value "!autoresize";
    call loadKeys

[main.inputLoop]   'wait here for input event
    wait

[newKey]   'ask the user for a new key
    call saveValue
    prompt "Enter a name for the key."; newKey$
    if newKey$ <> "" then
        call setValueByName newKey$, ""
        call loadKeys
        #main.keys "select "; newKey$
        #main.value "!cls";
        #main.value "!setfocus";
        call writeDictionary
        lastKey$ = newKey$
    end if
    wait

[deleteKey]  'left for later
    notice "Delete not implemented yet."
    wait

[keySelected] 'a key in the list was selected
    call saveValue
    #main.keys "selection? selectedKey$"
    selectedValue$ = getValue$(selectedKey$)
    #main.value "!contents selectedValue$";
    lastKey$ = selectedKey$
    wait

[quit] 'End the program
    call saveValue
    close #main
    end

sub saveValue   'if the value is changed, save it
    if lastKey$ <> "" then
        #main.value "!modified? modified$";
        if modified$ = "true" then
            #main.value "!contents? saveThisValue$";
            call setValueByName lastKey$, saveThisValue$
            call collectGarbage
            call writeDictionary
        end if
    end if
end sub

function getKeys$(delimiter$)
  global keyCount
  pointer = 1
  while pointer > 0
    'get the next key
    pointer = instr(dictionary$, "~key~", pointer)
    if pointer then
      keyPointer = pointer + 5
      pointer = instr(dictionary$, "~value~", pointer)
      key$ = mid$(dictionary$, keyPointer, pointer - keyPointer)
      if instr(keyList$, "~key~" + key$) = 0 then
        getKeys$ = getKeys$ + key$ + delimiter$
        keyList$ = keyList$ + "~key~" + key$
        keyCount = keyCount + 1
      end if
    end if
  wend
end function

sub writeDictionary
  open "dictionary.dat" for output as #writeDict
    print #writeDict, dictionary$
  close #writeDict
end sub

sub readDictionary
  if fileExists(DefaultDir$, "dictionary.dat") then
      open "dictionary.dat" for input as #readDict
    length = lof(#readDict)
    dictionary$ = input$(#readDict, length)
    close #readDict
  end if
end sub

sub collectGarbage
  pointer = 1
  while pointer > 0
    'get the next key
    pointer = instr(dictionary$, "~key~", pointer)
    if pointer then
      keyPointer = pointer + 5
      pointer = instr(dictionary$, "~value~", pointer)
      key$ = mid$(dictionary$, keyPointer, pointer - keyPointer)
      if instr(keyList$, key$) = 0 then
        value$ = getValue$(key$)
        newDictionary$ = "~key~" + key$ + "~value~" + value$ + newDictionary$
        keyList$ = keyList$ + key$
      end if
    end if
  wend
  dictionary$ = newDictionary$
end sub

sub setValueByName key$, value$
  dictionary$ = "~key~"+key$+"~value~"+value$+dictionary$
end sub

function getValue$(key$)
  getValue$ = chr$(0)
  keyPosition = instr(dictionary$, "~key~"+key$)
  if keyPosition > 0 then
    keyPosition = keyPosition + 5  'skip over key tag
    valuePosition = instr(dictionary$, "~value~",  keyPosition)
    if valuePosition > 0 then
      valuePosition = valuePosition + 7   'skip over value tag
      endPosition = instr(dictionary$, "~key~", valuePosition)
      if endPosition > 0 then
        getValue$ = mid$(dictionary$, valuePosition, endPosition - valuePosition)
      else
        getValue$ = mid$(dictionary$, valuePosition)
      end if
    end if
  end if
end function

sub loadKeys
    keyList$ = getKeys$("~")
    redim keys$(keyCount)
    for item = 1 to keyCount
      keys$(item-1) = word$(keyList$, item, "~")
    next item
    #main.keys "reload"
end sub

function fileExists(path$, filename$) ' Does file exist?
    files path$, filename$, info$(
    fileExists = val(info$(0, 0)) > 0
end function

Dictionary lookup - getting the keys

When you have an array you can simply loop through the contents to examine what's there, but when you have a dictionary you need to have the list of keys so that you can look up each value in the dictionary.  For that, we need a getKeys$() function.  The following function returns a single string with the keys from our global dictionary$ variable, each separated by a delimiter that we can specify.

function getKeys$(delimiter$)
  pointer = 1
  while pointer > 0
    'get the next key
    pointer = instr(dictionary$, "~key~", pointer)
    if pointer then
      keyPointer = pointer + 5
      pointer = instr(dictionary$, "~value~", pointer)
      key$ = mid$(dictionary$, keyPointer, pointer - keyPointer)
      if instr(keyList$, "~key~" + key$) = 0 then
        getKeys$ = getKeys$ + key$ + delimiter$
        keyList$ = keyList$ + "~key~" + key$
      end if
    end if
  wend
end function

Once have this string we can tease out each key.  Here is an quick example that shows how to do this.  The variable allKeys$ will hold all the keys, each separated by "~".  Then we use the word$() function to get each key.

global dictionary$

call setValueByName "first", "Tom"
call setValueByName "last", "Thumb"
call setValueByName "phone", "555-555-1234"

allKeys$ = getKeys$("~")
print allKeys$

key = 1
while word$(allKeys$, key, "~") <> ""
  key$ = word$(allKeys$, key, "~")
  print "Key number "; key; " is "; key$
  print "    value = "; getValue$(key$)
  key = key + 1
wend


Here is what the resulting output looks.

phone~last~first~
Key number 1 is phone
    value = 555-555-1234
Key number 2 is last
    value = Thumb
Key number 3 is first
    value = Tom

Notice that the keys do not come out in the order that we put them in.  This is typical in dictionary style lookup mechanisms.  The ordering of keys is not guaranteed.

Dictionary lookup - Garbage collection

If we need to use our keyed dictionary lookup functions for a purpose where we will change the values for any or all keys the string we save in dictionary$ will get larger each time we set a key and value.  This is because the setValueByName subroutine sets a key and value by adding onto the front of the dictionary$ variable but it does not remove any preexisting value for that key.  So if for example I set a key of "storeFolder" and a value of "c:\myStoreFolder" and then later I change the value to "c:\myOtherFolder" I will have two different entries for the key "storeFolder".  Only the latest value will be returned by the getValue$() function.

So, how do we fix this?  We implement a garbage collector.  We can create a subroutine that makes a copy of dictionary$ that only has the latest value for each key.

Here is a first stab at a garbage collector subroutine.

sub collectGarbage
  pointer = 1
  while pointer > 0
    'get the next key
    pointer = instr(dictionary$, "~key~", pointer)
    if pointer then
      keyPointer = pointer + 5
      pointer = instr(dictionary$, "~value~", pointer)
      key$ = mid$(dictionary$, keyPointer, pointer - keyPointer)
      if instr(keyList$, key$) = 0 then
        value$ = getValue$(key$)
        newDictionary$ = "~key~" + key$ + "~value~" + value$ + newDictionary$
        keyList$ = keyList$ + key$
      end if
    end if
  wend
  dictionary$ = newDictionary$
end sub

Keyed dictionary lookup in Liberty BASIC

Liberty BASIC has a way to manage collections of data by using arrays and you look up the information by numeric position.  You can do a lot with this but it doesn't let you look up information by name.

We can provide an easy to use way to do this in Liberty BASIC by using the string functions of Liberty BASIC.  By using a single string we can have easy lookup of values by name and also have the ability to store the collection of values in a file and retrieve it simply.  In some versions of BASIC this is only useful for small lists of information because of string size limitations of 255.  Liberty BASIC permits strings of millions of characters so this is not a problem.

Here is a very simple demo of the concept just to get us started.  In future postings we will explain and enhance the way this works.

global dictionary$

call setValueByName "first", "Tom"
call setValueByName "last", "Thumb"
call setValueByName "phone", "555-555-1234"

print getValue$("last")
print getValue$("blah")
print getValue$("phone")
print getValue$("first")

sub setValueByName key$, value$
  dictionary$ = "~key~"+key$+"~value~"+value$+dictionary$
end sub

function getValue$(key$)
  getValue$ = chr$(0)
  keyPosition = instr(dictionary$, "~key~"+key$)
  if keyPosition > 0 then
    keyPosition = keyPosition + 5  'skip over key tag
    valuePosition = instr(dictionary$, "~value~",  keyPosition)
    if valuePosition > 0 then
      valuePosition = valuePosition + 7   'skip over value tag
      endPosition = instr(dictionary$, "~key~", valuePosition)
      if endPosition > 0 then
        getValue$ = mid$(dictionary$, valuePosition, endPosition - valuePosition)
      else
        getValue$ = mid$(dictionary$, valuePosition)
      end if
    end if
  end if
end function