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