An O(1) Always-sorted Collection

Although we released Jelly Jump without fixing the problem, we had to fix it for the next game.

Back when I was running Red Hat Linux 8 with kernel 2.4.18 (or something), I remember reading that the under-development Linux 2.6 had an all-new O(1) scheduler. The news about this scheduler was that it could schedule many tasks in constant-time complexity, no matter how loaded the system was. This scheduler held up till 2.6.23, when it was replaced by the O(log n) Completely Fair Scheduler.

What made this an O(1) scheduler was that the author, Ingo Molnar, choose not to store priority information in the tasks themselves and sort them in a collection according to their priority, but to store the task's priority information in the collection itself -- he created a different queue for each priority level, giving him direct access to the head of each queue.

Because the number of priority levels was predetermined, scanning all priority queues for insertion and dequeuing is done in constant time.

Since tasks behave almost erratically, much like objects in our games, but still must be kept in order for scheduling, we tried a new approach, based on the Linux solution.

Let's review the requirements from our collection:

• Collection should be traversable by order in both directions in no more than O(n)
• Objects with the same Z-order should be ordered by sub-order of last-Z-action-on-top
• Insertion, removal and changing of Z-order should be O(1)
• Memory complexity should be kept low
• All Z-order values are legal (including negative and non-integer values) -- for backward-compatibility reasons

Simplification

We'll start with a simpler case, and ignore the last requirement. We'll define an object's Z-order to be a natural, bounded number (say, between 0 and 100), where lower Z-order means an object is further back.

The idea is to have a "bucket" for every legal Z-order in an array, holding all objects that have that Z-order by order of insertion. We'll implement a "bucket" with a double-ended linked-list, which allows us an O(1) insertion of a new object to its tail, and traversal in-order in both directions:

Simple data-structure

Adding a new object to a Z-order bucket involves looking up the Z-order in the buckets array, and appending the object to the list's tail:

Addition of an object to a bucket

By appending the object to the tail of the list, we maintain sub-ordering by last-Z-order action (we chose back-to-front forward traversal direction)

Traversing the entire structure is trivial -- all we have to do is scan the objects in the first (or last) bucket, and move to the next (previous) bucket until there are no more buckets left.

However, we still have to address the removal of objects from a bucket (either when it is being destroyed, or moved to another bucket as its Z-order changes). To avoid having to scan the entire collection to find the location of the object's link in the bucket's list, we'll use an auxiliary field in the object itself - we're going to cache the current linked-list link holding the object in the bucket inside the sprite, allowing us O(1) access to it.

We're creating a back-reference from an object to its location in the bucket it is currently in:

Removal of an object from a bucket (blue arrow donates back-reference from object to linked-list link)

From here things look trivial. Since selecting a bucket is matter of array lookup by index, adding to the end of a linked list is O(1) and removing a link from a linked-list is also O(1) (given the link object itself), we can achieve an always-sorted collection with O(1) runtime for all the actions we need.

Let's examine how it's implemented. First, a game object will have to be able to report its Z-order, and hold the auxiliary link:

For the sake of abstraction, we're not holding the actual linked-list link class in the object, but hold it through an interface that allows us to remove the link from the list:

Next step is to implement the list that will hold a bucket's contents. Remember that it has to expose the link that holds an object for caching, so we can't use any Java built-in collection:

Now all we have to do is to create a bucket for each legal Z-order:

And by that we've written our basic data structure. Let's examine each action separately, and see how we make it an O(1) operation.

Object Creation

To add a new object to the collection, all we have to do is to append it to the end of the bucket of its current Z-order, and cache the link in the object. That will also ensure sub-order of same-Z objects:

Since this is a double-ended linked-list, appending to its tail is an O(1) action.

Destroying an Object

To remove an object from the Z-collection, all we have to do is unlink it from the bucket's list:

Since unlinking a link from a double-linked-list is an O(1) operation, and we have a direct access to the link, this is also the runtime complexity for removing an object from the collection.

Changing Z-order

Changing the Z-order of an object is as simple as removing it from the previous bucket, and adding it to the new one, just like before:

Note that we're not skipping the operation even if the object is moved to the same Z as its current Z - this is on purpose as we have to pop the object up to be above all the rest according to the engine's contract with the developer. Since we're only using O(1) operations, this is also an O(1) operation.

Traversing in Order

Traversing in order (either back-to-front or front-to-back) is trivial -- we traverse all the buckets in the desired order, and for each bucket we traverse its list in the desired order (for back-to-front we'll iterate normally, and for front-to-back we'll iterate in reverse on both buckets and bucket-lists).

Since advancing in a linked-list is an O(1) operation, traversing the entire collection is O(n).

Note: I've included only interface listings for things that are trivial to implement. For a full code listing, check out https://github.com/mominis/zorder and the SimpleZCollection class.