Share 'Why we need a collection framework in ActionScript' on Delicious Share 'Why we need a collection framework in ActionScript' on Facebook Share 'Why we need a collection framework in ActionScript' on Google Bookmarks Share 'Why we need a collection framework in ActionScript' on Twitter

  1. Introduction to collections
    1. Built-in data containers
    2. ... to collections
    3. Classification of collections
  2. 10 reasons for a collection framework
  3. Requirements to an ActionScript collection framework
    1. Software requirements
    2. Acceptance criteria
  4. Existing solutions
  5. Comments (9)
  6. Leave a Comment

In this post, I will introduce you to the meanings of data collections and the different possiblities to collect data we have in ActionScript. Building on that, I am going to point out the most general requirements to a collection framework before I give a survey to existing solutions.

Introduction to collections

Unlike scripting for server environments, where we usually synchronously access the underlying data base and process those data more or less consecutively in response to preceding HTTP calls, in client applications we need to more seriously take care about how we manage storage and retrieval that data during the entire application lifecycle. A common pattern is to load a bunch of resources from the network and keep it in stock until the appliction gets terminated. This is often called proxying, since the data we are working on are copies of the orginal data living in the remote data base. A second important difference to server side data handling comes up with the needs to collect user generated data to fulfill what the application is made for.

Built-in data containers

Array

Each programming language consists of several native containers to file and access data sets. The best known is the Array, wich stores its elements in an ordered fashion and provides convenient (random) access over its indexes or, by using a for loop, sequential access. The same item can be contained multiple times. Arrays are exceptional fast and can hardly be beaten. There is also a typed array called vector, which promises to be even faster. However, keeping elements sorted, adding elements mostly at the begin or finding elements is not really Array’s business.

public function ArrayTest() {
     
  // adding at end
  var a : Array = new Array();
  var i : int;
  var start : Number = new Date().getTime();
  for (i = 0; i < 50000; i++) a.push(i);
  var end : Number = new Date().getTime();
  trace ("add last i:" + i + " t:" + (end - start));
 
  // adding at start
  a = new Array(); start = end;
  for (i = 0; i < 50000; i++) a.unshift(i);
  end = new Date().getTime();
  trace ("add first i:" + i + " t:" + (end - start));
 
  // finding
  start = end;
  for (i = 0; i < 50000; i++) {
    if (i + a.indexOf(i) != 49999) throw new Error("error");
  }
  end = new Date().getTime();
  trace ("find i:" + i + " t:" + (end - start));
 
  // add last i:50000 t:16
  // add first i:50000 t:1812
  // find i:50000 t:24954
}

Associative Array

Sometimes the programming language supports associative arrays. In Flash we can use the dynamic Object class to create simple lookup tables. We are here restricted to number or string typed keys. Internally new properties are being added to the object at runtime. Random access (using the keys) or sequential access (for in loop) is possible. The for in loop does not preserve the insertion order. Also, duplicate keys are not possible. ActionScript3 did introduce a Dictionary class, wich acts mainly like the Object but allows additionally reference typed keys (objects, arrays, functions).

public function DictionaryTest() {

  var d : Dictionary = new Dictionary();
  var o : Array = new Array();
  var i : int;
  for (i = 0; i < 50000; i++) o[i] = {index:i};

  // adding
  var start : Number = new Date().getTime();
  for (i = 0; i < 50000; i++) d[o[i]] = i;
  var end : Number = new Date().getTime();
  trace ("add i:" + i + " t:" + (end - start));
 
  // finding
  start = end;
  for (i = 0; i < 50000; i++) {
    if (d[o[i]] != i) throw new Error("error");
  }
  end = new Date().getTime();
  trace ("find i:" + i + " t:" + (end - start));
 
  // add i:50000 t:16
  // find i:50000 t:15
}

Compositions

A third fundamental data container can be easily self-made by applying composition. The idea is to link objects among each other, what creates this way a sequential list or even a tree. We always need to save the first object from that we start enumeration. The composite structure cannot be accessed randomly. Iterating returns the items in the order they were inserted. The composition can manage the insertion of duplicate elements.

