Arrays with more than 3 dimensions

[paravantis]

Paul and esteemed forum users,

I try to implement an algorithm (optimal location of wireless sensors on a grid) in eBasic (porting over from yabasic which is very slow when doing math computations) and have run across an eBasic issue that, I think, is unduly restrictive.

In my programming I need to use an array of integers that has 5 (FIVE) dimensions, say a[i,j,k,l,m]. Declaring such an array was not a problem in yabasic but arrays of more than 3 dimensions are NOT allowed in eBasic.

Since eBasic is NOT object oriented (thank God) and does not allow for array custom types, I cannot get around that by declaring, say, a 2 dimensional array aa[i,j] each cell of which would be a three dimensional array a[k,l,m].

Having the capability of using arrays of arbitrarily many dimensions or, at least, more than 3 (say up to 9) would be a great boon. Would Paul please consider adding this capability?

Also am I correct in understanding that I CANNOT use TYPE to declare an array of arrays?

Friendly regards from Greece,
John Paravantis
University of Piraeus

[Ionic Wind Support Team]

Sure you can use a type. 

[paravantis]

Would this be the way to declare an array of arrays?

type aaa
   def a3[10,10,10]:int
endtype

type aaaaa
   def a5[10,10]:aaa
endtyp

so that aaaaa may now be used as an array of (essentially) 5 dimensions? Can I NEST types this way?

Would this be equally FAST to being able to directly declare arrays of 5 dimensions?

John

[billhsln]

I haven't done this in many years, but we used to only have single dimensioned arrays and were still able to do Multi's.

The trick is: define array with enough elements as required by your dimensions.  (5,4) = 20 elements.  To directly address it within this frame work was to:

Array(Index1 + ((Index2-1)*5)) = Array2(Index1, Index2)

This can be expanded to any number of dimensions with a little work.

Bill

[Ionic Wind Support Team]

John,
Yes that is one way to do it, speed isn't an issue as it is all machine code once compiled and the reference to a type is actually a bit faster than the additional calculation that would be needed for each dimension index.

[paravantis]

OK, thank both of you for responding.

In regards to Paul observing "this is ONE way of doing it", is there a better/more elegant way of doing it? Could you provide a brief code example?

In the meantime, I will complete the translation of my yabasic program into eBasic and will report the speed increase to the forum.

[Ionic Wind Support Team]

I don't have a brief code example, but I'll write one for you.

An array in memory isn't comprised of cells, or indexes.  It is just a continuous block of memory.  You see it as an array because of how that memory is indexed by a calculation.  So you can create an array of any dimension if you know how to translate the indexes into the correct memory location.

So the calculations for accessing an element of a two and three dimension array are as follows:

'two dimensions
address = base + (index2 * dim1 + index1) * datasize

'three dimensions
address =  base + ((index3 * dim1 * dim2) + (index2 * dim1) + index1) * datasize

Where base is the starting address of the memory the array is stored in, and datasize is the size of an array element in bytes i.e 4 for an integer.  I am sure you can see the pattern, the calculations of a 4 dimension array access would be:

'four dimensions
address = base  + ((index4 * dim1 * dim2 * dim3) + (index3 * dim1 * dim2) + (index2 * dim1) + index1) * datasize

The calculations assume zero based indicies.  Knowing the formula for accessing the array elements you can create an array with allocated memory of any size, and a subroutine to access that array for storage and retrieval.  I will write a group of subs you can use for n dimensioned arrays.  The speed of access is determined by how fast you can calculate the element address.

Paul.

[paravantis]

Sorry, I meant providing a TYPE example.

Simulating a multidimensional array with an array of one dimension should be straightforward ALTHOUGH because my code runs for 40 MINUTES in yabasic I am concerned with the issue of speed: as you point out, indexing WILL take time.

John

[Ionic Wind Support Team]

It is not simulating.  It is how the compiler does the calcuations for arrays, in assembly of course.

[billhsln]

Based on Paul's example, I would think that the calculation of the index into a single dimensioned array would be pretty quick.  Since it would result in an integer, which should be very quick to calculate.  Integer math is usually very quick in assembly.

