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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
use std::collections::VecDeque;

#[derive(Clone, Debug, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
pub struct Settings {
    /// Maximum number of undos.
    /// If your state is resource intensive, you should keep this low.
    ///
    /// Default: `100`
    pub max_undos: usize,

    /// When that state hasn't changed for this many seconds,
    /// create a new undo point (if one is needed).
    ///
    /// Default value: `1.0` seconds.
    pub stable_time: f32,

    /// If the state is changing so often that we never get to `stable_time`,
    /// then still create a save point every `auto_save_interval` seconds,
    /// so we have something to undo to.
    ///
    /// Default value: `30` seconds.
    pub auto_save_interval: f32,
}

impl Default for Settings {
    fn default() -> Self {
        Self {
            max_undos: 100,
            stable_time: 1.0,
            auto_save_interval: 30.0,
        }
    }
}

/// Automatic undo system.
///
/// Every frame you feed it the most recent state.
/// The [`Undoer`] compares it with the latest undo point
/// and if there is a change it may create a new undo point.
///
/// [`Undoer`] follows two simple rules:
///
/// 1) If the state has changed since the latest undo point, but has
///    remained stable for `stable_time` seconds, an new undo point is created.
/// 2) If the state does not stabilize within `auto_save_interval` seconds, an undo point is created.
///
/// Rule 1) will make sure an undo point is not created until you _stop_ dragging that slider.
/// Rule 2) will make sure that you will get some undo points even if you are constantly changing the state.
#[derive(Clone, Default)]
#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
pub struct Undoer<State> {
    settings: Settings,

    /// New undoes are added to the back.
    /// Two adjacent undo points are never equal.
    /// The latest undo point may (often) be the current state.
    undos: VecDeque<State>,

    /// Stores redos immediately after a sequence of undos.
    /// Gets cleared every time the state changes.
    /// Does not need to be a deque, because there can only be up to undos.len() redos,
    /// which is already limited to settings.max_undos.
    redos: Vec<State>,

    #[cfg_attr(feature = "serde", serde(skip))]
    flux: Option<Flux<State>>,
}

impl<State> std::fmt::Debug for Undoer<State> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let Self { undos, redos, .. } = self;
        f.debug_struct("Undoer")
            .field("undo count", &undos.len())
            .field("redo count", &redos.len())
            .finish()
    }
}

/// Represents how the current state is changing
#[derive(Clone)]
struct Flux<State> {
    start_time: f64,
    latest_change_time: f64,
    latest_state: State,
}

impl<State> Undoer<State>
where
    State: Clone + PartialEq,
{
    /// Do we have an undo point different from the given state?
    pub fn has_undo(&self, current_state: &State) -> bool {
        match self.undos.len() {
            0 => false,
            1 => self.undos.back() != Some(current_state),
            _ => true,
        }
    }

    pub fn has_redo(&self, current_state: &State) -> bool {
        !self.redos.is_empty() && self.undos.back() == Some(current_state)
    }

    /// Return true if the state is currently changing
    pub fn is_in_flux(&self) -> bool {
        self.flux.is_some()
    }

    pub fn undo(&mut self, current_state: &State) -> Option<&State> {
        if self.has_undo(current_state) {
            self.flux = None;

            if self.undos.back() == Some(current_state) {
                self.redos.push(self.undos.pop_back().unwrap());
            } else {
                self.redos.push(current_state.clone());
            }

            // Note: we keep the undo point intact.
            self.undos.back()
        } else {
            None
        }
    }

    pub fn redo(&mut self, current_state: &State) -> Option<&State> {
        if !self.undos.is_empty() && self.undos.back() != Some(current_state) {
            // state changed since the last undo, redos should be cleared.
            self.redos.clear();
            None
        } else if let Some(state) = self.redos.pop() {
            self.undos.push_back(state);
            self.undos.back()
        } else {
            None
        }
    }

    /// Add an undo point if, and only if, there has been a change since the latest undo point.
    pub fn add_undo(&mut self, current_state: &State) {
        if self.undos.back() != Some(current_state) {
            self.undos.push_back(current_state.clone());
        }
        while self.undos.len() > self.settings.max_undos {
            self.undos.pop_front();
        }
        self.flux = None;
    }

    /// Call this as often as you want (e.g. every frame)
    /// and [`Undoer`] will determine if a new undo point should be created.
    ///
    /// * `current_time`: current time in seconds.
    pub fn feed_state(&mut self, current_time: f64, current_state: &State) {
        match self.undos.back() {
            None => {
                // First time feed_state is called.
                // always create an undo point:
                self.add_undo(current_state);
            }
            Some(latest_undo) => {
                if latest_undo == current_state {
                    self.flux = None;
                } else {
                    self.redos.clear();

                    match self.flux.as_mut() {
                        None => {
                            self.flux = Some(Flux {
                                start_time: current_time,
                                latest_change_time: current_time,
                                latest_state: current_state.clone(),
                            });
                        }
                        Some(flux) => {
                            if &flux.latest_state == current_state {
                                let time_since_latest_change =
                                    (current_time - flux.latest_change_time) as f32;
                                if time_since_latest_change >= self.settings.stable_time {
                                    self.add_undo(current_state);
                                }
                            } else {
                                let time_since_flux_start = (current_time - flux.start_time) as f32;
                                if time_since_flux_start >= self.settings.auto_save_interval {
                                    self.add_undo(current_state);
                                } else {
                                    flux.latest_change_time = current_time;
                                    flux.latest_state = current_state.clone();
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}