Generated on Mon Nov 30 23:53:19 2009 for Gecode by doxygen 1.6.1

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: 2009-02-05 05:50:25 +0100 (Thu, 05 Feb 2009) $ by $Author: tack $
00011  *     $Revision: 8151 $
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   }
00078 
00079   VisualNode::VisualNode(Space* root)
00080   : SpaceNode(root)
00081   , shape(NULL)
00082   , offset(0)
00083   , box(0,0)
00084   {
00085     setDirty(true);
00086     setChildrenLayoutDone(false);
00087     setHidden(false);
00088     setMarked(false);
00089     setOnPath(false);
00090   }
00091 
00092   VisualNode::~VisualNode(void) {
00093     Shape::deallocate(shape);
00094   }
00095 
00096   void
00097   VisualNode::dirtyUp(void) {
00098     VisualNode* cur = this;
00099     while (!cur->isDirty()) {
00100       cur->setDirty(true);
00101       if (! cur->isRoot()) {
00102         cur = cur->getParent();
00103       }
00104     }
00105   }
00106 
00107   void
00108   VisualNode::layout(void) {
00109     LayoutCursor l(this);
00110     PostorderNodeVisitor<LayoutCursor> p(l);
00111     // int nodesLayouted = 1;
00112     // clock_t t0 = clock();
00113     while (p.next()) {}
00114     // while (p.next()) { nodesLayouted++; }
00115     // double t = (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
00116     // double nps = static_cast<double>(nodesLayouted) /
00117     //   (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC);
00118     // std::cout << "Layout done. " << nodesLayouted << " nodes in "
00119     //   << t << " ms. " << nps << " nodes/s." << std::endl;
00120   }
00121 
00122   void VisualNode::pathUp(void) {
00123     VisualNode* cur = this;
00124     while (cur) {
00125       cur->setOnPath(true);
00126       cur = cur->getParent();
00127     }
00128   }
00129 
00130   void VisualNode::unPathUp(void) {
00131     VisualNode* cur = this;
00132     while (!cur->isRoot()) {
00133       cur->setOnPath(false);
00134       cur = cur->getParent();
00135     }
00136   }
00137 
00138   int
00139   VisualNode::getPathAlternative(void) {
00140     for (int i=getNumberOfChildren(); i--;) {
00141       if (getChild(i)->isOnPath())
00142         return i;
00143     }
00144     return -1;
00145   }
00146 
00147   void
00148   VisualNode::toggleHidden(void) {
00149     setHidden(!isHidden());
00150     dirtyUp();
00151   }
00152 
00153   void
00154   VisualNode::hideFailed(void) {
00155     HideFailedCursor c(this);
00156     PreorderNodeVisitor<HideFailedCursor> v(c);
00157     while (v.next()) {}
00158     dirtyUp();
00159   }
00160 
00161   void
00162   VisualNode::unhideAll(void) {
00163     UnhideAllCursor c(this);
00164     PreorderNodeVisitor<UnhideAllCursor> v(c);
00165     while (v.next()) {}
00166     dirtyUp();
00167   }
00168 
00169 
00170   void
00171   VisualNode::changedStatus() { dirtyUp(); }
00172 
00173   bool
00174   VisualNode::containsCoordinateAtDepth(int x, int depth) {
00175     if (x < box.left ||
00176         x > box.right ||
00177         depth > shape->depth()) {
00178       return false;
00179     }
00180     Extent theExtent;
00181     if (shape->getExtentAtDepth(depth, theExtent)) {
00182       return (theExtent.l <= x && x <= theExtent.r);
00183     } else {
00184       return false;
00185     }
00186   }
00187 
00188   VisualNode*
00189   VisualNode::findNode(int x, int y) {
00190     VisualNode* cur = this;
00191     int depth = y / Layout::dist_y;
00192 
00193     while (depth > 0 && cur != NULL) {
00194       if (cur->isHidden()) {
00195         break;
00196       }
00197       VisualNode* oldCur = cur;
00198       cur = NULL;
00199       for (unsigned int i=0; i<oldCur->getNumberOfChildren(); i++) {
00200         VisualNode* nextChild = oldCur->getChild(i);
00201         int newX = x - nextChild->getOffset();
00202         if (nextChild->containsCoordinateAtDepth(newX, depth - 1)) {
00203           cur = nextChild;
00204           x = newX;
00205           break;
00206         }
00207       }
00208       depth--;
00209       y -= Layout::dist_y;
00210     }
00211 
00212     if(cur == this && !cur->containsCoordinateAtDepth(x, 0)) {
00213       return NULL;
00214     }
00215     return cur;
00216   }
00217 
00218   std::string
00219   VisualNode::toolTip(BestNode*, int, int) {
00220     return "";
00221   }
00222 
00224   class Layouter {
00225   public:
00227     static int getAlpha(Extent* shape1, int depth1,
00228                         Extent* shape2, int depth2);
00230     static void merge(Extent* result,
00231                       Extent* shape1, int depth1,
00232                       Extent* shape2, int depth2, int alpha);
00233   };
00234 
00235   int
00236   Layouter::getAlpha(Extent* shape1, int depth1,
00237                      Extent* shape2, int depth2) {
00238     int alpha = Layout::minimalSeparation;
00239     int extentR = 0;
00240     int extentL = 0;
00241     for (int i=0; i<depth1 && i<depth2; i++) {
00242       extentR += shape1[i].r;
00243       extentL += shape2[i].l;
00244       alpha = std::max(alpha, extentR - extentL + Layout::minimalSeparation);
00245     }
00246     return alpha;
00247   }
00248 
00249   void
00250   Layouter::merge(Extent* result,
00251                   Extent* shape1, int depth1,
00252                   Extent* shape2, int depth2, int alpha) {
00253     if (depth1 == 0) {
00254       for (int i=depth2; i--;)
00255         result[i] = shape2[i];
00256     } else if (depth2 == 0) {
00257       for (int i=depth1; i--;)
00258         result[i] = shape1[i];
00259     } else {
00260       // Extend the topmost right extent by alpha.  This, in effect,
00261       // moves the second shape to the right by alpha units.
00262       int topmostL = shape1[0].l;
00263       int topmostR = shape2[0].r;
00264       int backoffTo1 =
00265         shape1[0].r - alpha - shape2[0].r;
00266       int backoffTo2 =
00267         shape2[0].l + alpha - shape1[0].l;
00268 
00269       result[0] = Extent(topmostL, topmostR+alpha);
00270 
00271       // Now, since extents are given in relative units, in order to
00272       // compute the extents of the merged shape, we can just collect the
00273       // extents of shape1 and shape2, until one of the shapes ends.  If
00274       // this happens, we need to "back-off" to the axis of the deeper
00275       // shape in order to properly determine the remaining extents.
00276       int i=1;
00277       for (; i<depth1 && i<depth2; i++) {
00278         Extent currentExtent1 = shape1[i];
00279         Extent currentExtent2 = shape2[i];
00280         int newExtentL = currentExtent1.l;
00281         int newExtentR = currentExtent2.r;
00282         result[i] = Extent(newExtentL, newExtentR);
00283         backoffTo1 += currentExtent1.r - currentExtent2.r;
00284         backoffTo2 += currentExtent2.l - currentExtent1.l;
00285       }
00286 
00287       // If shape1 is deeper than shape2, back off to the axis of shape1,
00288       // and process the remaining extents of shape1.
00289       if (i<depth1) {
00290         Extent currentExtent1 = shape1[i];
00291         int newExtentL = currentExtent1.l;
00292         int newExtentR = currentExtent1.r;
00293         result[i] = Extent(newExtentL, newExtentR+backoffTo1);
00294         ++i;
00295         for (; i<depth1; i++) {
00296           result[i] = shape1[i];
00297         }
00298       }
00299 
00300       // Vice versa, if shape2 is deeper than shape1, back off to the
00301       // axis of shape2, and process the remaining extents of shape2.
00302       if (i<depth2) {
00303         Extent currentExtent2 = shape2[i];
00304         int newExtentL = currentExtent2.l;
00305         int newExtentR = currentExtent2.r;
00306         result[i] = Extent(newExtentL+backoffTo2, newExtentR);
00307         ++i;
00308         for (; i<depth2; i++) {
00309           result[i] = shape2[i];
00310         }
00311       }
00312     }
00313   }
00314 
00315   void
00316   VisualNode::setShape(Shape* s) {
00317     Shape::deallocate(shape);
00318     shape = s;
00319     setBoundingBox(shape->getBoundingBox());
00320   }
00321 
00322   void
00323   VisualNode::computeShape(VisualNode* root) {
00324     Extent extent(Layout::extent);
00325     int numberOfShapes = getNumberOfChildren();
00326     if (numberOfShapes == 1) {
00327       getChild(0)->setOffset(0);
00328       Shape* result = Shape::allocate(extent, getChild(0)->getShape());
00329       (*result)[1].extend(- extent.l, - extent.r);
00330       setShape(result);
00331     } else {
00332       // alpha stores the necessary distances between the
00333       // axes of the shapes in the list: alpha[i].first gives the distance
00334       // between shape[i] and shape[i-1], when shape[i-1] and shape[i]
00335       // are merged left-to-right; alpha[i].second gives the distance between
00336       // shape[i] and shape[i+1], when shape[i] and shape[i+1] are merged
00337       // right-to-left.
00338       assert(root->copy != NULL);
00339       Region r(*root->copy);
00340       std::pair<int,int>* alpha =
00341         r.alloc<std::pair<int,int> >(numberOfShapes);
00342 
00343       // distance between the leftmost and the rightmost axis in the list
00344       int width = 0;
00345 
00346       int maxDepth = 0;
00347       for (int i = numberOfShapes; i--;)
00348         maxDepth = std::max(maxDepth, getChild(i)->getShape()->depth());
00349 
00350       Extent* currentShapeL = r.alloc<Extent>(maxDepth);
00351       int ldepth = getChild(0)->getShape()->depth();
00352       for (int i=ldepth; i--;)
00353         currentShapeL[i] = (*getChild(0)->getShape())[i];
00354 
00355       // After merging, we can pick the result of either merging left or right
00356       // Here we chose the result of merging right
00357       Shape* mergedShape = Shape::allocate(maxDepth+1);
00358       (*mergedShape)[0] = extent;
00359       Shape* rShape = getChild(numberOfShapes-1)->getShape();
00360       int rdepth = rShape->depth();
00361       for (int i=rdepth; i--;)
00362         (*mergedShape)[i+1] = (*rShape)[i];
00363       Extent* currentShapeR = &(*mergedShape)[1];
00364 
00365       for (int i = 1; i < numberOfShapes; i++) {
00366         // Merge left-to-right.  Note that due to the asymmetry of the
00367         // merge operation, nextAlphaL is the distance between the
00368         // *leftmost* axis in the shape list, and the axis of
00369         // nextShapeL; what we are really interested in is the distance
00370         // between the *previous* axis and the axis of nextShapeL.
00371         // This explains the correction.
00372 
00373         Shape* nextShapeL = getChild(i)->getShape();
00374         int nextAlphaL =
00375           Layouter::getAlpha(&currentShapeL[0], ldepth,
00376                              &(*nextShapeL)[0], nextShapeL->depth());
00377         Layouter::merge(&currentShapeL[0], &currentShapeL[0], ldepth,
00378                         &(*nextShapeL)[0], nextShapeL->depth(), nextAlphaL);
00379         ldepth = std::max(ldepth,nextShapeL->depth());
00380         alpha[i].first = nextAlphaL - width;
00381         width = nextAlphaL;
00382 
00383         // Merge right-to-left.  Here, a correction of nextAlphaR is
00384         // not required.
00385         Shape* nextShapeR = getChild(numberOfShapes-1-i)->getShape();
00386         int nextAlphaR =
00387           Layouter::getAlpha(&(*nextShapeR)[0], nextShapeR->depth(),
00388                                &currentShapeR[0], rdepth);
00389         Layouter::merge(&currentShapeR[0],
00390                         &(*nextShapeR)[0], nextShapeR->depth(),
00391                         &currentShapeR[0], rdepth, nextAlphaR);
00392         rdepth = std::max(rdepth,nextShapeR->depth());
00393         alpha[numberOfShapes - i].second = nextAlphaR;
00394       }
00395 
00396       // The merged shape has to be adjusted to its topmost extent
00397       (*mergedShape)[1].extend(- extent.l, - extent.r);
00398 
00399       // After the loop, the merged shape has the same axis as the
00400       // leftmost shape in the list.  What we want is to move the axis
00401       // such that it is the center of the axis of the leftmost shape in
00402       // the list and the axis of the rightmost shape.
00403       bool left = getStatus() == STEP;
00404       int halfWidth = left ? 0 : width / 2;
00405       (*mergedShape)[1].move(- halfWidth);
00406 
00407       // Finally, for the offset lists.  Now that the axis of the merged
00408       // shape is at the center of the two extreme axes, the first shape
00409       // needs to be offset by -halfWidth units with respect to the new
00410       // axis.  As for the offsets for the other shapes, we take the
00411       // median of the alphaL and alphaR values, as suggested in
00412       // Kennedy's paper.
00413       int offset = - halfWidth;
00414       getChild(0)->setOffset(offset);
00415       for (int i = 1; i < numberOfShapes; i++) {
00416         offset += (alpha[i].first + alpha[i].second) / 2;
00417         getChild(i)->setOffset(offset);
00418       }
00419       setShape(mergedShape);
00420     }
00421   }
00422 
00423   size_t
00424   VisualNode::size(void) const {
00425     size_t s = sizeof(*this);
00426     s += sizeof(Node*)*getNumberOfChildren();
00427     if (shape && shape != Shape::leaf && shape != Shape::hidden) {
00428       s += sizeof(Shape)+sizeof(Extent)*(shape->depth()-1);
00429     }
00430     if (copy)
00431       s += copy->allocated();
00432     if (workingSpace)
00433       s += workingSpace->allocated();
00434     if (getStatus() == SPECIAL)
00435       s += sizeof(SpecialDesc);
00436     else if (getStatus() == STEP)
00437       s += sizeof(StepDesc);
00438     else
00439       s += (desc.branch != NULL ? desc.branch->size() : 0);
00440     return s;
00441   }
00442 
00443 }}
00444 
00445 // STATISTICS: gist-any