dynamic-stack.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 namespace Gecode { namespace Support {
00035
00041 template<class T, class A>
00042 class DynamicStack {
00043 private:
00045 A& a;
00047 int limit;
00049 int tos;
00051 T* stack;
00053 void resize(void);
00054 public:
00056 DynamicStack(A& a, int n=64);
00058 ~DynamicStack(void);
00059
00061 bool empty(void) const;
00063 int entries(void) const;
00064
00066 T pop(void);
00068 T& top(void) const;
00070 T& last(void) const;
00072 void push(const T& x);
00073
00074
00081 T& operator [](int i);
00088 const T& operator [](int i) const;
00089 private:
00091 static void* operator new(size_t s) throw() { (void) s; return NULL; }
00093 static void operator delete(void* p) { (void) p; };
00095 DynamicStack(const DynamicStack& s) : a(s.a) {}
00097 const DynamicStack& operator =(const DynamicStack&) { return *this; }
00098 };
00099
00100
00101 template<class T, class A>
00102 void
00103 DynamicStack<T,A>::resize(void) {
00104 int nl = (limit * 3) / 2;
00105 stack = a.template realloc<T>(stack,limit,nl);
00106 limit = nl;
00107 }
00108
00109 template<class T, class A>
00110 forceinline
00111 DynamicStack<T,A>::DynamicStack(A& a0, int n)
00112 : a(a0), limit(n), tos(0), stack(a.template alloc<T>(n)) {}
00113
00114 template<class T, class A>
00115 forceinline
00116 DynamicStack<T,A>::~DynamicStack(void) {
00117 a.free(stack,limit);
00118 }
00119
00120 template<class T, class A>
00121 forceinline T
00122 DynamicStack<T,A>::pop(void) {
00123 return stack[--tos];
00124 }
00125
00126 template<class T, class A>
00127 forceinline T&
00128 DynamicStack<T,A>::top(void) const {
00129 return stack[tos-1];
00130 }
00131
00132 template<class T, class A>
00133 forceinline T&
00134 DynamicStack<T,A>::last(void) const {
00135 return stack[tos];
00136 }
00137
00138 template<class T, class A>
00139 forceinline void
00140 DynamicStack<T,A>::push(const T& x) {
00141 stack[tos++] = x;
00142 if (tos==limit)
00143 resize();
00144 }
00145
00146 template<class T, class A>
00147 forceinline bool
00148 DynamicStack<T,A>::empty(void) const {
00149 return tos==0;
00150 }
00151
00152 template<class T, class A>
00153 forceinline int
00154 DynamicStack<T,A>::entries(void) const {
00155 return tos;
00156 }
00157
00158 template<class T, class A>
00159 forceinline T&
00160 DynamicStack<T,A>::operator [](int i) {
00161 return stack[i];
00162 }
00163
00164 template<class T, class A>
00165 forceinline const T&
00166 DynamicStack<T,A>::operator [](int i) const {
00167 return stack[i];
00168 }
00169
00170 }}
00171
00172