1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

use crate::UndoOperation;
use std::cmp;
use sum_tree::{Bias, SumTree};

#[derive(Copy, Clone, Debug)]
struct UndoMapEntry {
    key: UndoMapKey,
    undo_count: u32,
}

impl sum_tree::Item for UndoMapEntry {
    type Summary = UndoMapKey;

    fn summary(&self) -> Self::Summary {
        self.key
    }
}

impl sum_tree::KeyedItem for UndoMapEntry {
    type Key = UndoMapKey;

    fn key(&self) -> Self::Key {
        self.key
    }
}

#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
struct UndoMapKey {
    edit_id: clock::Lamport,
    undo_id: clock::Lamport,
}

impl sum_tree::Summary for UndoMapKey {
    type Context = ();

    fn add_summary(&mut self, summary: &Self, _: &Self::Context) {
        *self = cmp::max(*self, *summary);
    }
}

#[derive(Clone, Default)]
pub struct UndoMap(SumTree<UndoMapEntry>);

impl UndoMap {
    pub fn insert(&mut self, undo: &UndoOperation) {
        let edits = undo
            .counts
            .iter()
            .map(|(edit_id, count)| {
                sum_tree::Edit::Insert(UndoMapEntry {
                    key: UndoMapKey {
                        edit_id: *edit_id,
                        undo_id: undo.timestamp,
                    },
                    undo_count: *count,
                })
            })
            .collect::<Vec<_>>();
        self.0.edit(edits, &());
    }

    pub fn is_undone(&self, edit_id: clock::Lamport) -> bool {
        self.undo_count(edit_id) % 2 == 1
    }

    pub fn was_undone(&self, edit_id: clock::Lamport, version: &clock::Global) -> bool {
        let mut cursor = self.0.cursor::<UndoMapKey>();
        cursor.seek(
            &UndoMapKey {
                edit_id,
                undo_id: Default::default(),
            },
            Bias::Left,
            &(),
        );

        let mut undo_count = 0;
        for entry in cursor {
            if entry.key.edit_id != edit_id {
                break;
            }

            if version.observed(entry.key.undo_id) {
                undo_count = cmp::max(undo_count, entry.undo_count);
            }
        }

        undo_count % 2 == 1
    }

    pub fn undo_count(&self, edit_id: clock::Lamport) -> u32 {
        let mut cursor = self.0.cursor::<UndoMapKey>();
        cursor.seek(
            &UndoMapKey {
                edit_id,
                undo_id: Default::default(),
            },
            Bias::Left,
            &(),
        );

        let mut undo_count = 0;
        for entry in cursor {
            if entry.key.edit_id != edit_id {
                break;
            }

            undo_count = cmp::max(undo_count, entry.undo_count);
        }
        undo_count
    }
}