# Multidimensional Arrays - Answering the challenge

September 21, 1999
by Irv Kalb

Recently, Brennan Young wrote an article for Director Online on the topic of recursion. In the article, he described how you could use recursion to create and access elements of multidimensional arrays. His article gives a very clear explanation of what recursion is, and his example of multidimensional arrays was an excellent way to demonstrate the technique. (You can find that article here)

However, in that article, he "threw down the gauntlet". He said, "I challenge anyone to make a purely iterative equivalent of this handler. Remember it should be capable of making an array of any number of dimensions". This article does just that, it shows how this can be done using two different approaches to represent a multidimensional array.

#### Functionality of a multidimensional array

In the following discussion, I will show two array objects that are functionally equivalent to Brennan's code. I have a naming convention that I use all the time, so the names are not exactly identical. The basic things that you want to do with an array are: create an array with a specified size, set the value of a cell in the array, and get the value of a cell from the array. I have set up the code to do range checking - that is, ensure that the indices which you pass are valid - only if you explicitly turn range checking on (or off) by calling a handler.

To create an array, let's say a 6 by 5 by 4 by 3 array, and set all elements to an initial value of zero, you would do this:

```set oArray = new(script "Array", [6, 5, 4, 3], 0)
```

And similar to Brennan's code, to identify an individual element of the array you always pass a list of indices. To set a given element to a value you would make a call like this:

```mSet(oArray, [4, 2, 1, 1], 15)
```

To get the value of a given element, you make a call like this:

```set theValue = mGet(oArray, [2, 3, 4, 3])
```

And finally to turn on range checking, just do this:

```mSetRangeChecking(oArray, TRUE)
```

#### Implementation #1, the property list

This technique was actually suggested by Zac Belado from DOUG. The approach is to represent the data of the multidimensional array as a simple property list. Below is a parent script which shows how this can be done:

```property plCells
-- the contents of the array as a property list
property plDimensions
-- list of dimensions
property pnDimensions
-- number of dimensions
property pfRangeChecking
-- flag to check if indices are valid
property pInitialValue
-- Initial value for individual cells
```

Within the object, the data for the array is kept in the property variable, "plCells". When the array is created, in the "new" handler below plCells is initialized to an empty property list. It is sorted to provide better speed. The array data is kept as a "sparse list", that is, a cell is only added to the property list when it is assigned a value.

```on new me, lDimensions, initialValue
set plDimensions = lDimensions
set pInitialValue = initialValue
set pnDimensions = count(plDimensions)

-- Initialize the array to empty
set plCells = [:]

-- And keep it in sorted order
sort(plCells)
set pfRangeChecking = FALSE
-- default to no range checking
return me

end new

```

But what are the property values of the pCells property list? The key code can be found in the handler "mGeneratePropertyFromIndices" below. This routine takes a list of indices for the element in question, and converts that list to a symbol. For example, if you want to access element [2, 3, 1, 2], mGeneratePropertyFromIndices converts that list into the symbol #2_3_1_2_. This routine is called for both storing and retrieving values in the array. The handler may seem very long, but the major portion of the code handles the optional range checking

```-- Converts a list of indices into a property
-- For example:
--  Input:  [2, 3, 4]
--  Output #2_3_4_
on mGeneratePropertyFromIndices me, lIndices
if pfRangeChecking then

-- Check to ensure validness of indices
set nIndices = count(lIndices)
if nIndices <> pnDimensions then
alert("Number of indexes specified doesn't match ¬
number in array")
debuggerBreak()
end if

repeat with i = 1 to pnDimensions

set thisIndex = getAt(lIndices, i)
if not(integerp(thisIndex)) then
alert("Index" && i  && "is not an integer")
debuggerBreak()
end if

if thisIndex < 1 then
alert("Index" && i  && "is less than 1")
debuggerBreak()
end if

set thisDimension = getAt(plDimensions, i)
if thisIndex > thisDimension then
alert("Index" && i  && "is biggger than this dimension ¬
for this array")
debuggerBreak()
end if
end repeat
end if

-- Here is where we really create the property
set sProp = ""
repeat with i = 1 to pnDimensions
set thisIndex = getAt(lIndices, i)
put string(thisIndex) & "_" after sProp
end repeat
set theProp = symbol(sProp)

return theProp

end mGeneratePropertyFromIndices
```

Given this simple handler, coding the mSet and mGet handlers are very straightforward, they are both just simple accessors into the property list.

```on mSet me, lIndices, theValue
set symThisItem = mGeneratePropertyFromIndices(me, lIndices)
setAProp(plCells, symThisItem, theValue)
end mSet
```

But there is one trick in the code. Imagine if you create an array with some default value, and then before setting any cell to any other value, you attempt to get a the value of some element of the array. The property list plCells is really an empty property list. So, in the mGet handler below, if you attempt to get an element in the array which does not yet exist, it returns the initial value specified when you created the array.

```on mGet me, lIndices
set symThisItem = mGeneratePropertyFromIndices(me, lIndices)

--Check to see if this element has been created yet.
-- If not return the initial value
set returnValue = getAProp(plCells, symThisItem)
if voidp(returnValue) then
set returnValue = pInitialValue
end if

return returnValue

end mGet
```

Here is how we can explicitly turn range checking on or off.

```on mSetRangeChecking me, fTrueOrFalse
set pfRangeChecking = fTrueOrFalse
end mSetRangeChecking
```

And here is a utility handler to dump the contents of the array.

```-- Just to see what the internal array
-- looks like at any time
on mDebug me
put plCells
end mDebug
```

#### Implementation #2, the 'computed' linear list

