Generated on Fri Aug 24 2012 04:52:06 for Gecode by doxygen 1.8.1.2
visualnode.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Copyright:
7  * Guido Tack, 2006
8  *
9  * Last modified:
10  * $Date: 2010-09-03 21:50:47 +1000 (Fri, 03 Sep 2010) $ by $Author: tack $
11  * $Revision: 11389 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
39 
42 
43 #include <utility>
44 
45 namespace Gecode { namespace Gist {
46 
47  Shape* Shape::leaf;
48  Shape* Shape::hidden;
49 
52  public:
57  (*Shape::hidden)[1] = Extent(Layout::extent);
60  }
64  }
65  };
66 
69 
71  : SpaceNode(p)
72  , offset(0)
73  {
74  shape = NULL;
75  setDirty(true);
76  setChildrenLayoutDone(false);
77  setHidden(false);
78  setMarked(false);
79  setOnPath(false);
80  setBookmarked(false);
81  }
82 
84  : SpaceNode(root)
85  , offset(0)
86  {
87  shape = NULL;
88  setDirty(true);
89  setChildrenLayoutDone(false);
90  setHidden(false);
91  setMarked(false);
92  setOnPath(false);
93  setBookmarked(false);
94  }
95 
96  void
100  }
101 
102  void
104  VisualNode* cur = this;
105  while (!cur->isDirty()) {
106  cur->setDirty(true);
107  if (! cur->isRoot()) {
108  cur = cur->getParent(na);
109  }
110  }
111  }
112 
113  void
115  LayoutCursor l(this,na);
117  // int nodesLayouted = 1;
118  // clock_t t0 = clock();
119  // while (p.next()) {}
120  // while (p.next()) { nodesLayouted++; }
121  // double t = (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
122  // double nps = static_cast<double>(nodesLayouted) /
123  // (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC);
124  // std::cout << "Layout done. " << nodesLayouted << " nodes in "
125  // << t << " ms. " << nps << " nodes/s." << std::endl;
126  }
127 
129  VisualNode* cur = this;
130  while (cur) {
131  cur->setOnPath(true);
132  cur = cur->getParent(na);
133  }
134  }
135 
137  VisualNode* cur = this;
138  while (!cur->isRoot()) {
139  cur->setOnPath(false);
140  cur = cur->getParent(na);
141  }
142  }
143 
144  int
146  for (int i=getNumberOfChildren(); i--;) {
147  if (getChild(na,i)->isOnPath())
148  return i;
149  }
150  return -1;
151  }
152 
153  void
155  setHidden(!isHidden());
156  dirtyUp(na);
157  }
158 
159  void
160  VisualNode::hideFailed(const NodeAllocator& na, bool onlyDirty) {
161  HideFailedCursor c(this,na,onlyDirty);
163  dirtyUp(na);
164  }
165 
166  void
168  UnhideAllCursor c(this,na);
170  dirtyUp(na);
171  }
172 
173  void
175  if (getStatus() == STOP)
176  setStatus(UNSTOP);
177  else if (getStatus() == UNSTOP)
178  setStatus(STOP);
179  dirtyUp(na);
180  }
181 
182  void
184  UnstopAllCursor c(this,na);
186  dirtyUp(na);
187  }
188 
189  void
191 
192  bool
195  if (x < box.left ||
196  x > box.right ||
197  depth >= getShape()->depth()) {
198  return false;
199  }
200  Extent theExtent;
201  if (getShape()->getExtentAtDepth(depth, theExtent)) {
202  return (theExtent.l <= x && x <= theExtent.r);
203  } else {
204  return false;
205  }
206  }
207 
208  VisualNode*
209  VisualNode::findNode(const NodeAllocator& na, int x, int y) {
210  VisualNode* cur = this;
211  int depth = y / Layout::dist_y;
212 
213  while (depth > 0 && cur != NULL) {
214  if (cur->isHidden()) {
215  break;
216  }
217  VisualNode* oldCur = cur;
218  cur = NULL;
219  for (unsigned int i=0; i<oldCur->getNumberOfChildren(); i++) {
220  VisualNode* nextChild = oldCur->getChild(na,i);
221  int newX = x - nextChild->getOffset();
222  if (nextChild->containsCoordinateAtDepth(newX, depth - 1)) {
223  cur = nextChild;
224  x = newX;
225  break;
226  }
227  }
228  depth--;
229  y -= Layout::dist_y;
230  }
231 
232  if(cur == this && !cur->containsCoordinateAtDepth(x, 0)) {
233  return NULL;
234  }
235  return cur;
236  }
237 
238  std::string
240  return "";
241  }
242 
244  class Layouter {
245  public:
247  template<class S1, class S2>
248  static int getAlpha(const S1& shape1, int depth1,
249  const S2& shape2, int depth2);
251  template<class S1, class S2>
252  static void merge(Extent* result,
253  const S1& shape1, int depth1,
254  const S2& shape2, int depth2, int alpha);
255  };
256 
257  template<class S1, class S2>
258  int
259  Layouter::getAlpha(const S1& shape1, int depth1,
260  const S2& shape2, int depth2) {
261  int alpha = Layout::minimalSeparation;
262  int extentR = 0;
263  int extentL = 0;
264  for (int i=0; i<depth1 && i<depth2; i++) {
265  extentR += shape1[i].r;
266  extentL += shape2[i].l;
267  alpha = std::max(alpha, extentR - extentL + Layout::minimalSeparation);
268  }
269  return alpha;
270  }
271 
272  template<class S1, class S2>
273  void
275  const S1& shape1, int depth1,
276  const S2& shape2, int depth2, int alpha) {
277  if (depth1 == 0) {
278  for (int i=depth2; i--;)
279  result[i] = shape2[i];
280  } else if (depth2 == 0) {
281  for (int i=depth1; i--;)
282  result[i] = shape1[i];
283  } else {
284  // Extend the topmost right extent by alpha. This, in effect,
285  // moves the second shape to the right by alpha units.
286  int topmostL = shape1[0].l;
287  int topmostR = shape2[0].r;
288  int backoffTo1 =
289  shape1[0].r - alpha - shape2[0].r;
290  int backoffTo2 =
291  shape2[0].l + alpha - shape1[0].l;
292 
293  result[0] = Extent(topmostL, topmostR+alpha);
294 
295  // Now, since extents are given in relative units, in order to
296  // compute the extents of the merged shape, we can just collect the
297  // extents of shape1 and shape2, until one of the shapes ends. If
298  // this happens, we need to "back-off" to the axis of the deeper
299  // shape in order to properly determine the remaining extents.
300  int i=1;
301  for (; i<depth1 && i<depth2; i++) {
302  Extent currentExtent1 = shape1[i];
303  Extent currentExtent2 = shape2[i];
304  int newExtentL = currentExtent1.l;
305  int newExtentR = currentExtent2.r;
306  result[i] = Extent(newExtentL, newExtentR);
307  backoffTo1 += currentExtent1.r - currentExtent2.r;
308  backoffTo2 += currentExtent2.l - currentExtent1.l;
309  }
310 
311  // If shape1 is deeper than shape2, back off to the axis of shape1,
312  // and process the remaining extents of shape1.
313  if (i<depth1) {
314  Extent currentExtent1 = shape1[i];
315  int newExtentL = currentExtent1.l;
316  int newExtentR = currentExtent1.r;
317  result[i] = Extent(newExtentL, newExtentR+backoffTo1);
318  ++i;
319  for (; i<depth1; i++) {
320  result[i] = shape1[i];
321  }
322  }
323 
324  // Vice versa, if shape2 is deeper than shape1, back off to the
325  // axis of shape2, and process the remaining extents of shape2.
326  if (i<depth2) {
327  Extent currentExtent2 = shape2[i];
328  int newExtentL = currentExtent2.l;
329  int newExtentR = currentExtent2.r;
330  result[i] = Extent(newExtentL+backoffTo2, newExtentR);
331  ++i;
332  for (; i<depth2; i++) {
333  result[i] = shape2[i];
334  }
335  }
336  }
337  }
338 
339  void
341  if (shape != s)
343  shape = s;
345  }
346 
347  void
349  int numberOfShapes = getNumberOfChildren();
350  Extent extent(Layout::extent);
351 
352  int maxDepth = 0;
353  for (int i = numberOfShapes; i--;)
354  maxDepth = std::max(maxDepth, getChild(na,i)->getShape()->depth());
355  Shape* mergedShape;
356  if (getShape() && getShape()->depth() >= maxDepth+1) {
357  mergedShape = getShape();
358  mergedShape->setDepth(maxDepth+1);
359  } else {
360  mergedShape = Shape::allocate(maxDepth+1);
361  }
362 
363  if (numberOfShapes == 1) {
364  getChild(na,0)->setOffset(0);
365  const Shape* childShape = getChild(na,0)->getShape();
366  for (int i=childShape->depth(); i--;)
367  (*mergedShape)[i+1] = (*childShape)[i];
368  (*mergedShape)[1].extend(- extent.l, - extent.r);
369  setShape(mergedShape);
370  } else {
371  // alpha stores the necessary distances between the
372  // axes of the shapes in the list: alpha[i].first gives the distance
373  // between shape[i] and shape[i-1], when shape[i-1] and shape[i]
374  // are merged left-to-right; alpha[i].second gives the distance between
375  // shape[i] and shape[i+1], when shape[i] and shape[i+1] are merged
376  // right-to-left.
377  assert(root->copy != NULL);
378  Region r(*root->copy);
379  std::pair<int,int>* alpha =
380  r.alloc<std::pair<int,int> >(numberOfShapes);
381 
382  // distance between the leftmost and the rightmost axis in the list
383  int width = 0;
384 
385  Extent* currentShapeL = r.alloc<Extent>(maxDepth);
386  int ldepth = getChild(na,0)->getShape()->depth();
387  for (int i=ldepth; i--;)
388  currentShapeL[i] = (*getChild(na,0)->getShape())[i];
389 
390  // After merging, we can pick the result of either merging left or right
391  // Here we chose the result of merging right
392  Shape* rShape = getChild(na,numberOfShapes-1)->getShape();
393  int rdepth = rShape->depth();
394  for (int i=rdepth; i--;)
395  (*mergedShape)[i+1] = (*rShape)[i];
396  Extent* currentShapeR = &(*mergedShape)[1];
397 
398  for (int i = 1; i < numberOfShapes; i++) {
399  // Merge left-to-right. Note that due to the asymmetry of the
400  // merge operation, nextAlphaL is the distance between the
401  // *leftmost* axis in the shape list, and the axis of
402  // nextShapeL; what we are really interested in is the distance
403  // between the *previous* axis and the axis of nextShapeL.
404  // This explains the correction.
405 
406  Shape* nextShapeL = getChild(na,i)->getShape();
407  int nextAlphaL =
408  Layouter::getAlpha<Extent*,Shape>(&currentShapeL[0], ldepth,
409  *nextShapeL, nextShapeL->depth());
410  Layouter::merge<Extent*,Shape>(&currentShapeL[0],
411  &currentShapeL[0], ldepth,
412  *nextShapeL, nextShapeL->depth(),
413  nextAlphaL);
414  ldepth = std::max(ldepth,nextShapeL->depth());
415  alpha[i].first = nextAlphaL - width;
416  width = nextAlphaL;
417 
418  // Merge right-to-left. Here, a correction of nextAlphaR is
419  // not required.
420  Shape* nextShapeR = getChild(na,numberOfShapes-1-i)->getShape();
421  int nextAlphaR =
422  Layouter::getAlpha<Shape,Extent*>(*nextShapeR, nextShapeR->depth(),
423  &currentShapeR[0], rdepth);
424  Layouter::merge<Shape,Extent*>(&currentShapeR[0],
425  *nextShapeR, nextShapeR->depth(),
426  &currentShapeR[0], rdepth,
427  nextAlphaR);
428  rdepth = std::max(rdepth,nextShapeR->depth());
429  alpha[numberOfShapes - i].second = nextAlphaR;
430  }
431 
432  // The merged shape has to be adjusted to its topmost extent
433  (*mergedShape)[1].extend(- extent.l, - extent.r);
434 
435  // After the loop, the merged shape has the same axis as the
436  // leftmost shape in the list. What we want is to move the axis
437  // such that it is the center of the axis of the leftmost shape in
438  // the list and the axis of the rightmost shape.
439  int halfWidth = false ? 0 : width / 2;
440  (*mergedShape)[1].move(- halfWidth);
441 
442  // Finally, for the offset lists. Now that the axis of the merged
443  // shape is at the center of the two extreme axes, the first shape
444  // needs to be offset by -halfWidth units with respect to the new
445  // axis. As for the offsets for the other shapes, we take the
446  // median of the alphaL and alphaR values, as suggested in
447  // Kennedy's paper.
448  int offset = - halfWidth;
449  getChild(na,0)->setOffset(offset);
450  for (int i = 1; i < numberOfShapes; i++) {
451  offset += (alpha[i].first + alpha[i].second) / 2;
452  getChild(na,i)->setOffset(offset);
453  }
454  setShape(mergedShape);
455  }
456  }
457 
458  size_t
459  VisualNode::size(void) const {
460  size_t s = sizeof(*this);
461  s += sizeof(Node*)*getNumberOfChildren();
462  if (shape && shape != Shape::leaf && shape != Shape::hidden) {
463  s += sizeof(Shape)+sizeof(Extent)*(shape->depth()-1);
464  }
465  if (copy)
466  s += static_cast<Space*>(Support::funmark(copy))->allocated();
467  s += (choice != NULL ? choice->size() : 0);
468  return s;
469  }
470 
471 }}
472 
473 // STATISTICS: gist-any