Generated on Mon May 10 06:46:31 2010 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  *  Last modified:
00010  *     $Date: 2010-03-31 11:23:42 +0200 (Wed, 31 Mar 2010) $ by $Author: tack $
00011  *     $Revision: 10619 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  * Permission is hereby granted, free of charge, to any person obtaining
00018  * a copy of this software and associated documentation files (the
00019  * "Software"), to deal in the Software without restriction, including
00020  * without limitation the rights to use, copy, modify, merge, publish,
00021  * distribute, sublicense, and/or sell copies of the Software, and to
00022  * permit persons to whom the Software is furnished to do so, subject to
00023  * the following conditions:
00024  *
00025  * The above copyright notice and this permission notice shall be
00026  * included in all copies or substantial portions of the Software.
00027  *
00028  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/gist/visualnode.hh>
00039 
00040 #include <gecode/gist/layoutcursor.hh>
00041 #include <gecode/gist/nodevisitor.hh>
00042 
00043 #include <utility>
00044 
00045 namespace Gecode { namespace Gist {
00046 
00047   Shape* Shape::leaf;
00048   Shape* Shape::hidden;
00049 
00051   class ShapeAllocator {
00052   public:
00054     ShapeAllocator(void) {
00055       Shape::leaf = Shape::allocate(Extent(Layout::extent));
00056       Shape::hidden = Shape::allocate(Extent(Layout::extent), Shape::leaf);
00057     }
00058     ~ShapeAllocator(void) {
00059       Shape::deallocate(Shape::leaf);
00060       Shape::deallocate(Shape::hidden);
00061     }
00062   };
00063 
00065   ShapeAllocator shapeAllocator;
00066 
00067   VisualNode::VisualNode(void)
00068   : shape(NULL)
00069   , offset(0)
00070   , box(0,0)
00071   {
00072     setDirty(true);
00073     setChildrenLayoutDone(false);
00074     setHidden(false);
00075     setMarked(false);
00076     setOnPath(false);
00077     setBookmarked(false);
00078   }
00079 
00080   VisualNode::VisualNode(Space* root)
00081   : SpaceNode(root)
00082   , shape(NULL)
00083   , offset(0)
00084   , box(0,0)
00085   {
00086     setDirty(true);
00087     setChildrenLayoutDone(false);
00088     setHidden(false);
00089     setMarked(false);
00090     setOnPath(false);
00091     setBookmarked(false);
00092   }
00093 
00094   VisualNode::~VisualNode(void) {
00095     Shape::deallocate(shape);
00096   }
00097 
00098   void
00099   VisualNode::dirtyUp(void) {
00100     VisualNode* cur = this;
00101     while (!cur->isDirty()) {
00102       cur->setDirty(true);
00103       if (! cur->isRoot()) {
00104         cur = cur->getParent();
00105       }
00106     }
00107   }
00108 
00109   void
00110   VisualNode::layout(void) {
00111     LayoutCursor l(this);
00112     PostorderNodeVisitor<LayoutCursor> p(l);
00113     // int nodesLayouted = 1;
00114     // clock_t t0 = clock();
00115     while (p.next()) {}
00116     // while (p.next()) { nodesLayouted++; }
00117     // double t = (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
00118     // double nps = static_cast<double>(nodesLayouted) /
00119     //   (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC);
00120     // std::cout << "Layout done. " << nodesLayouted << " nodes in "
00121     //   << t << " ms. " << nps << " nodes/s." << std::endl;
00122   }
00123 
00124   void VisualNode::pathUp(void) {
00125     VisualNode* cur = this;
00126     while (cur) {
00127       cur->setOnPath(true);
00128       cur = cur->getParent();
00129     }
00130   }
00131 
00132   void VisualNode::unPathUp(void) {
00133     VisualNode* cur = this;
00134     while (!cur->isRoot()) {
00135       cur->setOnPath(false);
00136       cur = cur->getParent();
00137     }
00138   }
00139 
00140   int
00141   VisualNode::getPathAlternative(void) {
00142     for (int i=getNumberOfChildren(); i--;) {
00143       if (getChild(i)->isOnPath())
00144         return i;
00145     }
00146     return -1;
00147   }
00148 
00149   void
00150   VisualNode::toggleHidden(void) {
00151     setHidden(!isHidden());
00152     dirtyUp();
00153   }
00154 
00155   void
00156   VisualNode::hideFailed(void) {
00157     HideFailedCursor c(this);
00158     PreorderNodeVisitor<HideFailedCursor> v(c);
00159     while (v.next()) {}
00160     dirtyUp();
00161   }
00162 
00163   void
00164   VisualNode::unhideAll(void) {
00165     UnhideAllCursor c(this);
00166     PreorderNodeVisitor<UnhideAllCursor> v(c);
00167     while (v.next()) {}
00168     dirtyUp();
00169   }
00170 
00171   void
00172   VisualNode::toggleStop(void) {
00173     if (getStatus() == STOP)
00174       setStatus(UNSTOP);
00175     else if (getStatus() == UNSTOP)
00176       setStatus(STOP);
00177     dirtyUp();
00178   }
00179   
00180   void
00181   VisualNode::unstopAll(void) {
00182     UnstopAllCursor c(this);
00183     PreorderNodeVisitor<UnstopAllCursor> v(c);
00184     while (v.next()) {}
00185     dirtyUp();
00186   }
00187 
00188   void
00189   VisualNode::changedStatus() { dirtyUp(); }
00190 
00191   bool
00192   VisualNode::containsCoordinateAtDepth(int x, int depth) {
00193     if (x < box.left ||
00194         x > box.right ||
00195         depth >= shape->depth()) {
00196       return false;
00197     }
00198     Extent theExtent;
00199     if (shape->getExtentAtDepth(depth, theExtent)) {
00200       return (theExtent.l <= x && x <= theExtent.r);
00201     } else {
00202       return false;
00203     }
00204   }
00205 
00206   VisualNode*
00207   VisualNode::findNode(int x, int y) {
00208     VisualNode* cur = this;
00209     int depth = y / Layout::dist_y;
00210 
00211     while (depth > 0 && cur != NULL) {
00212       if (cur->isHidden()) {
00213         break;
00214       }
00215       VisualNode* oldCur = cur;
00216       cur = NULL;
00217       for (unsigned int i=0; i<oldCur->getNumberOfChildren(); i++) {
00218         VisualNode* nextChild = oldCur->getChild(i);
00219         int newX = x - nextChild->getOffset();
00220         if (nextChild->containsCoordinateAtDepth(newX, depth - 1)) {
00221           cur = nextChild;
00222           x = newX;
00223           break;
00224         }
00225       }
00226       depth--;
00227       y -= Layout::dist_y;
00228     }
00229 
00230     if(cur == this && !cur->containsCoordinateAtDepth(x, 0)) {
00231       return NULL;
00232     }
00233     return cur;
00234   }
00235 
00236   std::string
00237   VisualNode::toolTip(BestNode*, int, int) {
00238     return "";
00239   }
00240 
00242   class Layouter {
00243   public:
00245     static int getAlpha(Extent* shape1, int depth1,
00246                         Extent* shape2, int depth2);
00248     static void merge(Extent* result,
00249                       Extent* shape1, int depth1,
00250                       Extent* shape2, int depth2, int alpha);
00251   };
00252 
00253   int
00254   Layouter::getAlpha(Extent* shape1, int depth1,
00255                      Extent* shape2, int depth2) {
00256     int alpha = Layout::minimalSeparation;
00257     int extentR = 0;
00258     int extentL = 0;
00259     for (int i=0; i<depth1 && i<depth2; i++) {
00260       extentR += shape1[i].r;
00261       extentL += shape2[i].l;
00262       alpha = std::max(alpha, extentR - extentL + Layout::minimalSeparation);
00263     }
00264     return alpha;
00265   }
00266 
00267   void
00268   Layouter::merge(Extent* result,
00269                   Extent* shape1, int depth1,
00270                   Extent* shape2, int depth2, int alpha) {
00271     if (depth1 == 0) {
00272       for (int i=depth2; i--;)
00273         result[i] = shape2[i];
00274     } else if (depth2 == 0) {
00275       for (int i=depth1; i--;)
00276         result[i] = shape1[i];
00277     } else {
00278       // Extend the topmost right extent by alpha.  This, in effect,
00279       // moves the second shape to the right by alpha units.
00280       int topmostL = shape1[0].l;
00281       int topmostR = shape2[0].r;
00282       int backoffTo1 =
00283         shape1[0].r - alpha - shape2[0].r;
00284       int backoffTo2 =
00285         shape2[0].l + alpha - shape1[0].l;
00286 
00287       result[0] = Extent(topmostL, topmostR+alpha);
00288 
00289       // Now, since extents are given in relative units, in order to
00290       // compute the extents of the merged shape, we can just collect the
00291       // extents of shape1 and shape2, until one of the shapes ends.  If
00292       // this happens, we need to "back-off" to the axis of the deeper
00293       // shape in order to properly determine the remaining extents.
00294       int i=1;
00295       for (; i<depth1 && i<depth2; i++) {
00296         Extent currentExtent1 = shape1[i];
00297         Extent currentExtent2 = shape2[i];
00298         int newExtentL = currentExtent1.l;
00299         int newExtentR = currentExtent2.r;
00300         result[i] = Extent(newExtentL, newExtentR);
00301         backoffTo1 += currentExtent1.r - currentExtent2.r;
00302         backoffTo2 += currentExtent2.l - currentExtent1.l;
00303       }
00304 
00305       // If shape1 is deeper than shape2, back off to the axis of shape1,
00306       // and process the remaining extents of shape1.
00307       if (i<depth1) {
00308         Extent currentExtent1 = shape1[i];
00309         int newExtentL = currentExtent1.l;
00310         int newExtentR = currentExtent1.r;
00311         result[i] = Extent(newExtentL, newExtentR+backoffTo1);
00312         ++i;
00313         for (; i<depth1; i++) {
00314           result[i] = shape1[i];
00315         }
00316       }
00317 
00318       // Vice versa, if shape2 is deeper than shape1, back off to the
00319       // axis of shape2, and process the remaining extents of shape2.
00320       if (i<depth2) {
00321         Extent currentExtent2 = shape2[i];
00322         int newExtentL = currentExtent2.l;
00323         int newExtentR = currentExtent2.r;
00324         result[i] = Extent(newExtentL+backoffTo2, newExtentR);
00325         ++i;
00326         for (; i<depth2; i++) {
00327           result[i] = shape2[i];
00328         }
00329       }
00330     }
00331   }
00332 
00333   void
00334   VisualNode::setShape(Shape* s) {
00335     Shape::deallocate(shape);
00336     shape = s;
00337     setBoundingBox(shape->getBoundingBox());
00338   }
00339 
00340   void
00341   VisualNode::computeShape(VisualNode* root) {
00342     Extent extent(Layout::extent);
00343     int numberOfShapes = getNumberOfChildren();
00344     if (numberOfShapes == 1) {
00345       getChild(0)->setOffset(0);
00346       Shape* result = Shape::allocate(extent, getChild(0)->getShape());
00347       (*result)[1].extend(- extent.l, - extent.r);
00348       setShape(result);
00349     } else {
00350       // alpha stores the necessary distances between the
00351       // axes of the shapes in the list: alpha[i].first gives the distance
00352       // between shape[i] and shape[i-1], when shape[i-1] and shape[i]
00353       // are merged left-to-right; alpha[i].second gives the distance between
00354       // shape[i] and shape[i+1], when shape[i] and shape[i+1] are merged
00355       // right-to-left.
00356       assert(root->copy != NULL);
00357       Region r(*root->copy);
00358       std::pair<int,int>* alpha =
00359         r.alloc<std::pair<int,int> >(numberOfShapes);
00360 
00361       // distance between the leftmost and the rightmost axis in the list
00362       int width = 0;
00363 
00364       int maxDepth = 0;
00365       for (int i = numberOfShapes; i--;)
00366         maxDepth = std::max(maxDepth, getChild(i)->getShape()->depth());
00367 
00368       Extent* currentShapeL = r.alloc<Extent>(maxDepth);
00369       int ldepth = getChild(0)->getShape()->depth();
00370       for (int i=ldepth; i--;)
00371         currentShapeL[i] = (*getChild(0)->getShape())[i];
00372 
00373       // After merging, we can pick the result of either merging left or right
00374       // Here we chose the result of merging right
00375       Shape* mergedShape = Shape::allocate(maxDepth+1);
00376       (*mergedShape)[0] = extent;
00377       Shape* rShape = getChild(numberOfShapes-1)->getShape();
00378       int rdepth = rShape->depth();
00379       for (int i=rdepth; i--;)
00380         (*mergedShape)[i+1] = (*rShape)[i];
00381       Extent* currentShapeR = &(*mergedShape)[1];
00382 
00383       for (int i = 1; i < numberOfShapes; i++) {
00384         // Merge left-to-right.  Note that due to the asymmetry of the
00385         // merge operation, nextAlphaL is the distance between the
00386         // *leftmost* axis in the shape list, and the axis of
00387         // nextShapeL; what we are really interested in is the distance
00388         // between the *previous* axis and the axis of nextShapeL.
00389         // This explains the correction.
00390 
00391         Shape* nextShapeL = getChild(i)->getShape();
00392         int nextAlphaL =
00393           Layouter::getAlpha(&currentShapeL[0], ldepth,
00394                              &(*nextShapeL)[0], nextShapeL->depth());
00395         Layouter::merge(&currentShapeL[0], &currentShapeL[0], ldepth,
00396                         &(*nextShapeL)[0], nextShapeL->depth(), nextAlphaL);
00397         ldepth = std::max(ldepth,nextShapeL->depth());
00398         alpha[i].first = nextAlphaL - width;
00399         width = nextAlphaL;
00400 
00401         // Merge right-to-left.  Here, a correction of nextAlphaR is
00402         // not required.
00403         Shape* nextShapeR = getChild(numberOfShapes-1-i)->getShape();
00404         int nextAlphaR =
00405           Layouter::getAlpha(&(*nextShapeR)[0], nextShapeR->depth(),
00406                                &currentShapeR[0], rdepth);
00407         Layouter::merge(&currentShapeR[0],
00408                         &(*nextShapeR)[0], nextShapeR->depth(),
00409                         &currentShapeR[0], rdepth, nextAlphaR);
00410         rdepth = std::max(rdepth,nextShapeR->depth());
00411         alpha[numberOfShapes - i].second = nextAlphaR;
00412       }
00413 
00414       // The merged shape has to be adjusted to its topmost extent
00415       (*mergedShape)[1].extend(- extent.l, - extent.r);
00416 
00417       // After the loop, the merged shape has the same axis as the
00418       // leftmost shape in the list.  What we want is to move the axis
00419       // such that it is the center of the axis of the leftmost shape in
00420       // the list and the axis of the rightmost shape.
00421       int halfWidth = false ? 0 : width / 2;
00422       (*mergedShape)[1].move(- halfWidth);
00423 
00424       // Finally, for the offset lists.  Now that the axis of the merged
00425       // shape is at the center of the two extreme axes, the first shape
00426       // needs to be offset by -halfWidth units with respect to the new
00427       // axis.  As for the offsets for the other shapes, we take the
00428       // median of the alphaL and alphaR values, as suggested in
00429       // Kennedy's paper.
00430       int offset = - halfWidth;
00431       getChild(0)->setOffset(offset);
00432       for (int i = 1; i < numberOfShapes; i++) {
00433         offset += (alpha[i].first + alpha[i].second) / 2;
00434         getChild(i)->setOffset(offset);
00435       }
00436       setShape(mergedShape);
00437     }
00438   }
00439 
00440   size_t
00441   VisualNode::size(void) const {
00442     size_t s = sizeof(*this);
00443     s += sizeof(Node*)*getNumberOfChildren();
00444     if (shape && shape != Shape::leaf && shape != Shape::hidden) {
00445       s += sizeof(Shape)+sizeof(Extent)*(shape->depth()-1);
00446     }
00447     if (copy)
00448       s += copy->allocated();
00449     if (workingSpace)
00450       s += workingSpace->allocated();
00451     s += (choice != NULL ? choice->size() : 0);
00452     return s;
00453   }
00454 
00455 }}
00456 
00457 // STATISTICS: gist-any