Generated on Fri Oct 19 11:25:00 2018 for Gecode by doxygen 1.6.3

visualnode.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2006
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  * Permission is hereby granted, free of charge, to any person obtaining
00014  * a copy of this software and associated documentation files (the
00015  * "Software"), to deal in the Software without restriction, including
00016  * without limitation the rights to use, copy, modify, merge, publish,
00017  * distribute, sublicense, and/or sell copies of the Software, and to
00018  * permit persons to whom the Software is furnished to do so, subject to
00019  * the following conditions:
00020  *
00021  * The above copyright notice and this permission notice shall be
00022  * included in all copies or substantial portions of the Software.
00023  *
00024  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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     // int nodesLayouted = 1;
00117     // clock_t t0 = clock();
00118     // while (p.next()) {}
00119     // while (p.next()) { nodesLayouted++; }
00120     // double t = (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
00121     // double nps = static_cast<double>(nodesLayouted) /
00122     //   (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC);
00123     // std::cout << "Layout done. " << nodesLayouted << " nodes in "
00124     //   << t << " ms. " << nps << " nodes/s." << std::endl;
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       // clear labels on path to root
00179       VisualNode* p = this;
00180       while (p) {
00181         na.clearLabel(p);
00182         p = p->getParent(na);
00183       }
00184     } else {
00185       // set labels on path to root
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       // Extend the topmost right extent by alpha.  This, in effect,
00336       // moves the second shape to the right by alpha units.
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       // Now, since extents are given in relative units, in order to
00347       // compute the extents of the merged shape, we can just collect the
00348       // extents of shape1 and shape2, until one of the shapes ends.  If
00349       // this happens, we need to "back-off" to the axis of the deeper
00350       // shape in order to properly determine the remaining extents.
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       // If shape1 is deeper than shape2, back off to the axis of shape1,
00363       // and process the remaining extents of shape1.
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       // Vice versa, if shape2 is deeper than shape1, back off to the
00376       // axis of shape2, and process the remaining extents of shape2.
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       // alpha stores the necessary distances between the
00453       // axes of the shapes in the list: alpha[i].first gives the distance
00454       // between shape[i] and shape[i-1], when shape[i-1] and shape[i]
00455       // are merged left-to-right; alpha[i].second gives the distance between
00456       // shape[i] and shape[i+1], when shape[i] and shape[i+1] are merged
00457       // right-to-left.
00458       Region r;
00459       std::pair<int,int>* alpha =
00460         r.alloc<std::pair<int,int> >(numberOfShapes);
00461 
00462       // distance between the leftmost and the rightmost axis in the list
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       // After merging, we can pick the result of either merging left or right
00471       // Here we chose the result of merging right
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         // Merge left-to-right.  Note that due to the asymmetry of the
00480         // merge operation, nextAlphaL is the distance between the
00481         // *leftmost* axis in the shape list, and the axis of
00482         // nextShapeL; what we are really interested in is the distance
00483         // between the *previous* axis and the axis of nextShapeL.
00484         // This explains the correction.
00485 
00486         Shape* nextShapeL = getChild(na,i)->getShape();
00487         int nextAlphaL =
00488           Layouter::getAlpha<Extent*,Shape>(&currentShapeL[0], ldepth,
00489                              *nextShapeL, nextShapeL->depth());
00490         Layouter::merge<Extent*,Shape>(&currentShapeL[0],
00491                                        &currentShapeL[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         // Merge right-to-left.  Here, a correction of nextAlphaR is
00499         // not required.
00500         Shape* nextShapeR = getChild(na,numberOfShapes-1-i)->getShape();
00501         int nextAlphaR =
00502           Layouter::getAlpha<Shape,Extent*>(*nextShapeR, nextShapeR->depth(),
00503                                &currentShapeR[0], rdepth);
00504         Layouter::merge<Shape,Extent*>(&currentShapeR[0],
00505                                        *nextShapeR, nextShapeR->depth(),
00506                                        &currentShapeR[0], rdepth,
00507                                        nextAlphaR);
00508         rdepth = std::max(rdepth,nextShapeR->depth());
00509         alpha[numberOfShapes - i].second = nextAlphaR;
00510       }
00511 
00512       // The merged shape has to be adjusted to its topmost extent
00513       (*mergedShape)[1].extend(- extent.l, - extent.r);
00514 
00515       // After the loop, the merged shape has the same axis as the
00516       // leftmost shape in the list.  What we want is to move the axis
00517       // such that it is the center of the axis of the leftmost shape in
00518       // the list and the axis of the rightmost shape.
00519       int halfWidth = false ? 0 : width / 2;
00520       (*mergedShape)[1].move(- halfWidth);
00521 
00522       // Finally, for the offset lists.  Now that the axis of the merged
00523       // shape is at the center of the two extreme axes, the first shape
00524       // needs to be offset by -halfWidth units with respect to the new
00525       // axis.  As for the offsets for the other shapes, we take the
00526       // median of the alphaL and alphaR values, as suggested in
00527       // Kennedy's paper.
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 // STATISTICS: gist-any