1 // Undo Library
2 // Copyright (C) 2015-2017 David Capello
3 //
4 // This file is released under the terms of the MIT license.
5 // Read LICENSE.txt for more information.
6 
7 #include "undo_history.h"
8 
9 #include "undo_command.h"
10 #include "undo_state.h"
11 
12 #include <cassert>
13 #include <stack>
14 
15 #define UNDO_TRACE(...)
16 
17 namespace undo {
18 
UndoHistory(UndoHistoryDelegate * delegate)19 UndoHistory::UndoHistory(UndoHistoryDelegate* delegate)
20   : m_delegate(delegate)
21   , m_first(nullptr)
22   , m_last(nullptr)
23   , m_cur(nullptr)
24 {
25 }
26 
~UndoHistory()27 UndoHistory::~UndoHistory()
28 {
29   m_cur = nullptr;
30   clearRedo();
31 }
32 
canUndo() const33 bool UndoHistory::canUndo() const
34 {
35   return m_cur != nullptr;
36 }
37 
canRedo() const38 bool UndoHistory::canRedo() const
39 {
40   return m_cur != m_last;
41 }
42 
undo()43 void UndoHistory::undo()
44 {
45   assert(m_cur);
46   if (!m_cur)
47     return;
48 
49   assert(
50     (m_cur != m_first && m_cur->m_prev) ||
51     (m_cur == m_first && !m_cur->m_prev));
52 
53   moveTo(m_cur->m_prev);
54 }
55 
redo()56 void UndoHistory::redo()
57 {
58   if (!m_cur)
59     moveTo(m_first);
60   else
61     moveTo(m_cur->m_next);
62 }
63 
clearRedo()64 void UndoHistory::clearRedo()
65 {
66   for (UndoState* state = m_last, *prev = nullptr;
67        state && state != m_cur;
68        state = prev) {
69     prev = state->m_prev;
70     deleteState(state);
71   }
72 
73   if (m_cur) {
74     m_cur->m_next = nullptr;
75     m_last = m_cur;
76   }
77   else {
78     m_first = m_last = nullptr;
79   }
80 }
81 
deleteFirstState()82 bool UndoHistory::deleteFirstState()
83 {
84   UNDO_TRACE("UndoHistory::deleteFirstState()\n");
85 
86   // We cannot delete the first state if we are in the first state.
87   if (m_cur == m_first) {
88     UNDO_TRACE(" - Cannot delete first state if it's the current state\n");
89     return false;
90   }
91 
92   UndoState* i = m_last;
93   while (i) {
94     // If this state depends on the delete one, this "i" is the new
95     // m_first undo state.
96     if (i->m_parent == m_first) {
97       // First we check if the current undo state is one of the states
98       // that we're going to delete.
99       UndoState* j = m_first;
100       while (j != i) {
101         // Cannot delete this "j" state because is the current one.
102         if (m_cur == j) {
103           UNDO_TRACE(" - Cannot delete first state because current state depends on it to go to the last state\n");
104           return false;
105         }
106         j = j->next();
107       }
108 
109       j = m_first;
110       while (j != i) {
111         UNDO_TRACE(" - Delete undo state\n");
112 
113         UndoState* k = j;
114         j = j->next();
115 
116         deleteState(k);
117       }
118 
119       i->m_prev = nullptr;
120       i->m_parent = nullptr;
121       m_first = i;
122       return true;
123     }
124     i = i->prev();
125   }
126 
127   UndoState* state = m_first;
128   assert(m_last == m_first);
129   assert(m_first->next() == nullptr);
130   m_first = m_last = nullptr;
131   UNDO_TRACE(" - Delete first state only\n");
132 
133   deleteState(state);
134   return true;
135 }
136 
add(UndoCommand * cmd)137 void UndoHistory::add(UndoCommand* cmd)
138 {
139   UndoState* state = new UndoState(cmd);
140   state->m_prev = m_last;
141   state->m_next = nullptr;
142   state->m_parent = m_cur;
143 
144   if (!m_first)
145     m_first = state;
146 
147   m_cur = m_last = state;
148 
149   if (state->m_prev) {
150     assert(!state->m_prev->m_next);
151     state->m_prev->m_next = state;
152   }
153 }
154 
findCommonParent(const UndoState * a,const UndoState * b)155 const UndoState* UndoHistory::findCommonParent(const UndoState* a,
156                                                const UndoState* b)
157 {
158   const UndoState* pA = a;
159   const UndoState* pB = b;
160 
161   if (pA == nullptr || pB == nullptr)
162     return nullptr;
163 
164   while (pA != pB) {
165     pA = pA->m_parent;
166     if (!pA) {
167       pA = a;
168       pB = pB->m_parent;
169       if (!pB)
170         return nullptr;
171     }
172   }
173 
174   return pA;
175 }
176 
moveTo(const UndoState * new_state)177 void UndoHistory::moveTo(const UndoState* new_state)
178 {
179   const UndoState* common = findCommonParent(m_cur, new_state);
180 
181   if (m_cur) {
182     while (m_cur != common) {
183       m_cur->m_cmd->undo();
184       m_cur = m_cur->m_parent;
185     }
186   }
187 
188   if (new_state) {
189     std::stack<const UndoState*> redo_parents;
190     const UndoState* p = new_state;
191     while (p != common) {
192       redo_parents.push(p);
193       p = p->m_parent;
194     }
195 
196     while (!redo_parents.empty()) {
197       p = redo_parents.top();
198       redo_parents.pop();
199 
200       p->m_cmd->redo();
201     }
202   }
203 
204   m_cur = const_cast<UndoState*>(new_state);
205 }
206 
deleteState(UndoState * state)207 void UndoHistory::deleteState(UndoState* state)
208 {
209   if (m_delegate)
210     m_delegate->onDeleteUndoState(state);
211 
212   delete state;
213 }
214 
215 } // namespace undo
216