QB64.org Forum

Active Forums => Programs => Topic started by: TempodiBasic on April 05, 2021, 10:08:41 pm

Title: A demo of Dictionary or hash table made with a array bidimensional(Rosetta Code)
Post by: TempodiBasic on April 05, 2021, 10:08:41 pm
Hi guys and gals
here the same concept of dictionary build up with an array bidimensional

Code: QB64: [Select]
  1. Const False = 0, True = Not False, sValue = 2, sKey = 1
  2.  
  3. Dim Mydict(1 To 10, 1 To 2) As String
  4.  
  5. ' start of demo
  6.  
  7. If PutDict(Mydict(), "b", "battle") = True Then Print " Inserted couple key value"
  8. If PutDict(Mydict(), "c", "cheesebattle") = True Then Print " Inserted couple key value"
  9. If PutDict(Mydict(), "a", "ancient") = True Then Print " Inserted couple key value"
  10. If PutDict(Mydict(), "d", "domus") = True Then Print " Inserted couple key value"
  11. If PutDict(Mydict(), "e", "embarassing") = True Then Print " Inserted couple key value"
  12. ShowDict Mydict()
  13. Print " we search the key a and e"
  14. If GetDict(Mydict(), "b") <> "" Then Print GetDict(Mydict(), "b")
  15. If GetDict(Mydict(), "e") <> "" Then Print GetDict(Mydict(), "e")
  16. Print " we change key b and e"
  17. If ChangeValueDict(Mydict(), "b", "BASIC") Then Print "changement done"
  18. If ChangeValueDict(Mydict(), "e", "Elephant") Then Print "changement done"
  19. If GetDict(Mydict(), "e") <> "" Then Print GetDict(Mydict(), "e")
  20. If GetDict(Mydict(), "b") <> "" Then Print GetDict(Mydict(), "b")
  21. Print " we erase key e"
  22. If EraseKeyDict(Mydict(), "e") = True Then Print "key passed erased"
  23. If GetDict(Mydict(), "e") <> "" Then Print GetDict(Mydict(), "e") Else Print "key passed not foud"
  24. ShowDict Mydict()
  25. ' end of demo
  26.  
  27.  
  28. Function PutDict (dict() As String, Keys As String, Value As String)
  29.     PutDict = False
  30.     Dim Count As Integer
  31.     For Count = 1 To UBound(dict, sKey)
  32.         If dict(Count, sKey) = "" Then Exit For
  33.     Next
  34.     dict(Count, sKey) = Keys
  35.     dict(Count, sValue) = Value
  36.     PutDict = True
  37.  
  38. Function GetDict$ (dict() As String, Keys As String)
  39.     GetDict$ = ""
  40.     Dim Count As Integer
  41.     For Count = 1 To UBound(dict, sKey)
  42.         If dict(Count, sKey) = Keys Then
  43.             GetDict$ = dict(Count, sValue)
  44.             Exit For
  45.         End If
  46.     Next
  47.  
  48. Function ChangeValueDict (dict() As String, Keys As String, Value As String)
  49.     ChangeValueDict = False
  50.     Dim Count As Integer
  51.     For Count = 1 To UBound(dict, sKey)
  52.         If dict(Count, sKey) = Keys Then
  53.             dict(Count, sValue) = Value
  54.             Exit For
  55.         End If
  56.     Next
  57.     ChangeValueDict = True
  58.  
  59. Function EraseKeyDict (dict() As String, Keys As String)
  60.     EraseKeyDict = False
  61.     Dim Count As Integer
  62.     For Count = 1 To UBound(dict, sKey)
  63.         If dict(Count, sKey) = Keys Then
  64.             dict(Count, sValue) = ""
  65.             dict(Count, sKey) = ""
  66.             Exit For
  67.         End If
  68.     Next
  69.     EraseKeyDict = True
  70.  
  71. Sub ShowDict (dict() As String)
  72.     Dim Count As Integer
  73.     For Count = 1 To UBound(dict, sKey)
  74.         Print dict(Count, sKey), dict(Count, sValue)
  75.     Next
Give a tray.

PS what do you think about UDT dictonary?
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 05, 2021, 11:09:07 pm
Can you put multiple entries under the letters a, b, c...

Quote
PS what do you think about UDT dictonary?

I think it might be better than demo, be right back!

Yeah less functions to fool with:
Code: QB64: [Select]
  1. Type dictionary
  2.     key As String
  3.     val As String
  4.  
  5. ReDim d(1 To 100) As dictionary
  6.  
  7. d(1).key = "mamals": d(1).val = "dogs, cats, bears, whales, bats"
  8. d(2).key = "fish": d(2).val = "bass, trout, carp"
  9. d(3).key = "trees": d(3).val = "oak, ash, maple, pine"
  10.  
  11.  
  12.  
  13.  

vals can be Astrings. This is pretty much variables and values used in oh interpreter.