public function CompositionTest() {
 
  // adding at start
  var i : int;
  var first : Node = new Node(0, null);;
  var start : Number = new Date().getTime();
  for (i = 1; i < 50000; i++) {
    first = new Node(i, first);
  }
  var end : Number = new Date().getTime();
  trace ("add first i:" + i + " t:" + (end - start));
 
  // finding
  var node : Node;
  i = 0; start = end;
  for (i = 1; i < 1000; i++) {
    node = first;
    while (node) {
      if (node.item == i) break;
      node = node.right;
    }
  }
  end = new Date().getTime();
  trace ("find i:" + i + " t:" + (end - start));
 
  // add first i:50000 t:141
  // find i:1000 t:9719
}

class Node {
  public var right : Node;
  public var item : uint;
  public function Node(theItem : uint, theRight : Node) {
    item = theItem;
    right = theRight;
  }
}

… to collections

You have seen that the different approaches to collect data have their particular pros and cons. More structured, there are 4 fields of quality, the choice of a collection should be done in respect to.

  • Performance of inserting

    an element at a specific position (at begin, in between, at end)

  • Performance of finding

    an element (constant, logarithmic, linear or worse time)

  • Order

    of the collection’s elements in enumeration (no order, insertion order, sorted order)

  • Multiplicity

    of elements (unique, multiple)

Each of the three described built-in data containers supports a distinctive set of the qualities just mentioned. For example, the Array returns its items in insertion order but is pretty slow in finding one, while the Object enables a very fast lookup but enumeration is always surprisingly. Well, what about an example phone book application where we need ordering (phone book index) as well as direct element access (search)? In cases like this we simply combine the advantages of different containers. We use a sorted array to store the phone book’s entries (index) and set up an associative array (in Flash the Object) to save the participant’s name together with the accordant array index (search). We can think about various combinations, and some of them are that common, that they became names and have been included into the core libraries of many programming languages where they are now called collections.

Classification of collections

The Java Collections Framework defines three main collection types: Lists, sets and maps. (The queues can be considered as optimised lists.) Lists are always ordered, may contain duplicates and can be handled the same way as usual arrays. Sets cannot contain duplicates and provide random access to its elements. Maps connect unique keys with values, provide random access to its keys and may host duplicate values. The simplest implementions are respectively ArrayList, HashSet, HashMap. Different implementations are available for each of those types. Either they focus on ordering (LinkedHashSet, LinkedHashMap) or sorting (TreeSet, TreeMap) or fast inserting (LinkedXXX).

Besides the functional aspects, collections can also be classified by their internal structure (implementation). The table below lists a few important collections and their characteristics as well as realisation possibilies in ActionScript.

Collection Characteristics Realisation
Multiplicity Order Access
ArrayList multiple ordered random
sequential
Array
LinkedList multiple ordered sequential Composition
SortedList multiple sorted random
sequential
Array
Set unique unordered random Dictionary
LinkedSet unique ordered random
sequential
Dictionary +
Composition
SortedSet unique sorted random
sequential
Binary tree
Map unique keys
multiple items
unordered random Dictionary
LinkedMap unique keys
multiple items
ordered random
sequential
Dictionary +
Composition
SortedMap unique keys
unique items
sorted random
sequential
Dictionary +
Binary tree

We can think of several applications for any of the different collections. The LinkedList would be for example perfectly suitable for an undo/redo history. Here we always add items at begin of the list and retrieve the elements sequentially. The phone book above uses the SortedMap. To reflect unmodifiable remote data we probably are going to use the LinkedMap, which enables access over an ID while it keeps the given order. The sets are most often used to collect runtime generated data. In a shopping application we might use a LinkedSet for the basket. Adding and removing of products can be done in constant time. The basket overview shows the products in the order they were added. When trying to add a product a second time, it’s simple to increase the quantity. Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package as3.collections {
  import flash.display.Sprite; 
  public class SetBasketExample extends Sprite {
    private var basket : ILinkedSet;
    public function SetBasketExample() {

      basket = new LinkedSet();
      var shirt : Product = new Product("shirt", 19.90);
      var cap : Product = new Product("cap", 14.00);
      add(shirt);
      add(cap);
      add(shirt);
     
      trace (basket.toArray().join("\n"));

      // cap #1 $14
      // shirt #2 $39.8
    }
    public function add(product : Product) : void {
      if (basket.hasItem(product)) {
        product.quantity++;
      } else {
        basket.addItemAtStart(product);
      }
    }
  }
}
internal class Product {
  public var name : String;
  public var price : Number;
  public var quantity : uint = 1;
  public function Product(theName : String, thePrice : Number) {
    name = theName;
    price = thePrice;
  }
  public function toString() : String {
    return name + " #" + quantity + " $" + quantity * price;
  }
}

