visualnode.cpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2006
 *
 *  Last modified:
 *     $Date: 2010-09-03 13:50:47 +0200 (Fri, 03 Sep 2010) $ by $Author: tack $
 *     $Revision: 11389 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#include <gecode/gist/visualnode.hh>

#include <gecode/gist/layoutcursor.hh>
#include <gecode/gist/nodevisitor.hh>

#include <utility>

namespace Gecode { namespace Gist {

  Shape* Shape::leaf;
  Shape* Shape::hidden;

  class ShapeAllocator {
  public:
    ShapeAllocator(void) {
      Shape::leaf = Shape::allocate(1);
      Shape::hidden = Shape::allocate(2);
      (*Shape::hidden)[1] = Extent(Layout::extent);
      Shape::leaf->computeBoundingBox();
      Shape::hidden->computeBoundingBox();
    }
    ~ShapeAllocator(void) {
      Shape::deallocate(Shape::leaf);
      Shape::deallocate(Shape::hidden);
    }
  };

  ShapeAllocator shapeAllocator;

  VisualNode::VisualNode(int p)
  : SpaceNode(p)
  , offset(0)
  {
    shape = NULL;
    setDirty(true);
    setChildrenLayoutDone(false);
    setHidden(false);
    setMarked(false);
    setOnPath(false);
    setBookmarked(false);
  }

  VisualNode::VisualNode(Space* root)
  : SpaceNode(root)
  , offset(0)
  {
    shape = NULL;
    setDirty(true);
    setChildrenLayoutDone(false);
    setHidden(false);
    setMarked(false);
    setOnPath(false);
    setBookmarked(false);
  }

  void
  VisualNode::dispose(void) {
    Shape::deallocate(shape);
    SpaceNode::dispose();
  }

  void
  VisualNode::dirtyUp(const NodeAllocator& na) {
    VisualNode* cur = this;
    while (!cur->isDirty()) {
      cur->setDirty(true);
      if (! cur->isRoot()) {
        cur = cur->getParent(na);
      }
    }
  }

  void
  VisualNode::layout(const NodeAllocator& na) {
    LayoutCursor l(this,na);
    PostorderNodeVisitor<LayoutCursor>(l).run();
    // int nodesLayouted = 1;
    // clock_t t0 = clock();
    // while (p.next()) {}
    // while (p.next()) { nodesLayouted++; }
    // double t = (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
    // double nps = static_cast<double>(nodesLayouted) /
    //   (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC);
    // std::cout << "Layout done. " << nodesLayouted << " nodes in "
    //   << t << " ms. " << nps << " nodes/s." << std::endl;
  }

  void VisualNode::pathUp(const NodeAllocator& na) {
    VisualNode* cur = this;
    while (cur) {
      cur->setOnPath(true);
      cur = cur->getParent(na);
    }
  }

  void VisualNode::unPathUp(const NodeAllocator& na) {
    VisualNode* cur = this;
    while (!cur->isRoot()) {
      cur->setOnPath(false);
      cur = cur->getParent(na);
    }
  }

  int
  VisualNode::getPathAlternative(const NodeAllocator& na) {
    for (int i=getNumberOfChildren(); i--;) {
      if (getChild(na,i)->isOnPath())
        return i;
    }
    return -1;
  }

  void
  VisualNode::toggleHidden(const NodeAllocator& na) {
    setHidden(!isHidden());
    dirtyUp(na);
  }

  void
  VisualNode::hideFailed(const NodeAllocator& na, bool onlyDirty) {
    HideFailedCursor c(this,na,onlyDirty);
    PreorderNodeVisitor<HideFailedCursor>(c).run();
    dirtyUp(na);
  }

  void
  VisualNode::unhideAll(const NodeAllocator& na) {
    UnhideAllCursor c(this,na);
    PreorderNodeVisitor<UnhideAllCursor>(c).run();
    dirtyUp(na);
  }

  void
  VisualNode::toggleStop(const NodeAllocator& na) {
    if (getStatus() == STOP)
      setStatus(UNSTOP);
    else if (getStatus() == UNSTOP)
      setStatus(STOP);
    dirtyUp(na);
  }
  
  void
  VisualNode::unstopAll(const NodeAllocator& na) {
    UnstopAllCursor c(this,na);
    PreorderNodeVisitor<UnstopAllCursor>(c).run();
    dirtyUp(na);
  }

  void
  VisualNode::changedStatus(const NodeAllocator& na) { dirtyUp(na); }

  bool
  VisualNode::containsCoordinateAtDepth(int x, int depth) {
    BoundingBox box = getShape()->getBoundingBox();
    if (x < box.left ||
        x > box.right ||
        depth >= getShape()->depth()) {
      return false;
    }
    Extent theExtent;
    if (getShape()->getExtentAtDepth(depth, theExtent)) {
      return (theExtent.l <= x && x <= theExtent.r);
    } else {
      return false;
    }
  }