Quote
Is there even any reason for the double dimensions?
I edit my demo to show need for key and multiple values under key.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: SMcNeill on April 06, 2021, 12:04:04 am
Is there even any reason for the double dimensions?  Why not just use a single array to store all the data, sort it, and then use a separate array of 26 items to track starting position?

For example:

Apple
Ax
Banana
Boat
Car

A single array holds the dictionary of 123,456 words.  (Use your imagination for the next 123,451...)

In a 2-dimensional array, or a 2-type UDT, you’re going to have that index being 123,456 elements as well...

OR, you just just use a second array.:
Index(65) = 1
Index(66) = 3
Index(67) = 5

Now, for quick searches, we know words that start with “A” begin at index 1, words that start with “B” begin at index 3, and so on....
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: TempodiBasic on April 06, 2021, 07:26:58 am
Hi friends
@bplus Yes the value can be all you want but the key seems it must be unique in fact are forbidden duplicate of  the key_value

@Steve Yes your answer is interesting and efficacy but it goes out of definition od Array associative said also as Dictionary or Hash table or Map in different programming languages.

To build from stratch a simple Dictionary engine in QB64 I have followed these instruction taken from Python
Quote
Python dictionary is an unordered collection of items. Each item of a dictionary has a key/value pair.

Dictionaries are optimized to retrieve values when the key is known.
really both as single string with bounder limiters both as bidimensional array the only order is that of registering the info into it, but this order is changed when you delete a key or insert a new couple (not yet developed in this demo) in the dictionary.


my code starts from this track
Quote
Task
The goal is to create an associative array (also known as a dictionary, map, or hash).
coming from there
http://rosettacode.org/wiki/Associative_array/Creation (http://rosettacode.org/wiki/Associative_array/Creation)

and from there for the definition of Associative Array
Quote
Associative array/Iteration 
Show how to iterate over the key-value pairs of an associative array, and print each pair out.
Also show how to iterate just over the keys, or the values, if there is a separate way to do that in your language.

coming from there
http://rosettacode.org/wiki/Associative_array/Iteration (http://rosettacode.org/wiki/Associative_array/Iteration)

so I have understood  that the original associative array is UNSORTED couple of data and the key cannot be duplicate and the key mustn't be numeric.
Thanks for your feedbacks
Waiting your thoughts
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 06, 2021, 10:50:57 am
Oh this is Rossetta Challenge, I never knew,  a couple of years ago we played with same thing at JB, Carl developer of JB started the thread. He doesn't hang around JB much but he did for this.

I think this is just Dictionary, not hash table. Oh but RC uses hash term too, I will read...
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: TempodiBasic on April 06, 2021, 12:47:32 pm
@bplus
your code cover the 3rd way to do a dictionary or Associative Array in QB64
but as you see from Task you need to build an engine to manage this UNordered data organized in a couple key-value

so please complete your code with basical routines/functions: AppendData to the dictionary, SearchData using a key, ChangeValue to a key, ChangeKey, DeleteKeyandValue, InsertKeyValue.

In this manner we'll have 3 different Dictionary engines as Associative Array are not native in QB64 but built from scratch!

About tasks of Rosetta Code yet posted into forum I have seen

Quote
the Solve the eight queens puzzle.
You can extend the problem to solve the puzzle with a board of size   NxN.
For the number of solutions for small values of   N,   see   OEIS: A000170.
at this link there is still QB64  http://rosettacode.org/wiki/N-queens_problem#QB64 (http://rosettacode.org/wiki/N-queens_problem#QB64)

Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 06, 2021, 01:12:31 pm
@bplus
your code cover the 3rd way to do a dictionary or Associative Array in QB64
but as you see from Task you need to build an engine to manage this UNordered data organized in a couple key-value

so please complete your code with basical routines/functions: AppendData to the dictionary, SearchData using a key, ChangeValue to a key, ChangeKey, DeleteKeyandValue, InsertKeyValue.

In this manner we'll have 3 different Dictionary engines as Associative Array are not native in QB64 but built from scratch!

Hi TempodiBasic,

Yes I am reading through Rosetta stuff now, disappointed by lack of "rules" or directions for Assoc. Arrays in Creation thread.

I will probably review what I used in my oh Interpreter because that is exactly what is needed to look up values and or create new variables with values. That was main problem with deciding to make a new variable & value pair or modify an existing one whenever you have a program line that calls for reassigning or creating a variable. For some reason I chose to make 2 separate arrays for variables and for values and I can't remember my reasoning at the time. I do remember hesitating and thinking a bit on the decision. So it is ironic I am advocating UDT's now ;-))

And yes, absolutely, the number 1 Rule is you can't have 2 keys of the same name! with different value sets. RC doesn't even mention this one basic rule for key - value pairs from my reading in Creation thread.