Until here, I have illustrated the potential of collections to solve common software problems. However, that’s not everything we can benefit from. In the next chapter I will give you a compact overview to the goals of collections, which moves the perspective more to software architecture and collaboration.

10 reasons for a collection framework

  1. As we already know: Collections are design patterns for solutions of common problems with storing and retrieving data. Patterns help us in understanding situations and designing software. They clearly express their benefits and weaknesses.
  2. Collections take over the implementation of the most commonly required functionality. No need to reinvent the wheel for each new project.
  3. Wisely chosen, also in the mix with built-in containers, collections will enhance the performance of applications, even although they are built onto the programming language and are not part of the language itself.
  4. Using collections results in far less and better readable source code.
  5. Collections are entirely extendable. New functionality can be added using inheritance as well as by setting up completely new implementations for the particular interfaces.
  6. Collections provide a generalised interface to the different underlying data structures. Wherever an ISet is accepted you can pass a Set, LinkedSet, SortedSet or MyCustomSet instance. May they internally hold an array or an object, the interface abstracts from the actual insertion strategy (push or []) and exposes the general addItem(). This way collections are interchangeable, portable and shareable.
  7. Collections provide a uniform way of enumeration by engaging the iterator design pattern. Regardless of their distinctive implementations, collections can be interchangeable passed wherever an iterable object is expected.
  8. A collection framework enables developers creating third party libraries based on collections rather than native containers. The libray interfaces are not restricted to accept ordinary arrays or objects. Without a framework, each libraray either would have to provide its own collection implementations, which can be considered as a reinvented framework, or simply had to abstain from using collections, which cannot be considered ;-) .
  9. The collection framework (assuming its existance) guarantees failure restistance, stability and sophistication. The framework is widely adapted, community based and proven by a lot of serious projects. Thus, it will be easy to explain its integration within official work flows.
  10. Finally, an existing collection framework can make up one of the reasons keeping ActionScript/Flex being the technology of choice for web client application development. This is an important point in consideration of the fast growing JavaScript and JavaFX communities.

At this point of explanations, I have no doubt, you fully agree to the needs of a unified collection framework in ActionScript. I will put my thoughts about realisation possibilities right away.

Requirements to an ActionScript collection framework

As with all frameworks, the collection framework combines sophisticated software with an active and helpful community. The following requirements are therefore slightly generic.

