Data structures

From RFO-BASIC! Manual
Manual contents (Statement index)
Language features The basicsArraysData structuresInterrupt routinesUser-defined functions
Interfaces Audio playerBluetoothFilesGraphicsHTMLKeyboardSocketsSQLTelecom
Programming notes Coexisting with Android

RFO-BASIC! provides scalar (single-element) and array variables of both numeric and string types. It also provides the following data structures for more complex needs:

  • Lists, which are comparable to arrays.
  • Stacks, which are last-in-first-out structures.
  • Bundles, which are lists of numeric and string items identified by tags.

The BASIC program deals with these data structures using a numeric pointer, just as it deals with files. When a BASIC statement creates a data structure, BASIC assigns it a pointer and the statement returns the data structure's pointer. The program must use the same pointer to refer to the data structure. (Many of BASIC's other features create data structures to which the BASIC program refers with a number. These include bitmaps, items in the graphics Display List, audio files, and SoundPool entries.)

The pointer is a number that refers to a data structure. You can compare two pointers to see if they refer to the same data structure. However, you should not modify any pointer, such as subtracting 1 from it to gain access to a data structure created previously. BASIC makes no guarantees about the value of any pointer except that it will continue to refer to the associated data structure.

The size of these data structures is unlimited except by the total amount of memory available to the program.

All data structures are destroyed when the BASIC program ends. Their information is not available if the same program runs again. For permanent storage of information, BASIC programs can use files, which reside on the Android device's internal storage device or on the SD card, or can use SQL to put the information in a database.

User-defined functions normally return to their callers a single value. However, they can use data structures to communicate with the rest of the program more freely. For example, a BASIC program could pass to a user-defined function a pointer to a stack. The function could push any number of items onto the stack for use elsewhere in the program.

Lists[edit]

A list is like an array, except that it can be extended indefinitely as the program runs and it is easy to insert and remove items from a list and have subsequent items shift position.

Every list is either a list of numbers or a list of strings, which is specified when you create the list. The LIST.TYPE statement checks the type of a specified list. A list statement with a variable that does not match the type of the list always produces a run-time error. Initially, every list has no items and its size is 0.

Elements in a list are referred to by number. A list's first element is always 1.

A list cannot be destroyed, but LIST.CLEAR removes all the information from a list.

LIST.CREATE[edit]

Create a list

Synopsis
LIST.CREATE N,<plist_nvar>
LIST.CREATE S,<plist_nvar>
Description

The LIST.CREATE statement creates a list and returns the pointer to it in <plist_nvar>. The form with N creates a numeric list. The form with S creates a string list. The N or S is not a string expression and cannot have quotes around it.

LIST.ADD[edit]

Append elements to a list

Synopsis
LIST.ADD <plist_nexp>{, <exp>}...
Description

The LIST.ADD statement adds one or more elements to the list pointed to by <plist_nexp>. The elements go to the end of the list, in the sequence in which they are specified in LIST.ADD.

If a LIST.ADD statement adds more than one element, the elements are separated by commas. The list may be continued onto subsequent lines by ending the line with ~. This character can appear after a comma or can take the place of a comma, but it cannot be placed in the middle of an element.

Example

The following code creates and populates a list of names:

LIST.CREATE S,Names
LIST.ADD Names~
 "Bill", "Jones"~
 "James", "Barnes"~
 "Jill", "Hanson"

LIST.ADD.LIST[edit]

Append elements to a list from another list

Synopsis
LIST.ADD.LIST <pdest_nexp>, <psource_nexp>
Description

The LIST.ADD.LIST statement appends to the list pointed to by <pdest_nexp> the entire contents of the list pointed to by <psource_nexp>. The source list is not changed. The resulting length of the destination list is its old length plus the length of the source list.

LIST.ADD.ARRAY[edit]

Append elements to a list from an array

Synopsis
LIST.ADD.ARRAY <pdest_nexp>, <source_arr>
Description

The LIST.ADD.ARRAY statement appends to the list pointed to by <pdest_nexp> the relevant contents of the array <source_arr>. The array is unchanged. The array must be the same type (numeric or string) as the destination list. You can specify any of the following:

A[] Append the entire array to the list
A[start,length] Append length elements of the array, starting with the element at position start.

Querying a list[edit]

If you have a pointer to an list, two BASIC statements let you retrieve attributes of the list:

  • LIST.TYPE <plist_nexp>, <type_svar>
    Sets <type_svar> to the character S if the list is a string list, or to the character N if the list is a numeric list.
  • LIST.SIZE <plist_nexp>, <size_nvar>
    Sets <size_nvar> to the number of elements in the list.

