this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 *
6 * Copyright:
7 * Guido Tack, 2006
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/gist/visualnode.hh>
35
36#include <gecode/gist/layoutcursor.hh>
37#include <gecode/gist/nodevisitor.hh>
38
39#include <utility>
40
41namespace Gecode { namespace Gist {
42
43 Shape* Shape::leaf;
44 Shape* Shape::hidden;
45
46 /// Allocate shapes statically
47 class ShapeAllocator {
48 public:
49 /// Constructor
50 ShapeAllocator(void) {
51 Shape::leaf = Shape::allocate(1);
52 (*Shape::leaf)[0] = Extent(Layout::extent);
53 Shape::leaf->computeBoundingBox();
54
55 Shape::hidden = Shape::allocate(2);
56 (*Shape::hidden)[0] = Extent(Layout::extent);
57 (*Shape::hidden)[1] = Extent(Layout::extent);
58 Shape::hidden->computeBoundingBox();
59 }
60 ~ShapeAllocator(void) {
61 Shape::deallocate(Shape::leaf);
62 Shape::deallocate(Shape::hidden);
63 }
64 };
65
66 /// Allocate shapes statically
67 ShapeAllocator shapeAllocator;
68
69 VisualNode::VisualNode(int p)
70 : SpaceNode(p)
71 , offset(0)
72 {
73 shape = nullptr;
74 setDirty(true);
75 setChildrenLayoutDone(false);
76 setHidden(false);
77 setMarked(false);
78 setOnPath(false);
79 setBookmarked(false);
80 }
81
82 VisualNode::VisualNode(Space* root)
83 : SpaceNode(root)
84 , offset(0)
85 {
86 shape = nullptr;
87 setDirty(true);
88 setChildrenLayoutDone(false);
89 setHidden(false);
90 setMarked(false);
91 setOnPath(false);
92 setBookmarked(false);
93 }
94
95 void
96 VisualNode::dispose(void) {
97 Shape::deallocate(shape);
98 SpaceNode::dispose();
99 }
100
101 void
102 VisualNode::dirtyUp(const NodeAllocator& na) {
103 VisualNode* cur = this;
104 while (!cur->isDirty()) {
105 cur->setDirty(true);
106 if (! cur->isRoot()) {
107 cur = cur->getParent(na);
108 }
109 }
110 }
111
112 void
113 VisualNode::layout(const NodeAllocator& na) {
114 LayoutCursor l(this,na);
115 PostorderNodeVisitor<LayoutCursor>(l).run();
116 // int nodesLayouted = 1;
117 // clock_t t0 = clock();
118 // while (p.next()) {}
119 // while (p.next()) { nodesLayouted++; }
120 // double t = (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
121 // double nps = static_cast<double>(nodesLayouted) /
122 // (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC);
123 // std::cout << "Layout done. " << nodesLayouted << " nodes in "
124 // << t << " ms. " << nps << " nodes/s." << std::endl;
125 }
126
127 void VisualNode::pathUp(const NodeAllocator& na) {
128 VisualNode* cur = this;
129 while (cur) {
130 cur->setOnPath(true);
131 cur = cur->getParent(na);
132 }
133 }
134
135 void VisualNode::unPathUp(const NodeAllocator& na) {
136 VisualNode* cur = this;
137 while (!cur->isRoot()) {
138 cur->setOnPath(false);
139 cur = cur->getParent(na);
140 }
141 }
142
143 int
144 VisualNode::getPathAlternative(const NodeAllocator& na) {
145 for (int i=getNumberOfChildren(); i--;) {
146 if (getChild(na,i)->isOnPath())
147 return i;
148 }
149 return -1;
150 }
151
152 void
153 VisualNode::toggleHidden(const NodeAllocator& na) {
154 setHidden(!isHidden());
155 dirtyUp(na);
156 }
157
158 void
159 VisualNode::hideFailed(const NodeAllocator& na, bool onlyDirty) {
160 HideFailedCursor c(this,na,onlyDirty);
161 PreorderNodeVisitor<HideFailedCursor>(c).run();
162 dirtyUp(na);
163 }
164
165 void
166 VisualNode::labelBranches(NodeAllocator& na,
167 BestNode* curBest, int c_d, int a_d) {
168 bool clear = na.hasLabel(this);
169 BranchLabelCursor c(this,curBest,c_d,a_d,clear,na);
170 PreorderNodeVisitor<BranchLabelCursor>(c).run();
171 dirtyUp(na);
172 }
173
174 void
175 VisualNode::labelPath(NodeAllocator& na,
176 BestNode* curBest, int c_d, int a_d) {
177 if (na.hasLabel(this)) {
178 // clear labels on path to root
179 VisualNode* p = this;
180 while (p) {
181 na.clearLabel(p);
182 p = p->getParent(na);
183 }
184 } else {
185 // set labels on path to root
186 std::vector<std::pair<VisualNode*,int> > path;
187 VisualNode* p = this;
188 while (p) {
189 path.push_back(std::pair<VisualNode*,int>(p,p->getAlternative(na)));
190 p = p->getParent(na);
191 }
192 while (!path.empty()) {
193 std::pair<VisualNode*,int> cur = path.back(); path.pop_back();
194 if (p) {
195 std::string l =
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()));
199 }
200 p = cur.first;
201 }
202 }
203 dirtyUp(na);
204 }
205
206 void
207 VisualNode::unhideAll(const NodeAllocator& na) {
208 UnhideAllCursor c(this,na);
209 PreorderNodeVisitor<UnhideAllCursor>(c).run();
210 dirtyUp(na);
211 }
212
213 void
214 VisualNode::toggleStop(const NodeAllocator& na) {
215 if (getStatus() == STOP)
216 setStatus(UNSTOP);
217 else if (getStatus() == UNSTOP)
218 setStatus(STOP);
219 dirtyUp(na);
220 }
221
222 void
223 VisualNode::unstopAll(const NodeAllocator& na) {
224 UnstopAllCursor c(this,na);
225 PreorderNodeVisitor<UnstopAllCursor>(c).run();
226 dirtyUp(na);
227 }
228
229 void
230 VisualNode::changedStatus(const NodeAllocator& na) { dirtyUp(na); }
231
232 bool
233 VisualNode::containsCoordinateAtDepth(int x, int depth) {
234 BoundingBox box = getShape()->getBoundingBox();
235 if (x < box.left ||
236 x > box.right ||
237 depth >= getShape()->depth()) {
238 return false;
239 }
240 Extent theExtent;
241 if (getShape()->getExtentAtDepth(depth, theExtent)) {
242 return (theExtent.l <= x && x <= theExtent.r);
243 } else {
244 return false;
245 }
246 }
247
248 VisualNode*
249 VisualNode::findNode(const NodeAllocator& na, int x, int y) {
250 VisualNode* cur = this;
251 int depth = y / Layout::dist_y;
252
253 while (depth > 0 && cur != nullptr) {
254 if (cur->isHidden()) {
255 break;
256 }
257 VisualNode* oldCur = cur;
258 cur = nullptr;
259 for (unsigned int i=0; i<oldCur->getNumberOfChildren(); i++) {
260 VisualNode* nextChild = oldCur->getChild(na,i);
261 int newX = x - nextChild->getOffset();
262 if (nextChild->containsCoordinateAtDepth(newX, depth - 1)) {
263 cur = nextChild;
264 x = newX;
265 break;
266 }
267 }
268 depth--;
269 y -= Layout::dist_y;
270 }
271
272 if(cur == this && !cur->containsCoordinateAtDepth(x, 0)) {
273 return nullptr;
274 }
275 return cur;
276 }
277
278 std::string
279 VisualNode::toolTip(NodeAllocator&, BestNode*, int, int) {
280 return "";
281 }
282
283 std::string
284 VisualNode::getBranchLabel(NodeAllocator& na,
285 VisualNode* p, const Choice* c,
286 BestNode* curBest, int c_d, int a_d, int alt) {
287 std::ostringstream oss;
288 p->acquireSpace(na,curBest,c_d,a_d);
289 p->getWorkingSpace()->print(*c,alt,oss);
290 return oss.str();
291 }
292
293
294 /// \brief Helper functions for the layout algorithm
295 class Layouter {
296 public:
297 /// Compute distance needed between \a shape1 and \a shape2
298 template<class S1, class S2>
299 static int getAlpha(const S1& shape1, int depth1,
300 const S2& shape2, int depth2);
301 /// Merge \a shape1 and \a shape2 into \a result with distance \a alpha
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);
306 };
307
308 template<class S1, class S2>
309 int
310 Layouter::getAlpha(const S1& shape1, int depth1,
311 const S2& shape2, int depth2) {
312 int alpha = Layout::minimalSeparation;
313 int extentR = 0;
314 int extentL = 0;
315 for (int i=0; i<depth1 && i<depth2; i++) {
316 extentR += shape1[i].r;
317 extentL += shape2[i].l;
318 alpha = std::max(alpha, extentR - extentL + Layout::minimalSeparation);
319 }
320 return alpha;
321 }
322
323 template<class S1, class S2>
324 void
325 Layouter::merge(Extent* result,
326 const S1& shape1, int depth1,
327 const S2& shape2, int depth2, int alpha) {
328 if (depth1 == 0) {
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];
334 } else {
335 // Extend the topmost right extent by alpha. This, in effect,
336 // moves the second shape to the right by alpha units.
337 int topmostL = shape1[0].l;
338 int topmostR = shape2[0].r;
339 int backoffTo1 =
340 shape1[0].r - alpha - shape2[0].r;
341 int backoffTo2 =
342 shape2[0].l + alpha - shape1[0].l;
343
344 result[0] = Extent(topmostL, topmostR+alpha);
345
346 // Now, since extents are given in relative units, in order to
347 // compute the extents of the merged shape, we can just collect the
348 // extents of shape1 and shape2, until one of the shapes ends. If
349 // this happens, we need to "back-off" to the axis of the deeper
350 // shape in order to properly determine the remaining extents.
351 int i=1;
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;
360 }
361
362 // If shape1 is deeper than shape2, back off to the axis of shape1,
363 // and process the remaining extents of shape1.
364 if (i<depth1) {
365 Extent currentExtent1 = shape1[i];
366 int newExtentL = currentExtent1.l;
367 int newExtentR = currentExtent1.r;
368 result[i] = Extent(newExtentL, newExtentR+backoffTo1);
369 ++i;
370 for (; i<depth1; i++) {
371 result[i] = shape1[i];
372 }
373 }
374
375 // Vice versa, if shape2 is deeper than shape1, back off to the
376 // axis of shape2, and process the remaining extents of shape2.
377 if (i<depth2) {
378 Extent currentExtent2 = shape2[i];
379 int newExtentL = currentExtent2.l;
380 int newExtentR = currentExtent2.r;
381 result[i] = Extent(newExtentL+backoffTo2, newExtentR);
382 ++i;
383 for (; i<depth2; i++) {
384 result[i] = shape2[i];
385 }
386 }
387 }
388 }
389
390 void
391 VisualNode::setShape(Shape* s) {
392 if (shape != s)
393 Shape::deallocate(shape);
394 shape = s;
395 shape->computeBoundingBox();
396 }
397
398 void
399 VisualNode::computeShape(const NodeAllocator& na) {
400 int numberOfShapes = getNumberOfChildren();
401 Extent extent;
402 if (na.hasLabel(this)) {
403 int ll = na.getLabel(this).length();
404 ll *= 7;
405 VisualNode* p = getParent(na);
406 int alt = 0;
407 int n_alt = 1;
408 if (p) {
409 alt = getAlternative(na);
410 n_alt = p->getNumberOfChildren();
411 }
412 extent = Extent(Layout::extent);
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);
417 } else {
418 extent.l = std::min(extent.l, -ll);
419 extent.r = std::max(extent.r, ll);
420 }
421 } else {
422 if (numberOfShapes==0) {
423 setShape(Shape::leaf);
424 return;
425 } else {
426 extent = Extent(Layout::extent);
427 }
428 }
429
430 int maxDepth = 0;
431 for (int i = numberOfShapes; i--;)
432 maxDepth = std::max(maxDepth, getChild(na,i)->getShape()->depth());
433 Shape* mergedShape;
434 if (getShape() && getShape() != Shape::leaf &&
435 getShape()->depth() >= maxDepth+1) {
436 mergedShape = getShape();
437 mergedShape->setDepth(maxDepth+1);
438 } else {
439 mergedShape = Shape::allocate(maxDepth+1);
440 }
441 (*mergedShape)[0] = extent;
442 if (numberOfShapes < 1) {
443 setShape(mergedShape);
444 } else if (numberOfShapes == 1) {
445 getChild(na,0)->setOffset(0);
446 const Shape* childShape = getChild(na,0)->getShape();
447 for (int i=childShape->depth(); i--;)
448 (*mergedShape)[i+1] = (*childShape)[i];
449 (*mergedShape)[1].extend(- extent.l, - extent.r);
450 setShape(mergedShape);
451 } else {
452 // alpha stores the necessary distances between the
453 // axes of the shapes in the list: alpha[i].first gives the distance
454 // between shape[i] and shape[i-1], when shape[i-1] and shape[i]
455 // are merged left-to-right; alpha[i].second gives the distance between
456 // shape[i] and shape[i+1], when shape[i] and shape[i+1] are merged
457 // right-to-left.
458 Region r;
459 std::pair<int,int>* alpha =
460 r.alloc<std::pair<int,int> >(numberOfShapes);
461
462 // distance between the leftmost and the rightmost axis in the list
463 int width = 0;
464
465 Extent* currentShapeL = r.alloc<Extent>(maxDepth);
466 int ldepth = getChild(na,0)->getShape()->depth();
467 for (int i=ldepth; i--;)
468 currentShapeL[i] = (*getChild(na,0)->getShape())[i];
469
470 // After merging, we can pick the result of either merging left or right
471 // Here we chose the result of merging right
472 Shape* rShape = getChild(na,numberOfShapes-1)->getShape();
473 int rdepth = rShape->depth();
474 for (int i=rdepth; i--;)
475 (*mergedShape)[i+1] = (*rShape)[i];
476 Extent* currentShapeR = &(*mergedShape)[1];
477
478 for (int i = 1; i < numberOfShapes; i++) {
479 // Merge left-to-right. Note that due to the asymmetry of the
480 // merge operation, nextAlphaL is the distance between the
481 // *leftmost* axis in the shape list, and the axis of
482 // nextShapeL; what we are really interested in is the distance
483 // between the *previous* axis and the axis of nextShapeL.
484 // This explains the correction.
485
486 Shape* nextShapeL = getChild(na,i)->getShape();
487 int nextAlphaL =
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(),
493 nextAlphaL);
494 ldepth = std::max(ldepth,nextShapeL->depth());
495 alpha[i].first = nextAlphaL - width;
496 width = nextAlphaL;
497
498 // Merge right-to-left. Here, a correction of nextAlphaR is
499 // not required.
500 Shape* nextShapeR = getChild(na,numberOfShapes-1-i)->getShape();
501 int nextAlphaR =
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,
507 nextAlphaR);
508 rdepth = std::max(rdepth,nextShapeR->depth());
509 alpha[numberOfShapes - i].second = nextAlphaR;
510 }
511
512 // The merged shape has to be adjusted to its topmost extent
513 (*mergedShape)[1].extend(- extent.l, - extent.r);
514
515 // After the loop, the merged shape has the same axis as the
516 // leftmost shape in the list. What we want is to move the axis
517 // such that it is the center of the axis of the leftmost shape in
518 // the list and the axis of the rightmost shape.
519 int halfWidth = false ? 0 : width / 2;
520 (*mergedShape)[1].move(- halfWidth);
521
522 // Finally, for the offset lists. Now that the axis of the merged
523 // shape is at the center of the two extreme axes, the first shape
524 // needs to be offset by -halfWidth units with respect to the new
525 // axis. As for the offsets for the other shapes, we take the
526 // median of the alphaL and alphaR values, as suggested in
527 // Kennedy's paper.
528 int offset = - halfWidth;
529 getChild(na,0)->setOffset(offset);
530 for (int i = 1; i < numberOfShapes; i++) {
531 offset += (alpha[i].first + alpha[i].second) / 2;
532 getChild(na,i)->setOffset(offset);
533 }
534 setShape(mergedShape);
535 }
536 }
537
538}}
539
540// STATISTICS: gist-any