You could create a subroutine which would be passed the indexes and returns the single index, which could then be used as a direct index into the single dimensioned array.

sub indexer(index1:int, index2:int, index3:int, index4:int, index5:int),int
....
return index
endsub

usage:   array(indexer(i1,i2,i3,i4,i5)) = value

This would make your code changes some what smaller.

Bill

[paravantis]

Many thanks to all.

Incidentally, I find it annoying that array indexes start at 0 and end at (n-1), e.g. a[8] contains a[0] ... a[7].

Would Paul consider adding an OPTION BASE command (or the like) that would allow the user to choose between 0 and 1?

[Barney]

Why don't you just dimension the arrays as n+1 and use 1..n range in your programs? Problem solved.

However, having said that I'd like to add that it would be nice to have something more powerful than a simple option base. For example if we are using years in our calculations we could use:

DIM aYears[1914:1918]

and later in the program we can access the array like this:

xyzzy=aYears[1915]

Pretty neat and easy to understand what the code does when we look at it few months later. I know this can be done fairly easily by creating an appropriate indexing function but I prefer the compiler to take care of such calculations.

Barney

[paravantis]

Barney,

Quite obviously, I DO dimension them as n+1.  BUT this is not a good way to achieve what I want.

You very correctly point out the a[first:last] syntax as the BEST possible improvement and I enthusiastically second your motion.

Paul, would you kindly consider such an enhancement?

John

[Barney]

...I know this can be done fairly easily by creating an appropriate indexing function but I prefer the compiler to take care of such calculations.

Quoting myself. I must be getting old. 

After reading it once again I realized that compiler would, of course, have problems with it. Such calculations belong to some sort of run time package and thus are much easier to do in interpreter environment. But there should still be a way of doing it, perhaps through the use of extra support functions...

Barney

[Jerry Muelver]

For many such applications, a hash (dictionary or associative array) solves the problem quite neatly. 

[Barney]

Yes, Jerry, I know but I've been using the a[100:122] approach in HP BASIC for years and got used to it so much I always wish I can have it in other languages.

Barney

[Ionic Wind Support Team]

Compiled languages use zero based indexes because the processor uses zero based memory.  A varaible in a compiled program is just memory, no types, no other information, just an address.  So there isn't any place to store an array 'offset' and remain compatible with all other compiled languages.

[barry]

Having subscripts begin at 0 is an advantage far more often than it is a drawback, in my opinion.  And having an option so you can choose that introduces a lot of room for confusion and potential for bugs.

I like that as it is.

Barry

[Bruce Peaslee]

Having subscripts begin at 0 is an advantage far more often than it is a drawback, in my opinion.ÂÃ,  And having an option so you can choose that introduces a lot of room for confusion and potential for bugs.

I agree. In mathematics (my background) indices start with zero.

[Parker]

The problem with varying array bounds is that you have to add in a bunch of helper functions. For example, in FreeBASIC you can say dim array(10 to 20) as integer, but then every time you access an array element, or assign one, or do anything else it has to call a function that works on the array. And the array isn't really a true array, because it is actually a UDT that describes it.

However, if you prefer this behaivor, you can write code to set it up. I have neither IBasic Pro nor EBASIC on my computer, but this should help you:

Code Select Expand

declare cdecl extern memcpy alias "_memcpy" ( dest:pointer, src:pointer, num:uint ),pointer
declare cdecl extern memset alias "_memset" ( buffer:pointer, c:int, num:uint ),pointer
declare import, GlobalReAlloc( hMem:pointer, dwBytes:uint, flags:uint ),pointer

type array
    int lbound
    int ubound
    uint elemsize
    pointer elems
endtype

global sub arrayDim( lbound:int, ubound:int, size:uint ), pointer
    pointer a
    a = new(array, 1)
    settype a,array
    *a.lbound = lbound
    *a.ubound = ubound
    *a.elemsize = size
    if ubound > lbound then *a.elems = new(char, ( ubound - lbound + 1 ) * size)

    return a
endsub

global sub arrayDelete( a:pointer )
    delete *<array>a.elems
    delete a
endsub

