/customers/iconara.net/iconara.net/httpd.www/blog/wp-content/plugins/wp-super-cache/wp-cache-phase1.php Iconara » On iteration (arrays are Evil)

On iteration (arrays are Evil)

ActionScript provides a couple of ways to do iteration, for-loops for arrays, for-in-loops for associative arrays and while-loops for the general case. What it doesn’t do is provide us with datastructures that are safe to let client code iterate over, and what’s more, for-loops are so very low-level.

In this article I’m going to make the case why arrays in ActionScript are Evil, give you suggestions on how to use them properly and tell you why iterators are so good.

Iterators and encapsulating iteration

If you have a list, the most common use case is to loop through it one element at a time and do something with the element. To do this in ActionScript you use a for-loop, which lets you initialize, and increment an index and also do boundary checking for the index.

Somewhere in that description there should be a list and elements, too, but they got lost in the details of the for-loop. That is the problem with the for-loop, it’s so low-level that you are more concerned with the index than the list. Moreover, the first line of a for-loop is almost identical every time you write it. Low-level and code duplication means we should encapsulate and abstract.

Then there is the case of the for-in-loop. It’s less low-level as we don’t have to write any boundary check or incrementor, but it’s another form of iteration, and that means we can add incompatible syntax to the list of bad things, switching between an array as data structure and an associative array means we have to rewrite the iteration code, which is not a god thing.

Arrays are mutable, and Evil

There is a deeper problem with the way most iteration code in ActionScript is written, and it has to do with arrays being mutable.

It’s convenient to have arrays and associative arrays built into the language, with these two you can solve most of the common data storage situations, but they are decietful. The problem is that both are mutable, only exists as mutable and that they don’t provide any simple copying mechanisms, which means that if you return an instance of one of them the client code can modify it however it wants, and that means your internal state is also modified. This breaks one of the fundamental co corner stones of object orientation: encapsulation.

An object has its state, which it guards as best as it can, protecting it from unwanted changes from the outside, because if it doesn’t client code can wreck havoc with its internal state.

It’s a basic object oriented maxim that you should never return mutable objects, yet in ActionScript it’s very inconvenient to do anything but. String, Array, Object and Number are all mutable and the only way to guard your data is to return copies, but since there is no simple copy mechanisms, you would have to do it yourself.

It’s not so hard to imagine a scenario where using only arrays can result in trouble. Consider this code:

class Something {
    private var somethingsInOrder : Array;

// ... things that initialize the array and add items to it

/**
 * Returns all somethings for your convenience.
 */
public function getSomethings( ) : Array {
    return somethingsInOrder;
}

}

