node.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Guido Tack, 2006
*
* 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 Gist {
template<class T>
void
NodeAllocatorBase<T>::allocate(void) {
cur_b++;
cur_t = 0;
if (cur_b==n) {
int oldn = n;
n = static_cast<int>(n*1.5+1.0);
b = heap.realloc<Block*>(b,oldn,n);
}
b[cur_b] = static_cast<Block*>(heap.ralloc(sizeof(Block)));
}
template<class T>
NodeAllocatorBase<T>::NodeAllocatorBase(bool bab)
: _bab(bab) {
b = heap.alloc<Block*>(10);
n = 10;
cur_b = -1;
cur_t = NodeBlockSize-1;
}
template<class T>
NodeAllocatorBase<T>::~NodeAllocatorBase(void) {
for (int i=cur_b+1; i--;)
heap.rfree(b[i]);
heap.free<Block*>(b,n);
}
template<class T>
forceinline int
NodeAllocatorBase<T>::allocate(int p) {
cur_t++;
if (cur_t==NodeBlockSize)
allocate();
new (&b[cur_b]->b[cur_t]) T(p);
b[cur_b]->best[cur_t] = -1;
return cur_b*NodeBlockSize+cur_t;
}
template<class T>
forceinline int
NodeAllocatorBase<T>::allocate(Space* root) {
cur_t++;
if (cur_t==NodeBlockSize)
allocate();
new (&b[cur_b]->b[cur_t]) T(root);
b[cur_b]->best[cur_t] = -1;
return cur_b*NodeBlockSize+cur_t;
}
template<class T>
forceinline T*
NodeAllocatorBase<T>::operator [](int i) const {
assert(i/NodeBlockSize < n);
assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
return &(b[i/NodeBlockSize]->b[i%NodeBlockSize]);
}
template<class T>
forceinline T*
NodeAllocatorBase<T>::best(int i) const {
assert(i/NodeBlockSize < n);
assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
int bi = b[i/NodeBlockSize]->best[i%NodeBlockSize];
return bi == -1 ? NULL : (*this)[bi];
}
template<class T>
forceinline void
NodeAllocatorBase<T>::setBest(int i, int best) {
assert(i/NodeBlockSize < n);
assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
b[i/NodeBlockSize]->best[i%NodeBlockSize] = best;
}
template<class T>
forceinline bool
NodeAllocatorBase<T>::bab(void) const {
return _bab;
}
template<class T>
forceinline bool
NodeAllocatorBase<T>::showLabels(void) const {
return !labels.isEmpty();
}
template<class T>
bool
NodeAllocatorBase<T>::hasLabel(T* n) const {
return labels.contains(n);
}
template<class T>
void
NodeAllocatorBase<T>::setLabel(T* n, const QString& l) {
labels[n] = l;
}
template<class T>
void
NodeAllocatorBase<T>::clearLabel(T* n) {
labels.remove(n);
}
template<class T>
QString
NodeAllocatorBase<T>::getLabel(T* n) const {
return labels.value(n);
}
forceinline unsigned int
Node::getTag(void) const {
return static_cast<unsigned int>
(reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & 3);
}
forceinline void
Node::setTag(unsigned int tag) {
assert(tag <= 3);
assert(getTag() == UNDET);
childrenOrFirstChild = reinterpret_cast<void*>
( (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) | tag);
}
forceinline void*
Node::getPtr(void) const {
return reinterpret_cast<void*>
(reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3));
}
forceinline int
Node::getFirstChild(void) const {
return static_cast<int>
((reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) >> 2);
}
forceinline
Node::Node(int p, bool failed) : parent(p) {
childrenOrFirstChild = NULL;
noOfChildren = 0;
setTag(failed ? LEAF : UNDET);
}
forceinline int
Node::getParent(void) const {
return parent;
}
forceinline VisualNode*
Node::getParent(const NodeAllocator& na) const {
return parent < 0 ? NULL : na[parent];
}
forceinline bool
Node::isUndetermined(void) const { return getTag() == UNDET; }
forceinline int
Node::getChild(int n) const {
assert(getTag() != UNDET && getTag() != LEAF);
if (getTag() == TWO_CHILDREN) {
assert(n != 1 || noOfChildren <= 0);
return n == 0 ? getFirstChild() : -noOfChildren;
}
assert(n < noOfChildren);
return static_cast<int*>(getPtr())[n];
}
forceinline VisualNode*
Node::getChild(const NodeAllocator& na, int n) const {
return na[getChild(n)];
}
forceinline bool
Node::isRoot(void) const { return parent == -1; }
forceinline unsigned int
Node::getNumberOfChildren(void) const {
switch (getTag()) {
case UNDET:
case LEAF:
return 0;
case TWO_CHILDREN:
return (noOfChildren <= 0) ? 2 : 1;
default:
return static_cast<unsigned int>(noOfChildren);
}
}
forceinline int
Node::getIndex(const NodeAllocator& na) const {
if (parent==-1)
return 0;
Node* p = na[parent];
for (int i=p->getNumberOfChildren(); i--;)
if (p->getChild(na,i) == this)
return p->getChild(i);
GECODE_NEVER;
return -1;
}
}}
// STATISTICS: gist-any
Gecode::Gist::NodeAllocatorBase::bab
bool bab(void) const
Return branch-and-bound flag.
Definition node.hpp:114
Gecode::Gist::NodeAllocatorBase::best
T * best(int i) const
Return index of best node before i.
Definition node.hpp:97
Gecode::Gist::NodeAllocatorBase::getLabel
QString getLabel(T *n) const
Get label of node n.
Definition node.hpp:144
Gecode::Gist::NodeAllocatorBase::showLabels
bool showLabels(void) const
Return branching label flag.
Definition node.hpp:120
Gecode::Gist::NodeAllocatorBase::operator[]
T * operator[](int i) const
Return node for index i.
Definition node.hpp:89
Gecode::Gist::NodeAllocatorBase::hasLabel
bool hasLabel(T *n) const
Return whether node n has a label.
Definition node.hpp:126
Gecode::Gist::NodeAllocatorBase::setLabel
void setLabel(T *n, const QString &l)
Set label of node n to l.
Definition node.hpp:132
Gecode::Gist::NodeAllocatorBase::setBest
void setBest(int i, int b)
Set index of best node before i to b.
Definition node.hpp:106
Gecode::Gist::NodeAllocatorBase::NodeAllocatorBase
NodeAllocatorBase(bool bab)
Constructor.
Definition node.hpp:50
Gecode::Gist::NodeAllocatorBase::clearLabel
void clearLabel(T *n)
Remove label of node n.
Definition node.hpp:138
Gecode::Gist::NodeAllocatorBase::~NodeAllocatorBase
~NodeAllocatorBase(void)
Destructor.
Definition node.hpp:59
Gecode::Gist::Node::NodeAllocator
NodeAllocatorBase< VisualNode > NodeAllocator
Definition node.hh:143
Gecode::Gist::Node::getNumberOfChildren
unsigned int getNumberOfChildren(void) const
Return the number of children.
Definition node.hpp:214
Gecode::Gist::Node::Node
Node(int p, bool failed=false)
Construct node with parent p.
Definition node.hpp:175
Gecode::Gist::Node::getParent
int getParent(void) const
Return the parent.
Definition node.hpp:182
Gecode::Gist::Node::isUndetermined
bool isUndetermined(void) const
Return whether this node is undetermined.
Definition node.hpp:192
Gecode::Gist::Node::getChild
int getChild(int n) const
Return index of child no n.
Definition node.hpp:195
Gecode::Gist::Node::isRoot
bool isRoot(void) const
Check if this node is the root of a tree.
Definition node.hpp:211
Gecode::Gist::Node::getIndex
int getIndex(const NodeAllocator &na) const
Return index of this node.
Definition node.hpp:227
Gecode::Gist::VisualNode
Node class that supports visual layout
Definition visualnode.hh:125
Gecode::Heap::realloc
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from heap.
Definition heap.hpp:482
Gecode::Heap::ralloc
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition heap.hpp:357
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Gist
The Gecode Interactive Search Tool.
Gecode
Gecode toplevel namespace
Test::Float::Arithmetic::b
Gecode::FloatVal b(9, 12)
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56