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
addAt(plMultipliers, 1, runningTotal)
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.
Copyright 1997-2024, Director Online. Article content copyright by respective authors.