Reading and modifying list elements[edit]

Apart from the LIST.ADD. statements discussed above, the following statements read and write individual list elements without affecting any other elements in the list:

  • LIST.GET <plist_nexp>, <index_nexp>, <element_var>
    Get element number <index_nexp> of the list whose pointer is <plist_nexp>, and deposit its value in <element_var>.
  • LIST.REPLACE <plist_nexp>, <index_nexp>, <new_exp>
    Set element number <index_nexp> of the list whose pointer is <plist_nexp> to have the value of <new_exp>.

Two other statements insert and remove list elements. These statements implicitly shift subsequent elements in the list.

  • LIST.INSERT <plist_nexp>, <index_nexp>, <new_exp>
    Insert a new element whose value is <new_exp> at location <index_nexp> in the list whose pointer is <plist_nexp>, first shifting the former element at that position, and all elements beyond it, to a position one greater. As well as addressing any of the existing elements of the list, <index_nexp> can be one greater than the size of the list; this appends the value to the list as a new last element. But <index_nexp> cannot have an even greater value; you cannot create new elements so as to create a gap in the list.
  • LIST.REMOVE <plist_nexp>, <index_nexp>
    Remove the element at location <index_nexp> from the list whose pointer is <plist_nexp>. If removing any element other than the final element, each element beyond it shifts to a position one smaller.
Example

A general form for processing every element of a list is as follows:

LIST.SIZE MyList, s
FOR i = 1 to s
 LIST.GET MyList, i, Value
 % Process "Value" as desired
NEXT i

Processing elements of a list as a queue is discussed below.

Miscellaneous list statements[edit]

  • LIST.CLEAR <pointer_nexp>
    Clear the list pointed to by <pointer_nexp>. The list now has size zero and none of its former values is accessible, but the program could now add new values to the list.
  • LIST.SEARCH <pointer_nexp>, <value_exp>, <result_nvar>{,<start_nexp>}
    Searches the specified list for <value_exp>. The statement sets <result_nvar> to the index of the first element with that value. If there are no such elements, then <result_nvar> is set to 0. If <start_nexp> is present, the search starts at the element with that number; otherwise, it starts with the first element (element number 1).
  • LIST.TOARRAY <pointer_nexp>, <dest_arr>
    Copies the specified list into an array. The statement fails if the list has no elements. If the array exists, it is overwritten, otherwise a new array is created. The result is always a one-dimensional array.

Using a list as a queue[edit]

The variety of statements in the LIST. group lets you use a list as a queue. A queue, like a teller line at a bank, is a list that is occasionally added to, but elements in it are processed starting with the one that has been in the queue the longest: on a first-in, first-out (FIFO) basis.

To use a list as a queue, append elements to it using any of the three LIST.ADD statements. Remove elements from the queue at the start of the list, with:

LIST.SIZE MyQueue, n
IF n > 0 THEN
 LIST.GET MyQueue, 1, Value
 LIST.REMOVE MyQueue, 1
 % Process "Value" as desired
ENDIF

To minimize time spent in an interrupt routine with other interrupts disabled, the routine might put reports of the events (such as keystrokes) into a queue. The main program would test the queue, remove the oldest elements, and do work based on them.

Stacks[edit]

Stacks, like lists, are sequences of numbers or strings. (You specify which when you create the stack.) You create a stack when you expect it to be used on a last-in, first-out (LIFO) basis. It is comparable to a stack of magazines on the table. You add a magazine to the top of the stack, which is then the first one you take off the stack. Instead of the general-purpose list statements, the BASIC statements for stacks push a new value onto the top of the stack and pop the top value off the stack. Usually, reading the top value from the stack removes it from the stack. There are a few other stack statements, but pushing and popping are the typical ways to use a stack.

Every stack is either a stack of numbers or a stack of strings, which is specified when you create the stack. The STACK.TYPE statement checks the type of a specified stack. A stack statement with a variable that does not match the type of the stack always produces a run-time error. Initially, every stack has no items and STACK.ISEMPTY returns TRUE.

The program Sample_Programs/f29_stack.bas included with the RFO-BASIC! installation illustrates the stack operations.

STACK.CREATE[edit]

Create a stack

Synopsis
STACK.CREATE N <pointer_nvar>
STACK.CREATE S <pointer_nvar>
Description

The STACK.CREATE statement creates a new stack. The form with N creates a numeric stack. The form with S creates a string stack. The N or S is not a string expression and cannot have quotes around it.

The statement sets <pointer_nvar> to a numeric value that can be used in subsequent STACK. statements to refer to this stack.

