Generated on Mon May 10 06:46:31 2010 for Gecode by doxygen 1.6.3

treecanvas.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-04-08 11:25:15 +0200 (Thu, 08 Apr 2010) $ by $Author: tack $
00011  *     $Revision: 10682 $
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 <QtGui/QPainter>
00039 
00040 #include <stack>
00041 #include <fstream>
00042 
00043 #include <gecode/gist/treecanvas.hh>
00044 
00045 #include <gecode/gist/nodevisitor.hh>
00046 #include <gecode/gist/layoutcursor.hh>
00047 #include <gecode/gist/visualnode.hh>
00048 #include <gecode/gist/drawingcursor.hh>
00049 
00050 #include <gecode/search.hh>
00051 #include <gecode/search/support.hh>
00052 
00053 namespace Gecode { namespace Gist {
00054 
00055   TreeCanvas::TreeCanvas(Space* rootSpace, bool bab,
00056                          QWidget* parent, const Options& opt)
00057     : QWidget(parent)
00058     , mutex(QMutex::Recursive)
00059     , layoutMutex(QMutex::Recursive)
00060     , finishedFlag(false)
00061     , compareNodes(false), compareNodesBeforeFP(false)
00062     , autoHideFailed(true), autoZoom(false)
00063     , refresh(500), smoothScrollAndZoom(false)
00064     , zoomTimeLine(500)
00065     , scrollTimeLine(1000), targetX(0), sourceX(0), targetY(0), sourceY(0)
00066     , targetW(0), targetH(0), targetScale(0)
00067     , layoutDoneTimerId(0) {
00068       QMutexLocker locker(&mutex);
00069       curBest = (bab ? new BestNode(NULL) : NULL);
00070       if (rootSpace->status() == SS_FAILED) {
00071         rootSpace = NULL;
00072       } else {
00073         rootSpace = Gecode::Search::snapshot(rootSpace,opt);
00074       }
00075       na = new Node::NodeAllocator();
00076       root = new (*na) VisualNode(rootSpace);
00077       root->layout();
00078       root->setMarked(true);
00079       currentNode = root;
00080       pathHead = root;
00081       scale = LayoutConfig::defScale / 100.0;
00082 
00083       setAutoFillBackground(true);
00084 
00085       connect(&searcher, SIGNAL(update(int,int,int)), this,
00086                          SLOT(layoutDone(int,int,int)));
00087       connect(&searcher, SIGNAL(statusChanged(bool)), this,
00088               SLOT(statusChanged(bool)));
00089 
00090       connect(&searcher, SIGNAL(solution(const Space*)),
00091               this, SIGNAL(solution(const Space*)),
00092               Qt::BlockingQueuedConnection);
00093       connect(&searcher, SIGNAL(solution(const Space*)),
00094               this, SLOT(inspectSolution(const Space*)),
00095               Qt::BlockingQueuedConnection);
00096 
00097       connect(&searcher, SIGNAL(searchFinished(void)), this, SIGNAL(searchFinished(void)));
00098 
00099       connect(&scrollTimeLine, SIGNAL(frameChanged(int)),
00100               this, SLOT(scroll(int)));
00101       scrollTimeLine.setCurveShape(QTimeLine::EaseInOutCurve);
00102 
00103       scaleBar = new QSlider(Qt::Vertical, this);
00104       scaleBar->setObjectName("scaleBar");
00105       scaleBar->setMinimum(LayoutConfig::minScale);
00106       scaleBar->setMaximum(LayoutConfig::maxScale);
00107       scaleBar->setValue(LayoutConfig::defScale);
00108       connect(scaleBar, SIGNAL(valueChanged(int)),
00109               this, SLOT(scaleTree(int)));
00110       connect(this, SIGNAL(scaleChanged(int)), scaleBar, SLOT(setValue(int)));
00111       connect(&searcher, SIGNAL(scaleChanged(int)),
00112               scaleBar, SLOT(setValue(int)));
00113 
00114       connect(&zoomTimeLine, SIGNAL(frameChanged(int)),
00115               scaleBar, SLOT(setValue(int)));
00116       zoomTimeLine.setCurveShape(QTimeLine::EaseInOutCurve);
00117 
00118       qRegisterMetaType<Statistics>("Statistics");
00119       update();
00120   }
00121 
00122   TreeCanvas::~TreeCanvas(void) { delete root; delete na; }
00123 
00124   void
00125   TreeCanvas::addDoubleClickInspector(Inspector* i) {
00126     doubleClickInspectors.append(QPair<Inspector*,bool>(i,false));
00127   }
00128 
00129   void
00130   TreeCanvas::activateDoubleClickInspector(int i, bool active) {
00131     assert(i < doubleClickInspectors.size());
00132     doubleClickInspectors[i].second = active;
00133   }
00134 
00135   void
00136   TreeCanvas::addSolutionInspector(Inspector* i) {
00137     solutionInspectors.append(QPair<Inspector*,bool>(i,false));
00138   }
00139 
00140   void
00141   TreeCanvas::activateSolutionInspector(int i, bool active) {
00142     assert(i < solutionInspectors.size());
00143     solutionInspectors[i].second = active;
00144   }
00145 
00146   void
00147   TreeCanvas::addMoveInspector(Inspector* i) {
00148     moveInspectors.append(QPair<Inspector*,bool>(i,false));
00149   }
00150 
00151   void
00152   TreeCanvas::activateMoveInspector(int i, bool active) {
00153     assert(i < moveInspectors.size());
00154     moveInspectors[i].second = active;
00155   }
00156 
00157   void
00158   TreeCanvas::addComparator(Comparator* c) {
00159     comparators.append(QPair<Comparator*,bool>(c,false));
00160   }
00161 
00162   void
00163   TreeCanvas::activateComparator(int i, bool active) {
00164     assert(i < comparators.size());
00165     comparators[i].second = active;
00166   }
00167 
00168   void
00169   TreeCanvas::scaleTree(int scale0, int zoomx, int zoomy) {
00170     QMutexLocker locker(&layoutMutex);
00171 
00172     QSize viewport_size = size();
00173     QAbstractScrollArea* sa =
00174       static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
00175 
00176     if (zoomx==-1)
00177       zoomx = viewport_size.width()/2;
00178     if (zoomy==-1)
00179       zoomy = viewport_size.height()/2;
00180 
00181     int xoff = (sa->horizontalScrollBar()->value()+zoomx)/scale;
00182     int yoff = (sa->verticalScrollBar()->value()+zoomy)/scale;
00183 
00184     BoundingBox bb;
00185     scale0 = std::min(std::max(scale0, LayoutConfig::minScale),
00186                       LayoutConfig::maxScale);
00187     scale = (static_cast<double>(scale0)) / 100.0;
00188     bb = root->getBoundingBox();
00189     int w =
00190       static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
00191     int h =
00192       static_cast<int>(2*Layout::extent+
00193         root->getShape()->depth()*Layout::dist_y*scale);
00194 
00195     sa->horizontalScrollBar()->setRange(0,w-viewport_size.width());
00196     sa->verticalScrollBar()->setRange(0,h-viewport_size.height());
00197     sa->horizontalScrollBar()->setPageStep(viewport_size.width());
00198     sa->verticalScrollBar()->setPageStep(viewport_size.height());
00199     sa->horizontalScrollBar()->setSingleStep(Layout::extent);
00200     sa->verticalScrollBar()->setSingleStep(Layout::extent);
00201 
00202     xoff *= scale;
00203     yoff *= scale;
00204 
00205     sa->horizontalScrollBar()->setValue(xoff-zoomx);
00206     sa->verticalScrollBar()->setValue(yoff-zoomy);
00207 
00208     emit scaleChanged(scale0);
00209     QWidget::update();
00210   }
00211 
00212   void
00213   TreeCanvas::update(void) {
00214     QMutexLocker locker(&mutex);
00215     layoutMutex.lock();
00216     if (root != NULL) {
00217       root->layout();
00218       BoundingBox bb = root->getBoundingBox();
00219 
00220       int w = static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
00221       int h =
00222         static_cast<int>(2*Layout::extent+
00223           root->getShape()->depth()*Layout::dist_y*scale);
00224       xtrans = -bb.left+(Layout::extent / 2);
00225       
00226       QSize viewport_size = size();
00227       QAbstractScrollArea* sa =
00228         static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
00229       sa->horizontalScrollBar()->setRange(0,w-viewport_size.width());
00230       sa->verticalScrollBar()->setRange(0,h-viewport_size.height());
00231       sa->horizontalScrollBar()->setPageStep(viewport_size.width());
00232       sa->verticalScrollBar()->setPageStep(viewport_size.height());
00233       sa->horizontalScrollBar()->setSingleStep(Layout::extent);
00234       sa->verticalScrollBar()->setSingleStep(Layout::extent);
00235     }
00236     if (autoZoom)
00237       zoomToFit();
00238     layoutMutex.unlock();
00239     QWidget::update();
00240   }
00241 
00242   void
00243   TreeCanvas::scroll(void) {
00244     QWidget::update();
00245   }
00246 
00247   void
00248   TreeCanvas::layoutDone(int w, int h, int scale0) {
00249     targetW = w; targetH = h; targetScale = scale0;
00250     if (layoutDoneTimerId == 0)
00251       layoutDoneTimerId = startTimer(15);
00252   }
00253 
00254   void
00255   TreeCanvas::statusChanged(bool finished) {
00256     if (finished) {
00257       update();
00258       centerCurrentNode();
00259     }
00260     emit statusChanged(currentNode, stats, finished);
00261   }
00262 
00263   void
00264   SearcherThread::search(VisualNode* n, bool all, TreeCanvas* ti) {
00265     node = n;
00266     
00267     depth = -1;
00268     for (VisualNode* p = n; p != NULL; p = p->getParent())
00269       depth++;
00270     
00271     a = all;
00272     t = ti;
00273     start();
00274   }
00275 
00276   void
00277   SearcherThread::updateCanvas(void) {
00278     t->layoutMutex.lock();
00279     if (t->root == NULL)
00280       return;
00281 
00282     if (t->autoHideFailed) {
00283       t->root->hideFailed();
00284     }
00285     for (VisualNode* n = t->currentNode; n != NULL; n = n->getParent()) {
00286       if (n->isHidden()) {
00287         t->currentNode->setMarked(false);
00288         t->currentNode = n;
00289         t->currentNode->setMarked(true);
00290         break;
00291       }
00292     }
00293     
00294     t->root->layout();
00295     BoundingBox bb = t->root->getBoundingBox();
00296 
00297     int w = static_cast<int>((bb.right-bb.left+Layout::extent)*t->scale);
00298     int h = static_cast<int>(2*Layout::extent+
00299                              t->root->getShape()->depth()
00300                               *Layout::dist_y*t->scale);
00301     t->xtrans = -bb.left+(Layout::extent / 2);
00302 
00303     int scale0 = static_cast<int>(t->scale*100);
00304     if (t->autoZoom) {
00305       QWidget* p = t->parentWidget();
00306       if (p) {
00307         double newXScale =
00308           static_cast<double>(p->width()) / (bb.right - bb.left +
00309                                              Layout::extent);
00310         double newYScale =
00311           static_cast<double>(p->height()) /
00312           (t->root->getShape()->depth() * Layout::dist_y + 2*Layout::extent);
00313 
00314         scale0 = static_cast<int>(std::min(newXScale, newYScale)*100);
00315         if (scale0<LayoutConfig::minScale)
00316           scale0 = LayoutConfig::minScale;
00317         if (scale0>LayoutConfig::maxAutoZoomScale)
00318           scale0 = LayoutConfig::maxAutoZoomScale;
00319         double scale = (static_cast<double>(scale0)) / 100.0;
00320 
00321         w = static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
00322         h = static_cast<int>(2*Layout::extent+
00323                              t->root->getShape()->depth()*Layout::dist_y*scale);
00324       }
00325     }
00326     t->layoutMutex.unlock();
00327     emit update(w,h,scale0);
00328   }
00329 
00331   class SearchItem {
00332   public:
00334     VisualNode* n;
00336     int i;
00338     int noOfChildren;
00340     SearchItem(VisualNode* n0, int noOfChildren0)
00341       : n(n0), i(-1), noOfChildren(noOfChildren0) {}
00342   };
00343 
00344   void
00345   SearcherThread::run() {
00346     {
00347       if (!node->isOpen())
00348         return;
00349       t->mutex.lock();
00350       emit statusChanged(false);
00351 
00352       unsigned int kids = 
00353         node->getNumberOfChildNodes(*t->na, t->curBest, t->stats,
00354                                     t->c_d, t->a_d);
00355       if (kids == 0 || node->getStatus() == STOP) {
00356         t->mutex.unlock();
00357         updateCanvas();
00358         emit statusChanged(true);
00359         return;
00360       }
00361 
00362       std::stack<SearchItem> stck;
00363       stck.push(SearchItem(node,kids));
00364       t->stats.maxDepth =
00365         std::max(static_cast<long unsigned int>(t->stats.maxDepth), 
00366                  static_cast<long unsigned int>(depth+stck.size()));
00367 
00368       VisualNode* sol = NULL;
00369       int nodeCount = 0;
00370       t->stopSearchFlag = false;
00371       while (!stck.empty() && !t->stopSearchFlag) {
00372         if (t->refresh > 0 && ++nodeCount > t->refresh) {
00373           node->dirtyUp();
00374           updateCanvas();
00375           emit statusChanged(false);
00376           nodeCount = 0;
00377         }
00378         SearchItem& si = stck.top();
00379         si.i++;
00380         if (si.i == si.noOfChildren) {
00381           stck.pop();
00382         } else {
00383           VisualNode* n = si.n->getChild(si.i);
00384           if (n->isOpen()) {
00385             kids = n->getNumberOfChildNodes(*t->na, t->curBest, t->stats,
00386                                             t->c_d, t->a_d);
00387             if (kids == 0) {
00388               if (n->getStatus() == SOLVED) {
00389                 assert(n->hasWorkingSpace());
00390                 emit solution(n->getWorkingSpace());
00391                 n->purge();
00392                 sol = n;
00393                 if (!a)
00394                   break;
00395               }
00396             } else {
00397               if ( n->getStatus() != STOP )
00398                 stck.push(SearchItem(n,kids));
00399               else if (!a)
00400                 break;
00401               t->stats.maxDepth =
00402                 std::max(static_cast<long unsigned int>(t->stats.maxDepth), 
00403                          static_cast<long unsigned int>(depth+stck.size()));
00404             }
00405           }
00406         }
00407       }
00408       node->dirtyUp();
00409       t->stopSearchFlag = false;
00410       t->mutex.unlock();
00411       if (sol != NULL) {
00412         t->setCurrentNode(sol,false);
00413       } else {
00414         t->setCurrentNode(node,false);
00415       }
00416     }
00417     updateCanvas();
00418     emit statusChanged(true);
00419     if (t->finishedFlag)
00420       emit searchFinished();
00421   }
00422 
00423   void
00424   TreeCanvas::searchAll(void) {
00425     QMutexLocker locker(&mutex);
00426     searcher.search(currentNode, true, this);
00427   }
00428 
00429   void
00430   TreeCanvas::searchOne(void) {
00431     QMutexLocker locker(&mutex);
00432     searcher.search(currentNode, false, this);
00433   }
00434 
00435   void
00436   TreeCanvas::toggleHidden(void) {
00437     QMutexLocker locker(&mutex);
00438     currentNode->toggleHidden();
00439     update();
00440     centerCurrentNode();
00441     emit statusChanged(currentNode, stats, true);
00442   }
00443 
00444   void
00445   TreeCanvas::hideFailed(void) {
00446     QMutexLocker locker(&mutex);
00447     currentNode->hideFailed();
00448     update();
00449     centerCurrentNode();
00450     emit statusChanged(currentNode, stats, true);
00451   }
00452 
00453   void
00454   TreeCanvas::unhideAll(void) {
00455     QMutexLocker locker(&mutex);
00456     QMutexLocker layoutLocker(&layoutMutex);
00457     currentNode->unhideAll();
00458     update();
00459     centerCurrentNode();
00460     emit statusChanged(currentNode, stats, true);
00461   }
00462 
00463   void
00464   TreeCanvas::toggleStop(void) {
00465     QMutexLocker locker(&mutex);
00466     currentNode->toggleStop();
00467     update();
00468     centerCurrentNode();
00469     emit statusChanged(currentNode, stats, true);
00470   }
00471 
00472   void
00473   TreeCanvas::unstopAll(void) {
00474     QMutexLocker locker(&mutex);
00475     QMutexLocker layoutLocker(&layoutMutex);
00476     currentNode->unstopAll();
00477     update();
00478     centerCurrentNode();
00479     emit statusChanged(currentNode, stats, true);    
00480   }
00481 
00482   void
00483   TreeCanvas::timerEvent(QTimerEvent* e) {
00484     if (e->timerId() == layoutDoneTimerId) {
00485       if (!smoothScrollAndZoom) {
00486         scaleTree(targetScale);
00487       } else {
00488         zoomTimeLine.stop();
00489         int zoomCurrent = static_cast<int>(scale*100);
00490         int targetZoom = targetScale;
00491         targetZoom = std::min(std::max(targetZoom, LayoutConfig::minScale),
00492                               LayoutConfig::maxAutoZoomScale);
00493         zoomTimeLine.setFrameRange(zoomCurrent,targetZoom);
00494         zoomTimeLine.start();
00495       }
00496       QWidget::update();
00497       killTimer(layoutDoneTimerId);
00498       layoutDoneTimerId = 0;
00499     }
00500   }
00501 
00502   void
00503   TreeCanvas::zoomToFit(void) {
00504     QMutexLocker locker(&layoutMutex);
00505     if (root != NULL) {
00506       BoundingBox bb;
00507       bb = root->getBoundingBox();
00508       QWidget* p = parentWidget();
00509       if (p) {
00510         double newXScale =
00511           static_cast<double>(p->width()) / (bb.right - bb.left +
00512                                              Layout::extent);
00513         double newYScale =
00514           static_cast<double>(p->height()) / (root->getShape()->depth() * 
00515                                               Layout::dist_y +
00516                                               2*Layout::extent);
00517         int scale0 = static_cast<int>(std::min(newXScale, newYScale)*100);
00518         if (scale0<LayoutConfig::minScale)
00519           scale0 = LayoutConfig::minScale;
00520         if (scale0>LayoutConfig::maxAutoZoomScale)
00521           scale0 = LayoutConfig::maxAutoZoomScale;
00522 
00523         if (!smoothScrollAndZoom) {
00524           scaleTree(scale0);
00525         } else {
00526           zoomTimeLine.stop();
00527           int zoomCurrent = static_cast<int>(scale*100);
00528           int targetZoom = scale0;
00529           targetZoom = std::min(std::max(targetZoom, LayoutConfig::minScale),
00530                                 LayoutConfig::maxAutoZoomScale);
00531           zoomTimeLine.setFrameRange(zoomCurrent,targetZoom);
00532           zoomTimeLine.start();
00533         }
00534       }
00535     }
00536   }
00537 
00538   void
00539   TreeCanvas::centerCurrentNode(void) {
00540     QMutexLocker locker(&mutex);
00541     int x=0;
00542     int y=0;
00543 
00544     VisualNode* c = currentNode;
00545     while (c != NULL) {
00546       x += c->getOffset();
00547       y += Layout::dist_y;
00548       c = c->getParent();
00549     }
00550 
00551     x = static_cast<int>((xtrans+x)*scale); y = static_cast<int>(y*scale);
00552 
00553     QAbstractScrollArea* sa =
00554       static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
00555 
00556     x -= sa->viewport()->width() / 2;
00557     y -= sa->viewport()->height() / 2;
00558 
00559     sourceX = sa->horizontalScrollBar()->value();
00560     targetX = std::max(sa->horizontalScrollBar()->minimum(), x);
00561     targetX = std::min(sa->horizontalScrollBar()->maximum(),
00562                        targetX);
00563     sourceY = sa->verticalScrollBar()->value();
00564     targetY = std::max(sa->verticalScrollBar()->minimum(), y);
00565     targetY = std::min(sa->verticalScrollBar()->maximum(),
00566                        targetY);
00567     if (!smoothScrollAndZoom) {
00568       sa->horizontalScrollBar()->setValue(targetX);
00569       sa->verticalScrollBar()->setValue(targetY);
00570     } else {
00571       scrollTimeLine.stop();
00572       scrollTimeLine.setFrameRange(0,100);
00573       scrollTimeLine.setDuration(std::max(200,
00574         std::min(1000,
00575         std::min(std::abs(sourceX-targetX),
00576                  std::abs(sourceY-targetY)))));
00577       scrollTimeLine.start();
00578     }
00579   }
00580 
00581   void
00582   TreeCanvas::scroll(int i) {
00583     QAbstractScrollArea* sa =
00584       static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
00585     double p = static_cast<double>(i)/100.0;
00586     double xdiff = static_cast<double>(targetX-sourceX)*p;
00587     double ydiff = static_cast<double>(targetY-sourceY)*p;
00588     sa->horizontalScrollBar()->setValue(sourceX+static_cast<int>(xdiff));
00589     sa->verticalScrollBar()->setValue(sourceY+static_cast<int>(ydiff));
00590   }
00591 
00592   void
00593   TreeCanvas::inspectCurrentNode(bool fix, int inspectorNo) {
00594     QMutexLocker locker(&mutex);
00595 
00596     if (currentNode->isHidden()) {
00597       toggleHidden();
00598       return;
00599     }
00600 
00601     switch (currentNode->getStatus()) {
00602     case UNDETERMINED:
00603         {
00604           unsigned int kids =  
00605             currentNode->getNumberOfChildNodes(*na,curBest,stats,c_d,a_d);
00606           int depth = -1;
00607           for (VisualNode* p = currentNode; p != NULL; p = p->getParent())
00608             depth++;
00609           if (kids > 0)
00610             depth++;
00611           stats.maxDepth =
00612             std::max(stats.maxDepth, depth);
00613           if (currentNode->getStatus() == SOLVED) {
00614             assert(currentNode->hasWorkingSpace());
00615             emit solution(currentNode->getWorkingSpace());
00616             currentNode->purge();
00617           }
00618           emit statusChanged(currentNode,stats,true);
00619           Space* curSpace = currentNode->getSpace(curBest,c_d,a_d);
00620           for (int i=0; i<moveInspectors.size(); i++) {
00621             if (moveInspectors[i].second) {
00622               moveInspectors[i].first->inspect(*curSpace);
00623             }
00624           }
00625         }
00626         break;
00627     case FAILED:
00628     case STOP:
00629     case UNSTOP:
00630     case BRANCH:
00631     case SOLVED:
00632       {
00633         // SizeCursor sc(currentNode);
00634         // PreorderNodeVisitor<SizeCursor> pnv(sc);
00635         // int nodes = 1;
00636         // while (pnv.next()) { nodes++; }
00637         // std::cout << "sizeof(VisualNode): " << sizeof(VisualNode)
00638         //           << std::endl;
00639         // std::cout << "Size: " << (pnv.getCursor().s)/1024 << std::endl;
00640         // std::cout << "Nodes: " << nodes << std::endl;
00641         // std::cout << "Size / node: " << (pnv.getCursor().s)/nodes
00642         //           << std::endl;
00643 
00644         Space* curSpace;
00645         
00646         if (fix) {
00647           if (currentNode->isRoot() && currentNode->getStatus() == FAILED)
00648             break;
00649           curSpace = currentNode->getSpace(curBest,c_d,a_d);
00650           if (currentNode->getStatus() == SOLVED &&
00651               curSpace->status() != SS_SOLVED) {
00652             // in the presence of weakly monotonic propagators, we may have to
00653             // use search to find the solution here
00654             Space* dfsSpace = Gecode::dfs(curSpace);
00655             delete curSpace;
00656             curSpace = dfsSpace;
00657           }          
00658         } else {
00659           if (currentNode->isRoot())
00660             break;
00661           VisualNode* p = currentNode->getParent();
00662           curSpace = p->getSpace(curBest,c_d,a_d);
00663           switch (curSpace->status()) {
00664           case SS_SOLVED:
00665           case SS_FAILED:
00666             break;
00667           case SS_BRANCH:
00668             curSpace->commit(*p->getChoice(), currentNode->getAlternative());
00669             break;
00670           default:
00671             GECODE_NEVER;
00672           }
00673         }
00674 
00675         if (inspectorNo==-1) {
00676           for (int i=0; i<doubleClickInspectors.size(); i++) {
00677             if (doubleClickInspectors[i].second) {
00678               doubleClickInspectors[i].first->inspect(*curSpace);
00679             }
00680           }
00681         } else {
00682           doubleClickInspectors[inspectorNo].first->inspect(*curSpace);          
00683         }
00684         delete curSpace;
00685       }
00686       break;
00687     }
00688 
00689     currentNode->dirtyUp();
00690     update();
00691     centerCurrentNode();
00692   }
00693   
00694   void
00695   TreeCanvas::inspectBeforeFP(void) {
00696     inspectCurrentNode(false);
00697   }
00698 
00699   void
00700   TreeCanvas::inspectSolution(const Space* s) {
00701     Space* c = NULL;
00702     for (int i=0; i<solutionInspectors.size(); i++) {
00703       if (solutionInspectors[i].second) {
00704         if (c == NULL)
00705           c = s->clone();
00706         solutionInspectors[i].first->inspect(*c);
00707       }
00708     }
00709     for (int i=0; i<moveInspectors.size(); i++) {
00710       if (moveInspectors[i].second) {
00711         if (c == NULL)
00712           c = s->clone();
00713         moveInspectors[i].first->inspect(*c);
00714       }
00715     }
00716     delete c;
00717   }
00718 
00719   void
00720   TreeCanvas::stopSearch(void) {
00721     stopSearchFlag = true;
00722     layoutDoneTimerId = startTimer(15);
00723   }
00724 
00725   void
00726   TreeCanvas::reset(void) {
00727     QMutexLocker locker(&mutex);
00728     Space* rootSpace =
00729       root->getStatus() == FAILED ? NULL : root->getSpace(curBest,c_d,a_d);
00730     if (curBest != NULL) {
00731       delete curBest;
00732       curBest = new BestNode(NULL);
00733     }
00734     delete root;
00735     delete na;
00736     na = new Node::NodeAllocator();
00737     root = new (*na) VisualNode(rootSpace);
00738     root->setMarked(true);
00739     currentNode = root;
00740     pathHead = root;
00741     scale = 1.0;
00742     stats = Statistics();
00743     for (int i=bookmarks.size(); i--;)
00744       emit removedBookmark(i);
00745     bookmarks.clear();
00746     root->layout();
00747 
00748     emit statusChanged(currentNode, stats, true);
00749     update();
00750   }
00751 
00752   void
00753   TreeCanvas::bookmarkNode(void) {
00754     QMutexLocker locker(&mutex);
00755     if (!currentNode->isBookmarked()) {
00756       bool ok;
00757       QString text =
00758         QInputDialog::getText(this, "Add bookmark", "Name:", 
00759                               QLineEdit::Normal,"",&ok);
00760       if (ok) {
00761         currentNode->setBookmarked(true);
00762         bookmarks.append(currentNode);
00763         if (text == "")
00764           text = QString("Node ")+QString().setNum(bookmarks.size());
00765         emit addedBookmark(text);
00766       }
00767     } else {
00768       currentNode->setBookmarked(false);
00769       int idx = bookmarks.indexOf(currentNode);
00770       bookmarks.remove(idx);
00771       emit removedBookmark(idx);
00772     }
00773     currentNode->dirtyUp();
00774     update();
00775   }
00776   
00777   void
00778   TreeCanvas::setPath(void) {
00779     QMutexLocker locker(&mutex);
00780     if(currentNode == pathHead)
00781       return;
00782 
00783     pathHead->unPathUp();
00784     pathHead = currentNode;
00785 
00786     currentNode->pathUp();
00787     currentNode->dirtyUp();
00788     update();
00789   }
00790 
00791   void
00792   TreeCanvas::inspectPath(void) {
00793     QMutexLocker locker(&mutex);
00794     setCurrentNode(root);
00795     if (currentNode->isOnPath()) {
00796       inspectCurrentNode();
00797       int nextAlt = currentNode->getPathAlternative();
00798       while (nextAlt >= 0) {
00799         setCurrentNode(currentNode->getChild(nextAlt));
00800         inspectCurrentNode();
00801         nextAlt = currentNode->getPathAlternative();
00802       }
00803     }
00804     update();
00805   }
00806 
00807   void
00808   TreeCanvas::startCompareNodes(void) {
00809     QMutexLocker locker(&mutex);
00810     compareNodes = true;
00811     compareNodesBeforeFP = false;
00812     setCursor(QCursor(Qt::CrossCursor));
00813   }
00814 
00815   void
00816   TreeCanvas::startCompareNodesBeforeFP(void) {
00817     QMutexLocker locker(&mutex);
00818     compareNodes = true;
00819     compareNodesBeforeFP = true;
00820     setCursor(QCursor(Qt::CrossCursor));
00821   }
00822 
00823   void
00824   TreeCanvas::emitStatusChanged(void) {
00825     emit statusChanged(currentNode, stats, true);
00826   }
00827 
00828   void
00829   TreeCanvas::navUp(void) {
00830     QMutexLocker locker(&mutex);
00831 
00832     VisualNode* p = currentNode->getParent();
00833 
00834     setCurrentNode(p);
00835 
00836     if (p != NULL) {
00837       centerCurrentNode();
00838     }
00839   }
00840 
00841   void
00842   TreeCanvas::navDown(void) {
00843     QMutexLocker locker(&mutex);
00844     if (!currentNode->isHidden()) {
00845       switch (currentNode->getStatus()) {
00846       case STOP:
00847       case UNSTOP:
00848       case BRANCH:
00849           {
00850             int alt = std::max(0, currentNode->getPathAlternative());
00851             VisualNode* n = currentNode->getChild(alt);
00852             setCurrentNode(n);
00853             centerCurrentNode();
00854             break;
00855           }
00856       case SOLVED:
00857       case FAILED:
00858       case UNDETERMINED:
00859         break;
00860       }
00861     }
00862   }
00863 
00864   void
00865   TreeCanvas::navLeft(void) {
00866     QMutexLocker locker(&mutex);
00867     VisualNode* p = currentNode->getParent();
00868     if (p != NULL) {
00869       int alt = currentNode->getAlternative();
00870       if (alt > 0) {
00871         VisualNode* n = p->getChild(alt-1);
00872         setCurrentNode(n);
00873         centerCurrentNode();
00874       }
00875     }
00876   }
00877 
00878   void
00879   TreeCanvas::navRight(void) {
00880     QMutexLocker locker(&mutex);
00881     VisualNode* p = currentNode->getParent();
00882     if (p != NULL) {
00883       unsigned int alt = currentNode->getAlternative();
00884       if (alt + 1 < p->getNumberOfChildren()) {
00885         VisualNode* n = p->getChild(alt+1);
00886         setCurrentNode(n);
00887         centerCurrentNode();
00888       }
00889     }
00890   }
00891 
00892   void
00893   TreeCanvas::navRoot(void) {
00894     QMutexLocker locker(&mutex);
00895     setCurrentNode(root);
00896     centerCurrentNode();
00897   }
00898 
00899   void
00900   TreeCanvas::navNextSol(bool back) {
00901     QMutexLocker locker(&mutex);
00902     NextSolCursor nsc(currentNode, back);
00903     PreorderNodeVisitor<NextSolCursor> nsv(nsc);
00904     while (nsv.next()) {}
00905     if (nsv.getCursor().node() != root) {
00906       setCurrentNode(nsv.getCursor().node());
00907       centerCurrentNode();
00908     }
00909   }
00910 
00911   void
00912   TreeCanvas::navPrevSol(void) {
00913     navNextSol(true);
00914   }
00915 
00916   void
00917   TreeCanvas::exportNodePDF(VisualNode* n) {
00918 #if QT_VERSION >= 0x040400
00919     QString filename = QFileDialog::getSaveFileName(this, tr("Export tree as pdf"), "", tr("PDF (*.pdf)"));
00920     if (filename != "") {
00921       QPrinter printer(QPrinter::ScreenResolution);
00922       QMutexLocker locker(&mutex);
00923 
00924       BoundingBox bb = n->getBoundingBox();
00925       printer.setFullPage(true);
00926       printer.setPaperSize(QSizeF(bb.right-bb.left+Layout::extent,
00927                                   n->getShape()->depth() * Layout::dist_y +
00928                                   Layout::extent), QPrinter::Point);
00929       printer.setOutputFileName(filename);
00930       QPainter painter(&printer);
00931 
00932       painter.setRenderHint(QPainter::Antialiasing);
00933 
00934       QRect pageRect = printer.pageRect();
00935       double newXScale =
00936         static_cast<double>(pageRect.width()) / (bb.right - bb.left +
00937                                                  Layout::extent);
00938       double newYScale =
00939         static_cast<double>(pageRect.height()) /
00940                             (n->getShape()->depth() * Layout::dist_y +
00941                              Layout::extent);
00942       double printScale = std::min(newXScale, newYScale);
00943       painter.scale(printScale,printScale);
00944 
00945       int printxtrans = -bb.left+(Layout::extent / 2);
00946 
00947       painter.translate(printxtrans, Layout::dist_y / 2);
00948       QRect clip(0,0,0,0);
00949       DrawingCursor dc(n, curBest, painter, clip, showCopies);
00950       currentNode->setMarked(false);
00951       PreorderNodeVisitor<DrawingCursor> v(dc);
00952       while (v.next()) {}
00953       currentNode->setMarked(true);
00954     }
00955 #else
00956     (void) n;
00957 #endif
00958   }
00959 
00960   void
00961   TreeCanvas::exportWholeTreePDF(void) {
00962 #if QT_VERSION >= 0x040400
00963     exportNodePDF(root);
00964 #endif
00965   }
00966 
00967   void
00968   TreeCanvas::exportPDF(void) {
00969 #if QT_VERSION >= 0x040400
00970     exportNodePDF(currentNode);
00971 #endif
00972   }
00973 
00974   void
00975   TreeCanvas::print(void) {
00976     QPrinter printer;
00977     if (QPrintDialog(&printer, this).exec() == QDialog::Accepted) {
00978       QMutexLocker locker(&mutex);
00979 
00980       BoundingBox bb = root->getBoundingBox();
00981       QRect pageRect = printer.pageRect();
00982       double newXScale =
00983         static_cast<double>(pageRect.width()) / (bb.right - bb.left +
00984                                                  Layout::extent);
00985       double newYScale =
00986         static_cast<double>(pageRect.height()) /
00987                             (root->getShape()->depth() * Layout::dist_y +
00988                              2*Layout::extent);
00989       double printScale = std::min(newXScale, newYScale)*100;
00990       if (printScale<1.0)
00991         printScale = 1.0;
00992       if (printScale > 400.0)
00993         printScale = 400.0;
00994       printScale = printScale / 100.0;
00995 
00996       QPainter painter(&printer);
00997       painter.setRenderHint(QPainter::Antialiasing);
00998       painter.scale(printScale,printScale);
00999       painter.translate(xtrans, 0);
01000       QRect clip(0,0,0,0);
01001       DrawingCursor dc(root, curBest, painter, clip, showCopies);
01002       PreorderNodeVisitor<DrawingCursor> v(dc);
01003       while (v.next()) {}
01004     }
01005   }
01006 
01007   VisualNode*
01008   TreeCanvas::eventNode(QEvent* event) {
01009     int x = 0;
01010     int y = 0;
01011     switch (event->type()) {
01012     case QEvent::ToolTip:
01013         {
01014           QHelpEvent* he = static_cast<QHelpEvent*>(event);
01015           x = he->x();
01016           y = he->y();
01017           break;
01018         }
01019     case QEvent::MouseButtonDblClick:
01020     case QEvent::MouseButtonPress:
01021     case QEvent::MouseButtonRelease:
01022     case QEvent::MouseMove:
01023         {
01024           QMouseEvent* me = static_cast<QMouseEvent*>(event);
01025           x = me->x();
01026           y = me->y();
01027           break;
01028         }
01029     case QEvent::ContextMenu:
01030         {
01031           QContextMenuEvent* ce = static_cast<QContextMenuEvent*>(event);
01032           x = ce->x();
01033           y = ce->y();
01034           break;
01035         }
01036     default:
01037       return NULL;
01038     }
01039     QAbstractScrollArea* sa =
01040       static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
01041     int xoff = sa->horizontalScrollBar()->value()/scale;
01042     int yoff = sa->verticalScrollBar()->value()/scale;
01043 
01044     BoundingBox bb = root->getBoundingBox();
01045     int w =
01046       static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
01047     if (w < sa->viewport()->width())
01048       xoff -= (sa->viewport()->width()-w)/2;
01049     
01050     VisualNode* n;
01051     n = root->findNode(static_cast<int>(x/scale-xtrans+xoff),
01052                        static_cast<int>((y-30)/scale+yoff));
01053     return n;
01054   }
01055 
01056   bool
01057   TreeCanvas::event(QEvent* event) {
01058     if (mutex.tryLock()) {
01059       if (event->type() == QEvent::ToolTip) {
01060         VisualNode* n = eventNode(event);
01061         if (n != NULL && !n->isHidden() &&
01062             (n->getStatus() == BRANCH || n->getStatus() == STOP)) {
01063           QHelpEvent* he = static_cast<QHelpEvent*>(event);
01064           QToolTip::showText(he->globalPos(),
01065                              QString(n->toolTip(curBest,c_d,a_d).c_str()));
01066         } else {
01067           QToolTip::hideText();
01068         }
01069       }
01070       mutex.unlock();
01071     }
01072     return QWidget::event(event);
01073   }
01074 
01075   void
01076   TreeCanvas::resizeToOuter(void) {
01077     if (autoZoom)
01078       zoomToFit();
01079   }
01080 
01081   void
01082   TreeCanvas::paintEvent(QPaintEvent* event) {
01083     QMutexLocker locker(&layoutMutex);
01084     QPainter painter(this);
01085     painter.setRenderHint(QPainter::Antialiasing);
01086 
01087     QAbstractScrollArea* sa =
01088       static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
01089     int xoff = sa->horizontalScrollBar()->value()/scale;
01090     int yoff = sa->verticalScrollBar()->value()/scale;
01091 
01092     BoundingBox bb = root->getBoundingBox();
01093     int w =
01094       static_cast<int>((bb.right-bb.left+Layout::extent)*scale);
01095     if (w < sa->viewport()->width())
01096       xoff -= (sa->viewport()->width()-w)/2;
01097 
01098     QRect origClip = event->rect();
01099     painter.translate(0, 30);
01100     painter.scale(scale,scale);
01101     painter.translate(xtrans-xoff, -yoff);
01102     QRect clip(static_cast<int>(origClip.x()/scale-xtrans+xoff),
01103                static_cast<int>(origClip.y()/scale+yoff),
01104                static_cast<int>(origClip.width()/scale),
01105                static_cast<int>(origClip.height()/scale));
01106     DrawingCursor dc(root, curBest, painter, clip, showCopies);
01107     PreorderNodeVisitor<DrawingCursor> v(dc);
01108 
01109     while (v.next()) {}
01110 
01111     // int nodesLayouted = 1;
01112     // clock_t t0 = clock();
01113     // while (v.next()) { nodesLayouted++; }
01114     // double t = (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
01115     // double nps = static_cast<double>(nodesLayouted) /
01116     //   (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC);
01117     // std::cout << "Drawing done. " << nodesLayouted << " nodes in "
01118     //   << t << " ms. " << nps << " nodes/s." << std::endl;
01119 
01120   }
01121 
01122   void
01123   TreeCanvas::mouseDoubleClickEvent(QMouseEvent* event) {
01124     if (mutex.tryLock()) {
01125       if(event->button() == Qt::LeftButton) {
01126         VisualNode* n = eventNode(event);
01127         if(n == currentNode) {
01128           inspectCurrentNode();
01129           event->accept();
01130           mutex.unlock();
01131           return;
01132         }
01133       }
01134       mutex.unlock();
01135     }
01136     event->ignore();
01137   }
01138 
01139   void
01140   TreeCanvas::contextMenuEvent(QContextMenuEvent* event) {
01141     if (mutex.tryLock()) {
01142       VisualNode* n = eventNode(event);
01143       if (n != NULL) {
01144         setCurrentNode(n);
01145         emit contextMenu(event);
01146         event->accept();
01147         mutex.unlock();
01148         return;
01149       }
01150       mutex.unlock();
01151     }
01152     event->ignore();
01153   }
01154 
01155   void
01156   TreeCanvas::resizeEvent(QResizeEvent* e) {
01157     QAbstractScrollArea* sa =
01158       static_cast<QAbstractScrollArea*>(parentWidget()->parentWidget());
01159 
01160     int w = sa->horizontalScrollBar()->maximum()+e->oldSize().width();
01161     int h = sa->verticalScrollBar()->maximum()+e->oldSize().height();
01162 
01163     sa->horizontalScrollBar()->setRange(0,w-e->size().width());
01164     sa->verticalScrollBar()->setRange(0,h-e->size().height());
01165     sa->horizontalScrollBar()->setPageStep(e->size().width());
01166     sa->verticalScrollBar()->setPageStep(e->size().height());
01167   }
01168 
01169   void
01170   TreeCanvas::wheelEvent(QWheelEvent* event) {
01171     if (event->modifiers() & Qt::ShiftModifier) {
01172       event->accept();
01173       if (event->orientation() == Qt::Vertical && !autoZoom)
01174         scaleTree(scale*100+ceil(static_cast<double>(event->delta())/4.0),
01175                   event->x(), event->y());
01176     } else {
01177       event->ignore();
01178     }
01179   }
01180 
01181   bool
01182   TreeCanvas::finish(void) {
01183     if (finishedFlag)
01184       return true;
01185     stopSearchFlag = true;
01186     finishedFlag = true;
01187     for (int i=0; i<doubleClickInspectors.size(); i++)
01188       doubleClickInspectors[i].first->finalize();
01189     for (int i=0; i<solutionInspectors.size(); i++)
01190       solutionInspectors[i].first->finalize();
01191     for (int i=0; i<moveInspectors.size(); i++)
01192       moveInspectors[i].first->finalize();
01193     for (int i=0; i<comparators.size(); i++)
01194       comparators[i].first->finalize();
01195     return !searcher.isRunning();
01196   }
01197 
01198   void
01199   TreeCanvas::setCurrentNode(VisualNode* n, bool update) {
01200     QMutexLocker locker(&mutex);
01201     if (update && n != NULL && n != currentNode &&
01202         n->getStatus() != UNDETERMINED && !n->isHidden()) {
01203       Space* curSpace = NULL;
01204       for (int i=0; i<moveInspectors.size(); i++) {
01205         if (moveInspectors[i].second) {
01206           if (curSpace == NULL)
01207             curSpace = n->getSpace(curBest,c_d,a_d);
01208           moveInspectors[i].first->inspect(*curSpace);
01209         }
01210       }
01211     }
01212     if (n != NULL) {
01213       compareNodes = false;
01214       setCursor(QCursor(Qt::ArrowCursor));
01215       currentNode->setMarked(false);
01216       currentNode = n;
01217       currentNode->setMarked(true);
01218       emit statusChanged(currentNode,stats,true);
01219       if (update)
01220         QWidget::update();
01221     }
01222   }
01223 
01224   void
01225   TreeCanvas::mousePressEvent(QMouseEvent* event) {
01226     if (mutex.tryLock()) {
01227       if (event->button() == Qt::LeftButton) {
01228         VisualNode* n = eventNode(event);
01229         if (compareNodes) {
01230           if (n != NULL && n->getStatus() != UNDETERMINED &&
01231               currentNode != NULL &&
01232               currentNode->getStatus() != UNDETERMINED) {
01233             Space* curSpace = NULL;
01234             Space* compareSpace = NULL;
01235             for (int i=0; i<comparators.size(); i++) {
01236               if (comparators[i].second) {
01237                 if (curSpace == NULL) {
01238                   curSpace = currentNode->getSpace(curBest,c_d,a_d);
01239 
01240                   if (!compareNodesBeforeFP || n->isRoot()) {
01241                     compareSpace = n->getSpace(curBest,c_d,a_d);
01242                   } else {
01243                     VisualNode* p = n->getParent();
01244                     compareSpace = p->getSpace(curBest,c_d,a_d);
01245                     switch (compareSpace->status()) {
01246                     case SS_SOLVED:
01247                     case SS_FAILED:
01248                       break;
01249                     case SS_BRANCH:
01250                       compareSpace->commit(*p->getChoice(), 
01251                                            n->getAlternative());
01252                       break;
01253                     default:
01254                       GECODE_NEVER;
01255                     }
01256                   }
01257                 }
01258                 comparators[i].first->compare(*curSpace,*compareSpace);
01259               }
01260             }
01261           }
01262         } else {
01263           setCurrentNode(n);
01264         }
01265         compareNodes = false;
01266         setCursor(QCursor(Qt::ArrowCursor));
01267         if (n != NULL) {
01268           event->accept();
01269           mutex.unlock();
01270           return;
01271         }
01272       }
01273       mutex.unlock();
01274     }
01275     event->ignore();
01276   }
01277 
01278   void
01279   TreeCanvas::setRecompDistances(int c_d0, int a_d0) {
01280     c_d = c_d0; a_d = a_d0;
01281   }
01282 
01283   void
01284   TreeCanvas::setAutoHideFailed(bool b) {
01285     autoHideFailed = b;
01286   }
01287 
01288   void
01289   TreeCanvas::setAutoZoom(bool b) {
01290     autoZoom = b;
01291     if (autoZoom) {
01292       zoomToFit();
01293     }
01294     emit autoZoomChanged(b);
01295     scaleBar->setEnabled(!b);
01296   }
01297 
01298   void
01299   TreeCanvas::setShowCopies(bool b) {
01300     showCopies = b;
01301   }
01302   bool
01303   TreeCanvas::getShowCopies(void) {
01304     return showCopies;
01305   }
01306 
01307   bool
01308   TreeCanvas::getAutoHideFailed(void) {
01309     return autoHideFailed;
01310   }
01311 
01312   bool
01313   TreeCanvas::getAutoZoom(void) {
01314     return autoZoom;
01315   }
01316 
01317   void
01318   TreeCanvas::setRefresh(int i) {
01319     refresh = i;
01320   }
01321 
01322   bool
01323   TreeCanvas::getSmoothScrollAndZoom(void) {
01324     return smoothScrollAndZoom;
01325   }
01326 
01327   void
01328   TreeCanvas::setSmoothScrollAndZoom(bool b) {
01329     smoothScrollAndZoom = b;
01330   }
01331 
01332 }}
01333 
01334 // STATISTICS: gist-any