45 namespace Gecode {
namespace Gist {
57 Shape::leaf->computeBoundingBox();
62 Shape::hidden->computeBoundingBox();
190 std::vector<std::pair<VisualNode*,int> >
path;
193 path.push_back(std::pair<VisualNode*,int>(p,p->
getAlternative(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;
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];
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(),
499 ldepth =
std::max(ldepth,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,
513 rdepth =
std::max(rdepth,nextShapeR->depth());
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;
A cursor that computes a tree layout for VisualNodes.
bool isOnPath(void)
Return whether node is on the path.
Node representing stop point.
std::string toolTip(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Return string that is used as a tool tip.
void unhideAll(const NodeAllocator &na)
Unhide all nodes in the subtree of this node.
int right
Right coordinate.
void labelPath(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Create or clear branch labels on path to root.
void setOnPath(bool onPath0)
Set whether node is on the path.
void setMarked(bool m)
Set mark of this node.
void dispose(void)
Free allocated memory.
Static reference to the currently best space.
const FloatNum max
Largest allowed float value.
void setLabel(T *n, const QString &l)
Set label of node n to l.
void computeBoundingBox(void)
Compute bounding box.
bool isDirty(void)
Return whether node is marked as dirty.
void layout(const NodeAllocator &na)
Compute layout for the subtree of this node.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
bool isHidden(void)
Return if node is hidden.
long long int ll(int x)
Cast x into a long long int.
void setChildrenLayoutDone(bool d)
Mark node whether the layout of the node's children has been completed.
void setDirty(bool d)
Mark node as dirty.
unsigned int getNumberOfChildren(void) const
Return the number of children.
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntConLevel icl)
Post propagator such that x forms a Hamiltonian path.
int offset
Relative offset from the parent node.
A cursor that marks failed subtrees as hidden.
void setHidden(bool h)
Set hidden state to h.
const Space * getWorkingSpace(void) const
Return working space (if present).
static Shape * allocate(int d)
Construct shape of depth d.
void toggleStop(const NodeAllocator &na)
Do not stop at this node.
void setBookmarked(bool m)
Set bookmark of this node.
void setStatus(NodeStatus s)
Set status to s.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
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 acquireSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Acquire working space, either from parent or by recomputation.
Run a cursor over a tree, processing nodes in post-order.
void labelBranches(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Create or clear branch labels in subtree.
Gecode::FloatVal c(-8, 8)
void unstopAll(const NodeAllocator &na)
Do not stop at any stop node in the subtree of this node.
const Choice * getChoice(void)
Return choice of this node.
int getParent(void) const
Return the parent.
NodeStatus getStatus(void) const
Return current status of the node.
QString getLabel(T *n) const
Get label of node n.
int p
Number of positive literals for node type.
bool isRoot(void) const
Check if this node is the root of a tree.
const FloatNum min
Smallest allowed float value.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Helper functions for the layout algorithm.
void clearLabel(T *n)
Remove label of node n.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
ShapeAllocator(void)
Constructor.
A cursor that marks all nodes in the tree as not stopping.
int getPathAlternative(const NodeAllocator &na)
Return the alternative of the child that is on the path (-1 if none)
void changedStatus(const NodeAllocator &na)
Signal that the status has changed.
Shape * getShape(void)
Return the shape of this node.
int depth(void) const
Return depth of the shape.
Node * x
Pointer to corresponding Boolean expression node.
Choice for performing commit
void dirtyUp(const NodeAllocator &na)
Mark all nodes up the path to the parent as dirty.
Run a cursor over a tree, processing nodes in pre-order.
static Shape * hidden
Static shape for hidden nodes.
Shape * shape
Shape of this node.
ShapeAllocator shapeAllocator
Allocate shapes statically.
void toggleHidden(const NodeAllocator &na)
Toggle whether this node is hidden.
A cursor that marks all nodes in the tree as not hidden.
const BoundingBox & getBoundingBox(void) const
Return bounding box.
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.
void unPathUp(const NodeAllocator &na)
Set all nodes from the node to the root not to be on the path.
Node class that supports visual layout
int getOffset(void)
Return offset off this node from its parent.
void dispose(void)
Free allocated memory.
Allocate shapes statically.
VisualNode * findNode(const NodeAllocator &na, int x, int y)
Find a node in this subtree at coordinates x, y.
VisualNode(int p)
Construct with parent p.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
void computeShape(const NodeAllocator &na, VisualNode *root)
Compute the shape according to the shapes of the children.
static void deallocate(Shape *)
A node of a search tree of Gecode spaces.
static int getAlpha(const S1 &shape1, int depth1, const S2 &shape2, int depth2)
Compute distance needed between shape1 and shape2.
Space * copy
A copy used for recomputation, or NULL.
void pathUp(const NodeAllocator &na)
Set all nodes from the node to the root to be on the path.
static Shape * leaf
Static shape for leaf nodes.
Gecode toplevel namespace
void setDepth(int d)
Set depth of the shape to d (must be smaller than original depth)
int getChild(int n) const
Return index of child no n.
bool containsCoordinateAtDepth(int x, int depth)
Check if the x at depth depth lies in this subtree.
bool hasLabel(T *n) const
Return whether node n has a label.
void setShape(Shape *s)
Set the shape of this node.
Extent representing shape of a tree at one depth level
A cursor that labels branches.
static const int minimalSeparation
void hideFailed(const NodeAllocator &na, bool onlyDirty=false)
Hide all failed subtrees of this node.
Node representing ignored stop point.