history_tree/
lib.rs

1//! A persistent history tree for undo/redo.
2//!
3//! This data structure makes programming of editors easier when the editor environment
4//! is open ended, such as editors that are hosting other editors.
5//! It makes it possible to create game engines where scripted components
6//! are interdependent and basis for new editor functionality.
7//!
8//! A persistent data structure is one that stores immutable data efficiently.
9//! This allows a programming pattern that does not rely on undoing
10//! and redoing by mutating a data structure.
11//! Instead, you store data in blocks that is referenced by index in the history tree.
12//!
13//! The relations between the blocks is controlled by reading out child relations.
14//! Data blocks can reference earlier data blocks safely.
15//! The history tree does not need to know how these references are represented,
16//! because the consistency is guaranteed by replicating the same state of earlier trees.
17//!
18//! This history tree stores records that points to previous version and parent.
19//! The tree is a function of these records plus a cursor.
20//! The cursor determine which records are active.
21//!
22//! When a record is pointed to by a new active record, it gets overriden.
23//! A record is considered child of a parent when it points to the parent or any previous version.
24//!
25//! `.add`/`.change`/`.delete` are `O(1)` operations.
26//!
27//! `.children` is `O(N * M)` operation where `N` is number of parent versions and `M` is records.
28//!
29//! To make `.children` fast, records are stored with only indices.
30
31#![deny(missing_docs)]
32
33/// Stores information about a node relation.
34#[derive(Clone, Debug, PartialEq, Eq)]
35pub struct Record {
36    /// Previous version.
37    pub prev: usize,
38    /// Parent id.
39    pub parent: usize,
40    /// Removes previous nodes.
41    pub remove: bool,
42}
43
44/// Stores information about history tree relations.
45#[derive(Clone, Debug, PartialEq, Eq)]
46pub struct HistoryTree {
47    /// Stores records.
48    pub records: Vec<Record>,
49    /// History cursor.
50    /// Points to an index of records where all previous changes
51    /// are active, and those after are inactive.
52    /// When set to `None`, it is assumed to point to the latest version.
53    pub cursor: Option<usize>,
54}
55
56impl HistoryTree {
57    /// Creates a new history tree.
58    pub fn new() -> HistoryTree {
59        HistoryTree {
60            records: vec![Record {
61                prev: 0, // Points back to itself.
62                parent: 0, // Points back to itself.
63                remove: false,
64            }],
65            cursor: None,
66        }
67    }
68
69    /// Gets the root.
70    pub fn root(&self) -> usize {0}
71
72    /// Gets the cursor.
73    pub fn cursor(&self) -> usize {
74        self.cursor.unwrap_or(self.records.len() - 1)
75    }
76
77    /// Add new node.
78    pub fn add(&mut self, parent: usize) -> usize {
79        let cursor = self.cursor();
80        self.records.truncate(cursor + 1);
81        self.cursor = None;
82
83        let n = self.records.len();
84        self.records.push(Record {
85            prev: n, // Points back to itself.
86            parent: parent,
87            remove: false,
88        });
89        n
90    }
91
92    /// Change node.
93    pub fn change(&mut self, node: &mut usize) {
94        let cursor = self.cursor();
95        self.records.truncate(cursor + 1);
96        self.cursor = None;
97
98        let n = self.records.len();
99        let parent = self.records[*node].parent;
100        self.records.push(Record {
101            prev: *node,
102            parent: parent,
103            remove: false,
104        });
105        *node = n
106    }
107
108    /// Delete node.
109    pub fn delete(&mut self, node: usize) {
110        let cursor = self.cursor();
111        self.records.truncate(cursor + 1);
112        self.cursor = None;
113
114        let parent = self.records[node].parent;
115        self.records.push(Record {
116            prev: node,
117            parent: parent,
118            remove: true,
119        });
120    }
121
122    /// Gets the names of children.
123    pub fn children(&self, parent: usize) -> Vec<usize> {
124        let cursor = self.cursor.unwrap_or(self.records.len() - 1);
125        if cursor < parent {return vec![];}
126
127        let nodes: Vec<usize> = self.records[1..cursor + 1].iter()
128            .enumerate()
129            .filter(|&(_, r)| {
130                    let mut node = parent;
131                    loop {
132                        if r.parent == node {return true;}
133                        let new_node = self.records[node].prev;
134                        if new_node == node {break;}
135                        node = new_node
136                    }
137                    false
138                })
139            .map(|(i, _)| i + 1)
140            .collect();
141
142        // Remove the older versions.
143        let mut new: Vec<bool> = vec![true; nodes.len()];
144        for i in 0..nodes.len() {
145            let a = nodes[i];
146            if self.records[a].remove {new[i] = false;}
147            let b = self.records[a].prev;
148            if b == a  {continue;}
149            if let Ok(j) = nodes.binary_search(&b) {
150                new[j] = false;
151            }
152        }
153        nodes.into_iter()
154            .enumerate()
155            .filter(|&(i, _)| new[i])
156            .map(|(_, id)| id)
157            .collect()
158    }
159
160    /// Goes back one step in history.
161    pub fn undo(&mut self) {
162        self.cursor = if let Some(index) = self.cursor {
163            if index > 0 {Some(index - 1)}
164            else if self.records.len() == 0 {None}
165            else {Some(0)}
166        } else {
167            if self.records.len() == 0 {None}
168            else {Some(self.records.len() - 2)}
169        };
170    }
171
172    /// Goes forward one step in history.
173    pub fn redo(&mut self) {
174        self.cursor = if let Some(index) = self.cursor {
175            if index + 1 >= self.records.len() {None}
176            else {Some(index + 1)}
177        } else {
178            None
179        }
180    }
181
182    /// Prints relations to standard output.
183    /// This is used for debugging.
184    pub fn print(&self, parent: usize, tabs: u32) {
185        if tabs > 0 {
186            for _ in 0..tabs - 1 {print!("  ")}
187            print!("|-");
188        }
189        println!("{}", parent);
190        for &ch in &self.children(parent) {
191            self.print(ch, tabs + 1);
192        }
193    }
194}