This approach is even simpler to explain, but a little more complicated to implement. The idea here is to represent the data as a simple linear list. The tricky part is coming up with an algorithm that converts the indices of a particular cell into an index into a linear list. Below is a parent script which shows how this can be done:

```property plCells
-- the contents of the array as a linear list
property plDimensions
-- list of dimensions
property pnDimensions
-- number of dimensions
property pfRangeChecking
-- flag to check if indices are valid
property pInitialValue
-- Initial value for individual cells
property pnCells
-- number of cells needed to represent the array
property plMultipliers
-- list of multipliers generated for this array
```

However, the basic difference is that here, there is a little setup in the "new" routine. First, it creates the linear array and sets all elements to the initial value. Then it computes a list of 'multipliers' that will be used later to access individual cells. The multipliers are generated by creating a list (starting with the value of 1) and multiplying by the next dimension (right to left). For example, for a 6 by 5 by 4 by 3 array, the multiplier array would be: [5*4*3, 4*3, 3, 1] or [60, 12, 3, 1], an array of 2 by 3 by 4 would generate a multiplier list of [3*4, 4, 1] or [12,4, 1].

```on new me, lDimensions, initialValue
set plDimensions = lDimensions
set pInitialValue = initialValue
set pnDimensions = count(plDimensions)

-- First find out how many cells there need to be
set pnCells = 1
repeat with i = 1 to pnDimensions
set thisDimension = getAt(plDimensions, i)
set pnCells = pnCells * thisDimension
end repeat

-- Initialize the array to initialValue
-- (set the last cell first to allocate
-- memory faster)
set plCells = []
setAt(plCells, pnCells, initialValue)
repeat with i = 1 to pnCells
setAt(plCells, i, initialValue)
end repeat

set plMultipliers = [1]
set runningTotal = 1
repeat with i = 1 to (pnDimensions - 1)
set j = pnDimensions - i + 1
set thisDimension = getAt(plDimensions, j)
set runningTotal = runningTotal * thisDimension
end repeat

set pfRangeChecking = FALSE  -- default to no range checking
return me

end new
```

When you want to access an element in the array, the routine "GenerateCellNumberFromIndices" takes the values passed as a list of indices, subtracts one from each value, and calculates a cell number. It does this by taking the sum of the multiplications of all these values times their associated multiplier. Finally, we add one because lists are1 based, not zero based. (Again, most of the code below deals with range checking.)

```-- Converts a list of indices into a cell number
on mGenerateCellNumberFromIndices me, lIndices
if pfRangeChecking then

-- Check to ensure validness of indices
set nIndices = count(lIndices)
if nIndices <> pnDimensions then
alert("Number of indexes specified doesn't match ¬
number in array")
debuggerBreak()
end if
repeat with i = 1 to pnDimensions
set thisIndex = getAt(lIndices, i)
if not(integerp(thisIndex)) then
alert("Index" && i  && "is not an integer")
debuggerBreak()
end if

if thisIndex < 1 then
alert("Index" && i  && "is less than 1")
debuggerBreak()
end if

set thisDimension = getAt(plDimensions, i)
if thisIndex > thisDimension then
alert("Index" && i  && "is biggger than this ¬
dimension for this array")
debuggerBreak()
end if
end repeat
end if

-- Here's where we calculate the cell number using
-- the multipliers
set cellNumber = 0

repeat with i = 1 to pnDimensions
set j = pnDimensions - i + 1
set thisMultiplier = getAt(plMultipliers, j)
set thisIndex = getAt(lIndices, j) - 1
set cellNumber = cellNumber + (thisMultiplier * thisIndex)
end repeat

-- Add one becaue lists are "1" based, not zero based
set cellNumber = cellNumber + 1
return cellNumber

end mGenerateCellNumberFromIndices
```

Once we have the routine which generates Cell numbers, indexing into the array in the mGet and mSet handlers is just a single line of code.

```on mSet me, lIndices, theValue
set thisCellNumber = mGenerateCellNumberFromIndices(me, lIndices)
setAt(plCells, thisCellNumber, theValue)
end mSet
on mGet me, lIndices
set symThisItem = mGenerateCellNumberFromIndices(me, lIndices)
set returnValue = getAt(plCells, symThisItem)
return returnValue
end mGet
```

This is used to explicitly turn range checking on or off.

```on mSetRangeChecking me, fTrueOrFalse
set pfRangeChecking = fTrueOrFalse
end mSetRangeChecking
```

And this dumps the contents of the array.

```-- Just to see what the internal array looks
-- like at any time
on mDebug me
put plCells
end mDebug
```

The code looks very similar to the property list approach. It has the exact same 'interfaces" - that is, the routines that you call are exactly the same. Such is the beauty of object oriented programming. In fact, these two parent scripts could be interchanged without affecting any other part of a larger program.

#### Timings

I was curious to see how these different approaches would perform. So I wrote a test program to find out. My test program creates a 6 by 5 by 4 by 3 array, and iterates through the array 25 times. For each element, it randomly decided whether to set the array element to the iteration number, get the array element, or do nothing.

For running the test, I decided to turn off range checking. I commented out some of Brennan's code so it wouldn't do range checking. The results (run on Director 6.5 on a Mac G3 233) were as follows:

```"Computed" linear array:  36 ticks
"Recursive" array:  42 ticks
"Property list" array:  58 ticks
```

The code of this test program that incorporates the parent scripts for the 'property list' array and the 'computed' array are available by clicking here:

A sample movie is available for download in Mac or PC format

This just goes to show that with Lingo, there are many ways to achieve the same results.

Irv Kalb has been working as an independent software developer in Director and Lingo for over ten years. He has written extensively on object oriented programming in Lingo, and his on-line Ebook on this topic can be found at http://www.furrypants.com/loope. Irv is always interested in discussing new projects.