Experilous

A few weeks ago I introduced you to what I felt was an impressive little data structure that can provide constant time complexity for the standard operations, stores data contiguously, and provides stable handles that remain valid across all operations other than removing the referenced items themselves.  Today I want to extend the basic data structure with some additional functionality which will be focused on iterating over the contiguous items in order.  While iterating, we may wish to modify the collection as we go (such as conditionally removing some items).  We may also wish to rearrange the items so that a simple linear traversal will also happen to hit the items in a particular order (such as sorting 3D objects from front to back to take advantage of a depth buffer and reduce fill-rate). (more…)

I recently ran across a couple of blog articles describing a data structure that provides a set of properties that I often am seeking:

  1. Contiguous data storage, good for linear iteration and maximizing cache utilization
  2. Constant-time insertion, deletion, and relocation of elements
  3. Stable external references to elements regardless of internal relocation
  4. Constant-time look-up from external references without hashing

(The two articles were from the makers of the Molecule Engine and the BitSquid engine, respectively.)

Fascinated by data structures and algorithms in general, and lured by the appeal of these properties, I set out to study the concept and implement my own version.  It’s quite simple to implement in a basic form to achieve the above four properties, and can easily be extended to acquire some additional behaviors at the cost of additional memory or extra operations.  In this first article, I’ll walk through the basic concept, as well as a simple implementation in JavaScript.  Later articles will explore some of the possible extensions. (more…)