Skip to content

Instantly share code, notes, and snippets.

@wtholliday
Created July 9, 2019 18:48
Show Gist options
  • Save wtholliday/77b911e24f5f8f6180e83d7aff520614 to your computer and use it in GitHub Desktop.
Save wtholliday/77b911e24f5f8f6180e83d7aff520614 to your computer and use it in GitHub Desktop.
Exercise in graph data structure with undo/redo.
#[derive(Debug)]
struct Node { }
#[derive(Copy, Clone, Debug)]
struct Wire {
from: u32, // node index
to: u32, // node index
}
#[derive(Debug)]
struct Patch {
nodes : Vec<Node>,
wires : Vec<Wire>
}
impl Patch {
fn connect(&mut self, from: u32, to: u32, undos: &mut UndoStack) {
self.wires.push(Wire{from: from, to: to});
undos.push(Box::new(move |patch, undos| patch.disconnect(from, to, undos)))
}
fn disconnect(&mut self, from: u32, to: u32, undos: &mut UndoStack) {
self.wires.retain(|w| w.from != from || w.to != to);
undos.push(Box::new(move |patch, undos| patch.connect(from, to, undos)))
}
fn add_node(&mut self, index: u32, undos: &mut UndoStack) {
// Insert
self.nodes.insert(index as usize, Node{ });
// Update wires.
for w in &mut self.wires {
w.from += (w.from >= index) as u32;
w.to += (w.to >= index) as u32;
}
// Record a function to undo.
undos.push(Box::new(move |patch, undos| patch.remove_node(index, undos)))
}
fn remove_node(&mut self, node: u32, undos: &mut UndoStack) {
// Get all the wires we'll need to disconnect.
let mut to_disconnect = Vec::new();
{
for w in &self.wires {
if w.from == node || w.to == node {
to_disconnect.push(Wire{from: w.from, to: w.to});
}
}
}
for w in to_disconnect {
self.disconnect(w.from, w.to, undos);
}
// Update other wires.
{
for w in &mut self.wires {
w.from -= (w.from > node) as u32;
w.to -= (w.to > node) as u32;
}
}
// Remove the node.
self.nodes.remove(node as usize);
}
}
struct UndoStack {
undoing: bool,
undos : Vec< Box< Fn(&mut Patch, &mut UndoStack) -> () > >,
redos : Vec< Box< Fn(&mut Patch, &mut UndoStack) -> () > >
}
impl UndoStack {
fn undo(&mut self, patch: &mut Patch) {
self.undoing = true;
if let Some(top) = self.undos.pop() {
(*top)(patch, self);
}
self.undoing = false;
}
fn push(&mut self, f : Box< Fn(&mut Patch, &mut UndoStack) -> () >) {
if self.undoing {
self.redos.push(f)
} else {
self.undos.push(f)
}
}
}
fn main() {
let mut patch = Patch{ nodes: Vec::new(), wires: Vec::new() };
let mut undos = UndoStack{ undos: Vec::new(), redos: Vec::new(), undoing: false };
patch.add_node(0, &mut undos);
patch.add_node(0, &mut undos);
patch.connect(0, 1, &mut undos);
patch.connect(1, 1, &mut undos);
assert_eq!(patch.wires.len(), 2);
//print!("{:?}\n", patch);
undos.undo(&mut patch);
//print!("{:?}\n", patch);
assert_eq!(patch.wires.len(), 1);
assert_eq!(patch.wires[0].from, 0);
assert_eq!(patch.wires[0].to, 1);
patch.connect(1, 1, &mut undos);
patch.remove_node(0, &mut undos);
assert_eq!(patch.wires.len(), 1);
assert_eq!(patch.nodes.len(), 1);
assert_eq!(patch.wires[0].from, 0);
assert_eq!(patch.wires[0].to, 0);
patch.add_node(0, &mut undos);
assert_eq!(patch.wires[0].from, 1);
assert_eq!(patch.wires[0].to, 1);
undos.undo(&mut patch);
assert_eq!(patch.wires[0].from, 0);
assert_eq!(patch.wires[0].to, 0);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment