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