If a BASIC program processes values off a stack until the stack is empty, it does not need to create another stack. It can push new values onto the same stack.

STACK.PUSH[edit]

Push a value onto a stack

Synopsis
STACK.PUSH <pointer_nvar>, <value_exp>
Description

The STACK.PUSH statement pushes <value_exp> onto the stack whose pointer is <pointer_nvar>. It does not remove or take the place of any other element; rather, the new value is now the top element of the stack and is the one that would be retrieved by a call to STACK.POP.

Example

User-defined functions do not have access to variables defined outside the function, but the caller could pass the function a pointer to a stack. Without needing to modify this pointer, the function could use it in calls to STACK.PUSH to push any number of values onto the stack for the caller to process:

FN.DEF Results(StackPointer)
 % Do some computing, resulting in A$, B$, and C$
 STACK.PUSH StackPointer, C$
 STACK.PUSH StackPointer, B$
 STACK.PUSH StackPointer, A$
 FN.RET 1  % Caller can now pop A$, B$, and then C$
FN.END

STACK.POP[edit]

Pop a value off the stack

Synopsis
STACK.POP <pointer_nvar>, <value_var>
Description

The STACK.POP statement pops the top value off the stack whose pointer is <pointer_nvar> and places the value in <value_var>. There is now one fewer element on the stack.

STACK.PEEK[edit]

Retrieve the top value on the stack without modifying the stack

Synopsis
STACK.PEEK <pointer_nvar>, <value_var>
Description

The STACK.PEEK statement retrieves the top value on the stack whose pointer is <pointer_nvar> and places the value in <value_var>. This is like STACK.POP; but unlike STACK.POP, STACK.PEEK does not pop the top value off. The stack is unchanged.

STACK.CLEAR[edit]

Pop all the values off a stack

Synopsis
STACK.CLEAR <pointer_nvar>
Description

The STACK.CLEAR statement pops all the values off the stack whose pointer is <pointer_nvar>, but does not return them to the caller. The stack is now empty, but the program could use STACK.PUSH to push new values onto the stack.

Querying a stack[edit]

If you have a pointer to a stack, two BASIC statements let you retrieve attributes of the stack:

  • STACK.TYPE <pstack_nexp>, <type_svar>
    Sets <type_svar> to the character S if the stack is a string stack, or to the character N if the stack is a numeric stack.
  • STACK.ISEMPTY <pstack_nexp>, <result_lvar>
    If the stack is empty, STACK.ISEMPTY sets <result_lvar> to TRUE (1). Otherwise, it sets <result_lvar> to FALSE (0).
Example

A BASIC loop that processes information off a stack would use STACK.ISEMPTY to determine when there was no more work to do:

DO
 STACK.ISEMPTY MyStack, Done
 IF Done THEN D_U.BREAK  % Leave loop if nothing left on the stack
 STACK.POP MyStack, Element
 % Process "Element" as desired
UNTIL 0

Bundles[edit]

A bundle is a data structure that can contain string and numeric values. Elements have no sequence within a bundle. Instead, each element has a string key with which the program gains access to the element. Bundle keys are:

  • Unique. A bundle cannot contain more than one element with the same key; if a program executes BUNDLE.PUT specifying a key that already exists, its previous value is replaced by the new value.
  • Case-sensitive. An element whose key is "ABC" is not the same as the element with key "abc". Failure to match capital and lowercase letters exactly may be the reason for an error message that the desired key does not exist.

To store multiple records whose data have the same key, or to store information that will last after the program ends, use SQL.

The only limit to the size of a bundle is the total amount of memory available to the BASIC program. A bundle is a compressed HashMap, so creating a large number of keys doesn't unduly slow down access. If sending a bundle to another app on your Android device using "intents," there is a limit of about one megabyte.

Auto-creation

In every statement in the BUNDLE. set, the first parameter is a pointer to the bundle. In BUNDLE.CREATE, this parameter must be a numeric variable; the statement sets the variable to a value that subsequent statements can use to refer to the bundle.

In all other BUNDLE. statements, the pointer can be a variable or an expression. If a BUNDLE. statement refers to a bundle that does not yet exist:

  • If the pointer is a numeric variable, the statement creates a bundle and sets the variable to a new bundle pointer.
  • If the pointer is some other numeric expression, the statement has no effect, because the statement has no way to return the new bundle pointer.
The Bundle 1 trick

