Author Topic: Dictionary by MrBcx and ChatGPT  (Read 629 times)

MrBcx

  • Administrator
  • Hero Member
  • *****
  • Posts: 1850
    • View Profile
Dictionary by MrBcx and ChatGPT
« on: January 15, 2023, 06:09:43 PM »
Raining all day, stuck inside, so I spent some time 'talking' with ChatGPT.

'We' came up with a pretty cool set of Dictionary functions.  This set
takes the form of a single header file that I named: strdict.h

That along with a BCX example showing off its functions are included below. 
Tested and working with LccWin32 / Pelles / Mingw / MSVC

As far as configuration options go, you have two (2) inside strdict.h
Increase or decrease to suit your needs:

#define MAXKEYS 1000       //  maximum dictionary entries
#define MAXSTRLEN 2047   //  maximum string sizes


BCX Example OUTPUT: 
Sample data added to dictionary
Saving dictionary to disk

Testing the REMOVE function ... removing 'cat','bird', and 'mouse'
Prove those removals completed ... should see 3 (nulls)

Value of key 'cat':  (null)
Value of key 'bird': (null)
Key of value 'rodent animal': (null)

Now re-load our dictionary from disk ...
And show that all our animals are back:

Value of key 'cat':  feline animal
Value of key 'bird': avian animal
Key of value 'rodent animal': mouse

Prove we cannot have duplicate keys by attempting to add 'fish' again
Key already exists in the dictionary.

Now we will test the 'Replace Value' function by changing
the value for the key 'cat' from 'canine animal' to 'Heavy Machinery'

Prove that the Replace Value() function worked:
New value of key 'cat':  Heavy Machinery

This concludes this example.


Press any key to continue . . .


Here is just the source code for the example, for your reading pleasure.
Code: [Select]

'***************************************************************
' A simple Dictionary by MrBcx and ChatGPT - MIT License  2023
'***************************************************************
#include "strdict.h"

DIM AS Dictionary Dict_Animals
dictionary_init(&Dict_Animals)
PRINT "Dictionary has been created"
dictionary_add(&Dict_Animals, "cat", "feline animal")
dictionary_add(&Dict_Animals, "dog", "canine animal")
dictionary_add(&Dict_Animals, "bird", "avian animal")
dictionary_add(&Dict_Animals, "fish", "aquatic animal")
dictionary_add(&Dict_Animals, "mouse", "rodent animal")
PRINT "Sample data added to dictionary"
PRINT "Saving dictionary to disk"
dictionary_write_to_file(&Dict_Animals, "animals.txt")  ' .txt is arbitrary - use whatever extension (or none) that you want
PRINT
PRINT "Testing the REMOVE function ... removing 'cat','bird', and 'mouse'"
dictionary_remove(&Dict_Animals, "cat")
dictionary_remove(&Dict_Animals, "bird")
dictionary_remove(&Dict_Animals, "mouse")

PRINT "Prove those removals completed ... should see 3 (nulls)"
PRINT
PRINT "Value of key 'cat':  ",          dictionary_find_key$   (&Dict_Animals, "cAT")             ' Prove case-insensitivity
PRINT "Value of key 'bird': ",          dictionary_find_key$   (&Dict_Animals, "BIrd")            '         ditto
PRINT "Key of value 'rodent animal': ", dictionary_find_value$ (&Dict_Animals, "RODent ANImal")   '         ditto
PRINT
PRINT "Now re-load our dictionary from disk ..."

dictionary_read_from_file(&Dict_Animals, "animals.txt")  ' .txt is arbitrary - use whatever extension (or none) that you want

PRINT "And show that all our animals are back:"
PRINT
PRINT "Value of key 'cat':  ",          dictionary_find_key$   (&Dict_Animals, "cAT")
PRINT "Value of key 'bird': ",          dictionary_find_key$   (&Dict_Animals, "BIrd")
PRINT "Key of value 'rodent animal': ", dictionary_find_value$ (&Dict_Animals, "RODent ANImal")
PRINT
PRINT "Prove we cannot have duplicate keys by attempting to add 'fish' again"
dictionary_add(&Dict_Animals, "fish", "aquatic animal")
PRINT
PRINT "Now we will test the 'Replace Value' function by changing"
PRINT "the value for the key 'cat' from 'canine animal' to 'Heavy Machinery'"
dictionary_replace_value (&Dict_Animals, "CAT", "Heavy Machinery")
PRINT
PRINT "Prove that the Replace Value() function worked:"
PRINT "New value of key 'cat':  ",          dictionary_find_key$   (&Dict_Animals, "cat")
PRINT
PRINT "This concludes this example."
PAUSE

« Last Edit: January 15, 2023, 10:11:10 PM by MrBcx »

MrBcx

  • Administrator
  • Hero Member
  • *****
  • Posts: 1850
    • View Profile
