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
17namespace undo {
18
19UndoHistory::UndoHistory(UndoHistoryDelegate* delegate)
20 : m_delegate(delegate)
21 , m_first(nullptr)
22 , m_last(nullptr)
23 , m_cur(nullptr)
24{
25}
26
27UndoHistory::~UndoHistory()
28{
29 m_cur = nullptr;
30 clearRedo();
31}
32
33bool UndoHistory::canUndo() const
34{
35 return m_cur != nullptr;
36}
37
38bool UndoHistory::canRedo() const
39{
40 return m_cur != m_last;
41}
42
43void 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
56void UndoHistory::redo()
57{
58 if (!m_cur)
59 moveTo(m_first);
60 else
61 moveTo(m_cur->m_next);
62}
63
64void 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
82bool 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
137void 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
155const 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
177void 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
207void UndoHistory::deleteState(UndoState* state)
208{
209 if (m_delegate)
210 m_delegate->onDeleteUndoState(state);
211
212 delete state;
213}
214
215} // namespace undo
216