global sub arrayRedim( a:pointer, lbound:int, ubound:int ),pointer
    if ubound <= lbound then return a
    *<array>a.elems = GlobalReAlloc( *<array>a.elems, (ubound - lbound + 1) * *<array>a.elemsize, 0x0040 )
    *<array>a.lbound = lbound
    *<array>a.ubound = ubound

    return a
endsub

global sub arrayRedimClear( a:pointer, lbound:int, ubound:int ),pointer
    a = arrayRedim( a, lbound, ubound )
    arrayClear( a )
    return a
endsub

global sub arrayClear( a:pointer )
    if *<array>a.elems <> 0 then memset( *<array>a.elems, 0, (*<array>a.ubound - *<array>a.lbound + 1) * *<array>a.elemsize )
endsub

global sub arraySet( a:pointer, index:int, elem:pointer )
    if index < *<array>a.lbound or index > *<array>a.ubound then return

    index -= *<array>a.lbound

    memcpy( *<array>a.elems + (*<array>a.elemsize * index), elem, *<array>a.elemsize )
endsub

global sub arrayGet( a:pointer, index:int ),pointer
    if index < *<array>a.lbound or index > *<array>a.ubound then return 0

    index -= *<array>a.lbound

    return *<array>a.elems + (*<array>a.elemsize * index)
endsub

Obviously this is untested since I don't have a tool installed to compile it. But I hope it works. This is an example usage:

Code Select Expand

pointer arr
int quit : quit = 0
int ind
pointer elem

'' Store integers (4 byte size) from 10 to 20 inclusive.
arr = arrayDim( 10, 20, 4 )
for i = 10 to 20
    elem = new(int, 1)
    *<int>elem = i - 10
    arraySet( arr, i, elem )
next i

do
    print "index from 10 to 20 (out of bounds = done)? ",
    input ind
    elem = arrayGet( arr, ind )
    if elem = 0 then quit = 1 else print "arr[" + ltrim$(str$(ind)) + "] =", *<int>elem
until quit = 1

arrayDelete( arr )

Again, please let me know if there are any errors.
Hope it helps,
Parker

P.S. Though this only supports one dimension, it could easily be modified to support any number of dimensions using variable arguments. Arrays are redim-able, where arrayRedimClear is the same as REDIM in BASIC, and arrayRedim is the same as REDIM PRESERVE. arrayClear sets all elements to zero (this works on UDTs too, so be careful). Boundaries are inclusive.

I give my permission for anyone to distribute this code, along with any modifications, provided the source code is made available to anyone who wants it, that people know this, and that it is not sold.

P.P.S. I've fixed the errors. It should work now. Sorry I couldn't test it before.

[Barney]

Apart from the obvious typo where you are using "a" instead of "arr"

Code Select Expand


elem = arrayGet( a, ind )

shouldl be

elem = arrayGet( arr, ind )


everything compiles nicely but bombs out with the usual "send error..." to Microsoft message. Will check it again tomorrow because it's rather late here and I'd rather hit the bed than stare at the screen.

Barney

[Parker]

The typo is fixed. I would debug it and fix it myself, but unfortunately I can't

If someone could compile a debug build and tell me which line it's crashing on I could probably fix it.

Thanks for trying it though. Sorry it crashes.
Parker

[Barney]

Well... I did not go to bed so here's the debug message:

Code Select Expand

Call stack:
CRTDLL! memcpy + 46
ArrayBounds! arraySet + 243 File: ArrayBounds.inc, Line: 53
ArrayBounds! arrayGet + 338 File: ArrayBounds.eba, Line: 13
kernel32! RegisterWaitForInputIdle + 73

Line 53 in ArrayBounds.inc is:

Code Select Expand

memcpy( *<array>a.elems + (*<array>a.elemsize * index), elem, *<array>a.elemsize )

Barney

[Parker]

Oops

That's because the arraySet function requires a pointer and I gave it an int. memcpy is trying to read from memory locations 0-10 and obviously it can't. I'll fix it in the original post.

[Parker]

So after that, I have to say that having arrays start at 0 and string functions start at 1 really throws me off. I personally would rather have both start at 0 how it is in C and Java. However, I know this discussion has been brought up before and I don't think it's going to change.