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::ContextLessSummary for UndoMapKey {
 34    fn zero() -> Self {
 35        Default::default()
 36    }
 37
 38    fn add_summary(&mut self, summary: &Self) {
 39        *self = cmp::max(*self, *summary);
 40    }
 41}
 42
 43#[derive(Clone, Default)]
 44pub struct UndoMap(SumTree<UndoMapEntry>);
 45
 46impl UndoMap {
 47    pub fn insert(&mut self, undo: &UndoOperation) {
 48        let edits = undo
 49            .counts
 50            .iter()
 51            .map(|(edit_id, count)| {
 52                sum_tree::Edit::Insert(UndoMapEntry {
 53                    key: UndoMapKey {
 54                        edit_id: *edit_id,
 55                        undo_id: undo.timestamp,
 56                    },
 57                    undo_count: *count,
 58                })
 59            })
 60            .collect::<Vec<_>>();
 61        self.0.edit(edits, ());
 62    }
 63
 64    pub fn is_undone(&self, edit_id: clock::Lamport) -> bool {
 65        self.undo_count(edit_id) % 2 == 1
 66    }
 67    pub fn was_undone(&self, edit_id: clock::Lamport, version: &clock::Global) -> bool {
 68        let mut cursor = self.0.cursor::<UndoMapKey>(());
 69        cursor.seek(
 70            &UndoMapKey {
 71                edit_id,
 72                undo_id: Default::default(),
 73            },
 74            Bias::Left,
 75        );
 76
 77        let mut undo_count = 0;
 78        for entry in cursor {
 79            if entry.key.edit_id != edit_id {
 80                break;
 81            }
 82
 83            if version.observed(entry.key.undo_id) {
 84                undo_count = cmp::max(undo_count, entry.undo_count);
 85            }
 86        }
 87
 88        undo_count % 2 == 1
 89    }
 90
 91    pub fn undo_count(&self, edit_id: clock::Lamport) -> u32 {
 92        let mut cursor = self.0.cursor::<UndoMapKey>(());
 93        cursor.seek(
 94            &UndoMapKey {
 95                edit_id,
 96                undo_id: Default::default(),
 97            },
 98            Bias::Left,
 99        );
100
101        let mut undo_count = 0;
102        for entry in cursor {
103            if entry.key.edit_id != edit_id {
104                break;
105            }
106
107            undo_count = cmp::max(undo_count, entry.undo_count);
108        }
109        undo_count
110    }
111}