1use crate::UndoOperation;
  2use std::cmp;
  3use sum_tree::{Bias, SumTree};
  4
  5#[derive(Copy, Clone, Debug)]
  6struct UndoMapEntry {
  7    key: UndoMapKey,
  8    undo_count: u32,
  9}
 10
 11impl sum_tree::Item for UndoMapEntry {
 12    type Summary = UndoMapKey;
 13
 14    fn summary(&self, _cx: &()) -> Self::Summary {
 15        self.key
 16    }
 17}
 18
 19impl sum_tree::KeyedItem for UndoMapEntry {
 20    type Key = UndoMapKey;
 21
 22    fn key(&self) -> Self::Key {
 23        self.key
 24    }
 25}
 26
 27#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
 28struct UndoMapKey {
 29    edit_id: clock::Lamport,
 30    undo_id: clock::Lamport,
 31}
 32
 33impl sum_tree::Summary for UndoMapKey {
 34    type Context = ();
 35
 36    fn zero(_cx: &Self::Context) -> Self {
 37        Default::default()
 38    }
 39
 40    fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
 41        *self = cmp::max(*self, *summary);
 42    }
 43}
 44
 45#[derive(Clone, Default)]
 46pub struct UndoMap(SumTree<UndoMapEntry>);
 47
 48impl UndoMap {
 49    pub fn insert(&mut self, undo: &UndoOperation) {
 50        let edits = undo
 51            .counts
 52            .iter()
 53            .map(|(edit_id, count)| {
 54                sum_tree::Edit::Insert(UndoMapEntry {
 55                    key: UndoMapKey {
 56                        edit_id: *edit_id,
 57                        undo_id: undo.timestamp,
 58                    },
 59                    undo_count: *count,
 60                })
 61            })
 62            .collect::<Vec<_>>();
 63        self.0.edit(edits, &());
 64    }
 65
 66    pub fn is_undone(&self, edit_id: clock::Lamport) -> bool {
 67        self.undo_count(edit_id) % 2 == 1
 68    }
 69    pub fn was_undone(&self, edit_id: clock::Lamport, version: &clock::Global) -> bool {
 70        let mut cursor = self.0.cursor::<UndoMapKey>(&());
 71        cursor.seek(
 72            &UndoMapKey {
 73                edit_id,
 74                undo_id: Default::default(),
 75            },
 76            Bias::Left,
 77            &(),
 78        );
 79
 80        let mut undo_count = 0;
 81        for entry in cursor {
 82            if entry.key.edit_id != edit_id {
 83                break;
 84            }
 85
 86            if version.observed(entry.key.undo_id) {
 87                undo_count = cmp::max(undo_count, entry.undo_count);
 88            }
 89        }
 90
 91        undo_count % 2 == 1
 92    }
 93
 94    pub fn undo_count(&self, edit_id: clock::Lamport) -> u32 {
 95        let mut cursor = self.0.cursor::<UndoMapKey>(&());
 96        cursor.seek(
 97            &UndoMapKey {
 98                edit_id,
 99                undo_id: Default::default(),
100            },
101            Bias::Left,
102            &(),
103        );
104
105        let mut undo_count = 0;
106        for entry in cursor {
107            if entry.key.edit_id != edit_id {
108                break;
109            }
110
111            undo_count = cmp::max(undo_count, entry.undo_count);
112        }
113        undo_count
114    }
115}