Future Developments
Not all of the Specific Implementations have been written yet. Many of these require an implementation of the above basic building blocks before they can be constructed:
- Fully-Retroactive Deque
- Fully-Retroactive Union-Find
- Partially-Retroactive Priority Queue
Also not yet written: Tests for each implementation.
On Abstraction and Elegance
Initially, I wanted to be able to unify all data structures under a single mechanism for creating retroactive versions of them: for example, PartiallyRetroactive({'foo':3, 'bar':55})
or FullyRetroactive(PriorityQueue())
, so that the interface for using retroactivity would be simple. However, there are some issues that create inelegance:
- Most data structures only allow exactly one sort of query, accessible via
query()
, but some must allow more (for example, the Partially Retroactive Queue must permit querying the elements at the front and back of the queue). - Most data structures require a number,
tminus
, specifying how long ago to insert or delete an operation, but other data structures (again, Partially Retroactive Queue) require specifying this information with a pointer, instead. - Most data structures require operations to be functions which take a data structure as an input and return a data structure as output, but some (for example, Partially Retroactive SDPS) require a different paradigm.
For these reasons, unifying the Specific Implementations under a single abstraction would have required adding extra options, making them more difficult for the user. For this reason, the Specific Implementations are presented as-is.