41namespace Gecode {
namespace Gist {
167 BestNode* curBest,
int c_d,
int a_d) {
176 BestNode* curBest,
int c_d,
int a_d) {
182 p =
p->getParent(na);
186 std::vector<std::pair<VisualNode*,int> >
path;
189 path.push_back(std::pair<VisualNode*,int>(
p,
p->getAlternative(na)));
190 p =
p->getParent(na);
192 while (!
path.empty()) {
193 std::pair<VisualNode*,int> cur =
path.back();
path.pop_back();
196 cur.first->getBranchLabel(na,
p,
p->getChoice(),
197 curBest,c_d,a_d,cur.second);
198 na.
setLabel(cur.first,QString(
l.c_str()));
241 if (
getShape()->getExtentAtDepth(depth, theExtent)) {
242 return (theExtent.
l <=
x &&
x <= theExtent.
r);
253 while (depth > 0 && cur != NULL) {
286 BestNode* curBest,
int c_d,
int a_d,
int alt) {
287 std::ostringstream oss;
289 p->getWorkingSpace()->print(*c,alt,oss);
298 template<
class S1,
class S2>
299 static int getAlpha(
const S1& shape1,
int depth1,
300 const S2& shape2,
int depth2);
302 template<
class S1,
class S2>
304 const S1& shape1,
int depth1,
305 const S2& shape2,
int depth2,
int alpha);
308 template<
class S1,
class S2>
311 const S2& shape2,
int depth2) {
315 for (
int i=0; i<depth1 && i<depth2; i++) {
316 extentR += shape1[i].r;
317 extentL += shape2[i].l;
323 template<
class S1,
class S2>
326 const S1& shape1,
int depth1,
327 const S2& shape2,
int depth2,
int alpha) {
329 for (
int i=depth2; i--;)
330 result[i] = shape2[i];
331 }
else if (depth2 == 0) {
332 for (
int i=depth1; i--;)
333 result[i] = shape1[i];
337 int topmostL = shape1[0].l;
338 int topmostR = shape2[0].r;
340 shape1[0].r - alpha - shape2[0].r;
342 shape2[0].l + alpha - shape1[0].l;
344 result[0] =
Extent(topmostL, topmostR+alpha);
352 for (; i<depth1 && i<depth2; i++) {
353 Extent currentExtent1 = shape1[i];
354 Extent currentExtent2 = shape2[i];
355 int newExtentL = currentExtent1.
l;
356 int newExtentR = currentExtent2.
r;
357 result[i] =
Extent(newExtentL, newExtentR);
358 backoffTo1 += currentExtent1.
r - currentExtent2.
r;
359 backoffTo2 += currentExtent2.
l - currentExtent1.
l;
365 Extent currentExtent1 = shape1[i];
366 int newExtentL = currentExtent1.
l;
367 int newExtentR = currentExtent1.
r;
368 result[i] =
Extent(newExtentL, newExtentR+backoffTo1);
370 for (; i<depth1; i++) {
371 result[i] = shape1[i];
378 Extent currentExtent2 = shape2[i];
379 int newExtentL = currentExtent2.
l;
380 int newExtentR = currentExtent2.
r;
381 result[i] =
Extent(newExtentL+backoffTo2, newExtentR);
383 for (; i<depth2; i++) {
384 result[i] = shape2[i];
403 int ll = na.
getLabel(
this).length();
410 n_alt =
p->getNumberOfChildren();
413 if (alt==0 && n_alt > 1) {
414 extent.
l = std::min(extent.
l, -ll);
415 }
else if (alt==n_alt-1 && n_alt > 1) {
416 extent.
r = std::max(extent.
r, ll);
418 extent.
l = std::min(extent.
l, -ll);
419 extent.
r = std::max(extent.
r, ll);
422 if (numberOfShapes==0) {
431 for (
int i = numberOfShapes; i--;)
435 getShape()->depth() >= maxDepth+1) {
441 (*mergedShape)[0] = extent;
442 if (numberOfShapes < 1) {
444 }
else if (numberOfShapes == 1) {
447 for (
int i=childShape->
depth(); i--;)
448 (*mergedShape)[i+1] = (*childShape)[i];
449 (*mergedShape)[1].extend(- extent.
l, - extent.
r);
459 std::pair<int,int>* alpha =
460 r.alloc<std::pair<int,int> >(numberOfShapes);
466 int ldepth =
getChild(na,0)->getShape()->depth();
467 for (
int i=ldepth; i--;)
473 int rdepth = rShape->
depth();
474 for (
int i=rdepth; i--;)
475 (*mergedShape)[i+1] = (*rShape)[i];
476 Extent* currentShapeR = &(*mergedShape)[1];
478 for (
int i = 1; i < numberOfShapes; i++) {
489 *nextShapeL, nextShapeL->
depth());
491 ¤tShapeL[0], ldepth,
492 *nextShapeL, nextShapeL->
depth(),
494 ldepth = std::max(ldepth,nextShapeL->
depth());
495 alpha[i].first = nextAlphaL - width;
500 Shape* nextShapeR =
getChild(na,numberOfShapes-1-i)->getShape();
503 ¤tShapeR[0], rdepth);
505 *nextShapeR, nextShapeR->
depth(),
506 ¤tShapeR[0], rdepth,
508 rdepth = std::max(rdepth,nextShapeR->
depth());
509 alpha[numberOfShapes - i].second = nextAlphaR;
513 (*mergedShape)[1].
extend(- extent.
l, - extent.
r);
519 int halfWidth =
false ? 0 : width / 2;
520 (*mergedShape)[1].move(- halfWidth);
530 for (
int i = 1; i < numberOfShapes; i++) {
531 offset += (alpha[i].first + alpha[i].second) / 2;
int p
Number of positive literals for node type.
Choice for performing commit
Static reference to the currently best space.
int right
Right coordinate.
A cursor that labels branches.
Extent representing shape of a tree at one depth level
void extend(int deltaL, int deltaR)
Extend extent by deltaL and deltaR.
A cursor that marks failed subtrees as hidden.
A cursor that computes a tree layout for VisualNodes.
static const int minimalSeparation
Helper functions for the layout algorithm.
static int getAlpha(const S1 &shape1, int depth1, const S2 &shape2, int depth2)
Compute distance needed between shape1 and shape2.
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.
QString getLabel(T *n) const
Get label of node n.
bool hasLabel(T *n) const
Return whether node n has a label.
void setLabel(T *n, const QString &l)
Set label of node n to l.
void clearLabel(T *n)
Remove label of node n.
unsigned int getNumberOfChildren(void) const
Return the number of children.
int getParent(void) const
Return the parent.
int getChild(int n) const
Return index of child no n.
bool isRoot(void) const
Check if this node is the root of a tree.
Run a cursor over a tree, processing nodes in post-order.
void run(void)
Execute visitor.
Run a cursor over a tree, processing nodes in pre-order.
void run(void)
Execute visitor.
Allocate shapes statically.
ShapeAllocator(void)
Constructor.
const BoundingBox & getBoundingBox(void) const
Return bounding box.
static Shape * allocate(int d)
Construct shape of depth d.
void computeBoundingBox(void)
Compute bounding box.
int depth(void) const
Return depth of the shape.
static Shape * leaf
Static shape for leaf nodes.
static Shape * hidden
Static shape for hidden nodes.
static void deallocate(Shape *)
void setDepth(int d)
Set depth of the shape to d (must be smaller than original depth)
A node of a search tree of Gecode spaces.
void setStatus(NodeStatus s)
Set status to s.
void dispose(void)
Free allocated memory.
void acquireSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Acquire working space, either from parent or by recomputation.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
NodeStatus getStatus(void) const
Return current status of the node.
A cursor that marks all nodes in the tree as not hidden.
A cursor that marks all nodes in the tree as not stopping.
Node class that supports visual layout
void unstopAll(const NodeAllocator &na)
Do not stop at any stop node in the subtree of this node.
int offset
Relative offset from the parent node.
int getPathAlternative(const NodeAllocator &na)
Return the alternative of the child that is on the path (-1 if none)
void unPathUp(const NodeAllocator &na)
Set all nodes from the node to the root not to be on the path.
void unhideAll(const NodeAllocator &na)
Unhide all nodes in the subtree of this node.
void setShape(Shape *s)
Set the shape of this node.
void setOnPath(bool onPath0)
Set whether node is on the path.
int getOffset(void)
Return offset off this node from its parent.
bool isHidden(void)
Return if node is hidden.
void toggleStop(const NodeAllocator &na)
Do not stop at this node.
void labelBranches(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Create or clear branch labels in subtree.
void setBookmarked(bool m)
Set bookmark of this node.
void computeShape(const NodeAllocator &na)
Compute the shape according to the shapes of the children.
Shape * shape
Shape of this node.
void dispose(void)
Free allocated memory.
void toggleHidden(const NodeAllocator &na)
Toggle whether this node is hidden.
void setHidden(bool h)
Set hidden state to h.
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.
void labelPath(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Create or clear branch labels on path to root.
void pathUp(const NodeAllocator &na)
Set all nodes from the node to the root to be on the path.
void dirtyUp(const NodeAllocator &na)
Mark all nodes up the path to the parent as dirty.
void changedStatus(const NodeAllocator &na)
Signal that the status has changed.
void layout(const NodeAllocator &na)
Compute layout for the subtree of this node.
void setDirty(bool d)
Mark node as dirty.
std::string toolTip(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Return string that is used as a tool tip.
VisualNode(int p)
Construct with parent p.
void hideFailed(const NodeAllocator &na, bool onlyDirty=false)
Hide all failed subtrees of this node.
VisualNode * findNode(const NodeAllocator &na, int x, int y)
Find a node in this subtree at coordinates x, y.
bool isDirty(void)
Return whether node is marked as dirty.
bool isOnPath(void)
Return whether node is on the path.
bool containsCoordinateAtDepth(int x, int depth)
Check if the x at depth depth lies in this subtree.
void setMarked(bool m)
Set mark of this node.
void setChildrenLayoutDone(bool d)
Mark node whether the layout of the node's children has been completed.
Shape * getShape(void)
Return the shape of this node.
int offset(void) const
Integer-precision integer scale view.
ShapeAllocator shapeAllocator
Allocate shapes statically.
@ UNSTOP
Node representing ignored stop point.
@ STOP
Node representing stop point.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Post propagator for SetVar SetOpType SetVar y
Post propagator for SetVar x