dynamic-queue.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2009
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
namespace Gecode { namespace Support {
template<class T, class A>
class DynamicQueue {
private:
A& a;
int limit;
int fst;
int lst;
T* q;
void resize(void);
void move(int& i);
public:
DynamicQueue(A& a);
~DynamicQueue(void);
bool empty(void) const;
void reset(void);
T pop(void);
void push(const T& x);
private:
static void* operator new(size_t s) throw() { (void) s; return NULL; }
static void operator delete(void* p) { (void) p; };
DynamicQueue(const DynamicQueue& s) : a(s.a) {}
const DynamicQueue& operator =(const DynamicQueue&) { return *this; }
};
template<class T, class A>
forceinline void
DynamicQueue<T,A>::move(int& i) {
i = (i+1) & (limit - 1);
}
template<class T, class A>
void
DynamicQueue<T,A>::resize(void) {
assert(fst == lst);
T* nq = a.template alloc<T>(limit << 1);
int j=0;
for (int i = fst; i<limit; i++)
nq[j++] = q[i];
for (int i = 0; i<lst; i++)
nq[j++] = q[i];
a.template free<T>(q,limit);
q = nq;
fst = 0;
lst = limit;
limit <<= 1;
}
template<class T, class A>
forceinline
DynamicQueue<T,A>::DynamicQueue(A& a0)
: a(a0), limit(8), fst(0), lst(0), q(a.template alloc<T>(limit)) {}
template<class T, class A>
forceinline
DynamicQueue<T,A>::~DynamicQueue(void) {
a.free(q,limit);
}
template<class T, class A>
forceinline bool
DynamicQueue<T,A>::empty(void) const {
return fst == lst;
}
template<class T, class A>
forceinline void
DynamicQueue<T,A>::reset(void) {
fst = lst = 0;
}
template<class T, class A>
forceinline T
DynamicQueue<T,A>::pop(void) {
assert(!empty());
T t = q[fst];
move(fst);
return t;
}
template<class T, class A>
forceinline void
DynamicQueue<T,A>::push(const T& x) {
q[lst] = x;
move(lst);
if (fst == lst)
resize();
}
}}
// STATISTICS: support-any
Gecode::Support::DynamicQueue::~DynamicQueue
~DynamicQueue(void)
Release memory.
Definition dynamic-queue.hpp:116
Gecode::Support::DynamicQueue::push
void push(const T &x)
Push element x to queue.
Definition dynamic-queue.hpp:143
Gecode::Support::DynamicQueue::empty
bool empty(void) const
Test whether queue is empty.
Definition dynamic-queue.hpp:122
Gecode::Support::DynamicQueue::DynamicQueue
DynamicQueue(A &a)
Initialize queue.
Definition dynamic-queue.hpp:111
Gecode::Support::DynamicQueue::pop
T pop(void)
Pop element added first from queue and return it.
Definition dynamic-queue.hpp:134
Gecode::Support::DynamicQueue::reset
void reset(void)
Reset queue to be empty.
Definition dynamic-queue.hpp:128
Gecode::Support
Support algorithms and datastructures
Gecode
Gecode toplevel namespace
Test::Float::Arithmetic::a
Gecode::FloatVal a(-8, 5)
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
forceinline
#define forceinline
Definition config.hpp:187