Software requirements

  • Slim and intuitive interfaces

    The framework consists only of the most necessary and commonly interfaces. Their definition is a challenging process and need not to be remade by each individual user. The framework integrates theoretical reflections, expert-knowledge and best practices and can be described as a general recommendation of approaches rather than as a ready-for-use library, which it is in the second place.

  • High degree of extensibility

    To be applicable also in custom circumstances, the framework must provide straightforward mechanisms to extend the built-in functionality. There are three ways of doing this.

    1. An interface architecture allows interchangeable implementations of the same type. The collection framework must provide interfaces to all public functionality such as collections, iterators or configuration objects.
    2. Inheritance let’s the developers benefit from available basic implementations. The latter must therefore live in a public or protected namespace.
    3. Configuration as the third mechanism is dedicated the customisation of framework internal workflows by passing configuration objects (inversion of control). The collection framework encapsulates algorithms such as for sorting or comparing and makes them that way replaceable. Particular implementations can furthermore offer their own parametrisation.
  • Ready-for-use implementations

    No framework would be accepted if it wouldn’t consists of a proper set of functionality applicable directly and without major preparation. The collection framework must contain base implemenations for all of the different collection types above.

  • Predictable and consistent behaviour

    A framework should smoothly handle special or corner cases such as the absence of data, type mismatchs or range errors. Those cases have to be described and tested sufficiently as well as how the framework is supposed to behave normally.

  • Good performance

    It’s obvious, that an unperformant framework is not much useful. The collection framework is targeted to the basis level of an application and bad performance here will be transferred to the overlying functionality. The performance of a collection depends on its structure and the algorithms modifying the structure. We have in ActionScript the high performing built-in Array and Dictionary, and in the most of the use cases it doesn’t get any faster than utilising them. A collection framework for ActionScript must reflect the special means and needs of the Flash platform.
    Performance has to be tested, compared and documented for each relevant function. Although performance is not the main goal of a collection framework, since performance and abstraction are a little bit contrary, it’s about to find the right balance between both poles.

Acceptance criteria

  • Appropriate licence

    First of all, a framework shouldn’t have much limitations in useage.

  • Easy utilisation

    Placing a new framework, you will need users for testing and feedback or getting convinced and hopefully spreading the word. For that, at least the installation of your framework should be exceedingly simple. Involving common software design concepts makes it relatively easy to get developers familiar with your framework. (In contrast, you cannot expect the user to spend much time to follow complicated and custom solutions.) This goes hand in hand with an intuitive and consistant naming of interfaces and methods, who should clearly express, what they are about and why they were invented.

  • Documentation, examples, tutorials

    Depending on the purpose of the software, either end user documentation (in running text) or source code documentation or even both are adequate, which is the case with a collection framework.
    There never can be enough examples and good tutorials. Missing manuals can disappoint beginners and cause them to leave before they had the chance to enjoy the benefits of the software.

  • Tested and stable software

    Existing test suites (and successful tests) are often the decisive factor for or against a third party software. A well-engineered framework ensures a high degree of stability. Subsequent and improved versions do not affect the base concepts and interfaces.

  • Active community

    Obviously some frameworks are widely accepted and gain users while others live a dire existance. As a rule of thumb: Active communities tend to become more active :-) It’s the good balance between excellent software, clever PR and the support of the right people, what makes a framework popular. Open source projects often limit themselves to the first point. Popular authorities can advance even immature software to a high distribution. Good documentation and promotion can compensate both weaknesses of the software and absent supporters.
    Besides the software itself, an active framework offers many possibilities to join and support the associated community.

    • Independent project page
    • Source code repository
    • Feedback, error and change request management
    • Discussion board
    • Donation box
  • High adoption rate

    There is no better recommendation as to have the software already being used in a large number of projects. A published list of applying projects provides confidence to new users and might give those projects a little advertisment.

I am now finished with the theoretical backgrounds of collections and collection frameworks. I will continue with a short review of some existing collection libraries for ActionScript.

