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
00035
00036
00037
00038 namespace Gecode { namespace Support {
00039
00045 template<class T, class A>
00046 class DynamicStack {
00047 private:
00049 A& a;
00051 int limit;
00053 int tos;
00055 T* stack;
00057 void resize(void);
00058 public:
00060 DynamicStack(A& a, int n=64);
00062 ~DynamicStack(void);
00063
00065 bool empty(void) const;
00067 int entries(void) const;
00068
00070 T pop(void);
00072 T& top(void) const;
00074 T& last(void) const;
00076 void push(const T& x);
00077
00078
00085 T& operator [](int i);
00092 const T& operator [](int i) const;
00093 private:
00095 static void* operator new(size_t s) throw() { (void) s; return NULL; }
00097 static void operator delete(void* p) { (void) p; };
00099 DynamicStack(const DynamicStack& s) : a(s.a) {}
00101 const DynamicStack& operator =(const DynamicStack&) { return *this; }
00102 };
00103
00104
00105 template<class T, class A>
00106 void
00107 DynamicStack<T,A>::resize(void) {
00108 int nl = (limit * 3) / 2;
00109 stack = a.template realloc<T>(stack,limit,nl);
00110 limit = nl;
00111 }
00112
00113 template<class T, class A>
00114 forceinline
00115 DynamicStack<T,A>::DynamicStack(A& a0, int n)
00116 : a(a0), limit(n), tos(0), stack(a.template alloc<T>(n)) {}
00117
00118 template<class T, class A>
00119 forceinline
00120 DynamicStack<T,A>::~DynamicStack(void) {
00121 a.free(stack,limit);
00122 }
00123
00124 template<class T, class A>
00125 forceinline T
00126 DynamicStack<T,A>::pop(void) {
00127 return stack[--tos];
00128 }
00129
00130 template<class T, class A>
00131 forceinline T&
00132 DynamicStack<T,A>::top(void) const {
00133 return stack[tos-1];
00134 }
00135
00136 template<class T, class A>
00137 forceinline T&
00138 DynamicStack<T,A>::last(void) const {
00139 return stack[tos];
00140 }
00141
00142 template<class T, class A>
00143 forceinline void
00144 DynamicStack<T,A>::push(const T& x) {
00145 stack[tos++] = x;
00146 if (tos==limit)
00147 resize();
00148 }
00149
00150 template<class T, class A>
00151 forceinline bool
00152 DynamicStack<T,A>::empty(void) const {
00153 return tos==0;
00154 }
00155
00156 template<class T, class A>
00157 forceinline int
00158 DynamicStack<T,A>::entries(void) const {
00159 return tos;
00160 }
00161
00162 template<class T, class A>
00163 forceinline T&
00164 DynamicStack<T,A>::operator [](int i) {
00165 return stack[i];
00166 }
00167
00168 template<class T, class A>
00169 forceinline const T&
00170 DynamicStack<T,A>::operator [](int i) const {
00171 return stack[i];
00172 }
00173
00174 }}
00175
00176