00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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
00114
00115 while (p.next()) {}
00116
00117
00118
00119
00120
00121
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
00279
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
00290
00291
00292
00293
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
00306
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
00319
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
00351
00352
00353
00354
00355
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
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
00374
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
00385
00386
00387
00388
00389
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
00402
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
00415 (*mergedShape)[1].extend(- extent.l, - extent.r);
00416
00417
00418
00419
00420
00421 int halfWidth = false ? 0 : width / 2;
00422 (*mergedShape)[1].move(- halfWidth);
00423
00424
00425
00426
00427
00428
00429
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