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}