This article describes how Small Basic arrays are handled internally.  It describes the advantages and disadvantages of the approach used, and introduces an alternative extension method 'LDList'.  As well as being faster, the extension method exposes new programmers to variable length collections, with some sorting and list handling capabilities.

Finally, a couple of examples are included.

Small Basic Arrays

Arrays in Small Basic consist of an index and value pair for each element of the array.  Since there is only one variable type in Small Basic (Primitive), the index and the value can be a number or string (or array).  The indices in an array must clearly be unique.

data[index] = value 'assign (or replace) a value to an array element
value = data[index] 'retrieve a value from an array element
data[index] = "" 'remove an element from an array
data = "" 'clear all elements of an array

Internally, the arrays are stored as Dictionaries with a <Key, Value> pair for each element of the array; both the Key and Value are of type Primitive.

The arrays can be converted to and from a string format, with index and value deliminated by '=' and elements deliminated by ';'.  In the example below data1 and data2 are equivalent.

data1[1] = "Hello"
data1[2] = "World"
 
data2 = "1=Hello;2=World;"

Multidimensional arrays are created by allowing the array values to be an array.  Actually the indices can also be arrays, which can be used to do interesting things.  Multidimensional arrays are accessed using multiple levels of [].  In the example below data1, data2 and data3 are equivalent 2D arrays.

data1[1][1] = "A1"
data1[1][2] = "A2"
 
data2[1] = "1=A1;2=A2;"
 
data[1] = "A1"
data[2] = "A2"
data3[1] = data

Since the indices may be integers or strings there is no order and therefore a lot of internal searching is required to identify array elements from an index.  Additionally, the Primitive data type conversion to and from the string representation can be a significant internal overhead.

The array index is usually, but not always simply an integer that allows the array elements to be easily accessed in a loop like below.

For 1 To 100
  sprite[i] = Shapes.AddImage(spriteImage)
EndFor

The benefits of the Small Basic method are:

  • Simple and intuitive to use for single and multidimensional arrays.  This is by far the most important feature and mean that this method is the 'best' for Small Basic.
  • A very general array structure that can be used to perform a wide range of array activities with a single syntax.
  • Array size, dimension and type do not have to be defined before they are used.

The drawbacks of the method include:

  • Can be slow or very slow for larger arrays (> 100 elements), especially for multidimensional arrays.
  • Can be harder to manage arrays (e.g. loop through) where elements are being created and deleted regularly where the indexing becomes non-contiguous (i.e. not sequential integer indexing).

Non contiguous indexing can be handled with Array.GetAllIndices, but this can add additional performance limitations.

Collections

A brief discussion of the characteristics of three common collection methods supported in .Net.  There are others and many variants, but these are the main ones.

Dictionary

A dictionary consists of elements that contain a <Key, Value> pair.  The Key and Value may be of any type.  Elements are indexed by the Key and can be added or removed at any time.  There is no internal order defined, access is simply by Key.

Array

An array has a predefined type, dimension and size.  Elements are indexed by integers and cannot be added or removed, only changed.  There is a strong internal order defined by the indices, therefore elements can be very rapidly accessed.

List

A list has characteristics of a dictionary and array, perhaps combining the best of both in many ways.

A list consists of elements of Values of a predefined type.  Elements are indexed either by an integer or the element Value, and can be added or removed at any time.  There is an internal order that always has contiguous integers (0, 1, 2, 3 etc), the index of an element may change when elements are inserted or removed.  Elements may be added to the end of the list or inserted within the list.  The list can also be easily sorted.  The number of indices that can be used to access the list is always equal to the current length of the list.

LDList object

A list object has been implemented in the Small Basic LitDev extension.  The following is the API.  There are quite a lot of methods, but most are for advanced sorting and list comparisons etc.

LDList
This object provides a way of storing values like an array that reorders itself as items are added or removed.
A list is an efficient array store (much faster than Small Basic arrays) that can be indexed by integers and perform various other operations.
The indexing is automatically updated (indexed from 1) as the list changes.


Add(listName,value)
Adds a value to the end of a specified list.
listName The name of the list.
value The value to add.
returns The number of items in the list or -1 on failure.

Append(listName1,listName2)

Appends a second list to the end of a first list.
listName1 The name of the first list.
listName2 The name of the second list to append to listName1.
returns The number of items in the list or -1 on failure.

Clear(listName)
Remove all values from a specified list.
listName The name of the list.
returns The number of items in the list or -1 on failure.

Contains(listName,value)

Check if a value is present within the specified list.
listName The name of the list.
value The value to check.
returns "True" or "False".

Copy(listName)

Copy a list.
listName The name of the list.
returns A copy of the list.

Count(listName)
Gets the count of items in the specified list.
listName The name of the list.
returns The number of items in the list or -1 on failure.