Regarding Steve's mention of sorting, yes when key - value pairs reach a certain number there would be definite advantage to sorting keys for speedy lookup of values.

Regarding the word "hash", I think of using a formula that assigns an index number to key so that it automatically sorts itself in a lookup table so maybe a binary search could be used to find items fast without a sort. I don't know, that is a bit fuzzy because I never worked it out for myself.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 06, 2021, 01:19:05 pm
http://rosettacode.org/mw/index.php?title=Associative_array/Creation&redirect=no

Confirmed nothing! Usually RC has some sort of guidelines or specifications so you know you did a task correctly.
Nothing here!!!

I propose a specification for creating or modifying a key and value pair.

You must search the keys you have already stored and if key is not found then create the new pair otherwise just modify the key with the new value.

I think this is all that is needed for key - value pairs to work as intended.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: TempodiBasic on April 06, 2021, 01:28:17 pm
@bplus
hey I never imagined the possible use in the programming of this data structure. peharps I have studied QBasic, TurboPascal, TurboC/C++ and their RAD evolution in Windows, but never I have used intensively for my hobbistic programming activity.
 As table for interpreter o compiler :-) cool!

about
Quote
For some reason I chose to make 2 separate arrays for variables and for values and I can't remember my reasoning at the time. I do remember hesitating and thinking a bit on the decision.
I cannot know your decision, but at my eyes with pointers you can save more space (RAM or Disk access) using pointers between 2 separated lists... just think for compression algorythm in which the compressor search repetitive value to store packed.

Thanks for feedback
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 06, 2021, 01:55:50 pm
The thing is you have to decide if you want static or dynamic arrays, easy choice there you want dynamic array because you have no idea how many variable - value pairs you will have to store.

Then there is question to SHARED the arrays or not. Here is the big decision, I decided to SHARED the arrays in oh interpreter because you don't want to pass arrays as arguments unless absolutely necessary.

Once I decided on SHARED the rest of the decisions were easy to decide:

Deciding on SHARED that means you have to design application specific subs and functions to handle the specific arrays so since I had to do that, I might as well use list type arrays because generally they are easier to type without all the dot stuff you have with UDT's.

And further, I decided on base 1 arrays because then the Ubound of the array is also the number of items in it, just to make things a little bit easier on myself.

So, while RC works on theory, that works for most cases generally, when it comes to actual application you want a fast efficient program easy to read, understand and modify.

So there, I think I have recreated the decision process I went through using an actual application of dictionary type structure in oh Interpreter.

Oh and you know what? You don't have to worry about initializing string arrays as you do with values in UDT's, though it may not matter with variable values tables.

So proceeding here, we have to talk generally with dictionary arrays so we need to pass them as arguments as TempodiBasic has begun. Using UDT's ??

Don't know if I want to proceed down that line, yeah UDT's might be better if we have to pass the Dictionary arrays!
Yeah! That surely beats having to pass 2 arrays! 1 for the keys and one for the values.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 06, 2021, 02:18:12 pm
So @TempodiBasic

This is good choice for keeping the 2 arrays attached:
Dim Mydict(1 To 10, 1 To 2) As String

with constants sKey = 1 and sValue = 2

Update: I would use ReDim so you can use a dynamic array and add to it if new keys go beyond the UBound of array.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 06, 2021, 03:42:40 pm
Oh hell ReDim of a double array is nightmare back to UDT's!