  VisualNode*
  VisualNode::findNode(const NodeAllocator& na, int x, int y) {
    VisualNode* cur = this;
    int depth = y / Layout::dist_y;

    while (depth > 0 && cur != NULL) {
      if (cur->isHidden()) {
        break;
      }
      VisualNode* oldCur = cur;
      cur = NULL;
      for (unsigned int i=0; i<oldCur->getNumberOfChildren(); i++) {
        VisualNode* nextChild = oldCur->getChild(na,i);
        int newX = x - nextChild->getOffset();
        if (nextChild->containsCoordinateAtDepth(newX, depth - 1)) {
          cur = nextChild;
          x = newX;
          break;
        }
      }
      depth--;
      y -= Layout::dist_y;
    }

    if(cur == this && !cur->containsCoordinateAtDepth(x, 0)) {
      return NULL;
    }
    return cur;
  }

  std::string
  VisualNode::toolTip(BestNode*, int, int) {
    return "";
  }

  class Layouter {
  public:
    template<class S1, class S2>
    static int getAlpha(const S1& shape1, int depth1,
                        const S2& shape2, int depth2);
    template<class S1, class S2>
    static void merge(Extent* result,
                      const S1& shape1, int depth1,
                      const S2& shape2, int depth2, int alpha);
  };

  template<class S1, class S2>
  int
  Layouter::getAlpha(const S1& shape1, int depth1,
                     const S2& shape2, int depth2) {
    int alpha = Layout::minimalSeparation;
    int extentR = 0;
    int extentL = 0;
    for (int i=0; i<depth1 && i<depth2; i++) {
      extentR += shape1[i].r;
      extentL += shape2[i].l;
      alpha = std::max(alpha, extentR - extentL + Layout::minimalSeparation);
    }
    return alpha;
  }

  template<class S1, class S2>
  void
  Layouter::merge(Extent* result,
                  const S1& shape1, int depth1,
                  const S2& shape2, int depth2, int alpha) {
    if (depth1 == 0) {
      for (int i=depth2; i--;)
        result[i] = shape2[i];
    } else if (depth2 == 0) {
      for (int i=depth1; i--;)
        result[i] = shape1[i];
    } else {
      // Extend the topmost right extent by alpha.  This, in effect,
      // moves the second shape to the right by alpha units.
      int topmostL = shape1[0].l;
      int topmostR = shape2[0].r;
      int backoffTo1 =
        shape1[0].r - alpha - shape2[0].r;
      int backoffTo2 =
        shape2[0].l + alpha - shape1[0].l;

      result[0] = Extent(topmostL, topmostR+alpha);

      // Now, since extents are given in relative units, in order to
      // compute the extents of the merged shape, we can just collect the
      // extents of shape1 and shape2, until one of the shapes ends.  If
      // this happens, we need to "back-off" to the axis of the deeper
      // shape in order to properly determine the remaining extents.
      int i=1;
      for (; i<depth1 && i<depth2; i++) {
        Extent currentExtent1 = shape1[i];
        Extent currentExtent2 = shape2[i];
        int newExtentL = currentExtent1.l;
        int newExtentR = currentExtent2.r;
        result[i] = Extent(newExtentL, newExtentR);
        backoffTo1 += currentExtent1.r - currentExtent2.r;
        backoffTo2 += currentExtent2.l - currentExtent1.l;
      }

      // If shape1 is deeper than shape2, back off to the axis of shape1,
      // and process the remaining extents of shape1.
      if (i<depth1) {
        Extent currentExtent1 = shape1[i];
        int newExtentL = currentExtent1.l;
        int newExtentR = currentExtent1.r;
        result[i] = Extent(newExtentL, newExtentR+backoffTo1);
        ++i;
        for (; i<depth1; i++) {
          result[i] = shape1[i];
        }
      }

      // Vice versa, if shape2 is deeper than shape1, back off to the
      // axis of shape2, and process the remaining extents of shape2.
      if (i<depth2) {
        Extent currentExtent2 = shape2[i];
        int newExtentL = currentExtent2.l;
        int newExtentR = currentExtent2.r;
        result[i] = Extent(newExtentL+backoffTo2, newExtentR);
        ++i;
        for (; i<depth2; i++) {
          result[i] = shape2[i];
        }
      }
    }
  }

  void
  VisualNode::setShape(Shape* s) {
    if (shape != s)
      Shape::deallocate(shape);
    shape = s;
    shape->computeBoundingBox();
  }

