MultiKey Dictionary

While developing some kind of event monitoring Manager class i come across a problem of too many Object used : Each IEventDispatcher source can dispatch multiple eventNames, each eventName can have several function attached to it. The popular approach is using nested Dictionary/Object as the main data structure :

_sourceDict : Dictionary; /* map IEventDispatchers to _eventObjects */
_eventObject : Object; /* map eventName to _handlerDict */
_handlerDict : Dictionary; /* map handler to its params */

For faster check and overwrite the existed _handler for a specific source and eventName we need to use a Dictionary for _handlerDict instead of an Array, and by the way, add support for user parameters.

This data structure of course will still work without any problem even though the code looks busy by nested properties access. We might also got slow down by looping through those nested structure. Let’s have a look through another implementation where we save multiple values as the key instead of only one.

Indexed Linked List

Indexed Linked List is an improved version of Single Linked List that enable random access (can only found on Array) and fast item splicing (can only found on Linked List). We can use it for prioritized queues where items often got inserted / removed at arbitrary positions. Some popular applications are loading queue manager (sort by priority), delayed tween list (sort by delay), or custom Event Dispatcher (addListeners with priority).

I. THE GENERAL IDEA :

We have a single linked list (to cut memory cost 30% compared to double linked list), every item has a {.next} pointer point to the next item in the list. Every item has a {.priority} property to be used as mandatory sort term, a {.time} stamp for secondary sort term, this way, every item is unique and can be compared to each other without equality worries.

Besides the normal linked list implementation we have another Array {_grid} to keep track of pivots items at some rough space {_gridSize}, that means for every roughly {_gridSize} items in the list we save an item into the {_grid}. This kind of indexing will enable binary search for position of any item in the list which means fast random access to items (fixed (and small) time to reach any item in the list). Of course, this won’t beat Array’s random access, but it’s fast enough for practical use !

onDataStructure();

One of the most common data structure in Flash is Array, which provides a fast way to construct a list of data items with compact memory cost. This data structure is working fine and rather fast, except for some operations, for example, insert / remove items randomly (splice) or pushing things to the beginning of the Arrays (unshift). Because of the compact memory implementation, all the existed items after the insert position will need to be migrated. With o(n) complexity, operated time goes up linearly with the number of items. And it’s just the same for Vector, although Vector is way faster than Array as there are no dense checking and converting between Dense Array & Hash Table (there are more reasons ? ). In short : Array is slowing down by items migration

A rather popular solution is using Linked List – either double or single. Linked list has ability to add and remove items very fast at an arbitrary position as no item is being migrated. Double linked list cost more memory (~ 1.5x ) and a bit slower than single Linked List (which, consume 2x more memory than Array) but it allows traversing in both direction. For some operations, the doubles run faster (~ 2x faster) than single ones. But as we won’t have random access to items by numeric indexes like Arrays, it’s really slow if we need to skip forward / backward to get to some random position. In short : Linked List is slowed down by skipping to specific position