IODyn: Collections for Dynamic Input and Output

IODyn is collections library for programs that use Adapton, a general-purpose framework for incremental computing.

IODyn consists of collections for sequences, finite maps, sets and graphs.

Sequences

• Random Access Zipper (RAZ): Sequence as a zipper, with a cursor for local edits, local navigation, and global navigation (via an associated level tree representation)
• Level tree: Sequence as a balanced tree; efficient global navigation, e.g., to an offset, to either end (first or last), or based on user-defined navigation data.
• Stack (last in first out): push, pop

Finite Maps and Sets

• Skip list: put, get, remove

In progress

• Queue (first in first out): push, pop
• Trie (persistent sets): put, get, remove, union, intersect
• Directed graph: XXX
• Undirected graph: XXX

lib.rs:

A collection of incremental data structures with dynamic input and output.

Many of the structures have an exposed mutable head for fast updates, and an archive function to move the current head past a pointer, defining subsequences. This pointer is mutable, so that the changes can propagate to later computations.

Fold and Map type computations over a level tree or a raz tree will be memoized, such that rerunning the computation after a change will be much faster than running from scratch.

These collections are partially mutable and partially persistent (shared data). However, the authors have concentrated on incremental features, so partial sharing is not well implemented. Data archived without names will be fully persistent so that changes to cloned data will not affect the original. Data archived with names should be treated as a mutable structure, with changes to cloned data affecting the original. These affects will probably not be consistent. Editing a mutable structure within a namespace (adapton::engine::ns) should produce a version whose edits do not affect the original, but this has not been thoroughly tested.