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)19UndoHistory::UndoHistory(UndoHistoryDelegate* delegate) 20 : m_delegate(delegate) 21 , m_first(nullptr) 22 , m_last(nullptr) 23 , m_cur(nullptr) 24 { 25 } 26 ~UndoHistory()27UndoHistory::~UndoHistory() 28 { 29 m_cur = nullptr; 30 clearRedo(); 31 } 32 canUndo() const33bool UndoHistory::canUndo() const 34 { 35 return m_cur != nullptr; 36 } 37 canRedo() const38bool UndoHistory::canRedo() const 39 { 40 return m_cur != m_last; 41 } 42 undo()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 redo()56void UndoHistory::redo() 57 { 58 if (!m_cur) 59 moveTo(m_first); 60 else 61 moveTo(m_cur->m_next); 62 } 63 clearRedo()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 deleteFirstState()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 add(UndoCommand * cmd)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 findCommonParent(const UndoState * a,const UndoState * b)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 moveTo(const UndoState * new_state)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 deleteState(UndoState * state)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