OK UDT's don't get confusing with more than one dimension, way more intuitive for developing:
Code: QB64: [Select]
  1. Type Dictionary
  2.     K As String
  3.     V As String
  4.  
  5. ReDim MyDict(1 To 1) As Dictionary ' use ubound of array to tell how many values we have
  6.  
  7. ' make some new pairs
  8. ShowDict MyDict()
  9. AddModDictionary MyDict(), "mammals", "Cats"
  10. ShowDict MyDict()
  11. AddModDictionary MyDict(), "trees", "Oak"
  12. ShowDict MyDict()
  13. AddModDictionary MyDict(), "fish", "Bass"
  14. ShowDict MyDict()
  15. AddModDictionary MyDict(), "mammals", "Dogs"
  16. ShowDict MyDict()
  17. Print "What is current mammal ? answer: "; GetValue$(MyDict(), "mammals")
  18.  
  19.  
  20.  
  21. ' replace 2 TempodiBasic Functions with 1 Sub, to handle both new and modified values for keys and dynamic Dict() dbl string array.
  22. ' Now just take ubound of dict() and have number of pairs it contains
  23. Sub AddModDictionary (Dict() As Dictionary, K$, V$)
  24.     ReDim ub As Long, i As Long, ky$
  25.     ub = UBound(dict)
  26.     ky$ = UCase$(_Trim$(K$)) 'don't change k$ but make case insensitive?
  27.     If ky$ <> "" Then ' bullet proof sub routine K$ must not be empty!
  28.         If ub = 1 And Dict(1).K = "" Then 'our very first pair!
  29.             Dict(1).K = ky$: Dict(1).V = V$: Exit Sub
  30.         Else
  31.             For i = 1 To ub ' see if we have that name yet
  32.                 If ky$ = Dict(i).K Then Dict(i).V = V$: Exit Sub ' yes name is registered so change value
  33.             Next
  34.             'still here? add var name and value to dictionary
  35.             ReDim _Preserve Dict(1 To ub + 1) As Dictionary ' create one slot at a time such that ubound = number or pairs
  36.             Dict(ub + 1).K = ky$: Dict(ub + 1).V = V$ ' fill it with key and value
  37.         End If
  38.     End If
  39.  
  40.  
  41. '===========  AddModDictionary replaces this
  42. 'Function PutDict (dict() As String, Keys As String, Value As String)
  43. '    PutDict = False
  44. '    Dim Count As Integer
  45. '    For Count = 1 To UBound(dict, sKey)
  46. '        If dict(Count, sKey) = "" Then Exit For
  47. '    Next
  48. '    dict(Count, sKey) = Keys
  49. '    dict(Count, sValue) = Value
  50. '    PutDict = True
  51. 'End Function
  52.  
  53. ' fixed for
  54. Function GetValue$ (Dict() As Dictionary, K$)
  55.     Dim i As Long
  56.     For i = 1 To UBound(Dict)
  57.         If Dict(i).K = UCase$(_Trim$(K$)) Then
  58.             GetValue$ = Dict(i).V: Exit Function
  59.         End If
  60.     Next
  61.  
  62. '===========  AddModDictionary replaces this
  63. 'Function ChangeValueDict (dict() As String, Keys As String, Value As String)
  64. '    ChangeValueDict = False
  65. '    Dim Count As Integer
  66. '    For Count = 1 To UBound(dict, sKey)
  67. '        If dict(Count, sKey) = Keys Then
  68. '            dict(Count, sValue) = Value
  69. '            Exit For
  70. '        End If
  71. '    Next
  72. '    ChangeValueDict = True
  73. 'End Function
  74.  
  75. ' save for later
  76. 'Function EraseKeyDict (dict() As String, Keys As String)
  77. '    EraseKeyDict = False
  78. '    Dim Count As Integer
  79. '    For Count = 1 To UBound(dict, sKey)
  80. '        If dict(Count, sKey) = Keys Then
  81. '            dict(Count, sValue) = ""
  82. '            dict(Count, sKey) = ""
  83. '            Exit For
  84. '        End If
  85. '    Next
  86. '    EraseKeyDict = True
  87. 'End Function
  88.  
  89. 'modified for quick look
  90. Sub ShowDict (Dict() As Dictionary)
  91.     Dim i As Long
  92.     Print: Print "Dictionary has "; _Trim$(Str$(UBound(dict))); " items."
  93.     For i = 1 To UBound(dict)
  94.         Print i, Dict(i).K, Dict(i).V
  95.     Next
  96.     Print
  97.  
  98.  
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: SMcNeill on April 06, 2021, 04:14:57 pm
From the example for BASIC256 here: http://rosettacode.org/mw/index.php?title=Associative_array/Creation&redirect=no , isn’t this what the _KEYHIT library does for us?  Map an unique value to each key on the keyboard, just as:

call updateKey("a","apple")
call updateKey("b","banana")
call updateKey("c","cucumber")
 

Only difference is we MapKey (“A”, 65) to set a value of 65 to the “A” key, rather than an “apple”.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 06, 2021, 04:37:53 pm
Here is what RC has on assoc arrays probably the key phrase is "indexed by arbitrary data types":
http://rosettacode.org/wiki/Associative_array

