Computer Science Canada

[Tutorial] Flexible Arrays - Become a Guru!
Author:  Cervantes [ Wed Nov 17, 2004 5:05 pm ]
Post subject:  [Tutorial] Flexible Arrays - Become a Guru!
Flexible Arrays


So, you've mastered the array, eh? Super! But now I'll bet you're wondering what a flexible array is. Good question.

A flexible array is an array with a dynamic upper bounds.

"What the heck does that mean?" It means you can change the upper bounds of your array.
Say you have:
code:
var myArray : flexible array 1 .. 6 of int

You could, with one line of code, make myArray into an integer array from 1 to 7. Or from 1 to 3. Or even from 1 to 0. That's right. With flexible arrays, you can make the upper bound one less than the lower bound. No more, however.

"So," you ask, "just how do I change this so called 'upper bounds'?" Another good question.
The new command is used to do this.
code:

var arrayName : flexible array lower .. upper of typeSpec
new arrayName, newUpper

The syntax is fairly simple, as it is throughout Turing. newUpper is an integer, and will be the new upper bounds of your array.
so,
code:

var myArray : flexible array 1 .. 0 of int
new myArray, 1

now, myArray goes from 1 to 1. It has 1 element. upper(myArray) would return 1.
say we go again:
code:

new myArray, 7

now, myArray goes from 1 to 7. It has 7 elements. upper(myArray) would return 7.

So, changing the upper bounds of an array is pretty simple, right? I hope so, it gets thicker.

Say we have our flexible array, named phoneNumbers, and it is filled from 1 to 10 with information: it stores the phone numbers of your ten of my friends. But what if I meet a new friend, and I want to store his phone number in my array? Well, that's easy! Just increase the upper bounds of my phoneNumbers array to 11 and add the new information!
code:

var phoneNumbers : flexible array 1 .. 10 of string

new phoneNumbers, 11
phoneNumbers (11) := "416-576-4382"


Good enough. It gets the job done. But there is one slight problem here. We have hardcoded the values. We have hardcoded the number 11. What if I meet yet another friend? We'd have to write code again and then use the number 12. To avoid hardcoding, a variable or constant is generally used. In this case, we can use a certain function that might come in useful in this situation. The function I'm talking about is the upper function.
This function returns the upper bounds of an array.
so, to avoid hardcoding:
code:

var phoneNumbers : flexible array 1 .. 10 of string

new phoneNumbers, upper (phoneNumbers) + 1
phoneNumbers (upper (phoneNumbers)) := "416-576-4382"

Now, instead of hardcoding the new upper bounds, we have increased the phoneNumbers array by 1.

*Ahem* To return to the point of this tutorial.. Adding a new element to an array is easy enough. Add it, then insert the information.
Earlier I said, "it gets thicker." Well, now it does.
The hard part comes when we want to eliminate an element in an array. Say we have a flexible array from 1 to 6, and it is saturated with information. Say we want to eliminate element 3. There is no built in turing command to do this. We must make use of our new command, as well as use our noodles (by which I mean our brains).
If we eliminate an element from our flexible array, then our array is going to have one less element. Makes sense? So, at some point, we're going to need to do something like this:
code:

new myArray, upper (myArray) - 1