Say that it’s important for the class’ inner workings to have the somethings in order, but for client code it may not matter (therefore the getSomethings method does not say anything about returning the somethings in order, it does not guarantee that this is the case, and the internal workings may change so the next version may have another way of storing the somethings.

What happens if you want the somethings in order, or another order perhaps? You do this:

var somethings = something.getSomethings();

somethings.sort(mySortFunction);

Since sort modifies an array you have, without knowing, or without thinking, changed the internal state of the something object. But you haven’t actually done anything wrong, it’s always up to the object to guarantee its own state, that’s the point of encapsulation.

The lesson to learn is that you should not return arrays, or at least return a copy of an array. Iterators are a good way to guard yourself against encapsulation problems, since the client code has no way of actually changing the order or other aspects of your arrays or other collections.

Conclusion

Arrays and iteration in ActionScript have many fundamental flaws; arrays are mutable and have no immutable counterparts giving you no choice but to break encapsulation and hope for the best, for-loops lead to code duplication, are generally low-level and also bind you to one specific data type, if you change it you need to change all iterations over that data type.

Simple solutions

First I’m going to present a couple of simpler suggestions to help with the problems described above, and after that I’m going to tell you the real solution.

Problem: arrays are mutable and that breaks encapsulation. Solution: return copies of arrays instead of the real array. Problem: ActionScript doesn’t provide a copy-mechanism for arrays. Solution: use slice or concat without parameters. It’s noted in the documentation that both these methods have the effect of copying the array if no parameters are given. It’s not pretty, but it works. Unfortunately there exists no simple solution for associative arrays.

Problem: switching between iterating over an array and an associative array means rewriting the whole loop. Solution: getting into the habit of always assigning the current item to a variable on the first line of the loop means that you can switch between for and for-in without having to rewrite more than the loop and that assignment. Example:

for ( var i = 0; i < list.length; i++ ) {
    var item = list[i];

item.doSomething1();
item.doSomething2();
item.doSomething3();

}

can easily be changed to

for ( var key in list ) {
    var item = list[key];

item.doSomething1();
item.doSomething2();
item.doSomething3();

}

the body of the loop remains the same. If you want to assign to the current index/key instead of modifying it you can assign to the item variable and then assign that back to the array/associative array on the last line, mirroring the first.

for ( var key in list ) {
    var item = list[key];

if ( item.testSomething() ) {
    item.doSomething1();
    item.doSomething2();
    item.doSomething3();
} else {
    item = new Thingie();
}

list[key] = item;

}

Problem: for-loops are low level, dealing more with maintaining an index than with the list that is being iterated. Problem: the first line of the for-loop is always the same, yet it has to be written every time. Solution: I have quick-and-dirty solution to these problems.

Although the solutions above are good and valid, they are not very good, mearly better than the alternative. What comes now is so much better.

Iterators

The iterator pattern is a well-known design pattern used to encapsulate and abstract away the specifics of iteration.

It tells us how to encapsulate iteration so that the code that iterates does not need to know which type of data structure the elements are stored in, nor does it need to change if the underlying data structure changes.

Iterator solves all the problems presented above: it makes it possible to not break encapsulation as iterators are immutable, it abstracts away the underlying data structure, so iteration will always be the same, and it (generally) uses while-loops and no indexes, so no more silly code duplication.

Using iterators usually looks something like this:

In Java:

Iterator somethings = somethingContainer.somethings();

while ( somethings.hasNext() ) { Something something = (Someting) somethings.next();

something.doSomething();
something.doSomething();

}

In Objective-C (iterators are sometimes called enumerators):

NSEnumerator *somethings = [somethingContainer somethings];

id something = nil;

while ( (something = [somethings next]) != nil ) { [something doSomething]; [something doSomething]; }

The iterator pattern describes iterators as having three methods (the names vary): hasNext, next and optionally remove. The last is optional as it means the iterator would be mutable, but in some cases it’s both valid and convenient to have mutable iterators (just as it is having mutable arrays). Note that in the Objective-C example, even the hasNext method has been omitted, instead next returns null if there are no more elements in the iterator.

An iterator implementation

Writing an iterator for ActionScript is dead simple. What is needed is something that encapsulates an array and makes it safe to return.

First we start with an interface defining what constitutes an iterator, we will omit the remove method, since I don’t belive it to be useful (it doesn’t exist in Objective-C and you rarely see it used in Java):

interface Iterator {

public function hasNext( ) : Boolean ;

public function next( ) ;

}

Note that the next method has no declared return type. The reason for this is that if it was declared, as in Java, to return Object we would need to cast the return value every time, and since type casting in ActionScript is broken I rather avoid it. If you want type checking, type the variable you’re assigning to.

Ok, so far so good, now let’s see a concrete iterator implementation, something that can actually iterate an array for us:

class ArrayIterator implements Iterator {

private var list : Array;

private var currentIndex : Number;

public ArrayIterator( list : Array ) {
    this.list = list;
    this.currentIndex = 0;
}

public function hasNext( ) : Boolean {
    return this.currentIndex &lt; this.list.length;
}

public function next( ) {
    var next = this.list[this.currentIndex];

    this.currentIndex++;

    return next;
}

}

There, you have it, the only code you need to never have to type another for-loop.

One more thing

That’s not all you can do with iterators. There are a lot more useful things than iterating over an array. You can write iterators that don’t have an array as underlying data structure, for example an iterator that takes an XML object and returns all nodes in document order, or all nodes with a specific name, or you can create an iterator that returns the Fibonacci sequence, if you want. You can write all sorts of generators, have you ever created a table with alternating background colour for each row? Instead of writing an if to determine which colour to use, write an iterator that returns a sequence of alternating colours:

class CycleIterator implements Iterator {

private var elements : Array;

private var index : Number;

public CycleIterator( elements : Array ) {
    this.elements = elements;
    this.index = 0;
}

public function hasNext( ) : Boolean {
    // the cycle never ends
    return true;
}

public function next( ) {
    var element = this.elements[this.index];

    this.index++;

    if ( this.index == this.elements.length ) {
        this.index = 0;
    }

    return element;
}

}

and use it like this:

var alternatingColors : Iterator = new CycleIterator(["even", "odd"]);

var rows : Iterator = ...;

while ( rows.hasNext() ) { var row = rows.next();

row.setBackgroundColor(alternatingColors.next());

// display row

}

Beatiful isn’t it?

One Response to “On iteration (arrays are Evil)”

  1. RaymonWazerri Says:

    Hey, I love what you’e doing! Don’t ever change and best of luck.

    Raymon W.

Leave a Reply