41 namespace Gecode {
namespace Gist {
53 Shape::leaf->computeBoundingBox();
58 Shape::hidden->computeBoundingBox();
186 std::vector<std::pair<VisualNode*,int> >
path;
189 path.push_back(std::pair<VisualNode*,int>(p,p->
getAlternative(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;
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>
303 static void merge(
Extent* result,
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];
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(),
494 ldepth =
std::max(ldepth,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,
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;
A cursor that computes a tree layout for VisualNodes.
bool isOnPath(void)
Return whether node is on the path.
Node representing stop point.
QString getLabel(T *n) const
Get label of node n.
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.
NodeStatus getStatus(void) const
Return current status of the node.
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.
bool isRoot(void) const
Check if this node is the root of a tree.
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.
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
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.
unsigned int getNumberOfChildren(void) const
Return the number of children.
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.
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 print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
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 p
Number of positive literals for node type.
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 Space * getWorkingSpace(void) const
Return working space (if present).
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
bool hasLabel(T *n) const
Return whether node n has a label.
ShapeAllocator(void)
Constructor.
A cursor that marks all nodes in the tree as not stopping.
const BoundingBox & getBoundingBox(void) const
Return bounding box.
int getPathAlternative(const NodeAllocator &na)
Return the alternative of the child that is on the path (-1 if none)
Post propagator for SetVar SetOpType SetVar SetRelType r
void changedStatus(const NodeAllocator &na)
Signal that the status has changed.
Shape * getShape(void)
Return the shape of this node.
int getParent(void) const
Return the parent.
Post propagator for SetVar SetOpType SetVar y
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.
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.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
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)
Post propagator for SetVar x
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.
void pathUp(const NodeAllocator &na)
Set all nodes from the node to the root to be on the path.
int getChild(int n) const
Return index of child no n.
static Shape * leaf
Static shape for leaf nodes.
Gecode toplevel namespace
void computeShape(const NodeAllocator &na)
Compute the shape according to the shapes of the children.
void setDepth(int d)
Set depth of the shape to d (must be smaller than original depth)
bool containsCoordinateAtDepth(int x, int depth)
Check if the x at depth depth lies in this subtree.
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.
int depth(void) const
Return depth of the shape.
Node representing ignored stop point.