Removing from Stack/Stack Assert?

About Monkey 2 › Forums › Monkey 2 Programming Help › Removing from Stack/Stack Assert?

Tagged: , , , , ,

This topic contains 13 replies, has 5 voices, and was last updated by  DruggedBunny 1 year, 3 months ago.

Viewing 14 posts - 1 through 14 (of 14 total)
  • Author
    Posts
  • January 11, 2018 at 4:34 am #12802

    DruggedBunny
    Participant

    Am I removing objects correctly from a stack here? I add 10 objects, iterate through to Remove each one, but the final count is 5…

    The code below is the actual code I’m puzzled about, and seems to cause a stack index/length Assert in Debug mode.

    See UpdateGame and If Keyboard.KeyHit (Key.Space) — let it run in Debug mode, and it may crash when some cubes fall over the side; if not, hit Space a few times and it should trigger the Assert.

    In Release mode, it keeps running, and each hit of Space removes more cubes, showing they’re still in the stack! Yet, hitting space in theory removes all objects from the stack… so what’s going on there?!

    Is there some sort of delay in updating the stack/stack.Length after removal?

    (Realise this is likely me, as usual.)

    January 11, 2018 at 1:36 pm #12814

    nerobot
    Participant

    Try to remove items inside of ‘foreach’ in Java or C# and you’ll get runtime error “collection was modified due iterating” (text isn’t exactly).

    To be able to remove items due iterating you have to use stack.iterator with while loop:

    January 11, 2018 at 6:27 pm #12818

    DruggedBunny
    Participant

    Hmm, thanks, nerobot. It’s quite complex, but seems to do the job anyway. I’ll try understand it!

    January 11, 2018 at 7:20 pm #12819

    Hezkore
    Participant

    Aha, I’ve been having similar issues.
    I added a bunch of particles to a stack and tried to remove them almost at the same.
    I kept getting some weird errors by doing so.

    I’m not sure I understand the ‘solution’, but good to know!

    But why isn’t Monkey 2 doing this itself?
    Is there any benefits to it acting this way?

    January 11, 2018 at 9:02 pm #12820

    Mark Sibly
    Keymaster

    The problem is to do with removing items from a container while you’re iterating though the same container. It’s a bit like doing this:

    This may or may not things clearer, but the problem here is that after you delete an item, the current item then becomes the next item (ie: all items ‘shift down’) but then the ‘Next’ statement ‘skips over’ that next item so you end up missing every second item! Worse than that, after removing an item, depending on the type of container involved, it may be very hard to even get to the next item as the current item is no longer really valid. For example, with a linked list, after removing an item the ‘next’ and ‘succ’ fields of the link node may (should) not be valid so there’s no way to get to the next item. I ended up fudging around this with lists in monkey2 because the outcry over not being able to remove items while you were iterating through a list from ex-blitz users was just too much to deal with (and because I avoid lists these days anyway). Looks like I fudged stacks too…

    The bigger idea here is it’s dangerous to modify a container while you’re iterating through it without being very careful, and the iterator.Erase() approach is one way to do that safely. The compiler can only really do so much to help here without things become very complex/slow as it has to deal with situations like nested eachin loops with the same container (eg: for collision checking) etc. In fact, to do it properly, a container would have to track every iterator to items within the container, which would of course incur significant overhead and be very slow.

    It’s just something I don’t do any more, and there are generally lots of alternatives, eg: instead of:

    …which wont even work properly due to the ‘skipped items’ issue, you can of course simply go…

    Which works properly and doesn’t involve any potentially slow ‘Remove’ operations.

    I also find this useful sometimes (for stacks/deques only):

    This also destroys all items in a stack, but it does it in such a way that the stack remains valid at all times so it’s always safe to add items to it at any time in the loop. I use this idea a lot in compilers, as they frequently have to deal with ‘todo’ lists and this is a nice way to process a todo list.

    January 11, 2018 at 11:06 pm #12821

    Amon
    Participant

    I ran into this problem when using C#. One of the methods was to go through the list backwards and remove what you want that way.

    Apologies if this is not the best method but it is something that worked for me.

    January 12, 2018 at 3:26 am #12823

    DruggedBunny
    Participant

    Interesting read! I was wondering why it worked with lists (in Blitz), and noticed they were also ‘failing’ in mx2 the way stacks do. (I’d tried switching the above code to a list.)

    The pb.Destroy () / boxes.Clear () option works well here for the Space-bar hit, but what would be the best way to handle removing an object mid-iteration, as UpdateBoxes () — minus boxes.Remove (pb) — still crashes, obviously for the reasons you’ve explained, since it’s not emptying the whole stack like Space does.

    Thinking about it, I suppose a stack isn’t the best solution for this scenario, ie. removing arbitrary objects from the middle of a collection, since stacks are all about adding/removing at the top of the stack, but what would be better here?

    (I just used a stack because I gather they’re quicker than lists!)

    That stack-top popping-copying thing is pretty cool, but I guess maybe a map could be a better overall solution?

    January 12, 2018 at 3:33 am #12824

    nerobot
    Participant

    Are you afraid of iterators? 🙂

    My example above is an analogue of native Eachin.

    I think it’s the fastest and easiest way.

    January 12, 2018 at 3:58 am #12825

    Mark Sibly
    Keymaster

    Are you afraid of iterators?

    A little bit maybe! Can never quite remember the syntax…

    (I’d tried switching the above code to a list.)

    Strange, you should be able to remove-while-you iterate through lists, eg:

    This is really easy to ‘hack’ into lists, but not into stacks. Either way, it offends my sensibilities as a gentleman programmer so I don’t do that any more! But I do get why it’s popular, it’s probably the easiest to grasp even if it is inefficient and error prone.

    what would be the best way to handle removing an object mid-iteration

    There are several ways to approach this, including:

    • Use iterator methods Bump() and Erase() to do it the ‘nice’ way.
    • Use a separate ‘kill’ list containing items you want to destroy later. Once you’ve gone through the main ‘live’ list, iterate through the kill list and kill anything there from the live list.
    • Use some other far out method, eg:

    This effectively does a simultaneous iterate/erase/compact pass. It’s based on the idea of ‘double buffering’ containers, another approach where you build the ‘next’ live list while processing the ‘current’ one, and then swap them afterwards.

    And last but not least, the recommend way using iterators:

    January 12, 2018 at 4:22 am #12826

    nerobot
    Participant

    Very nice explanation to be article-ized. 🙂

    January 12, 2018 at 7:11 pm #12831

    DruggedBunny
    Participant

    Yeah, that’s great, lots of options there. Even the iterator seems to makes sense… at first glance! Will play…

    January 14, 2018 at 4:04 pm #12859

    DruggedBunny
    Participant

    Just posting working versions with List and Stack (manual iteration) variants… quite different code needed for each! (For quick reference, the Game class’s boxes field is the container in both cases.)

    List:

    Stack:

    (Found a cooler remove effect than alpha!)

    January 14, 2018 at 4:41 pm #12860

    nerobot
    Participant

    You cat to simplify a bit logic with iterator:

    January 14, 2018 at 10:47 pm #12863

    DruggedBunny
    Participant

    Nice, thanks nerobot.

  • Author
    Posts
Viewing 14 posts - 1 through 14 (of 14 total)

You must be logged in to reply to this topic.