Generated on Sat May 25 2013 18:00:35 for Gecode by doxygen 1.8.3.1
treecanvas.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: 2013-03-07 17:39:13 +0100 (Thu, 07 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13458 $
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 
38 #include <QtGui/QPainter>
39 #include <QPrinter>
40 #include <QPrintDialog>
41 
42 #include <stack>
43 #include <fstream>
44 
46 
50 
51 #include <gecode/search.hh>
52 #include <gecode/search/support.hh>
53 
54 namespace Gecode { namespace Gist {
55 
56  TreeCanvas::TreeCanvas(Space* rootSpace, bool bab,
57  QWidget* parent, const Options& opt)
58  : QWidget(parent)
59  , mutex(QMutex::Recursive)
60  , layoutMutex(QMutex::Recursive)
61  , finishedFlag(false)
62  , compareNodes(false), compareNodesBeforeFP(false)
63  , autoHideFailed(true), autoZoom(false)
64  , refresh(500), refreshPause(0), smoothScrollAndZoom(false)
65  , moveDuringSearch(false)
66  , zoomTimeLine(500)
67  , scrollTimeLine(1000), targetX(0), sourceX(0), targetY(0), sourceY(0)
68  , targetW(0), targetH(0), targetScale(0)
69  , layoutDoneTimerId(0) {
70  QMutexLocker locker(&mutex);
71  curBest = (bab ? new BestNode(NULL) : NULL);
72  if (rootSpace->status() == SS_FAILED) {
73  if (!opt.clone)
74  delete rootSpace;
75  rootSpace = NULL;
76  } else {
77  rootSpace = Gecode::Search::snapshot(rootSpace,opt);
78  }
79  na = new Node::NodeAllocator(bab);
80  int rootIdx = na->allocate(rootSpace);
81  assert(rootIdx == 0); (void) rootIdx;
82  root = (*na)[0];
83  root->layout(*na);
84  root->setMarked(true);
85  currentNode = root;
86  pathHead = root;
87  scale = LayoutConfig::defScale / 100.0;
88 
89  setAutoFillBackground(true);
90 
91  connect(&searcher, SIGNAL(update(int,int,int)), this,
92  SLOT(layoutDone(int,int,int)));
93  connect(&searcher, SIGNAL(statusChanged(bool)), this,
94  SLOT(statusChanged(bool)));
95 
96  connect(&searcher, SIGNAL(solution(const Space*)),
97  this, SIGNAL(solution(const Space*)),
98  Qt::BlockingQueuedConnection);
99  connect(this, SIGNAL(solution(const Space*)),
100  this, SLOT(inspectSolution(const Space*)));
101  connect(&searcher, SIGNAL(solution(const Space*)),
102  this, SLOT(inspectSolution(const Space*)),
103  Qt::BlockingQueuedConnection);
104 
105  connect(&searcher, SIGNAL(moveToNode(VisualNode*,bool)),
106  this, SLOT(setCurrentNode(VisualNode*,bool)),
107  Qt::BlockingQueuedConnection);
108 
109  connect(&searcher, SIGNAL(searchFinished(void)), this, SIGNAL(searchFinished(void)));
110 
111  connect(&scrollTimeLine, SIGNAL(frameChanged(int)),
112  this, SLOT(scroll(int)));
113  scrollTimeLine.setCurveShape(QTimeLine::EaseInOutCurve);
114 
115  scaleBar = new QSlider(Qt::Vertical, this);
116  scaleBar->setObjectName("scaleBar");
117  scaleBar->setMinimum(LayoutConfig::minScale);
118  scaleBar->setMaximum(LayoutConfig::maxScale);
119  scaleBar->setValue(LayoutConfig::defScale);
120  connect(scaleBar, SIGNAL(valueChanged(int)),
121  this, SLOT(scaleTree(int)));
122  connect(this, SIGNAL(scaleChanged(int)), scaleBar, SLOT(setValue(int)));
123  connect(&searcher, SIGNAL(scaleChanged(int)),
124  scaleBar, SLOT(setValue(int)));
125 
126  connect(&zoomTimeLine, SIGNAL(frameChanged(int)),
127  scaleBar, SLOT(setValue(int)));
128  zoomTimeLine.setCurveShape(QTimeLine::EaseInOutCurve);
129 
130  qRegisterMetaType<Statistics>("Statistics");
131  update();
132  }
133 
135  if (root) {
136  DisposeCursor dc(root,*na);
138  }
139  delete na;
140  }
141 
142  void
144  doubleClickInspectors.append(QPair<Inspector*,bool>(i,false));
145  }
146 
147  void
149  assert(i < doubleClickInspectors.size());
150  doubleClickInspectors[i].second = active;
151  }
152 
153  void
155  solutionInspectors.append(QPair<Inspector*,bool>(i,false));
156  }
157 
158  void
160  assert(i < solutionInspectors.size());
161  solutionInspectors[i].second = active;
162  }
163 
164  void
166  moveInspectors.append(QPair<Inspector*,bool>(i,false));
167  }
168 
169  void
171  assert(i < moveInspectors.size());
172  moveInspectors[i].second = active;
173  }
174 
175  void
177  comparators.append(QPair<Comparator*,bool>(c,false));
178  }
179 
180  void
181  TreeCanvas::activateComparator(int i, bool active) {
182  assert(i < comparators.size());
183  comparators[i].second = active;
184  }
185 
186  void
187  TreeCanvas::scaleTree(int scale0, int zoomx, int zoomy) {
188  QMutexLocker locker(&layoutMutex);
189 
190  QSize viewport_size = size();
191  QAbstractScrollArea* sa =
192  static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
193 
194  if (zoomx==-1)
195  zoomx = viewport_size.width()/2;
196  if (zoomy==-1)
197  zoomy = viewport_size.height()/2;
198 
199  int xoff = (sa->horizontalScrollBar()->value()+zoomx)/scale;
200  int yoff = (sa->verticalScrollBar()->value()+zoomy)/scale;
201 
202  BoundingBox bb;
203  scale0 = std::min(std::max(scale0, LayoutConfig::minScale),
205  scale = (static_cast<double>(scale0)) / 100.0;
206  bb = root->getBoundingBox();
207  int w =
208  static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
209  int h =
210  static_cast<int>(2*Layout::extent+
212 
213  sa->horizontalScrollBar()->setRange(0,w-viewport_size.width());
214  sa->verticalScrollBar()->setRange(0,h-viewport_size.height());
215  sa->horizontalScrollBar()->setPageStep(viewport_size.width());
216  sa->verticalScrollBar()->setPageStep(viewport_size.height());
217  sa->horizontalScrollBar()->setSingleStep(Layout::extent);
218  sa->verticalScrollBar()->setSingleStep(Layout::extent);
219 
220  xoff *= scale;
221  yoff *= scale;
222 
223  sa->horizontalScrollBar()->setValue(xoff-zoomx);
224  sa->verticalScrollBar()->setValue(yoff-zoomy);
225 
226  emit scaleChanged(scale0);
227  QWidget::update();
228  }
229 
230  void
232  QMutexLocker locker(&mutex);
233  layoutMutex.lock();
234  if (root != NULL) {
235  root->layout(*na);
237 
238  int w = static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
239  int h =
240  static_cast<int>(2*Layout::extent+
242  xtrans = -bb.left+(Layout::extent / 2);
243 
244  QSize viewport_size = size();
245  QAbstractScrollArea* sa =
246  static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
247  sa->horizontalScrollBar()->setRange(0,w-viewport_size.width());
248  sa->verticalScrollBar()->setRange(0,h-viewport_size.height());
249  sa->horizontalScrollBar()->setPageStep(viewport_size.width());
250  sa->verticalScrollBar()->setPageStep(viewport_size.height());
251  sa->horizontalScrollBar()->setSingleStep(Layout::extent);
252  sa->verticalScrollBar()->setSingleStep(Layout::extent);
253  }
254  if (autoZoom)
255  zoomToFit();
256  layoutMutex.unlock();
257  QWidget::update();
258  }
259 
260  void
262  QWidget::update();
263  }
264 
265  void
266  TreeCanvas::layoutDone(int w, int h, int scale0) {
267  targetW = w; targetH = h; targetScale = scale0;
268 
269  QSize viewport_size = size();
270  QAbstractScrollArea* sa =
271  static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
272  sa->horizontalScrollBar()->setRange(0,w-viewport_size.width());
273  sa->verticalScrollBar()->setRange(0,h-viewport_size.height());
274 
275  if (layoutDoneTimerId == 0)
276  layoutDoneTimerId = startTimer(15);
277  }
278 
279  void
280  TreeCanvas::statusChanged(bool finished) {
281  if (finished) {
282  update();
284  }
285  emit statusChanged(currentNode, stats, finished);
286  }
287 
288  void
290  node = n;
291 
292  depth = -1;
293  for (VisualNode* p = n; p != NULL; p = p->getParent(*ti->na))
294  depth++;
295 
296  a = all;
297  t = ti;
298  start();
299  }
300 
301  void
302  SearcherThread::updateCanvas(void) {
303  t->layoutMutex.lock();
304  if (t->root == NULL)
305  return;
306 
307  if (t->autoHideFailed) {
308  t->root->hideFailed(*t->na,true);
309  }
310  for (VisualNode* n = t->currentNode; n != NULL; n=n->getParent(*t->na)) {
311  if (n->isHidden()) {
312  t->currentNode->setMarked(false);
313  t->currentNode = n;
314  t->currentNode->setMarked(true);
315  break;
316  }
317  }
318 
319  t->root->layout(*t->na);
320  BoundingBox bb = t->root->getBoundingBox();
321 
322  int w = static_cast<int>((bb.right-bb.left+Layout::extent)*t->scale);
323  int h = static_cast<int>(2*Layout::extent+
324  t->root->getShape()->depth()
325  *Layout::dist_y*t->scale);
326  t->xtrans = -bb.left+(Layout::extent / 2);
327 
328  int scale0 = static_cast<int>(t->scale*100);
329  if (t->autoZoom) {
330  QWidget* p = t->parentWidget();
331  if (p) {
332  double newXScale =
333  static_cast<double>(p->width()) / (bb.right - bb.left +
335  double newYScale =
336  static_cast<double>(p->height()) /
338 
339  scale0 = static_cast<int>(std::min(newXScale, newYScale)*100);
340  if (scale0<LayoutConfig::minScale)
341  scale0 = LayoutConfig::minScale;
344  double scale = (static_cast<double>(scale0)) / 100.0;
345 
346  w = static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
347  h = static_cast<int>(2*Layout::extent+
348  t->root->getShape()->depth()*Layout::dist_y*scale);
349  }
350  }
351 
352  t->layoutMutex.unlock();
353  emit update(w,h,scale0);
354  }
355 
357  class SearchItem {
358  public:
362  int i;
366  SearchItem(VisualNode* n0, int noOfChildren0)
367  : n(n0), i(-1), noOfChildren(noOfChildren0) {}
368  };
369 
370  void
372  {
373  if (!node->isOpen())
374  return;
375  t->mutex.lock();
376  emit statusChanged(false);
377 
378  unsigned int kids =
379  node->getNumberOfChildNodes(*t->na, t->curBest, t->stats,
380  t->c_d, t->a_d);
381  if (kids == 0 || node->getStatus() == STOP) {
382  t->mutex.unlock();
383  updateCanvas();
384  emit statusChanged(true);
385  return;
386  }
387 
388  std::stack<SearchItem> stck;
389  stck.push(SearchItem(node,kids));
390  t->stats.maxDepth =
391  std::max(static_cast<long unsigned int>(t->stats.maxDepth),
392  static_cast<long unsigned int>(depth+stck.size()));
393 
394  VisualNode* sol = NULL;
395  int nodeCount = 0;
396  t->stopSearchFlag = false;
397  while (!stck.empty() && !t->stopSearchFlag) {
398  if (t->refresh > 0 && nodeCount >= t->refresh) {
399  node->dirtyUp(*t->na);
400  updateCanvas();
401  emit statusChanged(false);
402  nodeCount = 0;
403  if (t->refreshPause > 0)
404  msleep(t->refreshPause);
405  }
406  SearchItem& si = stck.top();
407  si.i++;
408  if (si.i == si.noOfChildren) {
409  stck.pop();
410  } else {
411  VisualNode* n = si.n->getChild(*t->na,si.i);
412  if (n->isOpen()) {
413  if (n->getStatus() == UNDETERMINED)
414  nodeCount++;
415  kids = n->getNumberOfChildNodes(*t->na, t->curBest, t->stats,
416  t->c_d, t->a_d);
417  if (kids == 0) {
418  if (n->getStatus() == SOLVED) {
419  assert(n->hasCopy());
420  emit solution(n->getWorkingSpace());
421  n->purge(*t->na);
422  sol = n;
423  if (!a)
424  break;
425  }
426  } else {
427  if ( n->getStatus() != STOP )
428  stck.push(SearchItem(n,kids));
429  else if (!a)
430  break;
431  t->stats.maxDepth =
432  std::max(static_cast<long unsigned int>(t->stats.maxDepth),
433  static_cast<long unsigned int>(depth+stck.size()));
434  }
435  }
436  if (t->moveDuringSearch)
437  emit moveToNode(n,false);
438  }
439  }
440  node->dirtyUp(*t->na);
441  t->stopSearchFlag = false;
442  t->mutex.unlock();
443  if (sol != NULL) {
444  t->setCurrentNode(sol,true,false);
445  } else {
446  t->setCurrentNode(node,true,false);
447  }
448  }
449  updateCanvas();
450  emit statusChanged(true);
451  if (t->finishedFlag)
452  emit searchFinished();
453  }
454 
455  void
457  QMutexLocker locker(&mutex);
458  searcher.search(currentNode, true, this);
459  }
460 
461  void
463  QMutexLocker locker(&mutex);
464  searcher.search(currentNode, false, this);
465  }
466 
467  void
469  QMutexLocker locker(&mutex);
471  update();
473  emit statusChanged(currentNode, stats, true);
474  }
475 
476  void
478  QMutexLocker locker(&mutex);
480  update();
482  emit statusChanged(currentNode, stats, true);
483  }
484 
485  void
487  QMutexLocker locker(&mutex);
488  QMutexLocker layoutLocker(&layoutMutex);
490  update();
492  emit statusChanged(currentNode, stats, true);
493  }
494 
495  void
497  QMutexLocker locker(&mutex);
499  update();
501  emit statusChanged(currentNode, stats, true);
502  }
503 
504  void
506  QMutexLocker locker(&mutex);
507  QMutexLocker layoutLocker(&layoutMutex);
509  update();
511  emit statusChanged(currentNode, stats, true);
512  }
513 
514  void
515  TreeCanvas::timerEvent(QTimerEvent* e) {
516  if (e->timerId() == layoutDoneTimerId) {
517  if (!smoothScrollAndZoom) {
519  } else {
520  zoomTimeLine.stop();
521  int zoomCurrent = static_cast<int>(scale*100);
522  int targetZoom = targetScale;
523  targetZoom = std::min(std::max(targetZoom, LayoutConfig::minScale),
525  zoomTimeLine.setFrameRange(zoomCurrent,targetZoom);
526  zoomTimeLine.start();
527  }
528  QWidget::update();
529  killTimer(layoutDoneTimerId);
530  layoutDoneTimerId = 0;
531  }
532  }
533 
534  void
536  QMutexLocker locker(&layoutMutex);
537  if (root != NULL) {
538  BoundingBox bb;
539  bb = root->getBoundingBox();
540  QWidget* p = parentWidget();
541  if (p) {
542  double newXScale =
543  static_cast<double>(p->width()) / (bb.right - bb.left +
545  double newYScale =
546  static_cast<double>(p->height()) / (root->getShape()->depth() *
548  2*Layout::extent);
549  int scale0 = static_cast<int>(std::min(newXScale, newYScale)*100);
550  if (scale0<LayoutConfig::minScale)
551  scale0 = LayoutConfig::minScale;
554 
555  if (!smoothScrollAndZoom) {
556  scaleTree(scale0);
557  } else {
558  zoomTimeLine.stop();
559  int zoomCurrent = static_cast<int>(scale*100);
560  int targetZoom = scale0;
561  targetZoom = std::min(std::max(targetZoom, LayoutConfig::minScale),
563  zoomTimeLine.setFrameRange(zoomCurrent,targetZoom);
564  zoomTimeLine.start();
565  }
566  }
567  }
568  }
569 
570  void
572  QMutexLocker locker(&mutex);
573  int x=0;
574  int y=0;
575 
577  while (c != NULL) {
578  x += c->getOffset();
579  y += Layout::dist_y;
580  c = c->getParent(*na);
581  }
582 
583  x = static_cast<int>((xtrans+x)*scale); y = static_cast<int>(y*scale);
584 
585  QAbstractScrollArea* sa =
586  static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
587 
588  x -= sa->viewport()->width() / 2;
589  y -= sa->viewport()->height() / 2;
590 
591  sourceX = sa->horizontalScrollBar()->value();
592  targetX = std::max(sa->horizontalScrollBar()->minimum(), x);
593  targetX = std::min(sa->horizontalScrollBar()->maximum(),
594  targetX);
595  sourceY = sa->verticalScrollBar()->value();
596  targetY = std::max(sa->verticalScrollBar()->minimum(), y);
597  targetY = std::min(sa->verticalScrollBar()->maximum(),
598  targetY);
599  if (!smoothScrollAndZoom) {
600  sa->horizontalScrollBar()->setValue(targetX);
601  sa->verticalScrollBar()->setValue(targetY);
602  } else {
603  scrollTimeLine.stop();
604  scrollTimeLine.setFrameRange(0,100);
605  scrollTimeLine.setDuration(std::max(200,
606  std::min(1000,
607  std::min(std::abs(sourceX-targetX),
608  std::abs(sourceY-targetY)))));
609  scrollTimeLine.start();
610  }
611  }
612 
613  void
614  TreeCanvas::scroll(int i) {
615  QAbstractScrollArea* sa =
616  static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
617  double p = static_cast<double>(i)/100.0;
618  double xdiff = static_cast<double>(targetX-sourceX)*p;
619  double ydiff = static_cast<double>(targetY-sourceY)*p;
620  sa->horizontalScrollBar()->setValue(sourceX+static_cast<int>(xdiff));
621  sa->verticalScrollBar()->setValue(sourceY+static_cast<int>(ydiff));
622  }
623 
624  void
625  TreeCanvas::inspectCurrentNode(bool fix, int inspectorNo) {
626  QMutexLocker locker(&mutex);
627 
628  if (currentNode->isHidden()) {
629  toggleHidden();
630  return;
631  }
632 
633  int failedInspectorType = -1;
634  int failedInspector = -1;
635  bool needCentering = false;
636  try {
637  switch (currentNode->getStatus()) {
638  case UNDETERMINED:
639  {
640  unsigned int kids =
642  int depth = -1;
643  for (VisualNode* p = currentNode; p != NULL; p=p->getParent(*na))
644  depth++;
645  if (kids > 0) {
646  needCentering = true;
647  depth++;
648  }
649  stats.maxDepth =
650  std::max(stats.maxDepth, depth);
651  if (currentNode->getStatus() == SOLVED) {
652  assert(currentNode->hasCopy());
654  }
655  emit statusChanged(currentNode,stats,true);
656  for (int i=0; i<moveInspectors.size(); i++) {
657  if (moveInspectors[i].second) {
658  failedInspectorType = 0;
659  failedInspector = i;
660  if (currentNode->getStatus() == FAILED) {
661  if (!currentNode->isRoot()) {
662  Space* curSpace =
664  moveInspectors[i].first->inspect(*curSpace);
665  delete curSpace;
666  }
667  } else {
668  moveInspectors[i].first->
669  inspect(*currentNode->getWorkingSpace());
670  }
671  failedInspectorType = -1;
672  }
673  }
674  if (currentNode->getStatus() == SOLVED) {
675  currentNode->purge(*na);
676  }
677  }
678  break;
679  case FAILED:
680  case STOP:
681  case UNSTOP:
682  case BRANCH:
683  case SOLVED:
684  {
685  // SizeCursor sc(currentNode);
686  // PreorderNodeVisitor<SizeCursor> pnv(sc);
687  // int nodes = 1;
688  // while (pnv.next()) { nodes++; }
689  // std::cout << "sizeof(VisualNode): " << sizeof(VisualNode)
690  // << std::endl;
691  // std::cout << "Size: " << (pnv.getCursor().s)/1024 << std::endl;
692  // std::cout << "Nodes: " << nodes << std::endl;
693  // std::cout << "Size / node: " << (pnv.getCursor().s)/nodes
694  // << std::endl;
695 
696  Space* curSpace;
697 
698  if (fix) {
700  break;
701  curSpace = currentNode->getSpace(*na,curBest,c_d,a_d);
702  if (currentNode->getStatus() == SOLVED &&
703  curSpace->status() != SS_SOLVED) {
704  // in the presence of weakly monotonic propagators, we may have
705  // to use search to find the solution here
706  assert(curSpace->status() == SS_BRANCH &&
707  "Something went wrong - probably an incorrect brancher");
708  Space* dfsSpace = Gecode::dfs(curSpace);
709  delete curSpace;
710  curSpace = dfsSpace;
711  }
712  } else {
713  if (currentNode->isRoot())
714  break;
716  curSpace = p->getSpace(*na,curBest,c_d,a_d);
717  switch (curSpace->status()) {
718  case SS_SOLVED:
719  case SS_FAILED:
720  break;
721  case SS_BRANCH:
722  curSpace->commit(*p->getChoice(),
724  break;
725  default:
726  GECODE_NEVER;
727  }
728  }
729 
730  if (inspectorNo==-1) {
731  for (int i=0; i<doubleClickInspectors.size(); i++) {
732  if (doubleClickInspectors[i].second) {
733  failedInspectorType = 1;
734  failedInspector = i;
735  doubleClickInspectors[i].first->inspect(*curSpace);
736  failedInspectorType = -1;
737  }
738  }
739  } else {
740  failedInspectorType = 1;
741  failedInspector = inspectorNo;
742  doubleClickInspectors[inspectorNo].first->inspect(*curSpace);
743  failedInspectorType = -1;
744  }
745  delete curSpace;
746  }
747  break;
748  }
749  } catch (Exception& e) {
750  switch (failedInspectorType) {
751  case 0:
752  qFatal("Exception in move inspector %d: %s.\n Stopping.",
753  failedInspector, e.what());
754  break;
755  case 1:
756  qFatal("Exception in double click inspector %d: %s.\n Stopping.",
757  failedInspector, e.what());
758  break;
759  default:
760  qFatal("Exception: %s.\n Stopping.", e.what());
761  break;
762  }
763  }
764 
766  update();
767  if (needCentering)
769  }
770 
771  void
773  inspectCurrentNode(false);
774  }
775 
776  void
777  TreeCanvas::inspectSolution(const Space* s) {
778  int failedInspectorType = -1;
779  int failedInspector = -1;
780  try {
781  Space* c = NULL;
782  for (int i=0; i<solutionInspectors.size(); i++) {
783  if (solutionInspectors[i].second) {
784  if (c == NULL)
785  c = s->clone();
786  failedInspectorType = 1;
787  failedInspector = i;
788  solutionInspectors[i].first->inspect(*c);
789  failedInspectorType = -1;
790  }
791  }
792  delete c;
793  } catch (Exception& e) {
794  switch (failedInspectorType) {
795  case 0:
796  qFatal("Exception in move inspector %d: %s.\n Stopping.",
797  failedInspector, e.what());
798  break;
799  case 1:
800  qFatal("Exception in solution inspector %d: %s.\n Stopping.",
801  failedInspector, e.what());
802  break;
803  default:
804  qFatal("Exception: %s.\n Stopping.", e.what());
805  break;
806  }
807  }
808  }
809 
810  void
812  stopSearchFlag = true;
813  layoutDoneTimerId = startTimer(15);
814  }
815 
816  void
818  QMutexLocker locker(&mutex);
819  Space* rootSpace =
820  root->getStatus() == FAILED ? NULL :
822  if (curBest != NULL) {
823  delete curBest;
824  curBest = new BestNode(NULL);
825  }
826  if (root) {
827  DisposeCursor dc(root,*na);
829  }
830  delete na;
831  na = new Node::NodeAllocator(curBest != NULL);
832  int rootIdx = na->allocate(rootSpace);
833  assert(rootIdx == 0); (void) rootIdx;
834  root = (*na)[0];
835  root->setMarked(true);
836  currentNode = root;
837  pathHead = root;
838  scale = 1.0;
839  stats = Statistics();
840  for (int i=bookmarks.size(); i--;)
841  emit removedBookmark(i);
842  bookmarks.clear();
843  root->layout(*na);
844 
845  emit statusChanged(currentNode, stats, true);
846  update();
847  }
848 
849  void
851  QMutexLocker locker(&mutex);
852  if (!currentNode->isBookmarked()) {
853  bool ok;
854  QString text =
855  QInputDialog::getText(this, "Add bookmark", "Name:",
856  QLineEdit::Normal,"",&ok);
857  if (ok) {
858  currentNode->setBookmarked(true);
859  bookmarks.append(currentNode);
860  if (text == "")
861  text = QString("Node ")+QString().setNum(bookmarks.size());
862  emit addedBookmark(text);
863  }
864  } else {
865  currentNode->setBookmarked(false);
866  int idx = bookmarks.indexOf(currentNode);
867  bookmarks.remove(idx);
868  emit removedBookmark(idx);
869  }
871  update();
872  }
873 
874  void
876  QMutexLocker locker(&mutex);
877  if(currentNode == pathHead)
878  return;
879 
880  pathHead->unPathUp(*na);
882 
883  currentNode->pathUp(*na);
885  update();
886  }
887 
888  void
890  QMutexLocker locker(&mutex);
892  if (currentNode->isOnPath()) {
894  int nextAlt = currentNode->getPathAlternative(*na);
895  while (nextAlt >= 0) {
898  nextAlt = currentNode->getPathAlternative(*na);
899  }
900  }
901  update();
902  }
903 
904  void
906  QMutexLocker locker(&mutex);
907  compareNodes = true;
908  compareNodesBeforeFP = false;
909  setCursor(QCursor(Qt::CrossCursor));
910  }
911 
912  void
914  QMutexLocker locker(&mutex);
915  compareNodes = true;
916  compareNodesBeforeFP = true;
917  setCursor(QCursor(Qt::CrossCursor));
918  }
919 
920  void
922  emit statusChanged(currentNode, stats, true);
923  }
924 
925  void
927  QMutexLocker locker(&mutex);
928 
930 
931  setCurrentNode(p);
932 
933  if (p != NULL) {
935  }
936  }
937 
938  void
940  QMutexLocker locker(&mutex);
941  if (!currentNode->isHidden()) {
942  switch (currentNode->getStatus()) {
943  case STOP:
944  case UNSTOP:
945  case BRANCH:
946  {
947  int alt = std::max(0, currentNode->getPathAlternative(*na));
948  VisualNode* n = currentNode->getChild(*na,alt);
949  setCurrentNode(n);
951  break;
952  }
953  case SOLVED:
954  case FAILED:
955  case UNDETERMINED:
956  break;
957  }
958  }
959  }
960 
961  void
963  QMutexLocker locker(&mutex);
965  if (p != NULL) {
966  int alt = currentNode->getAlternative(*na);
967  if (alt > 0) {
968  VisualNode* n = p->getChild(*na,alt-1);
969  setCurrentNode(n);
971  }
972  }
973  }
974 
975  void
977  QMutexLocker locker(&mutex);
979  if (p != NULL) {
980  unsigned int alt = currentNode->getAlternative(*na);
981  if (alt + 1 < p->getNumberOfChildren()) {
982  VisualNode* n = p->getChild(*na,alt+1);
983  setCurrentNode(n);
985  }
986  }
987  }
988 
989  void
991  QMutexLocker locker(&mutex);
994  }
995 
996  void
998  QMutexLocker locker(&mutex);
999  NextSolCursor nsc(currentNode,back,*na);
1001  nsv.run();
1002  VisualNode* n = nsv.getCursor().node();
1003  if (n != root) {
1004  setCurrentNode(n);
1006  }
1007  }
1008 
1009  void
1011  navNextSol(true);
1012  }
1013 
1014  void
1015  TreeCanvas::exportNodePDF(VisualNode* n) {
1016 #if QT_VERSION >= 0x040400
1017  QString filename = QFileDialog::getSaveFileName(this, tr("Export tree as pdf"), "", tr("PDF (*.pdf)"));
1018  if (filename != "") {
1019  QPrinter printer(QPrinter::ScreenResolution);
1020  QMutexLocker locker(&mutex);
1021 
1022  BoundingBox bb = n->getBoundingBox();
1023  printer.setFullPage(true);
1024  printer.setPaperSize(QSizeF(bb.right-bb.left+Layout::extent,
1025  n->getShape()->depth() * Layout::dist_y +
1026  Layout::extent), QPrinter::Point);
1027  printer.setOutputFileName(filename);
1028  QPainter painter(&printer);
1029 
1030  painter.setRenderHint(QPainter::Antialiasing);
1031 
1032  QRect pageRect = printer.pageRect();
1033  double newXScale =
1034  static_cast<double>(pageRect.width()) / (bb.right - bb.left +
1035  Layout::extent);
1036  double newYScale =
1037  static_cast<double>(pageRect.height()) /
1038  (n->getShape()->depth() * Layout::dist_y +
1039  Layout::extent);
1040  double printScale = std::min(newXScale, newYScale);
1041  painter.scale(printScale,printScale);
1042 
1043  int printxtrans = -bb.left+(Layout::extent / 2);
1044 
1045  painter.translate(printxtrans, Layout::dist_y / 2);
1046  QRect clip(0,0,0,0);
1047  DrawingCursor dc(n, *na, curBest, painter, clip, showCopies);
1048  currentNode->setMarked(false);
1050  currentNode->setMarked(true);
1051  }
1052 #else
1053  (void) n;
1054 #endif
1055  }
1056 
1057  void
1059 #if QT_VERSION >= 0x040400
1060  exportNodePDF(root);
1061 #endif
1062  }
1063 
1064  void
1066 #if QT_VERSION >= 0x040400
1067  exportNodePDF(currentNode);
1068 #endif
1069  }
1070 
1071  void
1073  QPrinter printer;
1074  if (QPrintDialog(&printer, this).exec() == QDialog::Accepted) {
1075  QMutexLocker locker(&mutex);
1076 
1078  QRect pageRect = printer.pageRect();
1079  double newXScale =
1080  static_cast<double>(pageRect.width()) / (bb.right - bb.left +
1081  Layout::extent);
1082  double newYScale =
1083  static_cast<double>(pageRect.height()) /
1084  (root->getShape()->depth() * Layout::dist_y +
1085  2*Layout::extent);
1086  double printScale = std::min(newXScale, newYScale)*100;
1087  if (printScale<1.0)
1088  printScale = 1.0;
1089  if (printScale > 400.0)
1090  printScale = 400.0;
1091  printScale = printScale / 100.0;
1092 
1093  QPainter painter(&printer);
1094  painter.setRenderHint(QPainter::Antialiasing);
1095  painter.scale(printScale,printScale);
1096  painter.translate(xtrans, 0);
1097  QRect clip(0,0,0,0);
1098  DrawingCursor dc(root, *na, curBest, painter, clip, showCopies);
1100  }
1101  }
1102 
1103  VisualNode*
1104  TreeCanvas::eventNode(QEvent* event) {
1105  int x = 0;
1106  int y = 0;
1107  switch (event->type()) {
1108  case QEvent::ToolTip:
1109  {
1110  QHelpEvent* he = static_cast<QHelpEvent*>(event);
1111  x = he->x();
1112  y = he->y();
1113  break;
1114  }
1115  case QEvent::MouseButtonDblClick:
1116  case QEvent::MouseButtonPress:
1117  case QEvent::MouseButtonRelease:
1118  case QEvent::MouseMove:
1119  {
1120  QMouseEvent* me = static_cast<QMouseEvent*>(event);
1121  x = me->x();
1122  y = me->y();
1123  break;
1124  }
1125  case QEvent::ContextMenu:
1126  {
1127  QContextMenuEvent* ce = static_cast<QContextMenuEvent*>(event);
1128  x = ce->x();
1129  y = ce->y();
1130  break;
1131  }
1132  default:
1133  return NULL;
1134  }
1135  QAbstractScrollArea* sa =
1136  static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
1137  int xoff = sa->horizontalScrollBar()->value()/scale;
1138  int yoff = sa->verticalScrollBar()->value()/scale;
1139 
1141  int w =
1142  static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
1143  if (w < sa->viewport()->width())
1144  xoff -= (sa->viewport()->width()-w)/2;
1145 
1146  VisualNode* n;
1147  n = root->findNode(*na,
1148  static_cast<int>(x/scale-xtrans+xoff),
1149  static_cast<int>((y-30)/scale+yoff));
1150  return n;
1151  }
1152 
1153  bool
1154  TreeCanvas::event(QEvent* event) {
1155  if (mutex.tryLock()) {
1156  if (event->type() == QEvent::ToolTip) {
1157  VisualNode* n = eventNode(event);
1158  if (n != NULL && !n->isHidden() &&
1159  (n->getStatus() == BRANCH || n->getStatus() == STOP)) {
1160  QHelpEvent* he = static_cast<QHelpEvent*>(event);
1161  QToolTip::showText(he->globalPos(),
1162  QString(n->toolTip(curBest,c_d,a_d).c_str()));
1163  } else {
1164  QToolTip::hideText();
1165  }
1166  }
1167  mutex.unlock();
1168  }
1169  return QWidget::event(event);
1170  }
1171 
1172  void
1174  if (autoZoom)
1175  zoomToFit();
1176  }
1177 
1178  void
1179  TreeCanvas::paintEvent(QPaintEvent* event) {
1180  QMutexLocker locker(&layoutMutex);
1181  QPainter painter(this);
1182  painter.setRenderHint(QPainter::Antialiasing);
1183 
1184  QAbstractScrollArea* sa =
1185  static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
1186  int xoff = sa->horizontalScrollBar()->value()/scale;
1187  int yoff = sa->verticalScrollBar()->value()/scale;
1188 
1190  int w =
1191  static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
1192  if (w < sa->viewport()->width())
1193  xoff -= (sa->viewport()->width()-w)/2;
1194 
1195  QRect origClip = event->rect();
1196  painter.translate(0, 30);
1197  painter.scale(scale,scale);
1198  painter.translate(xtrans-xoff, -yoff);
1199  QRect clip(static_cast<int>(origClip.x()/scale-xtrans+xoff),
1200  static_cast<int>(origClip.y()/scale+yoff),
1201  static_cast<int>(origClip.width()/scale),
1202  static_cast<int>(origClip.height()/scale));
1203  DrawingCursor dc(root, *na, curBest, painter, clip, showCopies);
1205 
1206  // int nodesLayouted = 1;
1207  // clock_t t0 = clock();
1208  // while (v.next()) { nodesLayouted++; }
1209  // double t = (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
1210  // double nps = static_cast<double>(nodesLayouted) /
1211  // (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC);
1212  // std::cout << "Drawing done. " << nodesLayouted << " nodes in "
1213  // << t << " ms. " << nps << " nodes/s." << std::endl;
1214 
1215  }
1216 
1217  void
1219  if (mutex.tryLock()) {
1220  if(event->button() == Qt::LeftButton) {
1221  VisualNode* n = eventNode(event);
1222  if(n == currentNode) {
1224  event->accept();
1225  mutex.unlock();
1226  return;
1227  }
1228  }
1229  mutex.unlock();
1230  }
1231  event->ignore();
1232  }
1233 
1234  void
1235  TreeCanvas::contextMenuEvent(QContextMenuEvent* event) {
1236  if (mutex.tryLock()) {
1237  VisualNode* n = eventNode(event);
1238  if (n != NULL) {
1239  setCurrentNode(n);
1240  emit contextMenu(event);
1241  event->accept();
1242  mutex.unlock();
1243  return;
1244  }
1245  mutex.unlock();
1246  }
1247  event->ignore();
1248  }
1249 
1250  void
1251  TreeCanvas::resizeEvent(QResizeEvent* e) {
1252  QAbstractScrollArea* sa =
1253  static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
1254 
1255  int w = sa->horizontalScrollBar()->maximum()+e->oldSize().width();
1256  int h = sa->verticalScrollBar()->maximum()+e->oldSize().height();
1257 
1258  sa->horizontalScrollBar()->setRange(0,w-e->size().width());
1259  sa->verticalScrollBar()->setRange(0,h-e->size().height());
1260  sa->horizontalScrollBar()->setPageStep(e->size().width());
1261  sa->verticalScrollBar()->setPageStep(e->size().height());
1262  }
1263 
1264  void
1265  TreeCanvas::wheelEvent(QWheelEvent* event) {
1266  if (event->modifiers() & Qt::ShiftModifier) {
1267  event->accept();
1268  if (event->orientation() == Qt::Vertical && !autoZoom)
1269  scaleTree(scale*100+ceil(static_cast<double>(event->delta())/4.0),
1270  event->x(), event->y());
1271  } else {
1272  event->ignore();
1273  }
1274  }
1275 
1276  bool
1278  if (finishedFlag)
1279  return true;
1280  stopSearchFlag = true;
1281  finishedFlag = true;
1282  for (int i=0; i<doubleClickInspectors.size(); i++)
1283  doubleClickInspectors[i].first->finalize();
1284  for (int i=0; i<solutionInspectors.size(); i++)
1285  solutionInspectors[i].first->finalize();
1286  for (int i=0; i<moveInspectors.size(); i++)
1287  moveInspectors[i].first->finalize();
1288  for (int i=0; i<comparators.size(); i++)
1289  comparators[i].first->finalize();
1290  return !searcher.isRunning();
1291  }
1292 
1293  void
1294  TreeCanvas::setCurrentNode(VisualNode* n, bool finished, bool update) {
1295  if (finished)
1296  mutex.lock();
1297  if (update && n != NULL && n != currentNode &&
1298  n->getStatus() != UNDETERMINED && !n->isHidden()) {
1299  Space* curSpace = NULL;
1300  for (int i=0; i<moveInspectors.size(); i++) {
1301  if (moveInspectors[i].second) {
1302  if (curSpace == NULL)
1303  curSpace = n->getSpace(*na,curBest,c_d,a_d);
1304  try {
1305  moveInspectors[i].first->inspect(*curSpace);
1306  } catch (Exception& e) {
1307  qFatal("Exception in move inspector %d: %s.\n Stopping.",
1308  i, e.what());
1309  }
1310  }
1311  }
1312  }
1313  if (n != NULL) {
1314  currentNode->setMarked(false);
1315  currentNode = n;
1316  currentNode->setMarked(true);
1317  emit statusChanged(currentNode,stats,finished);
1318  if (update) {
1319  compareNodes = false;
1320  setCursor(QCursor(Qt::ArrowCursor));
1321  QWidget::update();
1322  }
1323  }
1324  if (finished)
1325  mutex.unlock();
1326  }
1327 
1328  void
1329  TreeCanvas::mousePressEvent(QMouseEvent* event) {
1330  if (mutex.tryLock()) {
1331  if (event->button() == Qt::LeftButton) {
1332  VisualNode* n = eventNode(event);
1333  if (compareNodes) {
1334  if (n != NULL && n->getStatus() != UNDETERMINED &&
1335  currentNode != NULL &&
1337  Space* curSpace = NULL;
1338  Space* compareSpace = NULL;
1339  for (int i=0; i<comparators.size(); i++) {
1340  if (comparators[i].second) {
1341  if (curSpace == NULL) {
1342  curSpace = currentNode->getSpace(*na,curBest,c_d,a_d);
1343 
1344  if (!compareNodesBeforeFP || n->isRoot()) {
1345  compareSpace = n->getSpace(*na,curBest,c_d,a_d);
1346  } else {
1347  VisualNode* p = n->getParent(*na);
1348  compareSpace = p->getSpace(*na,curBest,c_d,a_d);
1349  switch (compareSpace->status()) {
1350  case SS_SOLVED:
1351  case SS_FAILED:
1352  break;
1353  case SS_BRANCH:
1354  compareSpace->commit(*p->getChoice(),
1355  n->getAlternative(*na));
1356  break;
1357  default:
1358  GECODE_NEVER;
1359  }
1360  }
1361  }
1362  try {
1363  comparators[i].first->compare(*curSpace,*compareSpace);
1364  } catch (Exception& e) {
1365  qFatal("Exception in comparator %d: %s.\n Stopping.",
1366  i, e.what());
1367  }
1368  }
1369  }
1370  }
1371  } else {
1372  setCurrentNode(n);
1373  }
1374  compareNodes = false;
1375  setCursor(QCursor(Qt::ArrowCursor));
1376  if (n != NULL) {
1377  event->accept();
1378  mutex.unlock();
1379  return;
1380  }
1381  }
1382  mutex.unlock();
1383  }
1384  event->ignore();
1385  }
1386 
1387  void
1388  TreeCanvas::setRecompDistances(int c_d0, int a_d0) {
1389  c_d = c_d0; a_d = a_d0;
1390  }
1391 
1392  void
1394  autoHideFailed = b;
1395  }
1396 
1397  void
1399  autoZoom = b;
1400  if (autoZoom) {
1401  zoomToFit();
1402  }
1403  emit autoZoomChanged(b);
1404  scaleBar->setEnabled(!b);
1405  }
1406 
1407  void
1409  showCopies = b;
1410  }
1411  bool
1413  return showCopies;
1414  }
1415 
1416  bool
1418  return autoHideFailed;
1419  }
1420 
1421  bool
1423  return autoZoom;
1424  }
1425 
1426  void
1428  refresh = i;
1429  }
1430 
1431  void
1433  refreshPause = i;
1434  if (refreshPause > 0)
1435  refresh = 1;
1436  }
1437 
1438  bool
1440  return smoothScrollAndZoom;
1441  }
1442 
1443  void
1446  }
1447 
1448  bool
1450  return moveDuringSearch;
1451  }
1452 
1453  void
1455  moveDuringSearch = b;
1456  }
1457 
1458 }}
1459 
1460 // STATISTICS: gist-any