piston-history_tree

Crates.iopiston-history_tree
lib.rspiston-history_tree
version0.1.0
sourcesrc
created_at2017-02-13 16:45:38.484038
updated_at2017-02-13 16:45:38.484038
descriptionA persistent history tree for undo/redo
homepagehttps://github.com/pistondevelopers/history_tree
repositoryhttps://github.com/pistondevelopers/history_tree.git
max_upload_size
id8500
size12,442
publish (github:pistondevelopers:publish)

documentation

README

history_tree

A persistent history tree for undo/redo

This data structure makes programming of editors easier when the editor environment is open ended, such as editors that are hosting other editors. It makes it possible to create game engines where scripted components are interdependent and basis for new editor functionality.

A persistent data structure is one that stores immutable data efficiently. This allows a programming pattern that does not rely on undoing and redoing by mutating a data structure. Instead, you store data in blocks that is referenced by index in the history tree.

The relations between the blocks is controlled by reading out child relations. Data blocks can reference earlier data blocks safely. The history tree does not need to know how these references are represented, because the consistency is guaranteed by replicating the same state of earlier trees.

This history tree stores records that points to previous version and parent. The tree is a function of these records plus a cursor. The cursor determine which records are active.

When a record is pointed to by a new active record, it gets overriden. A record is considered child of a parent when it points to the parent or any previous version.

.add/.change/.delete are O(1) operations.

.children is O(N * M) operation where N is number of parent versions and M is records.

To make .children fast, records are stored with only indices.

Commit count: 4

cargo fmt