dynamic-stack.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, 2002
*
* 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 DynamicStack {
private:
A& a;
int limit;
int tos;
T* stack;
void resize(void);
public:
DynamicStack(A& a, int n=64);
~DynamicStack(void);
bool empty(void) const;
int entries(void) const;
T pop(void);
T& top(void) const;
T& last(void) const;
void push(const T& x);
T& operator [](int i);
const T& operator [](int i) const;
private:
static void* operator new(size_t s) throw() { (void) s; return NULL; }
static void operator delete(void* p) { (void) p; };
DynamicStack(const DynamicStack& s) : a(s.a) {}
const DynamicStack& operator =(const DynamicStack&) { return *this; }
};
template<class T, class A>
void
DynamicStack<T,A>::resize(void) {
int nl = (limit * 3) / 2;
stack = a.template realloc<T>(stack,limit,nl);
limit = nl;
}
template<class T, class A>
forceinline
DynamicStack<T,A>::DynamicStack(A& a0, int n)
: a(a0), limit(n), tos(0), stack(a.template alloc<T>(n)) {}
template<class T, class A>
forceinline
DynamicStack<T,A>::~DynamicStack(void) {
a.free(stack,limit);
}
template<class T, class A>
forceinline T
DynamicStack<T,A>::pop(void) {
return stack[--tos];
}
template<class T, class A>
forceinline T&
DynamicStack<T,A>::top(void) const {
return stack[tos-1];
}
template<class T, class A>
forceinline T&
DynamicStack<T,A>::last(void) const {
return stack[tos];
}
template<class T, class A>
forceinline void
DynamicStack<T,A>::push(const T& x) {
stack[tos++] = x;
if (tos==limit)
resize();
}
template<class T, class A>
forceinline bool
DynamicStack<T,A>::empty(void) const {
return tos==0;
}
template<class T, class A>
forceinline int
DynamicStack<T,A>::entries(void) const {
return tos;
}
template<class T, class A>
forceinline T&
DynamicStack<T,A>::operator [](int i) {
return stack[i];
}
template<class T, class A>
forceinline const T&
DynamicStack<T,A>::operator [](int i) const {
return stack[i];
}
}}
// STATISTICS: support-any
Gecode::Support::DynamicStack::push
void push(const T &x)
Push element x on top of stack.
Definition dynamic-stack.hpp:140
Gecode::Support::DynamicStack::DynamicStack
DynamicStack(A &a, int n=64)
Initialize stack with n elements.
Definition dynamic-stack.hpp:111
Gecode::Support::DynamicStack::entries
int entries(void) const
Return number of entries currently on stack.
Definition dynamic-stack.hpp:154
Gecode::Support::DynamicStack::empty
bool empty(void) const
Test whether stack is empty.
Definition dynamic-stack.hpp:148
Gecode::Support::DynamicStack::~DynamicStack
~DynamicStack(void)
Release memory.
Definition dynamic-stack.hpp:116
Gecode::Support::DynamicStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition dynamic-stack.hpp:122
Gecode::Support::DynamicStack::last
T & last(void) const
Return element that has just been popped.
Definition dynamic-stack.hpp:134
Gecode::Support::DynamicStack::top
T & top(void) const
Return element on top of stack.
Definition dynamic-stack.hpp:128
Gecode::Support::DynamicStack::operator[]
T & operator[](int i)
Return entry at position i.
Definition dynamic-stack.hpp:160
Gecode::Support
Support algorithms and datastructures
Gecode
Gecode toplevel namespace
Test::Float::Arithmetic::a
Gecode::FloatVal a(-8, 5)
forceinline
#define forceinline
Definition config.hpp:187