Distinct(listName)
Get a sub list of unique values from the specified list.
The text comparison is case insensitive.

listName The name of the list.
returns The sub list.

Except(listName1,listName2)
Get a sub list of non-shared values between two specified lists.
The text comparison is case insensitive.

listName1 The name of the first list.
listName2 The name of the second list.
returns The except list.

Find(listName,match,exact)
Get a sub list from the specified list where a text match is found.
The text match is case insensitive.

listName The name of the list.
match The match text.
exact An exact match (case insensitive) "True" or the match text is contained in the list "False".
returns The sub list.

FindIndices(listName,match,exact)

Get a sub list of indices from the specified list where a text match is found.
The text match is case insensitive.

listName The name of the list.
match The match text.
exact An exact match (case insensitive) "True" or the match text is contained in the list "False".
returns The sub list of indices in the list where a match is found.

FromArray(arrayName)

Copy a Small Basic array to a list.
The array indices are ignored by the list.

arrayName The Small Basic array.
returns The created list.

GetAt(listName,index)
Get a value from a specified list by index (starting from 1).
listName The name of the list.
index The value index to get.
returns The list value.

IndexOf(listName,value)
Get the index (starting from 1) of the first occurrence of a value from the specified list.
listName The name of the list.
value The value to get index of (0 for not found).
returns The value index or 0.

InsertAt(listName,index,value)

Insert a value in a specified list by index (starting from 1).
listName The name of the list.
index The index to insert at.
value The value to insert.
returns The number of items in the list or -1 on failure.

Intersect(listName1,listName2)

Get a sub list of shared values between two specified lists.
The text comparison is case insensitive.

listName1 The name of the first list.
listName2 The name of the second list.
returns The intersection list.

Print(listName)
Print a list to the TextWindow.
listName The name of the list.
returns The number of items in the list or -1 on failure.

Read(filePath)
Read a list from a file.
filePath The full path to read the list from.
returns The list if the operation was successful, otherwise "".

Remove(listName,match,exact)

Remove all occurrences from the specified list where a text match is found.
The text match is case insensitive.

listName The name of the list.
match The match text.
exact An exact match (case insensitive) "True" or the match text is contained in the list "False".
returns The number of items in the list or -1 on failure.

RemoveAt(listName,index)
Remove a value from a specified list by index (starting from 1).
listName The name of the list.
index The value index to remove.
returns The number of items in the list or -1 on failure.

Reverse(listName)
Reverse the order of values in the specified list.
listName The name of the list.
returns The number of items in the list or -1 on failure.

SetAt(listName,index,value)
Set (replace) a value in a specified list by index (starting from 1).
listName The name of the list.
index The index to set.
value The value to set.
returns The number of items in the list or -1 on failure.

SortByNumber(listName)

Sort a specified list with values treated as numbers.
All values must be numbers.

listName The name of the list.
returns The number of items in the list or -1 on failure.

SortByText(listName)
Sort a specified list with values treated as text strings (lexical sort).
The sort is case insensitive.

listName The name of the list.
returns The number of items in the list or -1 on failure.

SubList(listName,start,length)
Get a sub list from the specified list.
listName The name of the list.
start The first index of the sub list.
length The length of the sub list.
returns The sub list.

ToArray(listName)
Convert a list to a Small Basic array.
Not advised for large lists.

listName The name of the list.
returns The Small Basic array.

Union(listName1,listName2)
Get a sub list of combined values (duplicates single counted) between two specified lists.
The text comparison is case insensitive.

listName1 The name of the first list.
listName2 The name of the second list.
returns The union list.

Write(listName,filePath,append)
Save a list to file.
One line per list value is used.

listName The name of the list.
filePath The full path to save the list to.
append Append to end of existing file "True" or create a new file "False".
returns The number of items in the list or -1 on failure.

Examples

Features Example

The following is a TextWindow based example demonstrating some feature and of the usage of LDList.  It includes creating a 1000,000 element list with random numbers, sorting it and finding all distinct values as a performance test.

list = "myList"
For i = 1 To 10
  LDList.Add(list,"X"+i)
EndFor
For i = 1 To 3
  data["mydata"][i] = "Y"+i
EndFor
LDList.Add(list,data)
LDList.Print(list)
 
TextWindow.WriteLine("")
TextWindow.WriteLine("Array")
data1 = LDList.ToArray(list)
TextWindow.WriteLine(data1[11]["mydata"][2])
list = LDList.FromArray(data1)
data2 = LDList.GetAt(list,11)
TextWindow.WriteLine(data2["mydata"][2])
 
TextWindow.WriteLine("")
TextWindow.WriteLine("FindIndices")
LDList.Print(LDList.FindIndices(list,3,"False"))
 
