Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Removing an Element from a Flexible Array within a For Loop
Index -> Programming, Turing -> Turing Tutorials
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Cervantes




PostPosted: Sat Jan 15, 2005 11:13 pm   Post subject: Removing an Element from a Flexible Array within a For Loop

Below is a detailed description of everything leading up to the question. Skip it if you must; for the final question, check the bottom.

Let's say we've got a flexible array. Let's say it goes from 1 to 10. At some point in our program, some condition becomes true. Now, we want to remove a specific element from our flexible array. Easy enough:
Turing:

var myArray : flexible array 1 .. 10 of int
if condition = true then
  myArray (elementToRemove) := myArray (upper (myArray))
  new myArray, upper (myArray) - 1
end if

Right-o. But, what if we need to check the condition from inside a for loop, and the conidtion we are checking is related to the flexible array?
Turing:

for i : 1 .. upper (myArray)
  if condition_relating_to_myArray = true then
    myArray (i) := myArray (upper (myArray)
    new myArray, upper (myArray) - 1
  end if
end for

Uh oh! We are going to get an error, "Array subscript is out of range". Say we wanted to remove element 3. We're going through the for loop, then, shazam, i = 3. The condition is true, the last element of the array is copied to element 3's location, and the array is downsized such that it now goes from 1 to 9. Cool. But, the for loop is still going. When i = 10 (the last element in the array, as it was before the change), it can't evaluate the if statement because the last element of the array was removed. To solve this, we can put an exit inside the if statement to exit the for loop. This eliminates the error, but it also prevents our code from evaluating the if statement using other elements of the array. This is a problem: if two or more elements of the array would fulfill that if statement at any given time, only one of them would actually have any affect. The others would be passed by until the next time through the main loop, but by then they might have changed such that they would no longer satisfy the condition.

So, what do we do? So far, the best idea I've thought of would be to create another flexible array that will store the elements of myArray that need to be removed. Then, after the for loop, we can enter another for loop (from 1 to upper (removeTheseElements_FlexibleArray)) that will eliminate the necessary elements of myArray.
Turing:

    new elementsToRemove, 0 %clense the array
    for i : 1 .. upper (myArray)
        if condition_relating_to_myArray = true then
            new elementsToRemove, upper (elementsToRemove) + 1
            elementsToRemove (upper (elementsToRemove)) := i %will remove element i from myArray
        end if
    end for
    for j : 1 .. upper (elementsToRemove)
        myArray (elementsToRemove (j)) := myArray (upper (myArray))
        new myArray, upper (myArray) - 1
    end for

Looks good. Let's see it in action.
Turing:

var myArray : flexible array 1 .. 15 of int
for i : 1 .. upper (myArray)
    myArray (i) := Rand.Int (1, 5)
end for

var elementsToRemove : flexible array 1 .. 0 of int

loop %main loop

    cls
    for o : 1 .. upper (myArray)
        locate (o, 1)
        put o : 2, ": ", myArray (o)
    end for
    loop
        exit when hasch
    end loop
    Input.Flush

    new elementsToRemove, 0 %clense the array
    for i : 1 .. upper (myArray)
        if myArray (i) = 4 then
            new elementsToRemove, upper (elementsToRemove) + 1
            elementsToRemove (upper (elementsToRemove)) := i %will remove element i from myArray
        end if
    end for
    for j : 1 .. upper (elementsToRemove)
        myArray (elementsToRemove (j)) := myArray (upper (myArray))
        new myArray, upper (myArray) - 1
    end for

end loop

Hot damn! It works! Unfortunately, I already knew that, and I still have a question.

The Question
I use the above method in a turing program I am making (Robots, from Ubuntu Very Happy). But, for some reason, I experience major problems. The information I've gathered tells me that elementsToRemove has a ton of elements. Far more than it should. Because of this, too many elements are removed from my robots array (equivilant to myArray in the examples). What I'm looking for is the reason why I'm getting the error (or, the reason why elementsToRemove has so many elements) or another way to remove the elements from the robot array (the main array).
Complete program is attached. I've also noticed that sometimes a robot will disappear when it shouldn't. Wierd.
Helpers receivce BITS.



Robots Work.t
 Description:

Download
 Filename:  Robots Work.t
 Filesize:  11.02 KB
 Downloaded:  338 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
Bacchus




PostPosted: Sun Jan 16, 2005 12:37 am   Post subject: (No subject)

ok 1st Hi first post Razz 2nd isnt this suposed to be Tutorials lol and ur a mod
enouph of that 3rd i dont even pretend a little to understand much of this so.. bear with me if this is a noob comment
Quote:
for i : 1 .. upper (myArray)
if condition_relating_to_myArray = true then
myArray (i) := myArray (upper (myArray)
new myArray, upper (myArray) - 1
end if
end for

then in the part after you talked about how you would get an error when the first for statement got to a part of the array that had been deleted and you had to exit the for before it did this. but i didnt see the accual exit in the next bit of code. could you add in an exit checking if the array will go out of range? ex:
code:
for i : 1 .. upper (myArray)
  if condition_relating_to_myArray = true then
    myArray (i) := myArray (upper (myArray)
    new myArray, upper (myArray) - 1
  end if
exit when i+1>upper(myArray)
end for

ok im not sure if this will work and im not even sure if it will do anything to help.. (i know like this much: ->||<- of flexible array) if it doesnt work, please give an explaination why. it will help me learn. and even if it does help or you are feeling generous, bits are Not required, id rather learn what stupid mistake im doing lol
Cervantes




PostPosted: Sun Jan 16, 2005 11:52 am   Post subject: (No subject)

Hi Baccus! Welcome to CompSci.ca.
Ouch, jordan, you didn't have to quote the entire thing!
Baccus wrote:
2nd isnt this suposed to be Tutorials lol and ur a mod

Err, who moved this? This was genuine help; I merely gave a detailed description so that anyone who did not understand what I was asking would be able to. The idea was, after the problem got solved, then it would become a tutorial.
Well, all for the best, I suppose. Thanks for the idea Baccus! With some tweaking, I got it to work.
The problem with what you suggested is thus: say you want to remove element 3 and 10 of a 10 element flexible array. The for loop will reach 3, copy element 10 to element 3, then remove element 10. So, essentially, we've eliminated element 3, by this point. But then the program keeps going, la-di-da-di-da, then i = 10. (i + 1 > upper (myArray) ) so it exits, without eliminating element 10 (if it tried to, it would crash, mind you).
Turing:

var myArray : flexible array 1 .. 10 of int
for i : 1 .. upper (myArray)
    myArray (i) := i
    put i : 2, ": ", myArray (i)
end for
put skip
for i : 1 .. upper (myArray)
    if myArray (i) = 3 or myArray (i) = 10 then %we want to remove element 3 and 10, at the same time
        myArray (i) := myArray (upper (myArray))
        new myArray, upper (myArray) - 1
    end if
    exit when i + 1 > upper (myArray)
end for

for i : 1 .. upper (myArray)
    put i : 2, ": ", myArray (i)
end for

As you can see, the element with a value of 10 is still part of the flexible array. And, though we wanted to remove two elements from the array, only 1 was actually removed.

To fix this, I used a time-consuming and probably bad method: I wrapped the for loop (i) inside another for loop, that goes from 1 to 2.
Turing:

var myArray : flexible array 1 .. 10 of int
for i : 1 .. upper (myArray)
    myArray (i) := i
    put i : 2, ": ", myArray (i)
end for
put skip
for rep : 1 .. 2
    for i : 1 .. upper (myArray)
        if myArray (i) = 3 or myArray (i) = 10 then %we want to remove element 3 and 10, at the same time
            myArray (i) := myArray (upper (myArray))
            new myArray, upper (myArray) - 1
        end if
        exit when i + 1 > upper (myArray)
    end for
end for

for i : 1 .. upper (myArray)
    put i : 2, ": ", myArray (i)
end for


Works well enough, though probably unnecessarily time-consuming. A better method would be great: I've got studying to tackle, so I can't spend much more time at this, right now Sad
Lastly, the rep for loop might need to be increased from 1 .. 2 to 1 .. 3, depending on the elements you are removing. Ex., try removing elements 7, 8, 9, and 10 from the array, with the rep for loop from 1 .. 2. It won't work, it'll have to be changed to 1 .. 3.
+50 BITS to bacchus, extra for being new to the site Smile
-Cervantes

EDIT:
Bacchus wrote:

then in the part after you talked about how you would get an error when the first for statement got to a part of the array that had been deleted and you had to exit the for before it did this. but i didnt see the accual exit in the next bit of code.

The "next" code (the third bit of code) wasn't supposed to have the exit statement. Instead, it was supposed to, using another flexible array, keep track of all the elements that needed to be removed from myArray. Then, afterwards, another for loop would be entered that would go through and remove the necessary elements from myArray.
Bacchus




PostPosted: Sun Jan 16, 2005 12:36 pm   Post subject: (No subject)

ic, thxs youve shed some valuable light on flexible arrays for me Smile
Display posts from previous:   
   Index -> Programming, Turing -> Turing Tutorials
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 4 Posts ]
Jump to:   


Style:  
Search: