1 /*
2  *  ppui/UndoStack.h
3  *
4  *  Copyright 2009 Peter Barth
5  *
6  *  This file is part of Milkytracker.
7  *
8  *  Milkytracker is free software: you can redistribute it and/or modify
9  *  it under the terms of the GNU General Public License as published by
10  *  the Free Software Foundation, either version 3 of the License, or
11  *  (at your option) any later version.
12  *
13  *  Milkytracker is distributed in the hope that it will be useful,
14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  *  GNU General Public License for more details.
17  *
18  *  You should have received a copy of the GNU General Public License
19  *  along with Milkytracker.  If not, see <http://www.gnu.org/licenses/>.
20  *
21  */
22 
23 /*
24  *  UndoStack.h
25  *  MilkyTracker
26  *
27  *  Created by Peter Barth on 14.03.06.
28  *
29  */
30 #ifndef __UNDOSTACK_H__
31 #define __UNDOSTACK_H__
32 
33 #include "BasicTypes.h"
34 
35 //--- Undo-stack ------------------------------------------------------------
36 // The undo stack works like this:
37 //
38 //	  /--<--< New Entry pushed: Stack is full? => bottom element will be removed
39 //    |											  and all elements will be moved
40 //	  |											  one step down and the new element
41 //	|###|									      is placed on top
42 //	|###|  |
43 //	|###|  |
44 //	|###| \!/
45 //	|###|
46 //	  |
47 //    \-->--> /dev/null :) (bottom element will be deleted)
48 
49 template<class type>
50 class PPUndoStack
51 {
52 private:
53 	enum
54 	{
55 		DEFAULTSTACKSIZE = 1024
56 	};
57 
58 	// Our stacksize
59 	pp_int32 m_nStackSize;
60 
61 	// our stack
62 	type** m_pUndoStack;
63 
64 	// index of current stack entry
65 	pp_int32	m_nCurIndex;
66 
67 	// index of last valid stack entry
68 	pp_int32 m_nTopIndex;
69 
70 	// stack has overflowed and bottom elements have been removed
71 	bool m_bOverflow;
72 
73 public:
74 	//---------------------------------------------------------------------------
75 	// Pre     :
76 	// Post    :
77 	// Globals :
78 	// I/O     :
79 	// Task    : Construction: Create clean empty stack
80 	//---------------------------------------------------------------------------
81 	PPUndoStack(pp_int32 nStackSize = DEFAULTSTACKSIZE)
82 	{
83 		// Remember size
84 		m_nStackSize = nStackSize;
85 
86 		// create stack containing empty entries
87 		m_pUndoStack = new type*[nStackSize+1];
88 
89 		for (pp_int32 i = 0; i < nStackSize+1; i++)
90 			m_pUndoStack[i] = NULL;
91 
92 		// empty stack
93 		m_nCurIndex = -1;
94 		m_nTopIndex = 0;
95 
96 		// hasn't overflowed yet
97 		m_bOverflow = false;
98 	}
99 
100 	//---------------------------------------------------------------------------
101 	// Pre     :
102 	// Post    :
103 	// Globals :
104 	// I/O     :
105 	// Task    : Destruction
106 	//---------------------------------------------------------------------------
~PPUndoStack()107 	~PPUndoStack()
108 	{
109 		for (pp_int32 i = 0; i < m_nStackSize; i++)
110 			if (m_pUndoStack[i])
111 				delete m_pUndoStack[i];
112 
113 		delete[] m_pUndoStack;
114 	}
115 
116 	//---------------------------------------------------------------------------
117 	// Pre     :
118 	// Post    :
119 	// Globals :
120 	// I/O     :
121 	// Task    : Save entry on stack
122 	//---------------------------------------------------------------------------
Push(const type & stackEntry)123 	void Push(const type& stackEntry)
124 	{
125 		// does new entry fit onto stack?
126 		if (m_nCurIndex < m_nStackSize-1)
127 		{
128 			// current index always points to the last entry
129 			m_nCurIndex++;
130 		}
131 		// nope, kill bottom entry and move content
132 		else
133 		{
134 			// delete first entry
135 			delete m_pUndoStack[0];
136 
137 			// move references
138 			for (pp_int32 i = 0; i <= m_nCurIndex; i++)
139 				m_pUndoStack[i] = m_pUndoStack[i+1];
140 
141 			m_bOverflow = true;
142 		}
143 
144 		// make sure we don't leak something here
145 		if (m_pUndoStack[m_nCurIndex])
146 			delete m_pUndoStack[m_nCurIndex];
147 
148 		// new entry
149 		m_pUndoStack[m_nCurIndex] = new type(stackEntry);
150 
151 		m_nTopIndex = m_nCurIndex;
152 	}
153 
154 	//---------------------------------------------------------------------------
155 	// Pre     :
156 	// Post    :
157 	// Globals :
158 	// I/O     :
159 	// Task    : Get entry from stack (only by pointer)
160 	//---------------------------------------------------------------------------
Pop()161 	const type* Pop()
162 	{
163 		// anything on stack yet?
164 		if (m_nCurIndex>=0)
165 		{
166 			// get entry
167 			return m_pUndoStack[m_nCurIndex--];
168 
169 			/*type* pStackEntry = m_pUndoStack[m_nCurIndex];
170 
171 			// decrease stackpointer
172 			m_nCurIndex--;
173 			return pStackEntry;*/
174 		}
175 
176 		else
177 		{
178 			return NULL;
179 		}
180 	}
181 
182 	//---------------------------------------------------------------------------
183 	// Pre     :
184 	// Post    :
185 	// Globals :
186 	// I/O     :
187 	// Task    : Get superimposed entry if possible (Redo)
188 	//---------------------------------------------------------------------------
Advance()189 	const type* Advance()
190 	{
191 		// Nothing on stack
192 		if (m_nTopIndex == 0)
193 		{
194 			return NULL;
195 		}
196 
197 		// Redo possible?
198 		if (m_nCurIndex<m_nTopIndex-1)
199 		{
200 			// advance
201 			m_nCurIndex++;
202 		}
203 
204 		// get superimposed entry
205 		return m_pUndoStack[m_nCurIndex+1];
206 	}
207 
IsEmpty()208 	bool IsEmpty() const { return (m_nCurIndex == -1); }
209 
IsTop()210 	bool IsTop() const { return ((m_nTopIndex-1)==m_nCurIndex); }
211 
IsOverflowed()212 	bool IsOverflowed() const { return m_bOverflow; }
213 };
214 
215 #endif
216