but according to the PL your looking at, could be very different interpretations. Just about any array we know in QB64 is indexed with integers so we have to fiddle to make it work as if indexed by strings or other things.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 07, 2021, 12:55:07 am
I added some more bells and whistles to Dictionary Subs and Functions, appending to values and removing KV pair or removing a value in a list of them:
Code: QB64: [Select]
  1. Option _Explicit ' Dictionary 2 b+ remake of TempodiBasic post 2021-04-06
  2. ' ref: https://www.qb64.org/forum/index.php?topic=3786.msg131448#msg131448
  3. ' 2021-04-07 add some bells and whistles
  4.  
  5. Type Dictionary
  6.     K As String
  7.     V As String
  8.  
  9. ReDim MyDict(1 To 1) As Dictionary ' use ubound of array to tell how many values we have
  10.  
  11. ' make some new pairs
  12. Print "Show empty MyDict at start of this demo:"
  13. ShowDict MyDict()
  14. Print "Add a KV pair:"
  15. AddModDictionary MyDict(), "mammals", "Cats"
  16. ShowDict MyDict()
  17. Print "Add a KV pair:"
  18. AddModDictionary MyDict(), "trees", "Oak"
  19. ShowDict MyDict()
  20. Print "Add a KV pair:"
  21. AddModDictionary MyDict(), "fish", "Bass"
  22. ShowDict MyDict()
  23. Print "Swap Dogs for Cats in mammals:"
  24. AddModDictionary MyDict(), "mammals", "Dogs"
  25. ShowDict MyDict()
  26. Print "Check current mammals:"
  27. Print "What is current mammal ? answer: "; GetValue$(MyDict(), "mammals")
  28. Print "Remove mammals:"
  29. RemoveKV MyDict(), "mammals"
  30. ShowDict MyDict()
  31. Print "Bring mammals back with Horses AND Dogs,Cats:"
  32. AddAppendDictionary MyDict(), "Mammals", "Horses"
  33. AddAppendDictionary MyDict(), "mammals", "Cats,Dogs"
  34. ShowDict MyDict()
  35. Print "Remove Cats from mammals:"
  36. RemoveValue MyDict(), "mammals", "Cats"
  37. ShowDict MyDict()
  38. Print "Remove Horses from mammals:"
  39. RemoveValue MyDict(), "mammals", "Horses"
  40. ShowDict MyDict()
  41. Print "Remove Unicorns from mammals:"
  42. RemoveValue MyDict(), "mammals", "Unicorns"
  43. ShowDict MyDict()
  44. Print "And finally wipe out mammals again by removing dogs:"
  45. RemoveValue MyDict(), "mammals", "Dogs"
  46. ShowDict MyDict()
  47.  
  48.  
  49. ' replace 2 TempodiBasic Functions with 1 Sub, to handle both new and modified values for keys and dynamic Dict() dbl string array.
  50. ' Now just take ubound of dict() and have number of pairs it contains
  51. Sub AddModDictionary (Dict() As Dictionary, K$, V$)
  52.     ReDim ub As Long, i As Long, ky$
  53.     ub = UBound(dict)
  54.     ky$ = UCase$(_Trim$(K$)) 'don't change k$ but make case insensitive?
  55.     If ky$ <> "" Then ' bullet proof sub routine K$ must not be empty!
  56.         If ub = 1 And Dict(1).K = "" Then 'our very first pair!
  57.             Dict(1).K = ky$: Dict(1).V = V$: Exit Sub
  58.         Else
  59.             For i = 1 To ub ' see if we have that name yet
  60.                 If ky$ = Dict(i).K Then Dict(i).V = V$: Exit Sub ' yes name is registered so change value
  61.             Next
  62.             'still here? add var name and value to dictionary
  63.             ReDim _Preserve Dict(1 To ub + 1) As Dictionary ' create one slot at a time such that ubound = number or pairs
  64.             Dict(ub + 1).K = ky$: Dict(ub + 1).V = V$ ' fill it with key and value
  65.         End If
  66.     End If
  67.  
  68. ' fixed for
  69. Function GetValue$ (Dict() As Dictionary, K$)
  70.     Dim i As Long
  71.     For i = 1 To UBound(Dict)
  72.         If Dict(i).K = UCase$(_Trim$(K$)) Then
  73.             GetValue$ = Dict(i).V: Exit Function
  74.         End If
  75.     Next
  76.  
  77. 'modified for quick look
  78. Sub ShowDict (Dict() As Dictionary)
  79.     Dim i As Long
  80.     Print "Dictionary has "; _Trim$(Str$(UBound(dict))); " items."
  81.     For i = 1 To UBound(dict)
  82.         Print i, Dict(i).K, Dict(i).V
  83.     Next
  84.     Print
  85.     Print "zzz... press any to continue"
  86.     Sleep
  87.     Print
  88.  
  89. '========================== new stuff 2021-04-07
  90.  
  91. Sub RemoveKV (Dict() As Dictionary, K$)
  92.     Dim As Long i, j
  93.     For i = 1 To UBound(Dict)
  94.         If Dict(i).K = UCase$(_Trim$(K$)) Then
  95.             If i <> UBound(dict) Then
  96.                 For j = i + 1 To UBound(dict)
  97.                     Swap Dict(j - 1), Dict(j)
  98.                 Next
  99.             End If
  100.             ReDim _Preserve Dict(1 To UBound(dict) - 1) As Dictionary
  101.             Exit Sub
  102.         End If
  103.     Next
  104.  
  105. ' instead or replacing a value with another we will add the new value delimited by a comma
  106. Sub AddAppendDictionary (Dict() As Dictionary, K$, V$)
  107.     ReDim ub As Long, i As Long, ky$
  108.     ub = UBound(dict)
  109.     ky$ = UCase$(_Trim$(K$)) 'don't change k$ but make case insensitive?
  110.     If ky$ <> "" Then ' bullet proof sub routine K$ must not be empty!
  111.         If ub = 1 And Dict(1).K = "" Then 'our very first pair!
  112.             Dict(1).K = ky$: Dict(1).V = V$: Exit Sub
  113.         Else
  114.             For i = 1 To ub ' see if we have that name yet
  115.                 If ky$ = Dict(i).K Then Dict(i).V = Dict(i).V + "," + V$: Exit Sub ' yes name is registered so change value
  116.             Next
  117.             'still here? add var name and value to dictionary
  118.             ReDim _Preserve Dict(1 To ub + 1) As Dictionary ' create one slot at a time such that ubound = number or pairs
  119.             Dict(ub + 1).K = ky$: Dict(ub + 1).V = V$ ' fill it with key and value
  120.         End If
  121.     End If
  122.  
  123. Sub RemoveValue (Dict() As Dictionary, K$, RemoveV$)
  124.     ReDim As Long ub, i, j
  125.     ReDim ky$, b$
  126.     ub = UBound(dict)
  127.     ky$ = UCase$(_Trim$(K$)) 'don't change k$ but make case insensitive?
  128.     If ky$ <> "" Then ' bullet proof sub routine K$ must not be empty!
  129.         If ub = 1 And Dict(1).K = "" Then 'our very first pair!
  130.             Exit Sub
  131.         Else
  132.             For i = 1 To ub ' see if we have that name yet
  133.                 If ky$ = Dict(i).K Then
  134.                     If InStr(Dict(i).V, ",") > 0 Then
  135.                         ReDim t$(1 To 1)
  136.                         Split Dict(i).V, ",", t$()
  137.                         For j = 1 To UBound(t$)
  138.                             If t$(j) <> RemoveV$ Then
  139.                                 If b$ = "" Then
  140.                                     b$ = t$(j)
  141.                                 Else
  142.                                     b$ = b$ + "," + t$(j)
  143.                                 End If
  144.                             End If
  145.                         Next
  146.                         Dict(i).V = b$
  147.                     ElseIf Dict(i).V = RemoveV$ Then
  148.                         Dict(i).V = ""
  149.                     End If
  150.                     Exit Sub
  151.                 End If
  152.             Next
  153.         End If
  154.     End If
  155.  
  156. ' note: I buggered this twice now, FOR base 1 array REDIM MyArray (1 to 1) AS ... the (1 to 1) is not same as (1) which was the Blunder!!!
  157. 'notes: REDIM the array(0) to be loaded before calling Split '<<<< IMPORTANT dynamic array and empty, can use any lbound though
  158. 'This SUB will take a given N delimited string, and delimiter$ and create an array of N+1 strings using the LBOUND of the given dynamic array to load.
  159. 'notes: the loadMeArray() needs to be dynamic string array and will not change the LBOUND of the array it is given.  rev 2019-08-27
  160. Sub Split (SplitMeString As String, delim As String, loadMeArray() As String)
  161.     Dim curpos As Long, arrpos As Long, LD As Long, dpos As Long 'fix use the Lbound the array already has
  162.     curpos = 1: arrpos = LBound(loadMeArray): LD = Len(delim)
  163.     dpos = InStr(curpos, SplitMeString, delim)
  164.     Do Until dpos = 0
  165.         loadMeArray(arrpos) = Mid$(SplitMeString, curpos, dpos - curpos)
  166.         arrpos = arrpos + 1
  167.         If arrpos > UBound(loadMeArray) Then ReDim _Preserve loadMeArray(LBound(loadMeArray) To UBound(loadMeArray) + 1000) As String
  168.         curpos = dpos + LD
  169.         dpos = InStr(curpos, SplitMeString, delim)
  170.     Loop
  171.     loadMeArray(arrpos) = Mid$(SplitMeString, curpos)
  172.     ReDim _Preserve loadMeArray(LBound(loadMeArray) To arrpos) As String 'get the ubound correct
  173.  
  174.  
  175.  
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: TempodiBasic on April 08, 2021, 09:48:19 am
@bplus
Cool! Now you have done a complete basic dictionary data  (associated arrays or arrays of couple of value (a key of order not numeric + a value or sequence values)

and with the AddAppendDictionary you have covered the Achille's ankle of AddModDictionary!.

Good gimme just some time and I'll complete the Dictionary engine using bidimensional array and that other with string .
For now You can publish on RosettaCode website.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 08, 2021, 12:24:52 pm
I have come to realize that Dictionary allowing multiple values (or no values) for a Key's Value is a way to get an array of arrays functionality, as AStrings (Array-Strings) of course.

So next comes Saving and Loading Dictionary's to/from file and converting them for use in a Type String.

Quote
For now You can publish on RosettaCode website.
Perhaps after more critical review from experts. I was excited about posting something for Knapsack problem in JB then learned I missed an important aspect of problem even if I got the sample task correct. And after getting Word Search posted Richard Frost showed way to a stronger code method. The more brains involved the better.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: Aurel on April 09, 2021, 05:23:24 pm
well
first of all hash table or dictionary or map is not exactly same as associative array
of course hash table can be used as token list with token values ...ordinary as interger types like
key (print) , value(10)
hash or hashed means using prime number as hashing method but not nesesery.
lookup() function can be used here of course...
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: TempodiBasic on April 10, 2021, 04:58:50 pm
Hi
I have followed the definition on the Rosetta Code website but the definition on wikipedia seems very close
https://en.wikipedia.org/wiki/Associative_array#:~:text=In%20computer%20science%2C%20an%20associative,most%20once%20in%20the%20collection. (https://en.wikipedia.org/wiki/Associative_array#:~:text=In%20computer%20science%2C%20an%20associative,most%20once%20in%20the%20collection.)

Quote
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

After a complete dictionary engine in QB64 it will be fine to have some demonstrations in different fields of application of associative arrays.

what do you think about?
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: bplus on April 10, 2021, 05:18:28 pm
I'm thinking of doing oh with dictionaries to track variables in actual Subs and / or Functions along with Main module.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional
Post by: Aurel on April 11, 2021, 06:32:52 am
That is good thinking Mark..
i tried to make interpreter using hash table in past ...well  but i don't get any real boost
with that ..only more options

ps ..and please don't use too much ReDim -s that eat execution time .
(ps... ps ...but maybe i am in wrong )
Title: Re: A demo of Dictionary or hash table made with a array bidimensional(Rosetta Code)
Post by: TempodiBasic on April 21, 2021, 07:06:23 pm
@bplus
do you think that your engine for dictionary data type is completed and your code is ready to be published on Rosetta Code? Or do you need more time to  think about this task?
Title: Re: A demo of Dictionary or hash table made with a array bidimensional(Rosetta Code)
Post by: bplus on April 21, 2021, 07:52:31 pm
@bplus
do you think that your engine for dictionary data type is completed and your code is ready to be published on Rosetta Code? Or do you need more time to  think about this task?

I think I did all I would want from a Dictionary Library. Dang haven't got around to trying with the oh Interpreter yet.
Really it's when you go to apply something you learn what's needed!

If anyone sees something needed for complete set of functions I will be glad to try more.
Title: Re: A demo of Dictionary or hash table made with a array bidimensional(Rosetta Code)
Post by: TempodiBasic on April 22, 2021, 07:12:17 pm
Hi Bplus
here I post my version of Associates Arrays  using an array bidimensional of strings  to create a dictionary of couple Key-value
The dictionary engine has its basic functions: PutDict add a couple key-value to the dictionary, GetDict returns the value of a key, ChangeValueDict  changes  the value of key, ChangeKeyValueDict  change a key of dictionary,  EraseKeyDict  cancels a couple key-value from dictionary,  FindDuplicateKey finds if a key is still in dictionary, CompactDict moves all couples key-values to the bottom of dictionary, ShowDict shows the whole or a part of the dictionary.
Code: QB64: [Select]
  1. Const False = 0, True = Not False, sValue = 2, sKey = 1
  2.  
  3. Dim Mydict(1 To 10, 1 To 2) As String
  4.  
  5. ' start of demo
  6.  
  7. If PutDict(Mydict(), "b", "battle") = True Then Print " Inserted couple key value"
  8. If PutDict(Mydict(), "c", "cheesebattle") = True Then Print " Inserted couple key value"
  9. If PutDict(Mydict(), "a", "ancient") = True Then Print " Inserted couple key value"
  10. If PutDict(Mydict(), "d", "domus") = True Then Print " Inserted couple key value"
  11. If PutDict(Mydict(), "e", "embarassing") = True Then Print " Inserted couple key value"
  12. If PutDict(Mydict(), "e", "entering") = False Then Print " Key already in use"
  13. ShowDict Mydict(), 2, 5
  14. Print " we search the key a and e"
  15. If GetDict(Mydict(), "b") <> "" Then Print GetDict(Mydict(), "b")
  16. If GetDict(Mydict(), "e") <> "" Then Print GetDict(Mydict(), "e")
  17. Print " we change key b and e"
  18. If ChangeValueDict(Mydict(), "b", "BASIC") Then Print "changement done"
  19. If ChangeValueDict(Mydict(), "e", "Elephant") Then Print "changement done"
  20. If GetDict(Mydict(), "e") <> "" Then Print GetDict(Mydict(), "e")
  21. If GetDict(Mydict(), "b") <> "" Then Print GetDict(Mydict(), "b")
  22. Print PutDict(Mydict(), "q", "proof tool")
  23. Print PutDict(Mydict(), "y", "Yes/No")
  24. ShowDict Mydict(), 0, 0
  25. Print " we erase key e"
  26. If EraseKeyDict(Mydict(), "e") = True Then Print "key passed erased"
  27. If GetDict(Mydict(), "e") <> "" Then Print GetDict(Mydict(), "e") Else Print "key passed not foud"
  28. ShowDict Mydict(), 0, 0
  29. CompactDict Mydict()
  30. Print "Dictionary compacted"
  31. ShowDict Mydict(), 1, 0
  32. ' end of demo
  33.  
  34. ' it puts a couple key-value at the first free space in the array
  35. Function PutDict (dict() As String, Keys As String, Value As String)
  36.     PutDict = False
  37.     Dim Count As Integer
  38.     If FindDuplicateKey(dict(), Keys) = True Then Exit Function
  39.     For Count = 1 To UBound(dict, sKey)
  40.         If dict(Count, sKey) = "" Then Exit For
  41.     Next
  42.     dict(Count, sKey) = Keys
  43.     dict(Count, sValue) = Value
  44.     PutDict = True
  45.  
  46. 'it returns the value present at key passed
  47. Function GetDict$ (dict() As String, Keys As String)
  48.     GetDict$ = ""
  49.     Dim Count As Integer
  50.     For Count = 1 To UBound(dict, sKey)
  51.         If dict(Count, sKey) = Keys Then
  52.             GetDict$ = dict(Count, sValue)
  53.             Exit For
  54.         End If
  55.     Next
  56.  
  57. ' it changes the value related to a key passed
  58. Function ChangeValueDict (dict() As String, Keys As String, Value As String)
  59.     ChangeValueDict = False
  60.     Dim Count As Integer
  61.     For Count = 1 To UBound(dict, sKey)
  62.         If dict(Count, sKey) = Keys Then
  63.             dict(Count, sValue) = Value
  64.             Exit For
  65.         End If
  66.     Next
  67.     ChangeValueDict = True
  68.     If dict(Count, sValue) <> Value Then ChangeValueDict = False
  69.  
  70. 'it changes a key to another
  71. Function ChangeKeyValueDict (dict() As String, Keys As String, newKey As String)
  72.     ChangeKeyValueDict = False
  73.     Dim Count As Integer
  74.     'if there isn't keys  or if there is yet newKey , it exits
  75.     If FindDuplicateKey(dict(), newKey) = True Or FindDuplicateKey(dict(), Keys) = False Then Exit Function
  76.     For Count = 1 To UBound(dict, sKey)
  77.         If dict(Count, sKey) = Keys Then
  78.             dict(Count, sKey) = newKey
  79.             Exit For
  80.         End If
  81.     Next
  82.     ChangeKeyValueDict = True
  83.     If dict(Count, sKey) <> newKey Then ChangeKeyValueDict = False
  84.  
  85. 'it erases a couple with key Keys
  86. Function EraseKeyDict (dict() As String, Keys As String)
  87.     EraseKeyDict = False
  88.     Dim Count As Integer
  89.     For Count = 1 To UBound(dict, sKey)
  90.         If dict(Count, sKey) = Keys Then
  91.             dict(Count, sValue) = ""
  92.             dict(Count, sKey) = ""
  93.             Exit For
  94.         End If
  95.     Next
  96.     EraseKeyDict = True
  97.     If (dict(Count, sKey) <> "") Or (dict(Count, sValue) <> "") Then EraseKeyDict = False
  98.  
  99. 'it shows dict from start to the end or the full dict
  100. Sub ShowDict (dict() As String, Start As Integer, Ends As Integer)
  101.     Dim Count As Integer
  102.     If Start = 0 Or Start > Ends Or Start > UBound(dict, sKey) Then Start = 1
  103.     If Ends < Start Or Ends = 0 Or Ends > UBound(dict, sKey) Then Ends = UBound(dict, sKey)
  104.     For Count = Start To Ends
  105.         Print dict(Count, sKey); " - "; dict(Count, sValue)
  106.     Next
  107.  
  108. ' it finds a key if it is yet in the dict() array
  109. Function FindDuplicateKey (dict() As String, keys As String)
  110.     Dim Count As Integer
  111.     ' it searches a duplicate if it finds exit function
  112.     For Count = 1 To UBound(dict, sKey)
  113.         If dict(Count, sKey) = keys Then
  114.             FindDuplicateKey = True
  115.             Exit Function
  116.         End If
  117.     Next
  118.  
  119. 'it shrinks the dict  moving all keys to the bottom of array
  120. Sub CompactDict (dict() As String)
  121.     Dim count As Integer, count2 As Integer
  122.     For count = 1 To UBound(dict, sKey) - 1
  123.         If dict(count, sKey) = "" Then
  124.             For count2 = count + 1 To UBound(dict, sKey)
  125.                 If dict(count2, sKey) <> "" Then Exit For
  126.             Next
  127.             If count2 <= UBound(dict, sKey) Then Swap dict(count, sKey), dict(count2, sKey): Swap dict(count, sValue), dict(count2, sValue)
  128.         End If
  129.     Next

about the UDT version I seem to understand that it is ready to be published.
Good!