  void
  VisualNode::computeShape(const NodeAllocator& na, VisualNode* root) {
    int numberOfShapes = getNumberOfChildren();
    Extent extent(Layout::extent);

    int maxDepth = 0;
    for (int i = numberOfShapes; i--;)
      maxDepth = std::max(maxDepth, getChild(na,i)->getShape()->depth());
    Shape* mergedShape;
    if (getShape() && getShape()->depth() >= maxDepth+1) {
      mergedShape = getShape();
      mergedShape->setDepth(maxDepth+1);
    } else {
      mergedShape = Shape::allocate(maxDepth+1);
    }

    if (numberOfShapes == 1) {
      getChild(na,0)->setOffset(0);
      const Shape* childShape = getChild(na,0)->getShape();
      for (int i=childShape->depth(); i--;)
        (*mergedShape)[i+1] = (*childShape)[i];
      (*mergedShape)[1].extend(- extent.l, - extent.r);
      setShape(mergedShape);
    } else {
      // alpha stores the necessary distances between the
      // axes of the shapes in the list: alpha[i].first gives the distance
      // between shape[i] and shape[i-1], when shape[i-1] and shape[i]
      // are merged left-to-right; alpha[i].second gives the distance between
      // shape[i] and shape[i+1], when shape[i] and shape[i+1] are merged
      // right-to-left.
      assert(root->copy != NULL);
      Region r(*root->copy);
      std::pair<int,int>* alpha =
        r.alloc<std::pair<int,int> >(numberOfShapes);

      // distance between the leftmost and the rightmost axis in the list
      int width = 0;

      Extent* currentShapeL = r.alloc<Extent>(maxDepth);
      int ldepth = getChild(na,0)->getShape()->depth();
      for (int i=ldepth; i--;)
        currentShapeL[i] = (*getChild(na,0)->getShape())[i];

      // After merging, we can pick the result of either merging left or right
      // Here we chose the result of merging right
      Shape* rShape = getChild(na,numberOfShapes-1)->getShape();
      int rdepth = rShape->depth();
      for (int i=rdepth; i--;)
        (*mergedShape)[i+1] = (*rShape)[i];
      Extent* currentShapeR = &(*mergedShape)[1];

      for (int i = 1; i < numberOfShapes; i++) {
        // Merge left-to-right.  Note that due to the asymmetry of the
        // merge operation, nextAlphaL is the distance between the
        // *leftmost* axis in the shape list, and the axis of
        // nextShapeL; what we are really interested in is the distance
        // between the *previous* axis and the axis of nextShapeL.
        // This explains the correction.

        Shape* nextShapeL = getChild(na,i)->getShape();
        int nextAlphaL =
          Layouter::getAlpha<Extent*,Shape>(&currentShapeL[0], ldepth,
                             *nextShapeL, nextShapeL->depth());
        Layouter::merge<Extent*,Shape>(&currentShapeL[0],
                                       &currentShapeL[0], ldepth,
                                       *nextShapeL, nextShapeL->depth(), 
                                       nextAlphaL);
        ldepth = std::max(ldepth,nextShapeL->depth());
        alpha[i].first = nextAlphaL - width;
        width = nextAlphaL;

        // Merge right-to-left.  Here, a correction of nextAlphaR is
        // not required.
        Shape* nextShapeR = getChild(na,numberOfShapes-1-i)->getShape();
        int nextAlphaR =
          Layouter::getAlpha<Shape,Extent*>(*nextShapeR, nextShapeR->depth(),
                               &currentShapeR[0], rdepth);
        Layouter::merge<Shape,Extent*>(&currentShapeR[0],
                                       *nextShapeR, nextShapeR->depth(),
                                       &currentShapeR[0], rdepth,
                                       nextAlphaR);
        rdepth = std::max(rdepth,nextShapeR->depth());
        alpha[numberOfShapes - i].second = nextAlphaR;
      }

      // The merged shape has to be adjusted to its topmost extent
      (*mergedShape)[1].extend(- extent.l, - extent.r);

      // After the loop, the merged shape has the same axis as the
      // leftmost shape in the list.  What we want is to move the axis
      // such that it is the center of the axis of the leftmost shape in
      // the list and the axis of the rightmost shape.
      int halfWidth = false ? 0 : width / 2;
      (*mergedShape)[1].move(- halfWidth);

      // Finally, for the offset lists.  Now that the axis of the merged
      // shape is at the center of the two extreme axes, the first shape
      // needs to be offset by -halfWidth units with respect to the new
      // axis.  As for the offsets for the other shapes, we take the
      // median of the alphaL and alphaR values, as suggested in
      // Kennedy's paper.
      int offset = - halfWidth;
      getChild(na,0)->setOffset(offset);
      for (int i = 1; i < numberOfShapes; i++) {
        offset += (alpha[i].first + alpha[i].second) / 2;
        getChild(na,i)->setOffset(offset);
      }
      setShape(mergedShape);
    }
  }

  size_t
  VisualNode::size(void) const {
    size_t s = sizeof(*this);
    s += sizeof(Node*)*getNumberOfChildren();
    if (shape && shape != Shape::leaf && shape != Shape::hidden) {
      s += sizeof(Shape)+sizeof(Extent)*(shape->depth()-1);
    }
    if (copy)
      s += static_cast<Space*>(Support::funmark(copy))->allocated();
    s += (choice != NULL ? choice->size() : 0);
    return s;
  }

}}

// STATISTICS: gist-any