Newer
Older
/******************************************************************************
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v2.0
* which accompanies this distribution, and is available at
* https://www.eclipse.org/org/documents/epl-2.0/EPL-2.0.html
*
* Contributors:
* Balasko, Jeno
* Forstner, Matyas
* Gecse, Roland
* Raduly, Csaba
* Szabo, Janos Zoltan – initial implementation
*
******************************************************************************/
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#ifndef _Common_stack_HH
#define _Common_stack_HH
#include "error.h"
#include "../common/memory.h"
/**
* LIFO container optimized to store elements sequentially,
* and access only the element on the top of the stack.
* Accessing the top of the stack has amortized constant time cost.
*
* The container stores pointers to objects of type T; it doesn't own them.
* It is the responsibility of the caller to create and destroy the objects
* and supply the pointers to the container.
*
* \ingroup containers
*/
template<class T>
class stack {
private:
size_t num_s; ///< used size
size_t max_s; ///< allocated size
T **s_ptr; ///< array of pointers to objects of type T
static const size_t initial_size = 1, increment_factor = 2;
/** Copy constructor: DO NOT IMPLEMENT! */
stack(const stack&);
/** Copy assignment: DO NOT IMPLEMENT! */
stack& operator=(const stack&);
public:
static const size_t max_stack_length = static_cast<size_t>(-1 );
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/** Creates an empty stack. */
stack() : num_s(0), max_s(0), s_ptr(NULL) { }
/** Deallocates its memory. If the container is not empty,
* FATAL_ERROR occurs, so before destructing, clear()
* must be invoked explicitly.
*/
~stack() {
if(num_s > 0) FATAL_ERROR("stack::~stack(): stack is not empty");
Free(s_ptr);
}
/** Returns the number of elements in the container. */
size_t size() const { return num_s; }
/** Returns true if the container has no elements. */
bool empty() const { return num_s == 0; }
/** Forgets all elements in the container.
* No memory is freed. */
void clear() { num_s = 0; }
/** Push the elem onto the stack. */
void push(T *elem) {
if (max_s <= num_s) {
if (max_s == 0) {
max_s = initial_size;
s_ptr = static_cast<T**>(Malloc(initial_size * sizeof(*s_ptr)));
} else {
if(max_s >= max_stack_length / increment_factor)
FATAL_ERROR("stack::push(): stack index overflow");
max_s *= increment_factor;
s_ptr = static_cast<T**>(Realloc(s_ptr, max_s * sizeof(*s_ptr)));
}
}
s_ptr[num_s++] = elem;
}
/** Returns the top of the stack or FATAL_ERROR if empty. */
T* top() const {
if(num_s == 0) FATAL_ERROR("stack::top() const: stack is empty");
return s_ptr[num_s - 1];
}
/** Returns the top of the stack, and removes it from the
* container. If the stack is empty then FATAL_ERROR occurs. */
T* pop() {
if(num_s == 0) FATAL_ERROR("stack::pop(): stack is empty");
return s_ptr[--num_s];
}
};
#endif // _Common_stack_HH