Re: Dictionary by MrBcx and ChatGPT
« Reply #1 on: January 16, 2023, 06:20:05 AM »
Below are two more functions that can be added to strdict.h that I felt could be useful at times.

These are not represented in my BCX example and no part of strdict.h depends on them,
so whether you add these to strdict.h is entirely up to you.

Note:
Like all the other functions in this library, any searching that takes place is case-insensitive,
meaning the searching uses the CRT function: stricmp

Code: [Select]

bool dictionary_contains_key(Dictionary *d, char *key) {
//*** ***********************************************************************
//      This function returns TRUE if the 'key' is in the dictionary
//**************************************************************************
    for (int i = 0; i < d->size; i++) {
        if (stricmp(d->entries[i].key, key) == 0) {
            return true;
        }
    }
    return false;
}


bool dictionary_contains_value(Dictionary *d, char *value) {
//**************************************************************************
//      This function returns TRUE if the 'value' is in the dictionary
//**************************************************************************
    for (int i = 0; i < d->size; i++) {
        if (stricmp(d->entries[i].value, value) == 0) {
            return true;
        }
    }
    return false;
}


airr

  • Jr. Member
  • **
  • Posts: 62
    • View Profile
Re: Dictionary by MrBcx and ChatGPT
« Reply #2 on: January 31, 2023, 07:18:38 PM »
I know that the value of using STRUCTS for dictionary/hashmap implementations lies in the ability to mix types.

Since your demo uses strings for both the keys and values, I wanted to share an alternative Proof of Concept approach I whipped up today (tested with Pelles) that doesn't use structs:

Code: [Select]
const arraysize = 100

dim test$[arraysize]

set demo$[arraysize]
    "Harry", "32",
    "David", "20",
    "George", "11",
    "Judy", "N/A"
end set

addRecord(demo$, "John", "61")
addRecord(demo$, "Jane", "48")
addRecord(demo$, "Joe", "88")
addRecord(demo$, "Bob", "66")
addRecord(demo$, "Armando","Old as Methuselah") '<-- will be deleted
addRecord(demo$, "Judy", "31")  ' <-- will be updated (see SET above for original value)

print crlf$, "***** Get Values *****"
print "John = ",getValue(demo$,"John")
print "Bob = ",getValue(demo$,"Bob")
print "***** Get Values *****", crlf$

delRecord(demo$,"Armando")


print crlf$, "***** Keys / Values *****"
dump(demo$)
print "***** Keys / Values *****", crlf$

print crlf$, "***** Keys *****"
dumpKeys(demo$)
print "***** Keys *****", crlf$

saveData(demo$, "data.bin")

print crlf$, "***** Loaded from File *****"
loadData(test$, "data.bin")
dump(test$)
print "***** Loaded from File *****", crlf$



function getValue$(arr$[],key$)
    for integer x = 0 to arraysize-1 step 2
        if trim$(arr[x]) = key$ then
            function = arr[x+1]$
        end if
    next
    function = ""
end function

sub addRecord(arr$[],key$, value$)
    for integer x = 0 to arraysize-1 step 2
        ' UPDATE
        if arr$[x] = key$ then
            arr$[x+1] = value
            exit for
        ' CREATE
        elseif len(arr$[x]) = 0 then
            arr[x]$ = key
            arr[x+1]$ = value
            exit for
        end if
    next
end sub

sub delRecord(arr$[], key$)
    for integer x = 0 to arraysize-1 step 2
        if arr$[x] = key$ then
            for integer y = x to arraysize -1
                arr$[y] = arr$[y+2]
                arr$[y+1] = arr$[y+3]
            next
        END IF
    next
end sub

sub dump(arr$[])
    for int x = 0 to arraysize-1 step 2
        if len(arr$[x]) then
            print "Key: ",arr$[x], ", Value: ", arr$[x+1]
        end if
    next
end sub

sub dumpKeys(arr$[])
    for int x = 0 to arraysize-1 step 2
        if len(arr[x]) then print arr$[x]
    next
end sub

sub saveData(arr$[], filename$)
    dim as integer total = 0
    open filename$ for binary new as outFile

    for int x = 0 to arraysize-1 step 2
        if len(arr[x]) then total += 2
    next

    put$ outFile, &total, sizeof(total)
    put$ outFile, arr$, sizeof(*arr$) * total
    close outFile
end sub

sub loadData(arr$[], filename$)
    dim as integer total
    open filename$ for binary as inFile
    get$ inFile, &total, sizeof(total)
    get$ inFile, arr$, sizeof(*arr$) * total
    close inFile
end sub

AIR.

MrBcx

  • Administrator
  • Hero Member
  • *****
  • Posts: 1850
    • View Profile
Re: Dictionary by MrBcx and ChatGPT
« Reply #3 on: January 31, 2023, 07:35:37 PM »
Armando -- I like it a lot! 

There's something important to be said for easy to understand, easy to reuse code like this.


