Articles Archive
Articles Search
Director Wiki
 

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.

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.

Copyright 1997-2024, Director Online. Article content copyright by respective authors.