1 | #ifndef STACKCLASS_HPP_
|
---|
2 | #define STACKCLASS_HPP_
|
---|
3 |
|
---|
4 | using namespace std;
|
---|
5 |
|
---|
6 | /*********************************************** includes ***********************************/
|
---|
7 |
|
---|
8 | // include config.h
|
---|
9 | #ifdef HAVE_CONFIG_H
|
---|
10 | #include <config.h>
|
---|
11 | #endif
|
---|
12 |
|
---|
13 | #include "verbose.hpp"
|
---|
14 | #include "memoryallocator.hpp"
|
---|
15 |
|
---|
16 | /****************************************** forward declarations *****************************/
|
---|
17 |
|
---|
18 | template <typename T> class StackClass;
|
---|
19 |
|
---|
20 | /******************************** Functions for class StackClass ********************************/
|
---|
21 |
|
---|
22 | /* Stack of Stuff.
|
---|
23 | * Is used during DepthFirstSearchAnalysis() to detect nonseparable components.
|
---|
24 | */
|
---|
25 | template <typename T> class StackClass {
|
---|
26 | public:
|
---|
27 | StackClass<T>(int dimension);
|
---|
28 | ~StackClass<T>();
|
---|
29 |
|
---|
30 | bool Push(T object);
|
---|
31 | T PopFirst();
|
---|
32 | T PopLast();
|
---|
33 | bool RemoveItem(T ptr);
|
---|
34 | void ClearStack();
|
---|
35 | bool IsEmpty() const;
|
---|
36 | bool IsFull() const;
|
---|
37 | int ItemCount() const;
|
---|
38 | void Output(ofstream * const out) const;
|
---|
39 |
|
---|
40 | private:
|
---|
41 | T *StackList; //!< the list containing the atom pointers
|
---|
42 | int EntryCount; //!< number of entries in the stack
|
---|
43 | int CurrentLastEntry; //!< Current last entry (newest item on stack)
|
---|
44 | int CurrentFirstEntry; //!< Current first entry (oldest item on stack)
|
---|
45 | int NextFreeField; //!< Current index of next free field
|
---|
46 | };
|
---|
47 |
|
---|
48 | /** Constructor of class StackClass.
|
---|
49 | */
|
---|
50 | template <typename T> StackClass<T>::StackClass(int dimension) : StackList(NULL), EntryCount(dimension), CurrentLastEntry(0), CurrentFirstEntry(0), NextFreeField(0)
|
---|
51 | {
|
---|
52 | StackList = new T[EntryCount];
|
---|
53 | for (int i=0;i<EntryCount;i++)
|
---|
54 | StackList[i] = NULL;
|
---|
55 | };
|
---|
56 |
|
---|
57 | /** Destructor of class StackClass.
|
---|
58 | */
|
---|
59 | template <typename T> StackClass<T>::~StackClass()
|
---|
60 | {
|
---|
61 | delete[](StackList);
|
---|
62 | };
|
---|
63 |
|
---|
64 | /** Pushes an object onto the stack.
|
---|
65 | * \param *object atom to be pushed on stack
|
---|
66 | * \return true - sucess, false - failure, meaning stack field was occupied
|
---|
67 | */
|
---|
68 | template <typename T> bool StackClass<T>::Push(T object)
|
---|
69 | {
|
---|
70 | if (!IsFull()) { // check whether free field is really not occupied
|
---|
71 | StackList[NextFreeField] = object;
|
---|
72 | CurrentLastEntry = NextFreeField;
|
---|
73 | NextFreeField = (NextFreeField + 1) % EntryCount; // step on to next free field
|
---|
74 | return true;
|
---|
75 | } else {
|
---|
76 | DoeLog(1) && (eLog()<< Verbose(1) << "Stack is full, " << "Stack: CurrentLastEntry " << CurrentLastEntry<< "\tCurrentFirstEntry " << CurrentFirstEntry << "\tNextFreeField " << NextFreeField << "\tEntryCount " << EntryCount << "!" << endl);
|
---|
77 | return false;
|
---|
78 | }
|
---|
79 | };
|
---|
80 |
|
---|
81 | /** Pops first/oldest atom from stack.
|
---|
82 | * First in, last out.
|
---|
83 | * \return atom pointer from stack, NULL - if failure (no atom pointer in field)
|
---|
84 | */
|
---|
85 | template <typename T> T StackClass<T>::PopFirst()
|
---|
86 | {
|
---|
87 | T Walker = NULL;
|
---|
88 | if (!IsEmpty()) {
|
---|
89 | Walker = StackList[CurrentFirstEntry];
|
---|
90 | if (Walker == NULL)
|
---|
91 | DoeLog(1) && (eLog()<< Verbose(1) << "Stack's field is empty!" << endl);
|
---|
92 | StackList[CurrentFirstEntry] = NULL;
|
---|
93 | if (CurrentFirstEntry != CurrentLastEntry) { // hasn't last item been popped as well?
|
---|
94 | CurrentFirstEntry = (CurrentFirstEntry + 1) % EntryCount; // step back from current free field to last used (somehow modulo does not work in -1)
|
---|
95 | } else {
|
---|
96 | CurrentFirstEntry = (CurrentFirstEntry + 1) % EntryCount; // step back from current free field to last used (somehow modulo does not work in -1)
|
---|
97 | CurrentLastEntry = CurrentFirstEntry;
|
---|
98 | }
|
---|
99 | } else
|
---|
100 | DoeLog(1) && (eLog()<< Verbose(1) << "Stack is empty!" << endl);
|
---|
101 | return Walker;
|
---|
102 | };
|
---|
103 |
|
---|
104 | /** Pops last element from stack.
|
---|
105 | * First in, first out.
|
---|
106 | * \return element pointer from stack, NULL - if failure (no atom pointer in field)
|
---|
107 | */
|
---|
108 | template <typename T> T StackClass<T>::PopLast()
|
---|
109 | {
|
---|
110 | T Walker = NULL;
|
---|
111 | if (!IsEmpty()) {
|
---|
112 | Walker = StackList[CurrentLastEntry];
|
---|
113 | StackList[CurrentLastEntry] = NULL;
|
---|
114 | if (Walker == NULL)
|
---|
115 | DoeLog(1) && (eLog()<< Verbose(1) << "Stack's field is empty!" << endl);
|
---|
116 | NextFreeField = CurrentLastEntry;
|
---|
117 | if (CurrentLastEntry != CurrentFirstEntry) // has there been more than one item on stack
|
---|
118 | CurrentLastEntry = (CurrentLastEntry + (EntryCount-1)) % EntryCount; // step back from current free field to last (modulo does not work in -1, thus go EntryCount-1 instead)
|
---|
119 | } else {
|
---|
120 | DoeLog(1) && (eLog()<< Verbose(1) << "Stack is empty!" << endl);
|
---|
121 | }
|
---|
122 | return Walker;
|
---|
123 | };
|
---|
124 |
|
---|
125 | /** Removes a certain item from the stack.
|
---|
126 | * Item is seeked between \a CurrentFirstEntry and \a CurrentLastEntry, if found, place in stack is NULL'd and
|
---|
127 | * all subsequent items shifted by one position downward (with wrapping taken into account).
|
---|
128 | * \param *ptr adress of item
|
---|
129 | * \return true - item was removed, false - item was not found
|
---|
130 | */
|
---|
131 | template <typename T> bool StackClass<T>::RemoveItem(T ptr)
|
---|
132 | {
|
---|
133 | bool found = false;
|
---|
134 | DoLog(5) && (Log() << Verbose(5) << "First " << CurrentFirstEntry<< "\tLast " << CurrentLastEntry<< "\tNext " << NextFreeField<< "\tCount " << EntryCount<< "." << endl);
|
---|
135 | int i=CurrentFirstEntry;
|
---|
136 | if (!IsEmpty())
|
---|
137 | do {
|
---|
138 | if (StackList[i] == ptr) { // if item found, remove
|
---|
139 | DoLog(5) && (Log() << Verbose(5) << "Item " << *ptr << " was number " << i << " on stack, removing it." << endl);
|
---|
140 | found = true;
|
---|
141 | StackList[i] = NULL;
|
---|
142 | }
|
---|
143 | if ((found) && (StackList[i] != NULL)) { // means we have to shift (and not the removed item)
|
---|
144 | if (i == 0) { // we are down to first item in stack, have to put onto last item
|
---|
145 | DoLog(5) && (Log() << Verbose(5) << "Shifting item 0 to place " << EntryCount-1 << "." << endl);
|
---|
146 | StackList[EntryCount-1] = StackList[0];
|
---|
147 | } else {
|
---|
148 | DoLog(5) && (Log() << Verbose(5) << "Shifting item " << i << " to place " << i-1 << "." << endl);
|
---|
149 | StackList[i-1] = StackList[i];
|
---|
150 | }
|
---|
151 | }
|
---|
152 | i=((i + 1) % EntryCount); // step on
|
---|
153 | } while (i!=NextFreeField);
|
---|
154 | else
|
---|
155 | DoeLog(1) && (eLog()<< Verbose(1) << "Stack is already empty!" << endl);
|
---|
156 | if (found) {
|
---|
157 | NextFreeField = CurrentLastEntry;
|
---|
158 | if (CurrentLastEntry != CurrentFirstEntry) // has there been more than one item on stack
|
---|
159 | CurrentLastEntry = (CurrentLastEntry + (EntryCount-1)) % EntryCount;
|
---|
160 | }
|
---|
161 | return found;
|
---|
162 | };
|
---|
163 |
|
---|
164 |
|
---|
165 | /** Puts contents of stack into ofstream \a *out.
|
---|
166 | * \param *out ofstream for output
|
---|
167 | */
|
---|
168 | template <typename T> void StackClass<T>::Output(ofstream * const out) const
|
---|
169 | {
|
---|
170 | *out << "Contents of Stack: ";
|
---|
171 | for(int i=0;i<EntryCount;i++) {
|
---|
172 | *out << "\t";
|
---|
173 | if (i == CurrentFirstEntry)
|
---|
174 | *out << " 1";
|
---|
175 | if (i == CurrentLastEntry)
|
---|
176 | *out << " "<< EntryCount;
|
---|
177 | if (i == NextFreeField)
|
---|
178 | *out << " F";
|
---|
179 | *out << ": " << StackList[i];
|
---|
180 | }
|
---|
181 | *out << endl;
|
---|
182 | };
|
---|
183 |
|
---|
184 | /** Checks whether stack is empty.
|
---|
185 | * Simply checks whether StackClass::NextFreeField is equal to StackClass::CurrentFirstEntry and
|
---|
186 | * StackClass::CurrentFirstEntry is equal to StackClass::CurrentLastEntry.
|
---|
187 | * \return true - empty, false - not
|
---|
188 | */
|
---|
189 | template <typename T> bool StackClass<T>::IsEmpty() const
|
---|
190 | {
|
---|
191 | return((NextFreeField == CurrentFirstEntry) && (CurrentLastEntry == CurrentFirstEntry));
|
---|
192 | };
|
---|
193 |
|
---|
194 | /** Checks whether stack is full.
|
---|
195 | * Simply checks whether StackClass::NextFreeField is equal to StackClass::CurrentFirstEntry and
|
---|
196 | * StackClass::CurrentFirstEntry is _not_ equal to StackClass::CurrentLastEntry.
|
---|
197 | * \return true - full, false - not
|
---|
198 | */
|
---|
199 | template <typename T> bool StackClass<T>::IsFull() const
|
---|
200 | {
|
---|
201 | return((NextFreeField == CurrentFirstEntry) && (CurrentLastEntry != CurrentFirstEntry));
|
---|
202 | };
|
---|
203 |
|
---|
204 | /** Returns number of items on stack.
|
---|
205 | * Simply returns difference between StackClass::Stacklist entry StackClass::CurrentEntry-1.
|
---|
206 | * \return number of items on stack
|
---|
207 | * \warning will never return correct item count if stack is full, i.e. count would be StackClass::EntryCount.
|
---|
208 | */
|
---|
209 | template <typename T> int StackClass<T>::ItemCount() const
|
---|
210 | {
|
---|
211 | //Log() << Verbose(0) << "Stack: CurrentLastEntry " << CurrentLastEntry<< "\tCurrentFirstEntry " << CurrentFirstEntry << "\tEntryCount " << EntryCount << "." << endl;
|
---|
212 | return((NextFreeField + (EntryCount - CurrentFirstEntry)) % EntryCount);
|
---|
213 | };
|
---|
214 |
|
---|
215 | /** Clears the stack from all atoms.
|
---|
216 | * \return true - sucess, false - failure
|
---|
217 | */
|
---|
218 | template <typename T> void StackClass<T>::ClearStack()
|
---|
219 | {
|
---|
220 | for(int i=EntryCount; i--;)
|
---|
221 | StackList[i] = NULL;
|
---|
222 | CurrentFirstEntry = 0;
|
---|
223 | CurrentLastEntry = 0;
|
---|
224 | NextFreeField = 0;
|
---|
225 | };
|
---|
226 |
|
---|
227 |
|
---|
228 |
|
---|
229 | #endif /*STACKCLASS_HPP_*/
|
---|