Go to the documentation of this file.
45 namespace Gecode {
namespace Gist {
186 p =
p->getParent(na);
190 std::vector<std::pair<VisualNode*,int> >
path;
193 path.push_back(std::pair<VisualNode*,int>(
p,
p->getAlternative(na)));
194 p =
p->getParent(na);
196 while (!
path.empty()) {
197 std::pair<VisualNode*,int> cur =
path.back();
path.pop_back();
200 cur.first->getBranchLabel(na,
p,
p->getChoice(),
201 curBest,
c_d,
a_d,cur.second);
202 na.
setLabel(cur.first,QString(
l.c_str()));
245 if (
getShape()->getExtentAtDepth(depth, theExtent)) {
246 return (theExtent.
l <=
x &&
x <= theExtent.
r);
257 while (depth > 0 && cur != NULL) {
291 std::ostringstream oss;
292 p->acquireSpace(na,curBest,
c_d,
a_d);
293 p->getWorkingSpace()->print(*
c,alt,oss);
302 template<
class S1,
class S2>
303 static int getAlpha(
const S1& shape1,
int depth1,
304 const S2& shape2,
int depth2);
306 template<
class S1,
class S2>
308 const S1& shape1,
int depth1,
309 const S2& shape2,
int depth2,
int alpha);
312 template<
class S1,
class S2>
315 const S2& shape2,
int depth2) {
319 for (
int i=0;
i<depth1 &&
i<depth2;
i++) {
320 extentR += shape1[
i].r;
321 extentL += shape2[
i].l;
327 template<
class S1,
class S2>
330 const S1& shape1,
int depth1,
331 const S2& shape2,
int depth2,
int alpha) {
333 for (
int i=depth2;
i--;)
334 result[
i] = shape2[
i];
335 }
else if (depth2 == 0) {
336 for (
int i=depth1;
i--;)
337 result[
i] = shape1[
i];
341 int topmostL = shape1[0].
l;
342 int topmostR = shape2[0].r;
344 shape1[0].r - alpha - shape2[0].r;
346 shape2[0].l + alpha - shape1[0].l;
348 result[0] =
Extent(topmostL, topmostR+alpha);
356 for (;
i<depth1 &&
i<depth2;
i++) {
357 Extent currentExtent1 = shape1[
i];
358 Extent currentExtent2 = shape2[
i];
359 int newExtentL = currentExtent1.
l;
360 int newExtentR = currentExtent2.
r;
361 result[
i] =
Extent(newExtentL, newExtentR);
362 backoffTo1 += currentExtent1.
r - currentExtent2.
r;
363 backoffTo2 += currentExtent2.
l - currentExtent1.
l;
369 Extent currentExtent1 = shape1[
i];
370 int newExtentL = currentExtent1.
l;
371 int newExtentR = currentExtent1.
r;
372 result[
i] =
Extent(newExtentL, newExtentR+backoffTo1);
374 for (;
i<depth1;
i++) {
375 result[
i] = shape1[
i];
382 Extent currentExtent2 = shape2[
i];
383 int newExtentL = currentExtent2.
l;
384 int newExtentR = currentExtent2.
r;
385 result[
i] =
Extent(newExtentL+backoffTo2, newExtentR);
387 for (;
i<depth2;
i++) {
388 result[
i] = shape2[
i];
414 n_alt =
p->getNumberOfChildren();
417 if (alt==0 && n_alt > 1) {
419 }
else if (alt==n_alt-1 && n_alt > 1) {
426 if (numberOfShapes==0) {
435 for (
int i = numberOfShapes;
i--;)
439 getShape()->depth() >= maxDepth+1) {
445 (*mergedShape)[0] = extent;
446 if (numberOfShapes < 1) {
448 }
else if (numberOfShapes == 1) {
451 for (
int i=childShape->
depth();
i--;)
452 (*mergedShape)[
i+1] = (*childShape)[
i];
453 (*mergedShape)[1].extend(- extent.
l, - extent.
r);
462 assert(root->
copy != NULL);
464 std::pair<int,int>* alpha =
465 r.alloc<std::pair<int,int> >(numberOfShapes);
471 int ldepth =
getChild(na,0)->getShape()->depth();
472 for (
int i=ldepth;
i--;)
478 int rdepth = rShape->
depth();
479 for (
int i=rdepth;
i--;)
480 (*mergedShape)[
i+1] = (*rShape)[
i];
481 Extent* currentShapeR = &(*mergedShape)[1];
483 for (
int i = 1;
i < numberOfShapes;
i++) {
493 Layouter::getAlpha<Extent*,Shape>(¤tShapeL[0], ldepth,
494 *nextShapeL, nextShapeL->
depth());
495 Layouter::merge<Extent*,Shape>(¤tShapeL[0],
496 ¤tShapeL[0], ldepth,
497 *nextShapeL, nextShapeL->
depth(),
500 alpha[
i].first = nextAlphaL - width;
507 Layouter::getAlpha<Shape,Extent*>(*nextShapeR, nextShapeR->
depth(),
508 ¤tShapeR[0], rdepth);
509 Layouter::merge<Shape,Extent*>(¤tShapeR[0],
510 *nextShapeR, nextShapeR->
depth(),
511 ¤tShapeR[0], rdepth,
514 alpha[numberOfShapes -
i].second = nextAlphaR;
518 (*mergedShape)[1].extend(- extent.
l, - extent.
r);
524 int halfWidth =
false ? 0 : width / 2;
525 (*mergedShape)[1].move(- halfWidth);
535 for (
int i = 1;
i < numberOfShapes;
i++) {
536 offset += (alpha[
i].first + alpha[
i].second) / 2;
int getOffset(void)
Return offset off this node from its parent.
Post propagator for SetVar x
VisualNode * findNode(const NodeAllocator &na, int x, int y)
Find a node in this subtree at coordinates x, y.
Post propagator for SetVar SetOpType SetVar y
void dirtyUp(const NodeAllocator &na)
Mark all nodes up the path to the parent as dirty.
QString getLabel(T *n) const
Get label of node n.
Shape * shape
Shape of this node.
int right
Right coordinate.
void computeBoundingBox(void)
Compute bounding box.
@ STOP
Node representing stop point.
void setShape(Shape *s)
Set the shape of this node.
void pathUp(const NodeAllocator &na)
Set all nodes from the node to the root to be on the path.
long long int ll(int x)
Cast x into a long long int.
Node class that supports visual layout
static const int minimalSeparation
A cursor that computes a tree layout for VisualNodes.
void setBookmarked(bool m)
Set bookmark of this node.
void hideFailed(const NodeAllocator &na, bool onlyDirty=false)
Hide all failed subtrees of this node.
NodeStatus getStatus(void) const
Return current status of the node.
int getPathAlternative(const NodeAllocator &na)
Return the alternative of the child that is on the path (-1 if none)
Allocate shapes statically.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void dispose(void)
Free allocated memory.
const FloatNum min
Smallest allowed float value.
bool isOnPath(void)
Return whether node is on the path.
void run(void)
Execute visitor.
void changedStatus(const NodeAllocator &na)
Signal that the status has changed.
bool isRoot(void) const
Check if this node is the root of a tree.
bool hasLabel(T *n) const
Return whether node n has a label.
static Shape * allocate(int d)
Construct shape of depth d.
Gecode toplevel namespace
std::string toolTip(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Return string that is used as a tool tip.
bool containsCoordinateAtDepth(int x, int depth)
Check if the x at depth depth lies in this subtree.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
void toggleStop(const NodeAllocator &na)
Do not stop at this node.
void setDirty(bool d)
Mark node as dirty.
void clearLabel(T *n)
Remove label of node n.
void unhideAll(const NodeAllocator &na)
Unhide all nodes in the subtree of this node.
void layout(const NodeAllocator &na)
Compute layout for the subtree of this node.
Post propagator for SetVar SetOpType SetVar SetRelType r
Space * copy
A copy used for recomputation, or NULL.
void setMarked(bool m)
Set mark of this node.
void toggleHidden(const NodeAllocator &na)
Toggle whether this node is hidden.
Static reference to the currently best space.
const BoundingBox & getBoundingBox(void) const
Return bounding box.
A cursor that marks all nodes in the tree as not stopping.
int getChild(int n) const
Return index of child no n.
bool isDirty(void)
Return whether node is marked as dirty.
void setOnPath(bool onPath0)
Set whether node is on the path.
static int getAlpha(const S1 &shape1, int depth1, const S2 &shape2, int depth2)
Compute distance needed between shape1 and shape2.
VisualNode(int p)
Construct with parent p.
static void merge(Extent *result, const S1 &shape1, int depth1, const S2 &shape2, int depth2, int alpha)
Merge shape1 and shape2 into result with distance alpha.
int getParent(void) const
Return the parent.
void computeShape(const NodeAllocator &na, VisualNode *root)
Compute the shape according to the shapes of the children.
void run(void)
Execute visitor.
A cursor that labels branches.
void dispose(void)
Free allocated memory.
void setChildrenLayoutDone(bool d)
Mark node whether the layout of the node's children has been completed.
A cursor that marks failed subtrees as hidden.
unsigned int getNumberOfChildren(void) const
Return the number of children.
A cursor that marks all nodes in the tree as not hidden.
bool isHidden(void)
Return if node is hidden.
int offset
Relative offset from the parent node.
void labelBranches(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Create or clear branch labels in subtree.
void unstopAll(const NodeAllocator &na)
Do not stop at any stop node in the subtree of this node.
void setHidden(bool h)
Set hidden state to h.
A node of a search tree of Gecode spaces.
static Shape * hidden
Static shape for hidden nodes.
ShapeAllocator(void)
Constructor.
static Shape * leaf
Static shape for leaf nodes.
void labelPath(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Create or clear branch labels on path to root.
void setDepth(int d)
Set depth of the shape to d (must be smaller than original depth)
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path.
Run a cursor over a tree, processing nodes in pre-order.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Helper functions for the layout algorithm.
static void deallocate(Shape *)
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
void setStatus(NodeStatus s)
Set status to s.
Gecode::FloatVal c(-8, 8)
@ UNSTOP
Node representing ignored stop point.
std::string getBranchLabel(NodeAllocator &na, VisualNode *p, const Choice *c, BestNode *curBest, int c_d, int a_d, int alt)
Return string that describes the branch.
Choice for performing commit
void unPathUp(const NodeAllocator &na)
Set all nodes from the node to the root not to be on the path.
Shape * getShape(void)
Return the shape of this node.
Extent representing shape of a tree at one depth level
int depth(void) const
Return depth of the shape.
int p
Number of positive literals for node type.
ShapeAllocator shapeAllocator
Allocate shapes statically.
const FloatNum max
Largest allowed float value.
void setLabel(T *n, const QString &l)
Set label of node n to l.
Run a cursor over a tree, processing nodes in post-order.