ext/OGDF/src/energybased/LinearQuadtree.cpp

   1 /*
   2  * $Revision: 2565 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of class LinearQuadtree.
  11  *
  12  * \author Martin Gronemann
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #include "LinearQuadtree.h"
  44 #include "WSPD.h"
  45
  46 namespace ogdf {
  47
  48 void LinearQuadtree::init(float min_x, float min_y, float max_x, float max_y)
  49 {
  50         m_min_x = min_x;
  51         m_min_y = min_y;
  52         m_max_x = max_x;
  53         m_max_y = max_y;
  54         m_sideLengthGrid = ((double)(0x1 << 24) - 1.0);
  55         m_sideLengthPoints = (double)max(m_max_x - m_min_x, m_max_y - m_min_y);
  56         m_scaleInv = (m_sideLengthGrid / m_sideLengthPoints);
  57         m_cellSize = m_sideLengthPoints /((double)m_sideLengthGrid);
  58         clear();
  59 }
  60
  61
  62 void LinearQuadtree::clear()
  63 {
  64         m_numWSP = 0;
  65         m_numNotWSP = 0;
  66         m_numDirectNodes = 0;
  67         m_WSPD->clear();
  68 }
  69
  70
  71 LinearQuadtree::LinearQuadtree(__uint32 n, float* origXPos, float* origYPos, float* origSize) : m_origXPos(origXPos), m_origYPos(origYPos), m_origSize(origSize)
  72 {
  73         allocate(n);
  74         m_numPoints = n;
  75         m_maxNumNodes = 2*n;
  76 }
  77
  78
  79 LinearQuadtree::~LinearQuadtree(void)
  80 {
  81         deallocate();
  82 }
  83
  84
  85 void LinearQuadtree::allocate(__uint32 n)
  86 {
  87         m_numPoints = n;
  88         m_maxNumNodes = 2*n;
  89         m_tree = (LQNode*)MALLOC_16(m_maxNumNodes*sizeof(LQNode));
  90         m_nodeXPos = (float*)MALLOC_16(m_maxNumNodes*sizeof(float));
  91         m_nodeYPos = (float*)MALLOC_16(m_maxNumNodes*sizeof(float));
  92         m_nodeSize = (float*)MALLOC_16(m_maxNumNodes*sizeof(float));
  93         m_points = (LQPoint*)MALLOC_16(m_numPoints*sizeof(LQPoint));
  94         for (__uint32 i = 0; i < m_numPoints; i++)
  95                 m_points[i].ref = i;
  96         m_pointXPos = (float*)MALLOC_16(m_numPoints*sizeof(float));
  97         m_pointYPos = (float*)MALLOC_16(m_numPoints*sizeof(float));
  98         m_pointSize = (float*)MALLOC_16(m_numPoints*sizeof(float));
  99         m_notWspd = (LQWSPair*)MALLOC_16(m_maxNumNodes*sizeof(LQWSPair)*27);
 100         m_directNodes = (NodeID*)MALLOC_16(m_maxNumNodes*sizeof(NodeID));
 101         m_WSPD = new WSPD(m_maxNumNodes);
 102 }
 103
 104
 105 void LinearQuadtree::deallocate()
 106 {
 107         FREE_16(m_tree);
 108         FREE_16(m_nodeXPos);
 109         FREE_16(m_nodeYPos);
 110         FREE_16(m_nodeSize);
 111         FREE_16(m_points);
 112         FREE_16(m_pointXPos);
 113         FREE_16(m_pointYPos);
 114         FREE_16(m_pointSize);
 115         FREE_16(m_notWspd);
 116         FREE_16(m_directNodes);
 117         delete m_WSPD;
 118 }
 119
 120
 121 __uint64 LinearQuadtree::sizeInBytes() const
 122 {
 123         return m_numPoints*sizeof(LQPoint) +
 124                 m_maxNumNodes*sizeof(LQNode) +
 125                 m_maxNumNodes*sizeof(LQWSPair)*27 +
 126                 m_maxNumNodes*sizeof(NodeID) +
 127                 m_WSPD->sizeInBytes();
 128 }
 129
 130
 131 //! iterates back in the sequence until the first point with another morton number occures, returns that point +1
 132 LinearQuadtree::PointID LinearQuadtree::findFirstPointInCell(LinearQuadtree::PointID somePointInCell) const
 133 {
 134         if (somePointInCell==0) return 0;
 135         LinearQuadtree::PointID result = somePointInCell-1;
 136         while (mortonNr(somePointInCell) == mortonNr(result))
 137         {
 138                 if (result==0) return 0;
 139                 result--;
 140         }
 141         return result+1;
 142 }
 143
 144
 145 void LinearQuadtree::addWSPD(NodeID s, NodeID t)
 146 {
 147         m_numWSP++;
 148         m_WSPD->addWSP(s, t);
 149 }
 150
 151
 152 void LinearQuadtree::addDirectPair(NodeID s, NodeID t)
 153 {
 154         m_notWspd[m_numNotWSP].a = s;
 155         m_notWspd[m_numNotWSP].b = t;
 156         m_numNotWSP++;
 157 }
 158
 159
 160 void LinearQuadtree::addDirect(NodeID s)
 161 {
 162         m_directNodes[m_numDirectNodes] = s;
 163         m_numDirectNodes++;
 164 }
 165
 166 } // end of namespace ogdf