00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #include <gecode/gist/visualnode.hh>
00035
00036 #include <gecode/gist/layoutcursor.hh>
00037 #include <gecode/gist/nodevisitor.hh>
00038
00039 #include <utility>
00040
00041 namespace Gecode { namespace Gist {
00042
00043 Shape* Shape::leaf;
00044 Shape* Shape::hidden;
00045
00047 class ShapeAllocator {
00048 public:
00050 ShapeAllocator(void) {
00051 Shape::leaf = Shape::allocate(1);
00052 (*Shape::leaf)[0] = Extent(Layout::extent);
00053 Shape::leaf->computeBoundingBox();
00054
00055 Shape::hidden = Shape::allocate(2);
00056 (*Shape::hidden)[0] = Extent(Layout::extent);
00057 (*Shape::hidden)[1] = Extent(Layout::extent);
00058 Shape::hidden->computeBoundingBox();
00059 }
00060 ~ShapeAllocator(void) {
00061 Shape::deallocate(Shape::leaf);
00062 Shape::deallocate(Shape::hidden);
00063 }
00064 };
00065
00067 ShapeAllocator shapeAllocator;
00068
00069 VisualNode::VisualNode(int p)
00070 : SpaceNode(p)
00071 , offset(0)
00072 {
00073 shape = NULL;
00074 setDirty(true);
00075 setChildrenLayoutDone(false);
00076 setHidden(false);
00077 setMarked(false);
00078 setOnPath(false);
00079 setBookmarked(false);
00080 }
00081
00082 VisualNode::VisualNode(Space* root)
00083 : SpaceNode(root)
00084 , offset(0)
00085 {
00086 shape = NULL;
00087 setDirty(true);
00088 setChildrenLayoutDone(false);
00089 setHidden(false);
00090 setMarked(false);
00091 setOnPath(false);
00092 setBookmarked(false);
00093 }
00094
00095 void
00096 VisualNode::dispose(void) {
00097 Shape::deallocate(shape);
00098 SpaceNode::dispose();
00099 }
00100
00101 void
00102 VisualNode::dirtyUp(const NodeAllocator& na) {
00103 VisualNode* cur = this;
00104 while (!cur->isDirty()) {
00105 cur->setDirty(true);
00106 if (! cur->isRoot()) {
00107 cur = cur->getParent(na);
00108 }
00109 }
00110 }
00111
00112 void
00113 VisualNode::layout(const NodeAllocator& na) {
00114 LayoutCursor l(this,na);
00115 PostorderNodeVisitor<LayoutCursor>(l).run();
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125 }
00126
00127 void VisualNode::pathUp(const NodeAllocator& na) {
00128 VisualNode* cur = this;
00129 while (cur) {
00130 cur->setOnPath(true);
00131 cur = cur->getParent(na);
00132 }
00133 }
00134
00135 void VisualNode::unPathUp(const NodeAllocator& na) {
00136 VisualNode* cur = this;
00137 while (!cur->isRoot()) {
00138 cur->setOnPath(false);
00139 cur = cur->getParent(na);
00140 }
00141 }
00142
00143 int
00144 VisualNode::getPathAlternative(const NodeAllocator& na) {
00145 for (int i=getNumberOfChildren(); i--;) {
00146 if (getChild(na,i)->isOnPath())
00147 return i;
00148 }
00149 return -1;
00150 }
00151
00152 void
00153 VisualNode::toggleHidden(const NodeAllocator& na) {
00154 setHidden(!isHidden());
00155 dirtyUp(na);
00156 }
00157
00158 void
00159 VisualNode::hideFailed(const NodeAllocator& na, bool onlyDirty) {
00160 HideFailedCursor c(this,na,onlyDirty);
00161 PreorderNodeVisitor<HideFailedCursor>(c).run();
00162 dirtyUp(na);
00163 }
00164
00165 void
00166 VisualNode::labelBranches(NodeAllocator& na,
00167 BestNode* curBest, int c_d, int a_d) {
00168 bool clear = na.hasLabel(this);
00169 BranchLabelCursor c(this,curBest,c_d,a_d,clear,na);
00170 PreorderNodeVisitor<BranchLabelCursor>(c).run();
00171 dirtyUp(na);
00172 }
00173
00174 void
00175 VisualNode::labelPath(NodeAllocator& na,
00176 BestNode* curBest, int c_d, int a_d) {
00177 if (na.hasLabel(this)) {
00178
00179 VisualNode* p = this;
00180 while (p) {
00181 na.clearLabel(p);
00182 p = p->getParent(na);
00183 }
00184 } else {
00185
00186 std::vector<std::pair<VisualNode*,int> > path;
00187 VisualNode* p = this;
00188 while (p) {
00189 path.push_back(std::pair<VisualNode*,int>(p,p->getAlternative(na)));
00190 p = p->getParent(na);
00191 }
00192 while (!path.empty()) {
00193 std::pair<VisualNode*,int> cur = path.back(); path.pop_back();
00194 if (p) {
00195 std::string l =
00196 cur.first->getBranchLabel(na,p,p->getChoice(),
00197 curBest,c_d,a_d,cur.second);
00198 na.setLabel(cur.first,QString(l.c_str()));
00199 }
00200 p = cur.first;
00201 }
00202 }
00203 dirtyUp(na);
00204 }
00205
00206 void
00207 VisualNode::unhideAll(const NodeAllocator& na) {
00208 UnhideAllCursor c(this,na);
00209 PreorderNodeVisitor<UnhideAllCursor>(c).run();
00210 dirtyUp(na);
00211 }
00212
00213 void
00214 VisualNode::toggleStop(const NodeAllocator& na) {
00215 if (getStatus() == STOP)
00216 setStatus(UNSTOP);
00217 else if (getStatus() == UNSTOP)
00218 setStatus(STOP);
00219 dirtyUp(na);
00220 }
00221
00222 void
00223 VisualNode::unstopAll(const NodeAllocator& na) {
00224 UnstopAllCursor c(this,na);
00225 PreorderNodeVisitor<UnstopAllCursor>(c).run();
00226 dirtyUp(na);
00227 }
00228
00229 void
00230 VisualNode::changedStatus(const NodeAllocator& na) { dirtyUp(na); }
00231
00232 bool
00233 VisualNode::containsCoordinateAtDepth(int x, int depth) {
00234 BoundingBox box = getShape()->getBoundingBox();
00235 if (x < box.left ||
00236 x > box.right ||
00237 depth >= getShape()->depth()) {
00238 return false;
00239 }
00240 Extent theExtent;
00241 if (getShape()->getExtentAtDepth(depth, theExtent)) {
00242 return (theExtent.l <= x && x <= theExtent.r);
00243 } else {
00244 return false;
00245 }
00246 }
00247
00248 VisualNode*
00249 VisualNode::findNode(const NodeAllocator& na, int x, int y) {
00250 VisualNode* cur = this;
00251 int depth = y / Layout::dist_y;
00252
00253 while (depth > 0 && cur != NULL) {
00254 if (cur->isHidden()) {
00255 break;
00256 }
00257 VisualNode* oldCur = cur;
00258 cur = NULL;
00259 for (unsigned int i=0; i<oldCur->getNumberOfChildren(); i++) {
00260 VisualNode* nextChild = oldCur->getChild(na,i);
00261 int newX = x - nextChild->getOffset();
00262 if (nextChild->containsCoordinateAtDepth(newX, depth - 1)) {
00263 cur = nextChild;
00264 x = newX;
00265 break;
00266 }
00267 }
00268 depth--;
00269 y -= Layout::dist_y;
00270 }
00271
00272 if(cur == this && !cur->containsCoordinateAtDepth(x, 0)) {
00273 return NULL;
00274 }
00275 return cur;
00276 }
00277
00278 std::string
00279 VisualNode::toolTip(NodeAllocator&, BestNode*, int, int) {
00280 return "";
00281 }
00282
00283 std::string
00284 VisualNode::getBranchLabel(NodeAllocator& na,
00285 VisualNode* p, const Choice* c,
00286 BestNode* curBest, int c_d, int a_d, int alt) {
00287 std::ostringstream oss;
00288 p->acquireSpace(na,curBest,c_d,a_d);
00289 p->getWorkingSpace()->print(*c,alt,oss);
00290 return oss.str();
00291 }
00292
00293
00295 class Layouter {
00296 public:
00298 template<class S1, class S2>
00299 static int getAlpha(const S1& shape1, int depth1,
00300 const S2& shape2, int depth2);
00302 template<class S1, class S2>
00303 static void merge(Extent* result,
00304 const S1& shape1, int depth1,
00305 const S2& shape2, int depth2, int alpha);
00306 };
00307
00308 template<class S1, class S2>
00309 int
00310 Layouter::getAlpha(const S1& shape1, int depth1,
00311 const S2& shape2, int depth2) {
00312 int alpha = Layout::minimalSeparation;
00313 int extentR = 0;
00314 int extentL = 0;
00315 for (int i=0; i<depth1 && i<depth2; i++) {
00316 extentR += shape1[i].r;
00317 extentL += shape2[i].l;
00318 alpha = std::max(alpha, extentR - extentL + Layout::minimalSeparation);
00319 }
00320 return alpha;
00321 }
00322
00323 template<class S1, class S2>
00324 void
00325 Layouter::merge(Extent* result,
00326 const S1& shape1, int depth1,
00327 const S2& shape2, int depth2, int alpha) {
00328 if (depth1 == 0) {
00329 for (int i=depth2; i--;)
00330 result[i] = shape2[i];
00331 } else if (depth2 == 0) {
00332 for (int i=depth1; i--;)
00333 result[i] = shape1[i];
00334 } else {
00335
00336
00337 int topmostL = shape1[0].l;
00338 int topmostR = shape2[0].r;
00339 int backoffTo1 =
00340 shape1[0].r - alpha - shape2[0].r;
00341 int backoffTo2 =
00342 shape2[0].l + alpha - shape1[0].l;
00343
00344 result[0] = Extent(topmostL, topmostR+alpha);
00345
00346
00347
00348
00349
00350
00351 int i=1;
00352 for (; i<depth1 && i<depth2; i++) {
00353 Extent currentExtent1 = shape1[i];
00354 Extent currentExtent2 = shape2[i];
00355 int newExtentL = currentExtent1.l;
00356 int newExtentR = currentExtent2.r;
00357 result[i] = Extent(newExtentL, newExtentR);
00358 backoffTo1 += currentExtent1.r - currentExtent2.r;
00359 backoffTo2 += currentExtent2.l - currentExtent1.l;
00360 }
00361
00362
00363
00364 if (i<depth1) {
00365 Extent currentExtent1 = shape1[i];
00366 int newExtentL = currentExtent1.l;
00367 int newExtentR = currentExtent1.r;
00368 result[i] = Extent(newExtentL, newExtentR+backoffTo1);
00369 ++i;
00370 for (; i<depth1; i++) {
00371 result[i] = shape1[i];
00372 }
00373 }
00374
00375
00376
00377 if (i<depth2) {
00378 Extent currentExtent2 = shape2[i];
00379 int newExtentL = currentExtent2.l;
00380 int newExtentR = currentExtent2.r;
00381 result[i] = Extent(newExtentL+backoffTo2, newExtentR);
00382 ++i;
00383 for (; i<depth2; i++) {
00384 result[i] = shape2[i];
00385 }
00386 }
00387 }
00388 }
00389
00390 void
00391 VisualNode::setShape(Shape* s) {
00392 if (shape != s)
00393 Shape::deallocate(shape);
00394 shape = s;
00395 shape->computeBoundingBox();
00396 }
00397
00398 void
00399 VisualNode::computeShape(const NodeAllocator& na) {
00400 int numberOfShapes = getNumberOfChildren();
00401 Extent extent;
00402 if (na.hasLabel(this)) {
00403 int ll = na.getLabel(this).length();
00404 ll *= 7;
00405 VisualNode* p = getParent(na);
00406 int alt = 0;
00407 int n_alt = 1;
00408 if (p) {
00409 alt = getAlternative(na);
00410 n_alt = p->getNumberOfChildren();
00411 }
00412 extent = Extent(Layout::extent);
00413 if (alt==0 && n_alt > 1) {
00414 extent.l = std::min(extent.l, -ll);
00415 } else if (alt==n_alt-1 && n_alt > 1) {
00416 extent.r = std::max(extent.r, ll);
00417 } else {
00418 extent.l = std::min(extent.l, -ll);
00419 extent.r = std::max(extent.r, ll);
00420 }
00421 } else {
00422 if (numberOfShapes==0) {
00423 setShape(Shape::leaf);
00424 return;
00425 } else {
00426 extent = Extent(Layout::extent);
00427 }
00428 }
00429
00430 int maxDepth = 0;
00431 for (int i = numberOfShapes; i--;)
00432 maxDepth = std::max(maxDepth, getChild(na,i)->getShape()->depth());
00433 Shape* mergedShape;
00434 if (getShape() && getShape() != Shape::leaf &&
00435 getShape()->depth() >= maxDepth+1) {
00436 mergedShape = getShape();
00437 mergedShape->setDepth(maxDepth+1);
00438 } else {
00439 mergedShape = Shape::allocate(maxDepth+1);
00440 }
00441 (*mergedShape)[0] = extent;
00442 if (numberOfShapes < 1) {
00443 setShape(mergedShape);
00444 } else if (numberOfShapes == 1) {
00445 getChild(na,0)->setOffset(0);
00446 const Shape* childShape = getChild(na,0)->getShape();
00447 for (int i=childShape->depth(); i--;)
00448 (*mergedShape)[i+1] = (*childShape)[i];
00449 (*mergedShape)[1].extend(- extent.l, - extent.r);
00450 setShape(mergedShape);
00451 } else {
00452
00453
00454
00455
00456
00457
00458 Region r;
00459 std::pair<int,int>* alpha =
00460 r.alloc<std::pair<int,int> >(numberOfShapes);
00461
00462
00463 int width = 0;
00464
00465 Extent* currentShapeL = r.alloc<Extent>(maxDepth);
00466 int ldepth = getChild(na,0)->getShape()->depth();
00467 for (int i=ldepth; i--;)
00468 currentShapeL[i] = (*getChild(na,0)->getShape())[i];
00469
00470
00471
00472 Shape* rShape = getChild(na,numberOfShapes-1)->getShape();
00473 int rdepth = rShape->depth();
00474 for (int i=rdepth; i--;)
00475 (*mergedShape)[i+1] = (*rShape)[i];
00476 Extent* currentShapeR = &(*mergedShape)[1];
00477
00478 for (int i = 1; i < numberOfShapes; i++) {
00479
00480
00481
00482
00483
00484
00485
00486 Shape* nextShapeL = getChild(na,i)->getShape();
00487 int nextAlphaL =
00488 Layouter::getAlpha<Extent*,Shape>(¤tShapeL[0], ldepth,
00489 *nextShapeL, nextShapeL->depth());
00490 Layouter::merge<Extent*,Shape>(¤tShapeL[0],
00491 ¤tShapeL[0], ldepth,
00492 *nextShapeL, nextShapeL->depth(),
00493 nextAlphaL);
00494 ldepth = std::max(ldepth,nextShapeL->depth());
00495 alpha[i].first = nextAlphaL - width;
00496 width = nextAlphaL;
00497
00498
00499
00500 Shape* nextShapeR = getChild(na,numberOfShapes-1-i)->getShape();
00501 int nextAlphaR =
00502 Layouter::getAlpha<Shape,Extent*>(*nextShapeR, nextShapeR->depth(),
00503 ¤tShapeR[0], rdepth);
00504 Layouter::merge<Shape,Extent*>(¤tShapeR[0],
00505 *nextShapeR, nextShapeR->depth(),
00506 ¤tShapeR[0], rdepth,
00507 nextAlphaR);
00508 rdepth = std::max(rdepth,nextShapeR->depth());
00509 alpha[numberOfShapes - i].second = nextAlphaR;
00510 }
00511
00512
00513 (*mergedShape)[1].extend(- extent.l, - extent.r);
00514
00515
00516
00517
00518
00519 int halfWidth = false ? 0 : width / 2;
00520 (*mergedShape)[1].move(- halfWidth);
00521
00522
00523
00524
00525
00526
00527
00528 int offset = - halfWidth;
00529 getChild(na,0)->setOffset(offset);
00530 for (int i = 1; i < numberOfShapes; i++) {
00531 offset += (alpha[i].first + alpha[i].second) / 2;
00532 getChild(na,i)->setOffset(offset);
00533 }
00534 setShape(mergedShape);
00535 }
00536 }
00537
00538 }}
00539
00540