TextWindow.WriteLine("")
TextWindow.WriteLine("Basics")
TextWindow.WriteLine(LDList.GetAt(list,2))
TextWindow.WriteLine(LDList.Contains(list,"X"+2))
LDList.Reverse(list)
LDList.InsertAt(list,12,12)
TextWindow.WriteLine(LDList.IndexOf(list,12))
LDList.Remove(list,12,"True")
TextWindow.WriteLine(LDList.IndexOf(list,12))
LDList.RemoveAt(list,2)
TextWindow.WriteLine(LDList.IndexOf(list,"X"+8))
TextWindow.WriteLine(LDList.Count(list))
 
TextWindow.WriteLine("")
TextWindow.WriteLine("Append")
LDList.Add(list,"x"+5)
LDList.SortByText(list)
LDList.Append(list,list)
LDList.Print(list)
 
TextWindow.WriteLine("")
TextWindow.WriteLine("Distinct Find")
newList = LDList.Find(LDList.Distinct(list),1,"False")
LDList.Print(newList)
 
TextWindow.WriteLine("")
TextWindow.WriteLine("Union")
newList = LDList.Union(list,newList)
LDList.Print(newList)
 
TextWindow.WriteLine("")
TextWindow.WriteLine("SubList")
newList = LDList.SubList(list,3,3)
LDList.Clear(list)
LDList.Print(newList)
 
TextWindow.WriteLine("")
TextWindow.WriteLine("File")
fileName = Program.Directory+"\list.txt"
LDList.Write(LDList.Copy(newList),fileName,"False")
newList = LDList.Read(fileName)
LDList.Print(newList)
 
TextWindow.WriteLine("")
TextWindow.WriteLine("Create")
dim = 1000000
For i = 1 To dim
  LDList.Add(list,Math.GetRandomNumber(dim))
EndFor
TextWindow.WriteLine("Sort")
LDList.SortByNumber(list)
TextWindow.WriteLine("Done")
TextWindow.WriteLine(LDList.Count(LDList.Distinct(list))+" Distinct values")

Sprite Array Example

The second example is a simplified sprite handling program.  This example is modified from code presented in another TechNet article describing how to handle arrays of sprites in Small Basic.

gw = 600
gh = 600
GraphicsWindow.Width = gw
GraphicsWindow.Height = gh
GraphicsWindow.MouseDown = OnMouseDown
 
CreateSprites()
 
'Game Loop
While ("True")
  start = Clock.ElapsedMilliseconds
  
  If (mouseDown) Then
    FireMissile()
    mouseDown = "False"
  EndIf
  UpdateSprites()
  
  delay = 20 - (Clock.ElapsedMilliseconds - start)
  If (delay > 0) Then
    Program.Delay(delay)
  EndIf
EndWhile
 
Sub CreateSprites
  spriteImage = ImageList.LoadImage("http://litdev.hostoi.com/game_images/missile.png")
  'Sprite dimensions we use the half width and height
  spriteWidth = ImageList.GetWidthOfImage(spriteImage)/2
  spriteHeight = ImageList.GetHeightOfImage(spriteImage)/2
EndSub
 
Sub UpdateSprites
  For i = 1 To LDList.Count("sprites")
    spriteData = LDList.GetAt("sprites",i) 'get current sprite array
    
    'Reposition sprite center
    spriteData["Xpos"] = spriteData["Xpos"] + spriteData["Xvel"]
    spriteData["Ypos"] = spriteData["Ypos"] + spriteData["Yvel"]
    
    'Move sprite center
    Shapes.Move(spriteData["image"],spriteData["Xpos"]-spriteWidth,spriteData["Ypos"]-spriteHeight)
    
    'Sprite finished with
    If (spriteData["Ypos"] < -spriteHeight) Then
      Shapes.Remove(spriteData["image"])
      LDList.RemoveAt("sprites",i)
    Else        
      LDList.SetAt("sprites",i,spriteData) 'save updated sprite array (it may have been modified)
    EndIf
  EndFor
EndSub
 
Sub FireMissile
  spriteData["image"] = Shapes.AddImage(spriteImage)
  spriteData["Xpos"] = GraphicsWindow.MouseX
  spriteData["Ypos"] = gh-spriteHeight
  spriteData["Xvel"] = 0
  spriteData["Yvel"] = -5
  LDList.Add("sprites",spriteData)
EndSub
 
Sub OnMouseDown
  mouseDown = "True"
EndSub

Conclusion

For Small Basic games that use arrays, the LDList method can speed these games significantly.  There are other performance related methods in the LitDev extension that can also improve the speed of games or other programs, and in the process guide new programmers to ideas that will be useful when the move on from Small Basic, whether writing games or other software.

See Also