mod builder;
mod checkpoint;
mod display;
mod queue;
pub use builder::Builder;
pub use checkpoint::Checkpoint;
pub use display::Display;
pub use queue::Queue;
use crate::socket::{Event, Slot};
use crate::{At, Edit, Entry, Record};
use alloc::collections::{BTreeMap, VecDeque};
use alloc::string::{String, ToString};
use alloc::vec::Vec;
#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Clone, Debug)]
pub struct History<E, S = ()> {
root: usize,
next: usize,
saved: Option<At>,
pub(crate) record: Record<E, S>,
branches: BTreeMap<usize, Branch<E>>,
}
impl<E> History<E> {
pub fn new() -> History<E> {
History::builder().build()
}
}
impl<E, S> History<E, S> {
pub fn builder() -> Builder<E, S> {
Builder::default()
}
pub fn reserve(&mut self, additional: usize) {
self.record.reserve(additional);
}
pub fn capacity(&self) -> usize {
self.record.capacity()
}
pub fn shrink_to_fit(&mut self) {
self.record.shrink_to_fit();
}
pub fn len(&self) -> usize {
self.record.len()
}
pub fn is_empty(&self) -> bool {
self.record.is_empty()
}
pub fn limit(&self) -> usize {
self.record.limit()
}
pub fn connect(&mut self, slot: S) -> Option<S> {
self.record.connect(slot)
}
pub fn disconnect(&mut self) -> Option<S> {
self.record.disconnect()
}
pub fn is_saved(&self) -> bool {
self.record.is_saved()
}
pub fn can_undo(&self) -> bool {
self.record.can_undo()
}
pub fn can_redo(&self) -> bool {
self.record.can_redo()
}
pub fn head(&self) -> At {
At::new(self.root, self.record.index)
}
pub fn display(&self) -> Display<E, S> {
Display::from(self)
}
pub fn edits(&self) -> impl Iterator<Item = &E> {
self.record.edits()
}
pub fn queue(&mut self) -> Queue<E, S> {
Queue::from(self)
}
pub fn checkpoint(&mut self) -> Checkpoint<E, S> {
Checkpoint::from(self)
}
}
impl<E: Edit, S: Slot> History<E, S> {
pub fn edit(&mut self, target: &mut E::Target, edit: E) -> E::Output {
let head = self.head();
let saved = self.record.saved.filter(|&saved| saved > head.index);
let (output, merged, tail) = self.record.edit_and_push(target, edit.into());
if !merged && head.index == self.record.index {
let root = self.root;
self.rm_child(root, 0);
self.branches
.values_mut()
.filter(|branch| branch.parent.root == root)
.for_each(|branch| branch.parent.index -= 1);
}
if !tail.is_empty() {
let new = self.next;
self.next += 1;
self.branches
.insert(head.root, Branch::new(new, head.index, tail));
self.set_root(new, head.index, saved);
}
output
}
pub fn undo(&mut self, target: &mut E::Target) -> Option<E::Output> {
self.record.undo(target)
}
pub fn redo(&mut self, target: &mut E::Target) -> Option<E::Output> {
self.record.redo(target)
}
pub fn set_saved(&mut self, saved: bool) {
self.saved = None;
self.record.set_saved(saved);
}
pub fn clear(&mut self) {
self.root = 0;
self.next = 1;
self.saved = None;
self.record.clear();
self.branches.clear();
}
pub(crate) fn jump_to(&mut self, root: usize) {
let mut branch = self.branches.remove(&root).unwrap();
debug_assert_eq!(branch.parent, self.head());
let index = self.record.index;
let saved = self.record.saved.filter(|&saved| saved > index);
let tail = self.record.entries.split_off(index);
self.record.entries.append(&mut branch.entries);
self.branches
.insert(self.root, Branch::new(root, index, tail));
self.set_root(root, index, saved);
}
fn set_root(&mut self, root: usize, index: usize, saved: Option<usize>) {
let old = self.root;
self.root = root;
debug_assert_ne!(old, root);
self.branches
.values_mut()
.filter(|branch| branch.parent.root == old && branch.parent.index <= index)
.for_each(|branch| branch.parent.root = root);
match (self.record.saved, saved, self.saved) {
(Some(_), None, None) | (None, None, Some(_)) => self.swap_saved(root, old, index),
(None, Some(_), None) => {
self.record.saved = saved;
self.swap_saved(old, root, index);
}
(None, None, None) => (),
_ => unreachable!(),
}
}
fn swap_saved(&mut self, old: usize, new: usize, index: usize) {
debug_assert_ne!(old, new);
if let Some(At { index: saved, .. }) =
self.saved.filter(|at| at.root == new && at.index <= index)
{
self.saved = None;
self.record.saved = Some(saved);
self.record.socket.emit(|| Event::Saved(true));
} else if let Some(saved) = self.record.saved {
self.saved = Some(At::new(old, saved));
self.record.saved = None;
self.record.socket.emit(|| Event::Saved(false));
}
}
fn rm_child(&mut self, branch: usize, index: usize) {
let mut dead: Vec<_> = self
.branches
.iter()
.filter(|&(_, child)| child.parent == At::new(branch, index))
.map(|(&id, _)| id)
.collect();
while let Some(parent) = dead.pop() {
self.branches.remove(&parent).unwrap();
self.saved = self.saved.filter(|saved| saved.root != parent);
dead.extend(
self.branches
.iter()
.filter(|&(_, child)| child.parent.root == parent)
.map(|(&id, _)| id),
)
}
}
fn mk_path(&mut self, mut to: usize) -> Option<impl Iterator<Item = (usize, Branch<E>)>> {
debug_assert_ne!(self.root, to);
let mut dest = self.branches.remove(&to)?;
let mut i = dest.parent.root;
let mut path = alloc::vec![(to, dest)];
while i != self.root {
dest = self.branches.remove(&i).unwrap();
to = i;
i = dest.parent.root;
path.push((to, dest));
}
Some(path.into_iter().rev())
}
pub fn go_to(&mut self, target: &mut E::Target, at: At) -> Vec<E::Output> {
let root = self.root;
if root == at.root {
return self.record.go_to(target, at.index);
}
let mut outputs = Vec::new();
let Some(path) = self.mk_path(at.root) else {
return Vec::new();
};
for (new, branch) in path {
let o = self.record.go_to(target, branch.parent.index);
outputs.extend(o);
for entry in branch.entries {
let index = self.record.index;
let saved = self.record.saved.filter(|&saved| saved > index);
let (_, _, entries) = self.record.redo_and_push(target, entry);
if !entries.is_empty() {
self.branches
.insert(self.root, Branch::new(new, index, entries));
self.set_root(new, index, saved);
}
}
}
let o = self.record.go_to(target, at.index);
outputs.extend(o);
outputs
}
}
impl<E: ToString, S> History<E, S> {
pub fn undo_string(&self) -> Option<String> {
self.record.undo_string()
}
pub fn redo_string(&self) -> Option<String> {
self.record.redo_string()
}
}
impl<E> Default for History<E> {
fn default() -> History<E> {
History::new()
}
}
impl<E, S> From<Record<E, S>> for History<E, S> {
fn from(record: Record<E, S>) -> Self {
History {
root: 0,
next: 1,
saved: None,
record,
branches: BTreeMap::new(),
}
}
}
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Clone, Debug, Hash, Eq, PartialEq)]
pub(crate) struct Branch<E> {
pub(crate) parent: At,
pub(crate) entries: VecDeque<Entry<E>>,
}
impl<E> Branch<E> {
fn new(branch: usize, index: usize, entries: VecDeque<Entry<E>>) -> Branch<E> {
Branch {
parent: At::new(branch, index),
entries,
}
}
}
#[cfg(test)]
mod tests {
use crate::*;
#[test]
fn go_to() {
let mut target = String::new();
let mut history = History::new();
history.edit(&mut target, Add('a'));
history.edit(&mut target, Add('b'));
history.edit(&mut target, Add('c'));
history.edit(&mut target, Add('d'));
history.edit(&mut target, Add('e'));
assert_eq!(target, "abcde");
history.undo(&mut target).unwrap();
history.undo(&mut target).unwrap();
assert_eq!(target, "abc");
let abc = history.head();
history.edit(&mut target, Add('f'));
history.edit(&mut target, Add('g'));
assert_eq!(target, "abcfg");
let abcfg = history.head();
history.undo(&mut target).unwrap();
history.edit(&mut target, Add('h'));
history.edit(&mut target, Add('i'));
history.edit(&mut target, Add('j'));
assert_eq!(target, "abcfhij");
let abcfhij = history.head();
history.undo(&mut target).unwrap();
history.edit(&mut target, Add('k'));
assert_eq!(target, "abcfhik");
let abcfhik = history.head();
history.undo(&mut target).unwrap();
history.edit(&mut target, Add('l'));
assert_eq!(target, "abcfhil");
history.edit(&mut target, Add('m'));
assert_eq!(target, "abcfhilm");
let abcfhilm = history.head();
history.go_to(&mut target, At::new(abc.root, 2));
history.edit(&mut target, Add('n'));
history.edit(&mut target, Add('o'));
assert_eq!(target, "abno");
let abno = history.head();
history.undo(&mut target).unwrap();
history.edit(&mut target, Add('p'));
history.edit(&mut target, Add('q'));
assert_eq!(target, "abnpq");
let abnpq = history.head();
history.go_to(&mut target, abc);
assert_eq!(target, "abc");
history.go_to(&mut target, abcfg);
assert_eq!(target, "abcfg");
history.go_to(&mut target, abcfhij);
assert_eq!(target, "abcfhij");
history.go_to(&mut target, abcfhik);
assert_eq!(target, "abcfhik");
history.go_to(&mut target, abcfhilm);
assert_eq!(target, "abcfhilm");
history.go_to(&mut target, abno);
assert_eq!(target, "abno");
history.go_to(&mut target, abnpq);
assert_eq!(target, "abnpq");
}
}