Existing solutions

  • Flex collection package

    Flex collections are designed to seamlessly integrate Flex user interfaces with data models. Whenever data changes, the Flex component gets automatically updated and vice versa. Using Flex collections without Flex components does not make much sense. The Flex collections actually consist only of a single list interface with two different implementations.
    http://livedocs.adobe.com/flex/3/html/help.html?content=about_dataproviders_1.html

  • AS3 Data Structures For Game Developers

    The first choice (and best source) when it comes to bare algorithms and speed optimised data structures. Apparently the widest acceptance of all libraries. More a losely coupled set of distinctive implementations than a framework (doesn’t claim do be one). Great explanations and visual examples of data structures. Provided and maintained by the German Michael Baczynski.
    http://lab.polygonal.de/ds/

  • dpdk_os_flash

    A pretty comprehensive and shophisticated library with excellent source code documentation. Entirely unit tested. Includes special purpose functionality such as commands, specifications, folding and mapping or remote data management and appears therefore a little bit overengineered. Maps are not dealed with. Provided and maintained by a Dutch media agency as their company framework.
    http://www.dpdk.nl/opensource/the-collections-package

  • AS3-Collection-Framework

    A custom implementation of the Java interfaces. Provides various collections including a linked map. Very committed work. Could do with a little compression. Sometimes not using the best solution strategy. Developed by Tim Richter, Germany.
    http://www.addicted2flash.com/category/as3-collection-framework/

  • as3commons

    A port of the Java Collections Framework to ActionScript, probably not longer active. The ported versions performed noticeable slow in tests. Might be an effect of the heavy composite architecture.
    http://sourceforge.net/projects/as3commons/

  • ActionScript Foundry collection package

    The collections are part of the Foundry framework, which is targeted to simplify Flex application development. Is a port of the Java framework. I have not tested the collections, but after a short review of the code, I expect the collections performing similiar to those of the as3commons package.
    http://www.servebox.org/actionscript-foundry/actionscript-foundry-documentation/the-collections-framework/

  • VEGAS

    Actually I didn’t get what VEGAS is especially for and if there are people out of the developer group using this huge library. However, they have their own package consisting of numerous different collections. Contains a lot of secondary and project internal functionality. Poor documented but readable source code. Depends on other VEGAS packages. It’s a bit tricky to come through to the sources.
    http://www.ekameleon.net/blog/index.php?pages/VEGAS-AS3-AS2-SSAS-Opensource-Framework

  • Other libraries

    The Prada framework (nowadays Spring ActionScript) contains a map extension of the Flex collections. The same with Eric Feminella’s Open Source AS3 APIs.

Summary: We have quite a few solutions for exactly the same problem of how do we store and retrieve data in ActionScript client applications. There is obviously a need to work with collections rather than with native containers. Especially the general purpose frameworks rely on their custom collection implementations, who are often stuffed with internal functionality and are not likely to be used out of the box. Among the designated collection frameworks can be emphasized the dpdk_os_flash project because of the cleanest architecture and the AS3 Data Structures with the best algorithms.
None of the solutions reviewed match the most of the requirements prior proposed. However, the Dutch’s work is the most serious alternative and should be considered when planning to involve a third party collection library.

Thank you for reading these long explanations. I hope, I could bring some light into the matter and have made you hungry for working with data collections.



9 Comments

  1. rolf vreijdenberger

    3. April 2009

    Hi Jens,

    thanks for the great indepth review on why to use collections in the first place. This is what the mentioned frameworks mostly don’t explain, including ours. Obviously we all understand the need :)

    I think Michael Baczynski of polygonal.de has done an excellent job explaining a lot of implementation issues of collections in a visual way, we totally didn’t focus on that as there are excellent resources for that including his. We try to put up some implementation code or short examples but do assume a prior knowledge of datastructures.

    I do want to add an important thing concerning our framework at dpdk: the whole collections package is fully unittested for loads of edge cases. I do not have coverage statistics but the tests are very extensive.

    This means that the code is very reliable and it is also included in the framework so you can run it yourself. It saves us days of implementation time when refactoring (as in the case of the refactoring to cs4) and assures a high level of quality and reliability.

    As mentioned, there has been a lot of thought in the architecture, which is also partly based on the Java collections, to make it extensible and robust. Raw speed was not an issue. For speed, real speed speed, just go with Michael’s excellent stuff. Our benchmarks indicate some slight speed gains for certain api calls for our stuff, but mostly between 0 to 15% speed gain for his :) .

    In our work with the polygonal package, we ran into some structural issues concerning the api and some inconveniences or things we missed. For us it paid off to implement stuff ourselves.

    Our collections are integrated in the only fully comprehensive as3 flash remoting package with resultsets (ours ;) ), which is a killer feature for a company doing lot’s of data exchange with a backend.

    We obviously have more code in our package but only release a subpart. We will probably also release Graphs soon and some other datastructures related stuff.

    That said, it’s great that you provided this overview for people so they can choose. Collections are an easily overlooked issue in flash programming, but should be part of everyone’s toolkit.

    good luck with your implementations, I’ll definitely take a good look!

    cheers

  2. tearaway_Tea

    3. April 2009

    I hope it will be a really cool stuff.

    It will be very good if Adobe update Flash Player with such an usefull thing like supporting of comparing items in collections by IComparable (or IEquils etc.) interface.

    I’m so tired about using manual checking of objects by custom fields:

    var sourceItem : CustomType = new CustomType("test");
    
    var targetItem : CustomType;
    for each (var CustomType : item in items)
    {
    	if (item.name == sourceItem.name)
    	{
    		targetItem = item;
    		break;
    	}
    }
    
    // impossible
    items.removeItemAt(items.getItemIndex(sourceItem));
    
    // possible because we've found proper instance
    items.removeItemAt(items.getItemIndex(targetItem));
  3. Jens Struwe

    6. April 2009

    You would like to find an item that matches a certain criteria.
    In SQL does it a simple select: “SELECT * WHERE name = ‘customName’”.
    I can think of several possibilities to do so in ActionScript.
    I will deal with this in an example :-) Thanks for the note.

    Update: I got a link to another library, which I have added
    to the “review” section of this post (addicted2flash).

  4. PC Games » Архив блога » Why we need a collection framework in ActionScript

    7. April 2009

    [...] завести блог на своем сайте Russischer Bär. И его первый пост Why we need a collection framework in ActionScript говорит о довольно неплохом [...]

  5. tearaway_Tea

    7. April 2009

    I agree it is OK to make a method like getItemByCondition(“name = ‘test’”) but using the special interface is a much better solution. It is more OOP way =).

    Flex has a similar interface IUID which must cover the described issue (at least Help says that http://livedocs.adobe.com/flex/3/html/help.html?content=about_dataproviders_8.html) but it don’t work as I suppose.

    That is not working:

    [Bindable]
    public class Entry implements IUID
    {
    	public var name : String;
    		
    	public function get uid() : String
    	{
    		return name + "Entry";
    	}
    
    	public function set uid(value : String) : void
    	{
    	}
    
    	public function Entry(name : String)
    	{
    		this.name = name;
    	}
    }
    
    function main() : void {
    	var list : ArrayCollection = new ArrayCollection();
    				
    	var entry1 : Entry = new Entry("name1");
    	var entry2 : Entry = new Entry("name2");
    	var entry3 : Entry = new Entry("name1");
    				
    	list.addItem(entry1);
    	list.addItem(entry2);
    	
    	trace(list.getItemIndex(entry1));
    	trace(list.getItemIndex(entry2));
    	trace(list.getItemIndex(entry3));
    }

    Outputs:

    0
    1
    -1

  6. rolf vreijdenberger

    15. April 2009

    hi tearaway_tea
    selecting via a criterium is exactly what specifications are for.
    we implemented those in our framework at http://www.dpdk.nl/opensource.
    It’s a pattern based solution by martin fowler and eric evans, both very big names in the design pattern and OOP community.

    our implementation can be found in the website, and there is a tutorial about it right here: http://www.dpdk.nl/opensource/specification-pattern-for-selection-on-lists

    also, we just released a HashMap (unittested) and a full suite of Graph related stuff (unittested) which I might say is probably the best one out there in terms of algorithms, stability, interface and possibilities :)

    check it out

  7. Tweets that mention Why we need a collection framework in ActionScript at Russischer Bär Project Blog -- Topsy.com

    1. Mai 2010

    [...] This post was mentioned on Twitter by JuwalBose and Vipin Chandran, AS3hash. AS3hash said: RT @flashchemist: Why we need a collection framework in ActionScript – http://bit.ly/9LMvwb #as3 #flash #FlashDev [...]

  8. Kartikey

    17. Juni 2011

    Hi!

    Do you have a book idea on “open source flash and actionscript libraries” ehich seems promising enough?

    Please submit your idea here: http://www.google.com/moderator/#16/e=8e0cc

    Thanks

  9. Sexy Games

    20. Juli 2011

    We really need a collection framework.

Leave a Comment

You have a question or have experienced an issue? Please post it in the forum: http://sibirjak.tenderapp.com/ in order to make the discussion available at a more central place.