Specific Implementations

Specific implementations are methods for taking certain data structures and converting them into retroactive data structures, using specific strategies outlined in Demaine et al 2007 in order to optimize for speed.

Queue

A queue permits enqueue and dequeue operations on an ordered collection of data.

Partial retroactivity: O(1).

Creating a partially retroactive queue involves storing a doubly-linked list of items, inserting whenever an enqueue is made, but not deleting any old data when a dequeue is made – because that dequeue operation might be deleted later, for example.

Instead, two pointers, F and B, point to the items at the front and back of the queue when t=0; these two pointers are moved according to the proper logic whenever an enqueue or dequeue is retroactively inserted or removed. Then, querying is as simple as looking up those two pointers.

Unlike the other retroactive data structures, this data structure has a few quirks. First, the time at which a retroactive operation is inserted or deleted cannot be specified by an integer number: it must instead by specified by a pointer to a reference operation which occurs immediately after the time when the operation is to be retroactively inserted. Inserting an operation must therefore return a pointer to that operation, in case the operation is used later as a time reference. The pointer is used to instantly navigate to therelevant part of the doubly-linked list in O(1) time. One possibility is that the data structure could be converted to a form which uses integer times, with a binary tree on top of the doubly-linked list; to insert or remove an operation would then be O(log m), instead. A second quirk of the interface is that it does not have a single query() method: instead, there are two possible queries that can be made – front() and back().

Full retroactivity, O(log m): See Deque.

A better fully retroactive solution exists, which is O(log m) but O(1) for present-time operations. This requires an implementation of order-statistic trees (Cormen et al, 2001).

Stack

Partial retroactivity, O(log m): See Deque.

Full retroactivity, O(log m): See Deque.

Deque

Partial retroactivity, O(log m): Implied by fully retroactive solution.

Full retroactivity, O(log m). Requires an implementation of modified (a,b)-trees.

Union-Find

Partial retroactivity, O(log m): Implied by fully retroactive solution.

Full retroactivity, O(log m). Requires an implementation of link-cut trees.

Priority Queue

Partial retroactivity, O(log m). Requires an implementation of modified (a,b)-trees.

Full retroactivity: Use the General Transformation from partial to full.

Searchable, Dynamic Partial Sums

A searchable, dynamic partial sums (SDPS) data structure stores a sequence of numbers, and permits appending numbers at the end, computing the overall sum, or searching for the earliest point at which the sum exceeds a given threshold.

This data structure has commutative, invertible operations – allowing partial retroactivity to be achieved with no overhead.

Partial retroactivity: O(1).

Since operations on the “Searchable, Dynamic Partial Sums” data structure are commutative and invertible, partial retroactivity is easy: to insert an operation, perform it; to delete an operation, perform its inverse.

Some special wrapping was required to implement this in Python: it needs to be possible to determine the inverse of any operation. To fix this, the method PartiallyRetroactiveSDPS.update(i,c) was modified so that it returns a function to use as an operation to pass to insert and delete; this function remembers c as an attribute, enabling delete to apply the inverse operation, update(i,-c).

It would be difficult to create a wrapper that works for all data structures with commutative, invertible operations, because of this same hurdle: determining the inverse of an arbitrary Python function. When the functions are defined beforehand, however, as with this implementation of partially-retroactive searchable dynamic sums, the task is more tractable.

Full retroactivity: Use the General Transformation from partial to full.