Fun with Time Travel

Implementing retroactive data structures in Python

6.851 Advanced Data Structures final project by Chelsea Voss, Spring 2014.

Implements algorithms for various types of retroactive data structures. Retroactive data structures allow operations to be 'retroactively' performed, affecting the history of the data structure.

Read the code at GitHub.

Read the documentation at Read The Docs.

A number of retroactive data structures were implemented, from general transformations that work for any series of operations on any data structures, to special cases that get improved efficiency for particular data structures. The result can easily be utilized within any Python application.

Note: In all runtimes listed here, r is a parameter describing how far back in the past retroactive operations are allowed to occur, and m is the total number of retroactive updates that are ever performed on a data structure.