dynamic-stack.hh
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 #ifndef __GECODE_SUPPORT_DYNAMIC_STACK_HH__
00023 #define __GECODE_SUPPORT_DYNAMIC_STACK_HH__
00024
00025 #include "gecode/kernel.hh"
00026
00027 namespace Gecode { namespace Support {
00028
00035 template <class T>
00036 class DynamicStack {
00037 private:
00039 int limit;
00041 int tos;
00043 T* stack;
00045 void resize(void);
00046 public:
00048 DynamicStack(int n=64);
00050 ~DynamicStack(void);
00051
00053 bool empty(void) const;
00055 T pop(void);
00057 T& top(void);
00059 void push(T);
00060
00061
00063 int entries(void) const;
00070 T& operator[](int i);
00077 const T& operator [] (int i) const;
00078
00080 size_t size(void) const;
00081 };
00082
00083
00084 template <class T>
00085 void
00086 DynamicStack<T>::resize(void) {
00087 int nl = (limit * 3) / 2;
00088 stack = Memory::brealloc<T>(stack,limit,nl);
00089 limit = nl;
00090 }
00091
00092 template <class T>
00093 forceinline
00094 DynamicStack<T>::DynamicStack(int n)
00095 : limit(n), tos(0), stack(Memory::bmalloc<T>(n)) {}
00096
00097 template <class T>
00098 forceinline
00099 DynamicStack<T>::~DynamicStack(void) {
00100 Memory::free(stack);
00101 }
00102
00103 template <class T>
00104 forceinline T
00105 DynamicStack<T>::pop(void) {
00106 return stack[--tos];
00107 }
00108
00109 template <class T>
00110 forceinline T&
00111 DynamicStack<T>::top(void) {
00112 return stack[tos-1];
00113 }
00114
00115 template <class T>
00116 forceinline void
00117 DynamicStack<T>::push(T x) {
00118 stack[tos++] = x;
00119 if (tos==limit)
00120 resize();
00121 }
00122
00123 template <class T>
00124 forceinline bool
00125 DynamicStack<T>::empty(void) const {
00126 return tos==0;
00127 }
00128
00129 template <class T>
00130 forceinline int
00131 DynamicStack<T>::entries(void) const {
00132 return tos;
00133 }
00134
00135 template <class T>
00136 forceinline T&
00137 DynamicStack<T>::operator [] (int i) {
00138 return stack[i];
00139 }
00140
00141 template <class T>
00142 forceinline const T&
00143 DynamicStack<T>::operator [] (int i) const {
00144 return stack[i];
00145 }
00146
00147 template <class T>
00148 forceinline size_t
00149 DynamicStack<T>::size(void) const {
00150 return (limit * sizeof(T)) + sizeof(DynamicStack<T>);
00151 }
00152
00153 }}
00154
00155 #endif
00156
00157