airr

  • Jr. Member
  • **
  • Posts: 62
    • View Profile
Re: Dictionary by MrBcx and ChatGPT
« Reply #4 on: January 31, 2023, 08:00:07 PM »
Glad you like it!

I should have used 'ICOMPARE' for the key checks, now that I think about it... :(

airr

  • Jr. Member
  • **
  • Posts: 62
    • View Profile
Re: Dictionary by MrBcx and ChatGPT
« Reply #5 on: July 28, 2023, 06:33:02 PM »
I was thinking about this today, because it bugged me that my code was doing key look-ups in linear time [O(n)] vs constant time [O(1)].

With such a small data set it's not a problem, but will slow down proportionally the larger the array/data gets.

So after reading a bunch about hashtables, I coded a hashing function that I could use with my demo which in theory should bring me closer to O(1).

This ain't perfect, but it's a good exercise

Code: [Select]
dim demo$[BCXSTRSIZE]


addRecord(demo$, "John", "61")
addRecord(demo$, "Jane", "48")
addRecord(demo$, "Joe", "88")
addRecord(demo$, "Bob", "66")
addRecord(demo$, "Armando","Old as Methuselah") '<-- will be deleted
addRecord(demo$, "Judy", "31")

print crlf$, "***** Manually Get Values *****"
print "John = ", getValue(demo$,"John")
print "Bob = ", getValue(demo$,"Bob")
print "Jane = ", getValue(demo$,"Jane")
print "Judy = ", getValue(demo$,"Judy")
print "Joe = ", getValue(demo$,"Joe")
print "Armando = ", getValue(demo$,"Armando")
print "***** Manually Get Values *****", crlf$

delRecord(demo$,"Armando")


print crlf$, "***** Keys / Values *****"
dump(demo$)
print "***** Keys / Values *****", crlf$

print crlf$, "***** Keys *****"
dumpKeys(demo$)
print "***** Keys *****", crlf$



function getValue$(arr$[],key$)
    dim as UINT x = hash(trim$(key$))

    if trim$(arr[x]) = key$ then
        function = arr[x+1]$
    end if   

    function = ""
end function

sub addRecord(arr$[],key$, value$)
    dim as UINT x = hash(key$)

    arr[x]$ = trim$(key)
    arr[x+1]$ = trim$(value)
end sub

sub delRecord(arr$[], key$)
    dim as UINT x = hash(key$)

    arr$[x] = ""
    arr$[x+1] = ""
end sub

sub dump(arr$[])
    for int x = 0 to BCXSTRSIZE-1 step 2
        if len(arr$[x]) then
            print "Key: ",arr$[x], ", Value: ", arr$[x+1]
        end if
    next
end sub

sub dumpKeys(arr$[])
    for int x = 0 to BCXSTRSIZE-1 step 2
        if len(arr[x]) then print arr$[x]
    next
end sub


' Function that computes a hash based on the
' key value provided, which is used later
' to directly index the array, instead of looping
' through the array to find the requested key
function hash(key as string) as UINT
    dim as ULONG value = 0
    dim as UINT key_len = strlen(key)

    ' multiply value by prime number (37)
    ' and add the char value of the current letter
    ' in the string being looped over
    for int i = 0 to key_len-1
        value = value * 37 + key[i]
    next

    ' Contrain value to range of "BCXSTRSIZE"
    value = mod(value, BCXSTRSIZE)

    ' ensure that value is an even number,
    ' because odd numbers are used to store
    ' the actual value of a given key
    if mod(value,2) then function = value + 1

    function = value;
end function

As always, comments/suggestions are welcome!

AIR.

MrBcx

  • Administrator
  • Hero Member
  • *****
  • Posts: 1850
    • View Profile
Re: Dictionary by MrBcx and ChatGPT
« Reply #6 on: July 28, 2023, 08:44:28 PM »
Thanks a bunch Armando -- that's a keeper!

Compiles with Mingw, MSVC, PellesC, and Lcc-Win32 and all produce same results.

Code: [Select]

***** Manually Get Values *****
John = 61
Bob = 66
Jane = 48
Judy = 31
Joe = 88
Armando = Old as Methuselah
***** Manually Get Values *****


***** Keys / Values *****
Key: Jane, Value: 48
Key: Bob, Value: 66
Key: Judy, Value: 31
Key: John, Value: 61
Key: Joe, Value: 88
***** Keys / Values *****


***** Keys *****
Jane
Bob
Judy
John
Joe
***** Keys *****


Press any key to continue . . .



rlawson

  • Newbie
  • *
  • Posts: 1
    • View Profile
Re: Dictionary by MrBcx and ChatGPT
« Reply #7 on: January 02, 2024, 07:55:16 AM »
This looks good but isn't it possible that two different keys produce the same hash (collide)?

In that case, since you do a key check when you retrieve the value so you could always output a warning that key passed in did not match the expected key