Despite the general rule that BASIC programs should not rely on the numeric value of a pointer to any data structure, BASIC programs often take advantage of the fact that the first bundle created has a pointer with value 1. Programs can get around the fact that user-defined functions do not have access to variables created outside the function by using BUNDLE. statements with a pointer of 1. This uses the first bundle created by the mainline as a repository of common variables. For example, user-defined functions performing operations on the graphics screen can obtain variables through keys in Bundle 1 that describe global rules for using the screen, such as the dimensions of a portion of the screen designated for use.

If several routines use Bundle 1 without coordination, each routine should add a prefix to the names of its keys, to avoid interference with keys created by other software.

The Bundle 1 trick is problematic when writing a library to be used (via INCLUDE) by potentially many programs. This is because there might be other such libraries, and only the first library to create a bundle for global variables actually obtains the number 1.

Adding complexity

Keys can be arbitrarily long. By structuring the names of keys, a program can make a bundle act like an array or act as though it contained sub-bundles. Suppose a bundle contained the following keys:

WINDOW-5-TOP
WINDOW-5-LEFT
WINDOW-5-HEIGHT
WINDOW-5-WIDTH

An expression such as "WINDOW-" + STR$(I) + "-TOP" composes a key name and gains access to bundle elements specifying the top, or other measurements, of window number I. By extending the key name, a program could use a bundle as a multidimensional array:

POLYGON-5-VERTEX-2-YCOORD

A bundle with keys like this could describe many polygons, which might have different numbers of vertices.

BUNDLE.CREATE[edit]

Create a bundle

Synopsis
BUNDLE.CREATE <pbundle_nvar>
Description

The BUNDLE.CREATE statement creates a new bundle and returns in <pbundle_nvar> a numeric value that subsequent statements can use to refer to the bundle. The new bundle contains no elements.

BUNDLE.PUT[edit]

Put an element into a bundle

Synopsis
BUNDLE.PUT <pbundle_nvar>, <key_sexp>, <value_exp>
Description

The BUNDLE.PUT statement puts <value_exp> into the bundle pointed to by <pbundle_nvar>, under the key <key_sexp>. If the bundle already had an element with the specified key, it is replaced; otherwise, a new element is created. The element is of type string or numeric depending on the type of <value_exp>.

Examples
BUNDLE.PUT bptr, "first_name", "Frank"   % Create a string element
BUNDLE.PUT bptr, "age", 44               % Create a numeric element

BUNDLE.GET[edit]

Get an element from a bundle

Synopsis
BUNDLE.GET <pbundle_nvar>, <key_sexp>, <value_var>
Description

The BUNDLE.GET statement obtains a value from the bundle pointed to by <pbundle_nvar> that has the key <key_sexp>.

It is a run-time error if there is no element with the specified key or if its type is different from the type of <value_var>. A program can avoid this error by querying a bundle before getting a value from it.

Examples

The following statements retrieve values put into a bundle by the examples in the previous section.

BUNDLE.GET bptr, "first_name", fn$
BUNDLE.GET bptr, "age", age

Removing elements from a bundle[edit]

Two statements remove elements from a specified bundle:

  • BUNDLE.REMOVE <pbundle_nexp>, <key_sexp>
    Removes from the bundle pointed to by <pbundle_nexp> the element with key <key_sexp>.
  • BUNDLE.CLEAR <pbundle_nexp>
    Removes all the elements from the bundle pointed to by <pbundle_nexp>.

Querying a bundle[edit]

Two statements query the presence and type of an element in a bundle:

  • BUNDLE.CONTAIN <pbundle_nexp>, <key_sexp>, <result_lvar>
    If the bundle pointed to by <pbundle_nexp> contains an element with key <key_sexp>, sets <result_lvar> to TRUE (1); otherwise, sets <result_lvar> to FALSE (0).
  • BUNDLE.TYPE <pbundle_nexp>, <key_sexp>, <result_svar>
    If the bundle pointed to by <pbundle_nexp> contains a string element with key <key_sexp> sets <result_svar> to the character S. If the element is numeric, sets <result_svar> to the character N. If there is no such element, it is a run-time error.
Example

Here is an example of the use of both statements to ensure that a BUNDLE.GET statement will succeed:

number = -1                           % Assume failure
BUNDLE.CONTAIN bptr, "key1", exists
IF exists THEN
 BUNDLE.TYPE bptr, "key1", type
 IF type = "N" then
  BUNDLE.GET bptr, "key1", number     % Bundle contains a number
 ELSE
  BUNDLE.GET bptr, "key1", str$       % Bundle contains a string,
  number = VAL(str$)                  % convert it to a number
 ENDIF
ENDIF

Editor's queries[edit]

  • Does the rule for LIST.INSERT, regarding indexes beyond the last existing element, also apply to LIST.REPLACE?

Sources[edit]