34 namespace Gecode {
namespace Gist {
38 NodeAllocatorBase<T>::allocate(
void) {
43 n =
static_cast<int>(
n*1.5+1.0);
46 b[cur_b] =
static_cast<Block*
>(
heap.
ralloc(
sizeof(Block)));
55 cur_t = NodeBlockSize-1;
60 for (
int i=cur_b+1;
i--;)
69 if (cur_t==NodeBlockSize)
71 new (&b[cur_b]->b[cur_t]) T(p);
72 b[cur_b]->best[cur_t] = -1;
73 return cur_b*NodeBlockSize+cur_t;
80 if (cur_t==NodeBlockSize)
82 new (&b[cur_b]->b[cur_t]) T(root);
83 b[cur_b]->best[cur_t] = -1;
84 return cur_b*NodeBlockSize+cur_t;
90 assert(i/NodeBlockSize < n);
91 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
92 return &(b[i/NodeBlockSize]->b[i%NodeBlockSize]);
98 assert(i/NodeBlockSize < n);
99 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
100 int bi = b[i/NodeBlockSize]->best[i%NodeBlockSize];
101 return bi == -1 ? NULL : (*this)[
bi];
107 assert(i/NodeBlockSize < n);
108 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
109 b[i/NodeBlockSize]->best[i%NodeBlockSize] =
best;
121 return !labels.isEmpty();
127 return labels.contains(n);
145 return labels.value(n);
149 Node::getTag(
void)
const {
150 return static_cast<unsigned int> 151 (
reinterpret_cast<ptrdiff_t
>(childrenOrFirstChild) & 3);
155 Node::setTag(
unsigned int tag) {
157 assert(getTag() == UNDET);
158 childrenOrFirstChild =
reinterpret_cast<void*
> 159 ( (
reinterpret_cast<ptrdiff_t
>(childrenOrFirstChild) & ~(3)) | tag);
163 Node::getPtr(
void)
const {
164 return reinterpret_cast<void*
> 165 (
reinterpret_cast<ptrdiff_t
>(childrenOrFirstChild) & ~(3));
169 Node::getFirstChild(
void)
const {
170 return static_cast<int> 171 ((
reinterpret_cast<ptrdiff_t
>(childrenOrFirstChild) & ~(3)) >> 2);
176 childrenOrFirstChild = NULL;
178 setTag(failed ? LEAF : UNDET);
188 return parent < 0 ? NULL : na[parent];
196 assert(getTag() != UNDET && getTag() != LEAF);
197 if (getTag() == TWO_CHILDREN) {
198 assert(n != 1 || noOfChildren <= 0);
199 return n == 0 ? getFirstChild() : -noOfChildren;
201 assert(n < noOfChildren);
202 return static_cast<int*
>(getPtr())[n];
220 return (noOfChildren <= 0) ? 2 : 1;
222 return static_cast<unsigned int>(noOfChildren);
230 Node*
p = na[parent];
QString getLabel(T *n) const
Get label of node n.
bool isRoot(void) const
Check if this node is the root of a tree.
T * operator[](int i) const
Return node for index i.
void setLabel(T *n, const QString &l)
Set label of node n to l.
void rfree(void *p)
Free memory block starting at p.
void * ralloc(size_t s)
Allocate s bytes from heap.
Base class for nodes of the search tree.
unsigned int getNumberOfChildren(void) const
Return the number of children.
NodeAllocatorBase(bool bab)
Constructor.
int getIndex(const NodeAllocator &na) const
Return index of this node.
T * best(int i) const
Return index of best node before i.
int p
Number of positive literals for node type.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
void clearLabel(T *n)
Remove label of node n.
Node(int p, bool failed=false)
Construct node with parent p.
bool hasLabel(T *n) const
Return whether node n has a label.
void setBest(int i, int b)
Set index of best node before i to b.
~NodeAllocatorBase(void)
Destructor.
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
int getParent(void) const
Return the parent.
bool showLabels(void) const
Return branching label flag.
void free(T *b, long unsigned int n)
Delete n objects starting at b.
bool bab(void) const
Return branch-and-bound flag.
Heap heap
The single global heap.
Node class that supports visual layout
int bab(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for branch-and-bound search of root.
bool isUndetermined(void) const
Return whether this node is undetermined.
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.
int getChild(int n) const
Return index of child no n.
Gecode toplevel namespace
#define GECODE_NEVER
Assert that this command is never executed.