dynamic-queue.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 DynamicQueue {
00047 private:
00049 A& a;
00051 int limit;
00053 int fst;
00055 int lst;
00057 T* q;
00059 void resize(void);
00061 void move(int& i);
00062 public:
00064 DynamicQueue(A& a);
00066 ~DynamicQueue(void);
00067
00069 bool empty(void) const;
00070
00072 void reset(void);
00073
00075 T pop(void);
00077 void push(const T& x);
00078 private:
00080 static void* operator new(size_t s) throw() { (void) s; return NULL; }
00082 static void operator delete(void* p) { (void) p; };
00084 DynamicQueue(const DynamicQueue& s) : a(s.a) {}
00086 const DynamicQueue& operator =(const DynamicQueue&) { return *this; }
00087 };
00088
00089
00090 template<class T, class A>
00091 forceinline void
00092 DynamicQueue<T,A>::move(int& i) {
00093 i = (i+1) & (limit - 1);
00094 }
00095
00096 template<class T, class A>
00097 void
00098 DynamicQueue<T,A>::resize(void) {
00099 assert(fst == lst);
00100 T* nq = a.template alloc<T>(limit << 1);
00101 int j=0;
00102 for (int i = fst; i<limit; i++)
00103 nq[j++] = q[i];
00104 for (int i = 0; i<lst; i++)
00105 nq[j++] = q[i];
00106 a.template free<T>(q,limit);
00107 q = nq;
00108 fst = 0;
00109 lst = limit;
00110 limit <<= 1;
00111 }
00112
00113 template<class T, class A>
00114 forceinline
00115 DynamicQueue<T,A>::DynamicQueue(A& a0)
00116 : a(a0), limit(8), fst(0), lst(0), q(a.template alloc<T>(limit)) {}
00117
00118 template<class T, class A>
00119 forceinline
00120 DynamicQueue<T,A>::~DynamicQueue(void) {
00121 a.free(q,limit);
00122 }
00123
00124 template<class T, class A>
00125 forceinline bool
00126 DynamicQueue<T,A>::empty(void) const {
00127 return fst == lst;
00128 }
00129
00130 template<class T, class A>
00131 forceinline void
00132 DynamicQueue<T,A>::reset(void) {
00133 fst = lst = 0;
00134 }
00135
00136 template<class T, class A>
00137 forceinline T
00138 DynamicQueue<T,A>::pop(void) {
00139 assert(!empty());
00140 T t = q[fst];
00141 move(fst);
00142 return t;
00143 }
00144
00145 template<class T, class A>
00146 forceinline void
00147 DynamicQueue<T,A>::push(const T& x) {
00148 q[lst] = x;
00149 move(lst);
00150 if (fst == lst)
00151 resize();
00152 }
00153
00154 }}
00155
00156