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 }
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
00112
00113 while (p.next()) {}
00114
00115
00116
00117
00118
00119
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
00261
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
00272
00273
00274
00275
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
00288
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
00301
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
00333
00334
00335
00336
00337
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
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
00356
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
00367
00368
00369
00370
00371
00372
00373 Shape* nextShapeL = getChild(i)->getShape();
00374 int nextAlphaL =
00375 Layouter::getAlpha(¤tShapeL[0], ldepth,
00376 &(*nextShapeL)[0], nextShapeL->depth());
00377 Layouter::merge(¤tShapeL[0], ¤tShapeL[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
00384
00385 Shape* nextShapeR = getChild(numberOfShapes-1-i)->getShape();
00386 int nextAlphaR =
00387 Layouter::getAlpha(&(*nextShapeR)[0], nextShapeR->depth(),
00388 ¤tShapeR[0], rdepth);
00389 Layouter::merge(¤tShapeR[0],
00390 &(*nextShapeR)[0], nextShapeR->depth(),
00391 ¤tShapeR[0], rdepth, nextAlphaR);
00392 rdepth = std::max(rdepth,nextShapeR->depth());
00393 alpha[numberOfShapes - i].second = nextAlphaR;
00394 }
00395
00396
00397 (*mergedShape)[1].extend(- extent.l, - extent.r);
00398
00399
00400
00401
00402
00403 bool left = getStatus() == STEP;
00404 int halfWidth = left ? 0 : width / 2;
00405 (*mergedShape)[1].move(- halfWidth);
00406
00407
00408
00409
00410
00411
00412
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