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