Generated on Tue May 22 09:40:16 2018 for Gecode by doxygen 1.6.3

dynamic-queue.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2009
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Support {
00035 
00041   template<class T, class A>
00042   class DynamicQueue {
00043   private:
00045     A& a;
00047     int limit;
00049     int fst;
00051     int lst;
00053     T*  q;
00055     void resize(void);
00057     void move(int& i);
00058   public:
00060     DynamicQueue(A& a);
00062     ~DynamicQueue(void);
00063 
00065     bool empty(void) const;
00066 
00068     void reset(void);
00069 
00071     T pop(void);
00073     void push(const T& x);
00074   private:
00076     static void* operator new(size_t s) throw() { (void) s; return NULL; }
00078     static void  operator delete(void* p) { (void) p; };
00080     DynamicQueue(const DynamicQueue& s) : a(s.a) {}
00082     const DynamicQueue& operator =(const DynamicQueue&) { return *this; }
00083   };
00084 
00085 
00086   template<class T, class A>
00087   forceinline void
00088   DynamicQueue<T,A>::move(int& i) {
00089     i = (i+1) & (limit - 1);
00090   }
00091 
00092   template<class T, class A>
00093   void
00094   DynamicQueue<T,A>::resize(void) {
00095     assert(fst == lst);
00096     T* nq = a.template alloc<T>(limit << 1);
00097     int j=0;
00098     for (int i = fst; i<limit; i++)
00099       nq[j++] = q[i];
00100     for (int i = 0; i<lst; i++)
00101       nq[j++] = q[i];
00102     a.template free<T>(q,limit);
00103     q = nq;
00104     fst = 0;
00105     lst = limit;
00106     limit <<= 1;
00107   }
00108 
00109   template<class T, class A>
00110   forceinline
00111   DynamicQueue<T,A>::DynamicQueue(A& a0)
00112     : a(a0), limit(8), fst(0), lst(0), q(a.template alloc<T>(limit)) {}
00113 
00114   template<class T, class A>
00115   forceinline
00116   DynamicQueue<T,A>::~DynamicQueue(void) {
00117     a.free(q,limit);
00118   }
00119 
00120   template<class T, class A>
00121   forceinline bool
00122   DynamicQueue<T,A>::empty(void) const {
00123     return fst == lst;
00124   }
00125 
00126   template<class T, class A>
00127   forceinline void
00128   DynamicQueue<T,A>::reset(void) {
00129     fst = lst = 0;
00130   }
00131 
00132   template<class T, class A>
00133   forceinline T
00134   DynamicQueue<T,A>::pop(void) {
00135     assert(!empty());
00136     T t = q[fst];
00137     move(fst);
00138     return t;
00139   }
00140 
00141   template<class T, class A>
00142   forceinline void
00143   DynamicQueue<T,A>::push(const T& x) {
00144     q[lst] = x;
00145     move(lst);
00146     if (fst == lst)
00147       resize();
00148   }
00149 
00150 }}
00151 
00152 // STATISTICS: support-any