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(¤tShapeL[0], ldepth, 00394 &(*nextShapeL)[0], nextShapeL->depth()); 00395 Layouter::merge(¤tShapeL[0], ¤tShapeL[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 ¤tShapeR[0], rdepth); 00407 Layouter::merge(¤tShapeR[0], 00408 &(*nextShapeR)[0], nextShapeR->depth(), 00409 ¤tShapeR[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