use self::UndoLog::*;
use std::mem;
use std::ops;
pub enum UndoLog<D: SnapshotVecDelegate> {
OpenSnapshot,
CommittedSnapshot,
NewElem(usize),
SetElem(usize, D::Value),
Other(D::Undo),
}
pub struct SnapshotVec<D: SnapshotVecDelegate> {
values: Vec<D::Value>,
undo_log: Vec<UndoLog<D>>,
}
pub struct Snapshot {
length: usize,
}
pub trait SnapshotVecDelegate {
type Value;
type Undo;
fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
}
impl<D: SnapshotVecDelegate> SnapshotVec<D> {
pub fn new() -> SnapshotVec<D> {
SnapshotVec {
values: Vec::new(),
undo_log: Vec::new(),
}
}
pub fn with_capacity(n: usize) -> SnapshotVec<D> {
SnapshotVec {
values: Vec::with_capacity(n),
undo_log: Vec::new(),
}
}
fn in_snapshot(&self) -> bool {
!self.undo_log.is_empty()
}
pub fn record(&mut self, action: D::Undo) {
if self.in_snapshot() {
self.undo_log.push(Other(action));
}
}
pub fn len(&self) -> usize {
self.values.len()
}
pub fn push(&mut self, elem: D::Value) -> usize {
let len = self.values.len();
self.values.push(elem);
if self.in_snapshot() {
self.undo_log.push(NewElem(len));
}
len
}
pub fn get(&self, index: usize) -> &D::Value {
&self.values[index]
}
pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
&mut self.values[index]
}
pub fn set(&mut self, index: usize, new_elem: D::Value) {
let old_elem = mem::replace(&mut self.values[index], new_elem);
if self.in_snapshot() {
self.undo_log.push(SetElem(index, old_elem));
}
}
pub fn start_snapshot(&mut self) -> Snapshot {
let length = self.undo_log.len();
self.undo_log.push(OpenSnapshot);
Snapshot { length: length }
}
pub fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[UndoLog<D>] {
&self.undo_log[snapshot.length..]
}
fn assert_open_snapshot(&self, snapshot: &Snapshot) {
assert!(self.undo_log.len() > snapshot.length);
assert!(match self.undo_log[snapshot.length] {
OpenSnapshot => true,
_ => false,
});
}
pub fn rollback_to(&mut self, snapshot: Snapshot) {
debug!("rollback_to({})", snapshot.length);
self.assert_open_snapshot(&snapshot);
while self.undo_log.len() > snapshot.length + 1 {
match self.undo_log.pop().unwrap() {
OpenSnapshot => {
panic!("Cannot rollback an uncommitted snapshot");
}
CommittedSnapshot => {
}
NewElem(i) => {
self.values.pop();
assert!(self.values.len() == i);
}
SetElem(i, v) => {
self.values[i] = v;
}
Other(u) => {
D::reverse(&mut self.values, u);
}
}
}
let v = self.undo_log.pop().unwrap();
assert!(match v {
OpenSnapshot => true,
_ => false,
});
assert!(self.undo_log.len() == snapshot.length);
}
pub fn commit(&mut self, snapshot: Snapshot) {
debug!("commit({})", snapshot.length);
self.assert_open_snapshot(&snapshot);
if snapshot.length == 0 {
self.undo_log.truncate(0);
} else {
self.undo_log[snapshot.length] = CommittedSnapshot;
}
}
}
impl<D: SnapshotVecDelegate> ops::Deref for SnapshotVec<D> {
type Target = [D::Value];
fn deref(&self) -> &[D::Value] {
&*self.values
}
}
impl<D: SnapshotVecDelegate> ops::DerefMut for SnapshotVec<D> {
fn deref_mut(&mut self) -> &mut [D::Value] {
&mut *self.values
}
}
impl<D: SnapshotVecDelegate> ops::Index<usize> for SnapshotVec<D> {
type Output = D::Value;
fn index(&self, index: usize) -> &D::Value {
self.get(index)
}
}
impl<D: SnapshotVecDelegate> ops::IndexMut<usize> for SnapshotVec<D> {
fn index_mut(&mut self, index: usize) -> &mut D::Value {
self.get_mut(index)
}
}
impl<D: SnapshotVecDelegate> Extend<D::Value> for SnapshotVec<D> {
fn extend<T>(&mut self, iterable: T) where T: IntoIterator<Item=D::Value> {
for item in iterable {
self.push(item);
}
}
}