An always-sorted collection with O(1) insertion and removal with Java reference-implementation use to sort object according to their Z-order in a game engine.

This idea (and the story that lead to it) was featured in a Gamasutra article. The full reference implementation is on a GitHub project.

[...] 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 a game, but still must be kept in order for scheduling, we developed anO(1) always-sorted collection, based on the Linux solution.

Let's review the requirements from our collection:

  • Collection should be traversable in-order in both directions at 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

Let's 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:

public interface ZSortable {
    public int getZOrder();
    public Unlinkable getCurrentLink();
    public void setCurrentLink(Unlinkable currentLink);
}

Optionally, links can be held in a hashtable under a key, to allow an object to be managed by many collections. 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:

public interface Unlinkable {
    public ZLinkedList getOwner();
}

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:

public interface ZLinkedList extends Iterable<ZSortable> {
    public Unlinkable append(ZSortable object);
public void unlink(Unlinkable link); public Iterator<ZSortable> iterator(); public Iterator<ZSortable> reverseIterator(); }

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

public class ZCollection implements Iterable<ZSortable> {

    private final ZLinkedList[] buckets =
        new ZLinkedList[MAX_Z_LEVEL + 1];

    public ZCollection() {
        for (int i = 0; i <= MAX_Z_LEVEL; ++i) {
            buckets[i] = new ZLinkedListImpl();
        }
    }

    public void add(ZSortable object) { /* ... */ }
    public void remove(ZSortable object) { /* ... */ }
    public void change(ZSortable object) { /* ... */ }

    public Iterator<ZSortable> iterator();
    public Iterator<ZSortable> reverseIterator();
}

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:

// member of ZCollection
public void add(ZSortable object) {
    // ... check that 'object' isn't null ...
    int zOrder = object.getZOrder();
    // ... assert that: zOrder >= 0 and zOrder <= MAX_Z_LEVEL ...
    Unlinkable link = buckets[zOrder].append(object);
    object.setCurrentLink(link);
}

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:

// member of ZCollection
public void remove(ZSortable object) {
    // ... check that 'object' isn't null ...
    // ... check that 'object' has a valid link ...
    Unlinkable link = object.getCurrentLink();
link.getOwner().unlink(link); object.setCurrentLink(null); }

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:

// member of ZCollection
public void change(ZSortable object) {
    // ... check that 'object' isn't null ...
    // ... check that 'object' has a valid link ...
    remove(object);
    add(object);
}

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.

Print