The problem is, we can't do that just yet. We wanted to eliminate element 3 of our array (that goes from 1 to 6). Well, if we did our new command right away, we would eliminate element 6, not element 3.
What we have to do is move element 4 to position 3, move element 5 to position 4, and move element 6 to position 5. Then we can use our new command and eliminate element 6 (we already moved it, so it's safe).
So, how do we do a complex procedure like this?
code:

var myArray : flexible array 1 .. 6 of int
for r : 3 + 1 .. 6
    myArray (r - 1) := myArray (r)
end for
new myArray, 5

That should do it. But, you see, we've gone back to hardcoding. Coincidently, the procedure is harder to understand because it's hardcoded.
Doing it like this would be a better idea:
code:

var myArray : flexible array 1 .. 6 of int
var elementToBeRemoved : int := 3
for r : elementToBeRemoved + 1 .. upper (myArray)
    myArray (r - 1) := myArray (r)
end for
new myArray, upper (myArray) - 1


Hopefully, that's a little more understandable.
If not, I'll run through it.
We want to remove element 3. So, we declare the variable "elementToBeRemoved" and initialize it as 3. Then, we enter our for loop, which runs from 4 (which is 3 + 1) to 6 (which is the upper bounds of myArray). First time through the for loop, r is 4. So, element 4 - 1 (element 3) is made equal to element 4. Then, second time through, r is 5. Element 5 - 1 (element 4) is made equal to element 4. Third (and last) time through the loop, r is 6. Element 6 - 1 (element 5) is made equal to element 6.
Thus, we first copied element 4 to position 3, then copied element 5 to position 4, then finally copied element 6 to position 5. In this manner, element 3 was copied over. At this point, we have two copies of element 6. Thus, we eliminate the second copy of element 6 by reducing the upper bounds of the array by 1, using our new command.

You may be thinking, "But that code won't work if I want to remove element 6, the last element in the array!"
Oh, but it will. Turing has this nice feature that prevents it from entering a for loop if the first number is bigger than the second number. So, if you did this:
code:

var myArray : flexible array 1 .. 6 of int
var elementToBeRemoved : int := 6
for r : elementToBeRemoved + 1 .. upper (myArray)

    myArray (r - 1) := myArray (r)
end for
new myArray, upper (myArray) - 1

the first number for the for loop would be 6 + 1 = 7, and the second number would be 6. The first number is bigger than the second, so the for loop is skipped over. Thus, no elements are changed. Then, the new command is reached and the array loses it's last element, which is what you wanted in the first place! (Actually, what I said about the for loops is not entirely correct. It is correct for standard for loops, but the reverse applies for decreasing for loops. In a decreasing for loop, if the second number is bigger than the first number, then the for loop will be passed by.)


Hopefully everyone got through that.
Now we know what flexible arrays are, and we know how to manipulate them, both in adding elements and in removing elements.

Multi-Dimensional Flexible Arrays
"Complex multi-dimensioned flexible array reallocation not implemented yet - sorry."
Bullsh*t! Contrary to popular belief, we can change the upper bounds of multi-dimensional flexible arrays. However, there are limitations.
I am working with Turing 4.0.5, so everything I say is valid only for this version. The third post of this topic, by myself, gives a quote of Coutsos' code that shows reallocation of multi-dimensional flexible arrays in pre Turing 4.0.5 versions. All I am saying is that what I am about to say may not apply to your paricular version of Turing. You'll have to try it out for yourself. Wink
So, to change the upper bounds of a multi-dimensional flexible array, it would seem that we first have to set the upper bounds of at least one of the dimensions to zero or leave one of the dimensions alone. Let's have some code:
code:

var a : flexible array 1 .. 2, 1 .. 3 of int
put upper (a, 1)
put upper (a, 2)
put "---"
new a, 0, 3
put upper (a, 1)
put upper (a, 2)
put "---"
new a, 1, 5
put upper (a, 1)
put upper (a, 2)
put "---"
new a, 15, 0
put upper (a, 1)
put upper (a, 2)
put "---"

This is all valid, Turing-loving code (again, for 4.0.5, not necessarily previous versions). Let's try leaving one dimension as it is while changing the other:
code:

var a : flexible array 1 .. 2, 1 .. 3 of int
put upper (a, 1)
put upper (a, 2)
put "---"
new a, 1, 3
put upper (a, 1)
put upper (a, 2)
put "---"
new a, 1, 6
put upper (a, 1)
put upper (a, 2)
put "---"

Part of it works. We can change the first dimension, but not the second, provided we leave the other dimension alone. If you must change both dimensions, there's a roundabout method:
Bacchus wrote:

There is a bit of a way around this, takes up a bit of space thought. Just create a new array (doesn't have to be flexible) and store the orginal array in that then change the dimension to 0 and back to what you want before restoring the original array's values.


Now, let's try 3 dimensions.
code:

var a : flexible array 1 .. 2, 1 .. 3, 1 .. 4 of int
put upper (a, 1)
put upper (a, 2)
put upper (a, 3)
put "---"
new a, 10, 0, 9
put upper (a, 1)
put upper (a, 2)
put upper (a, 3)
put "---"
new a, 10, 8, 9
put upper (a, 1)
put upper (a, 2)
put upper (a, 3)
put "---"

This also works. So, let's get some rules going on here.

  • You can change any upper bounds from a 0 to x, or from x to 0.
  • If you change one upper bounds to a zero, you can do whatever you want with the other upper bounds.
  • In a 2D array, if you leave the second upper bounds alone, you can change the first upper bounds.

Application of Records
The next thing to do (though it's entirely optional) would be to read AsianSensation's tutorial on records and types. Learn records. Learn to love them. You can do something like this:
code:

var object : flexible array 1 .. 10 of
    record
        x, y : int
    end record

Now, say you want object (5).x to become equal to object (2).x as well as wanting object (5).y to become equal to object (2).y. You could do this:
code:

object (5).x := object (2).x
object (5).y := object (2).y

or, you could do this:
code:

object (5) := object (2)

This makes every aspect of the record, object (5), equal to every apsect of the record, object (2).
Why is this useful? Well, I found it useful when I made the basis for a dueling game:

Turing:

var winID := Window.Open ("graphics:500;500,nobuttonbar,offscreenonly")
var player :
    record
        x, y : real
        dir : real
        forward_speed, backward_speed : int
        life : int
        radius : int
    end record

player.x := 100
player.y := 100
player.dir := 45
player.forward_speed := 2
player.backward_speed := 1
player.life := 100
player.radius := 10

var bullet : flexible array 1 .. 0 of
    record
        startx, starty : real
        x, y, vx, vy : real
        dir : real
    end record

const bulletVelocity := 5


var keys : array char of boolean

var timeLast := 0
function cooldown (timeDelay : int) : boolean
    if Time.Elapsed - timeLast >= timeDelay then
        result true
    end if
    result false
end cooldown

procedure playerControls
    if keys (KEY_RIGHT_ARROW) then
        if player.dir <= 0 then
            player.dir += 360
        end if
        player.dir -= 2
    end if
    if keys (KEY_LEFT_ARROW) then
        if player.dir >= 360 then
            player.dir -= 360
        end if
        player.dir += 2
    end if
    if keys (KEY_UP_ARROW) then
        player.x += cosd (player.dir) * player.forward_speed
        player.y += sind (player.dir) * player.forward_speed
    end if
    if keys (KEY_DOWN_ARROW) then
        player.x -= cosd (player.dir) * player.backward_speed
        player.y -= sind (player.dir) * player.backward_speed
    end if
    if keys (KEY_SHIFT) then
        if cooldown (300) then
            new bullet, upper (bullet) + 1
            bullet (upper (bullet)).startx := player.x + (cosd (player.dir) * player.radius)
            bullet (upper (bullet)).starty := player.y + (sind (player.dir) * player.radius)

            bullet (upper (bullet)).x := bullet (upper (bullet)).startx
            bullet (upper (bullet)).y := bullet (upper (bullet)).starty
            bullet (upper (bullet)).dir := player.dir
            bullet (upper (bullet)).vx := cosd (bullet (upper (bullet)).dir) * bulletVelocity
            bullet (upper (bullet)).vy := sind (bullet (upper (bullet)).dir) * bulletVelocity
            timeLast := Time.Elapsed
        end if
    end if
end playerControls
procedure updateBullet
    for i : 1 .. upper (bullet)
        if Math.Distance (bullet (i).startx, bullet (i).starty, bullet (i).x, bullet (i).y) >= 300 then
            for k : i + 1 .. upper (bullet)
                bullet (k - 1) := bullet (k)
            end for
            new bullet, upper (bullet) - 1
            exit %problematic
        end if

        bullet (i).x += bullet (i).vx
        bullet (i).y += bullet (i).vy

        Draw.FillOval (round (bullet (i).x), round (bullet (i).y), 2, 2, black)
    end for
end updateBullet
loop
    cls

    Input.KeyDown (keys)
    playerControls
    updateBullet

    drawline (round (player.x), round (player.y), round (player.x) + round ((cosd (player.dir) * (player.radius * 1.5))), round (player.y) + round ((sind (player.dir) * (player.radius *
        1.5))), black)
    drawfilloval (round (player.x), round (player.y), player.radius, player.radius, 12)
    View.Update
    delay (10)

    exit when keys (KEY_ESC)
end loop

Window.Close (winID)

I apologize for the lack of comments.
The only comment is a little note beside the exit command on line 81, saying that it is "problematic". I put this here because using the exit like that is indeed problematic. You may say, "But it runs just fine!" but, in theory, it doesn't. The error just isn't noticable. The problem is that, any time an element of the bullet array needs to be removed (because the bullet has travelled 300 pixels or more), every element of the bullet array after the one that needed to be removed will not be updated. That is, it's x and y values will not be updated.
Why did I stick that exit in there at all? Well, take it out, and you'll get an error. That's because, after decreasing the upper bounds of the bullet array by 1, the for loop will still try to access bullet (upper(bullet)). But it's not there. So we get our nice little error.
I believe that I fixed this problem once, but then I neglected to save it, and now I've forgot how I fixed it.
Well, all that about the exit is besides the point. The point is that flexible arrays are cool, and that they allow us to do cool stuff. 8)

-Cervantes
Author:  skier [ Fri Nov 26, 2004 2:49 pm ]
Post subject: 
to bad this doesnt work for 2d arrays eh
Author:  Cervantes [ Fri Nov 26, 2004 3:58 pm ]
Post subject: 
Thanks for reminding me. I totally forgot about that:

Coutsos wrote:

A two dimensional array is just an array in which each element is another array. Changing the dimensions means adding another array to the end, or taking one off.

You can use two-dimensional flexible arrays, but you can only change the first element of that array. You cannot change the second element.
This is illustrated by Coutsos' code:
Coutsos wrote:

code:

var stuff : flexible array 1 .. 3, 1 .. 6 of string

put "initialize elements"
for i : 1 .. upper (stuff)
    stuff (i, 1) := "checking " + intstr (i)
end for

put "outputting elements"
for i : 1 .. upper (stuff)
    put stuff (i, 1)
end for

put "new element"
new stuff, upper (stuff) + 1, 6
stuff (upper (stuff), 1) := "new 4"

put "outputting elements"
for i : 1 .. upper (stuff)
    put stuff (i, 1)
end for



Quote:

Complex mutli-demensioned flexible array reallocation not implemented yet.
Author:  BPhelmet [ Tue Dec 21, 2004 7:59 pm ]
Post subject: 
code:
var BulletMove : flexible array 1 .. 0 of
    record
        %variable for bullets to move
        xb1, yb1, xb2, yb2 : int
    end record



here's how i have declared my varialbes

but when i try to give them value, like this

code:
BulletMove (upper (BulletMove)).xb1 := x1Mustang + 30
                    BulletMove (upper (BulletMove)).yb1 := y1Mustang + 60
                    BulletMove (upper (BulletMove)).xb2 := x1Mustang + 48
                    BulletMove (upper (BulletMove)).yb2 := y1Mustang + 60


it says "array subscription is out of range"

what can i do?
Author:  Tony [ Tue Dec 21, 2004 8:27 pm ]
Post subject: 
BPhelmet wrote:

it says "array subscription is out of range"

try
code:

put upper(BulletMove)

to see the actual range. My guess is that you forgot to change the size of your array first.
Author:  BPhelmet [ Tue Dec 21, 2004 8:44 pm ]
Post subject: 
when i use your code
code:

                    put upper (BulletMove)


it still says "array subscription is out of range"

and BulletMove is 0
Author:  BPhelmet [ Tue Dec 21, 2004 8:48 pm ]
Post subject: 
then if i change the size first, it says variable has no value
Author:  Tony [ Tue Dec 21, 2004 9:22 pm ]
Post subject: 
oh wow, if only there was somebody to think for you, and put those two together Surprised

right now your array is empty. It has 0 elements in it. To create a new bullet or whatever, you first increase the array size, then fill all of the newly created elements with default values.
Author:  BPhelmet [ Tue Dec 21, 2004 9:23 pm ]
Post subject: 
alrighty then

i'll try that
Author:  Kold [ Thu Feb 17, 2005 6:51 pm ]
Post subject: 
I used flexible arrays today. They own. helped me make snake. Geoff helped me. w00t to Cervantes
Author:  Kold [ Thu Feb 17, 2005 6:52 pm ]
Post subject:  Geoff...
Cervantes = Geoff Stanley
Geoff Stanley loves his flexible arrays like he loves his fro.
I love to utilize Geoff's mad turing skills in computer science. You ppl gotta respect the mad Geoff skills.

Peace
Author:  Andy [ Thu Feb 17, 2005 6:54 pm ]
Post subject: 
wtf???? ok people have their privacy, and quit your spamming, thats my job
Author:  Jorbalax [ Wed Jun 01, 2005 4:47 pm ]
Post subject: 
BUMP

First of all, very good tutorial. It really helped me get a grasp over the idea of flexible arrays.

Anyways, I've been working on a game that uses them, in a fashion similar to the "bullet" example you provided (missiles flying across the screen). I ran into the exact same problem as you had....the "exit" statement there caused gap, making the missiles flicker whenever the array shrank. After a week or so of toiling around with it, I finally came up with a solution so simple that I punched myself in the gut for not thinking of it. All you need to do is create a variable to count the amount of elements leaving the array, and then adjust the array outside of the for statement.

So, in your example:

code:

var ArrayCounter : int

proc UpdateBullet
    [b]ArrayCounter := 0 %reset[/b]
    for i : 1 .. upper (bullet)
        if Math.Distance (bullet (i).startx, bullet (i).starty, bullet (i).x, bullet (i).y) >= 300 then
            for k : i + 1 .. upper (bullet)
                bullet (k - 1) := bullet (k)
            end for
            [b]ArrayCounter += 1 %Count the total amount of elements to be removed[/b]

        end if

        bullet (i).x += bullet (i).vx
        bullet (i).y += bullet (i).vy
        Draw.FillOval (round (bullet (i).x), round (bullet (i).y), 2, 2, black)
    end for
    [b]new bullet, upper (bullet) - ArrayCounter %Remove the elements from the array[/b]
end Updatebullet


Of course, there's probably some flaw to it that I haven't picked up on, but it eliminates the flicker for me, so I'm content.
Author:  Cervantes [ Wed Jun 01, 2005 4:58 pm ]
Post subject: 
Looks like that would work. If you want, check out the tutorial/thread entitled "Removing and Element from a flexible array from within a for loop" or something along those lines. Wink
The method I came up with is way too cumbersome. I like this method. Mind you, I would modify it such that ArrayCounter starts having a value of upper (bullet) and then subtract one from it each time you want to remove an element. Then do upper bullet, ArrayCounter. That's just how I think. Wink

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy