Go to the documentation of this file.
41 namespace Gecode {
namespace Gist {
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) {
287 std::ostringstream oss;
288 p->acquireSpace(na,curBest,
c_d,
a_d);
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];
410 n_alt =
p->getNumberOfChildren();
413 if (alt==0 && n_alt > 1) {
415 }
else if (alt==n_alt-1 && n_alt > 1) {
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++) {
488 Layouter::getAlpha<Extent*,Shape>(¤tShapeL[0], ldepth,
489 *nextShapeL, nextShapeL->
depth());
490 Layouter::merge<Extent*,Shape>(¤tShapeL[0],
491 ¤tShapeL[0], ldepth,
492 *nextShapeL, nextShapeL->
depth(),
495 alpha[
i].first = nextAlphaL - width;
502 Layouter::getAlpha<Shape,Extent*>(*nextShapeR, nextShapeR->
depth(),
503 ¤tShapeR[0], rdepth);
504 Layouter::merge<Shape,Extent*>(¤tShapeR[0],
505 *nextShapeR, nextShapeR->
depth(),
506 ¤tShapeR[0], rdepth,
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 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.
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.
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.
void computeShape(const NodeAllocator &na)
Compute the shape according to the shapes of the children.
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
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 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)
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
Gecode::IntArgs i({1, 2, 3, 4})
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.