TI-BASIC:Dictionary

A dictionary (also known as a map) is a data structure in which one piece of data maps to another piece of data, and the first datum (the key) maps to and only to the second datum (the value). Much like how a word in a dictionary maps to a definition. However, there can be multiple keys for the same value. The major operations for a dictionary are put, contains, get, and remove. Put adds a key and a value to the dictionary. Contains indicates whether or not a key is to be found within the dictionary. Get retrieves the value associated with the given key. Remove removes a key and value pair based on a given key.

Implementation in TI-Basic

The most easily created dictionary in TI-Basic is implemented using a string. The string would have many keys and values, separated by delimiters (similar to the string implementations of stacks and queues). The string can have keys and values of any length so a delimiter must be used to separate the keys and values from each other. The delimiter can be any short string that will never appear in any of the entries. To create a dictionary store an instance of the delimiter into the string. This is because in TI-Basic, one cannot add to empty strings, and for our implementation, each key and value must be surrounded by a delimiter on either end. The reason for this will become clear soon. We must also add a padding character at each end. This will be to remove special cases for the remove operation.

:"?::?"→Str0

It does not matter onto which end we put data because we can get and remove data from any point in the dictionary so for this instance, we're going to add to the end of the dictionary.

:sub(Str0,1,length(Str0)-1)+"KEY"+"::"+"VALUE"+"::"+"?"→Str0

To find whether a key is contained with in the dictionary use inString(. If it returns 0, the key is not in the dictionary.

:inString("::"+KEY+"::")→N

To retrieve a value, we first have to find the location of the key using the inString( function. Then we add to that the length of the key and the lengths of the two surrounding delimiters. We now know the location of the first character of the value. To find the length of value use inString( starting at that location and subtract it from the first location.

:"KEY"→Str1
:"::"→Str2
:inString(Str0,Str2+Str1+Str2)
:If Ans:Then
:Ans+length(Str1)+2*length(Str2)→N
:inString(Str0,Str2,N)→M
:sub(Str0,N,M-N)→Str3
:End

To remove a value, we have to use the same code as above to locate the end of the key-value segment of the string. We then concatenate the part of the string before the key-value combination and the part of the string after the key-value combination. This is why we added the surrounding characters ("?"), because we can't concatenate with an empty string in TI-Basic.

:instring(Str0,Str2+Str1+Str2)→N
:Ans+length(Str1)+2*length(Str2)
:inString(Str0,Str2,Ans)+length(Str2)→M
:sub(Str0,1,N-1)+sub(Str0,M,length(Str0)-M+1)→Str1