Got a question that the wiki doesn't answer? Ask on the forum (preferred), or join us on IRC.

BeastNode

CommandHelper/Staged/Array Iteration

From EngineHub.org Wiki
Jump to: navigation, search


Array iteration is an often overlooked aspect of programming. At first glance, iterating an array and making modifications to it as you are iterating it seems like a trivial operation. However, this is not the case, as several unrelated operations can cause the iteration to cause undefined behavior. MethodScript has some automatic controls to make this operation easier in straightforward cases, while preventing accidental behavior caused by concurrent modification operations. All the specified operations involve the builtin foreach loop, for loops, while, and do/while loops do not support these behaviors, as it is up to the programmer to manage the counter loops in those cases.

There are a few cases that have special handling: Current/previous item deletion, insertion of new items before the iterated item, and insertion of new items after the iterated item. Removal of items after the iterated item, and changes to any values, including the one currently being iterated doesn't have any effect on the iteration order, and therefore won't cause any issues.

The behavior of the foreach loop covers typical behavior, and will not suite the needs of every case. If the behavior is not acceptable, use of the for loop is preferred, as finer grained control of the looping mechanism can be controlled that way.

The iterators are globally managed automatically by MethodScript, and nested iterations will not affect this. If an array is being iterated by two different loops at once, all operations will apply to both internal iterators, and each loop will follow the rules as specified below, depending on where in the iteration each loop is. Each loop is otherwise independent of other loops. The array itself is not changed during the iteration by the automatic iteration handling, just the key/value that is assigned during each iteration. Insertions/deletions are handled with the indexes of the array as they currently exist at that particular moment. The key in the foreach isn't adjusted accordingly either, so you must account for this manually, if you perform multiple operations within the iteration, and the key is used multiple times as a reference point.

Associative Arrays

Associative arrays are handled by "freezing" the keyset as soon as iteration begins, and so insertions and removals do not affect iteration order. As associative arrays are maps, rather than sequential arrays, this does not present an issue while iterating.

Current item deletion/Deletion of index before current item

This simple code demonstrates the problem:

1   @array = array(1, 2, 3);
2   foreach(@key@value in @array){
3      array_remove(@array@key);
4   }
5   msg(@array); //{}


Let us consider what this code would do without the special behavior provided by MethodScript. @key would start out being 0. We would then remove the 0th element in the array, in this case, 1, which would cause the values to shift to the left 1. The array would then be array(2, 3). The loop would start over, and the key would increment to 1. The next call to array_remove would remove the item at index 1, at this point, now 3. The size of the array would now be greater than the iterator count, and we would exit the loop. But 2 would still be left in the array!

To fix this issue, MethodScript tracks the changes in the array, and decreases the counter by 1. This causes the item at index 1 to be iterated "again" which in this case points to an entirely different value. So in reality, this code will remove all the items in the array, without skipping items. The same logic applies to deletion of items before the current index, as the same behavior (shifting items left one) causes the same problems.

Additions of new items before the iterated item

This simple code demonstrates the problem:

1   @array = array('last value');
2   foreach(@key@value in @array){
3      array_insert(@array'value', 0);
4   }
5   msg(@array); // {value, last value}


Without the special behavior, this would cause an infinite loop, as the key would increment each time, and would cause the 'last value' item to be iterated each time. The special behavior prevents this however, as the assumption is that the newly inserted item has already been "processed" by user code, and so essentially, the counter is increased by 1, making the next iteration bypass the item which is currently the "current" item.

Insertion of new items after the index

This simple code demonstrates the problem:

1   @array = array('first value');
2   foreach(@key@value in @array){
3      @array[] = array_size(@array);
4   }
5   msg(@array); // {first value, 1}


Or additionally:

1   @array = array(1, 2, 3);
2   foreach(@key@value in @array){
3      array_insert(@array@key + 1, 0);
4   }
5   msg(@array); // {1, 0, 2, 0, 3, 0}


Without the special behavior, these two examples would cause an infinite loop, as the key would constantly be set to the last item in the array. The special behavior prevents newly inserted items from being processed, essentially adding them to a "blacklist" of values to ignore when the iterator gets to that item. The blacklist is automatically managed as the iteration occurs, so that even if those values shift due to future operations, that particular value is still not iterated. The assumption is that newly inserted values have already been "processed" by user code.

Also of note, if a continue() is used, this will account for and skip these blacklisted values, including if a number greater than 1 is used.

The behavior of other languages can be matched by using the following code:

1   @array = _some_array();
2   for(@i = 0, @i <= length(@array), @i++){
3      if(_some_condition()){
4         @array[] = 'value';
5      }
6   }




Navigation menu