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
00095 size_t size(void) const;
00096 private:
00098 static void* operator new(size_t s) throw() { (void) s; return NULL; }
00100 static void operator delete(void* p) { (void) p; };
00102 DynamicStack(const DynamicStack& s) : a(s.a) {}
00104 const DynamicStack& operator =(const DynamicStack&) { return *this; }
00105 };
00106
00107
00108 template<class T, class A>
00109 void
00110 DynamicStack<T,A>::resize(void) {
00111 int nl = (limit * 3) / 2;
00112 stack = a.template realloc<T>(stack,limit,nl);
00113 limit = nl;
00114 }
00115
00116 template<class T, class A>
00117 forceinline
00118 DynamicStack<T,A>::DynamicStack(A& a0, int n)
00119 : a(a0), limit(n), tos(0), stack(a.template alloc<T>(n)) {}
00120
00121 template<class T, class A>
00122 forceinline
00123 DynamicStack<T,A>::~DynamicStack(void) {
00124 a.free(stack,limit);
00125 }
00126
00127 template<class T, class A>
00128 forceinline T
00129 DynamicStack<T,A>::pop(void) {
00130 return stack[--tos];
00131 }
00132
00133 template<class T, class A>
00134 forceinline T&
00135 DynamicStack<T,A>::top(void) const {
00136 return stack[tos-1];
00137 }
00138
00139 template<class T, class A>
00140 forceinline T&
00141 DynamicStack<T,A>::last(void) const {
00142 return stack[tos];
00143 }
00144
00145 template<class T, class A>
00146 forceinline void
00147 DynamicStack<T,A>::push(const T& x) {
00148 stack[tos++] = x;
00149 if (tos==limit)
00150 resize();
00151 }
00152
00153 template<class T, class A>
00154 forceinline bool
00155 DynamicStack<T,A>::empty(void) const {
00156 return tos==0;
00157 }
00158
00159 template<class T, class A>
00160 forceinline int
00161 DynamicStack<T,A>::entries(void) const {
00162 return tos;
00163 }
00164
00165 template<class T, class A>
00166 forceinline T&
00167 DynamicStack<T,A>::operator [](int i) {
00168 return stack[i];
00169 }
00170
00171 template<class T, class A>
00172 forceinline const T&
00173 DynamicStack<T,A>::operator [](int i) const {
00174 return stack[i];
00175 }
00176
00177 template<class T, class A>
00178 forceinline size_t
00179 DynamicStack<T,A>::size(void) const {
00180 return (static_cast<size_t>(limit) * sizeof(T)) +
00181 sizeof(DynamicStack<T,A>);
00182 }
00183
00184 }}
00185
00186