ext/OGDF/src/energybased/LinearQuadtree.h

   1 /*
   2  * $Revision: 2559 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration 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 #ifndef OGDF_LINEAR_QUADTREE_H
  44 #define OGDF_LINEAR_QUADTREE_H
  45
  46 #include "FastUtils.h"
  47 #include "FMEFunctional.h"
  48
  49 #define M2L_MIN_BOUND 8
  50 #define WSPD_BRANCH_BOUND 16
  51 #define WSPD_BOUND 25
  52
  53 namespace ogdf {
  54
  55 class LinearQuadtreeBuilder;
  56 class WSPD;
  57
  58 class LinearQuadtree
  59 {
  60         friend class LinearQuadtreeBuilder;
  61         friend class LinearQuadtreeBuilderList;
  62 public:
  63         typedef unsigned int NodeID;
  64         typedef unsigned int PointID;
  65
  66         struct LQPoint                          // 16 byte
  67         {
  68                 MortonNR mortonNr;              // 8 byte
  69                 __uint32 node;                  // 4 byte
  70                 __uint32 ref;                   // 4 byte
  71         };
  72
  73         struct LQNode                           // 27 byte
  74         {
  75                 __uint32 level;                 // 4 byte
  76                 NodeID next;                    // 4 byte
  77                 NodeID child[4];                // 4 byte *4 = 16 byte
  78                 __uint32 numChilds;             // 4 byte
  79                 PointID firstPoint;             // 4 byte
  80                 __uint32 numPoints;             // 4 byte
  81                 bool fence;                             // 1 byte
  82         };
  83
  84         struct LQWSPair
  85         {
  86                 LQWSPair(NodeID c, NodeID d) : a(c), b(d) {};
  87                 NodeID a;
  88                 NodeID b;
  89         };
  90
  91         struct is_fence_condition_functor
  92         {
  93                 const LinearQuadtree& tree;
  94                 is_fence_condition_functor(const LinearQuadtree& t) : tree(t) { }
  95                 inline bool operator()(NodeID u) {      return tree.isFence(u); }
  96         };
  97
  98         //! creator
  99         inline is_fence_condition_functor is_fence_condition() const {  return is_fence_condition_functor(*this); }
 100
 101
 102         struct is_leaf_condition_functor
 103         {
 104                 const LinearQuadtree& tree;
 105                 is_leaf_condition_functor(const LinearQuadtree& t) : tree(t) { }
 106                 inline bool operator()(NodeID u) {      return tree.isLeaf(u); }
 107         };
 108
 109         //! creator
 110         inline is_leaf_condition_functor is_leaf_condition() const { return is_leaf_condition_functor(*this); }
 111
 112
 113         //! simple functor for iterating over all nodes
 114         template<typename F>
 115         struct forall_tree_nodes_functor
 116         {
 117                 const LinearQuadtree& tree;
 118                 F func;
 119                 NodeID begin;
 120                 __uint32 numNodes;
 121
 122                 forall_tree_nodes_functor(const LinearQuadtree& t, F f, NodeID b, __uint32 num) : tree(t), func(f), begin(b), numNodes(num) { }
 123
 124                 inline void operator()()
 125                 {
 126                         NodeID it = begin;
 127                         for (__uint32 i=0; i<numNodes; i++)
 128                         {
 129                                 func(it);
 130                                 it = tree.nextNode(it);
 131                         }
 132                 }
 133         };
 134
 135         //! creator
 136         template<typename F>
 137         inline forall_tree_nodes_functor<F> forall_tree_nodes(F f, NodeID begin, __uint32 num) const
 138         {
 139                 return forall_tree_nodes_functor<F>(*this, f, begin, num);
 140         }
 141
 142         //! simple functor for iterating over all children of a node
 143         template<typename F>
 144         struct forall_children_functor
 145         {
 146                 const LinearQuadtree& tree;
 147                 F func;
 148
 149                 forall_children_functor(const LinearQuadtree& t, F f) : tree(t), func(f) { }
 150
 151                 inline void operator()(NodeID u)
 152                 {
 153                         if (tree.isLeaf(u)) return;
 154                         for (__uint32 i = 0; i < tree.numberOfChilds(u); i++) func(tree.child(u, i));
 155                 }
 156         };
 157
 158         //! creator
 159         template<typename F>
 160         inline forall_children_functor<F> forall_children(F f) const
 161         {
 162                 return forall_children_functor<F>(*this, f);
 163         }
 164
 165
 166         //! simple functor for iterating over all points of a node
 167         template<typename Func>
 168         struct forall_points_functor
 169         {
 170                 const LinearQuadtree& tree;
 171                 Func func;
 172
 173                 forall_points_functor(const LinearQuadtree& t, const Func& f) : tree(t), func(f) { }
 174
 175                 inline void operator()(NodeID u)
 176                 {
 177                         PointID firstPoint = tree.firstPoint(u);
 178                         PointID end = firstPoint + tree.numberOfPoints(u);
 179                         for (PointID i = firstPoint; i < end; i++)
 180                                 func(i);
 181                 }
 182         };
 183
 184         //! creator
 185         template<typename Func>
 186         inline forall_points_functor<Func> forall_points(const Func& func) const
 187         {
 188                 return forall_points_functor<Func>(*this, func);
 189         }
 190
 191         //! functor for iterating over all ordered pairs of children of a node
 192         template<typename F>
 193         struct forall_ordered_pairs_of_children_functor
 194         {
 195                 const LinearQuadtree& tree;
 196                 F func;
 197
 198                 forall_ordered_pairs_of_children_functor(const LinearQuadtree& t, F f) : tree(t), func(f) { }
 199
 200                 inline void operator()(NodeID u)
 201                 {
 202                         if (tree.isLeaf(u)) return;
 203                         for (__uint32 i = 0; i < tree.numberOfChilds(u); i++)
 204                                 for (__uint32 j = i+1; j < tree.numberOfChilds(u); j++)
 205                                         func(tree.child(u, i), tree.child(u, j));
 206                 }
 207         };
 208
 209         //! creator
 210         template<typename F>
 211         inline forall_ordered_pairs_of_children_functor<F> forall_ordered_pairs_of_children(F f)  const
 212         {
 213                 return forall_ordered_pairs_of_children_functor<F>(*this, f);
 214         }
 215
 216         //! top down traversal of the subtree of a given node
 217         template<typename F, typename CondType = true_condition>
 218         struct top_down_traversal_functor
 219         {
 220                 const LinearQuadtree& tree;
 221                 F func;
 222                 CondType cond;
 223
 224                 top_down_traversal_functor(const LinearQuadtree& t, F f) : tree(t), func(f) { }
 225                 top_down_traversal_functor(const LinearQuadtree& t, F f, CondType c) : tree(t), func(f), cond(c) { }
 226
 227                 inline void operator()(NodeID u)
 228                 {
 229                         if (cond(u)) {  func(u); tree.forall_children(*this)(u); };
 230                 }
 231         };
 232
 233         //! creator
 234         template<typename F>
 235         inline top_down_traversal_functor<F> top_down_traversal(F f) const
 236         {
 237                 return top_down_traversal_functor<F>(*this, f);
 238         }
 239
 240         //! creator
 241         template<typename F, typename Cond>
 242         inline top_down_traversal_functor<F, Cond> top_down_traversal(F f, Cond cond) const
 243         {
 244                 return top_down_traversal_functor<F, Cond>(*this, f, cond);
 245         }
 246
 247
 248         //! bottom up traversal of the subtree of a given node
 249         template<typename F, typename CondType = true_condition>
 250         struct bottom_up_traversal_functor
 251         {
 252                 const LinearQuadtree& tree;
 253                 F func;
 254                 CondType cond;
 255
 256                 bottom_up_traversal_functor(const LinearQuadtree& t, F f) : tree(t), func(f) { }
 257                 bottom_up_traversal_functor(const LinearQuadtree& t, F f, CondType c) : tree(t), func(f), cond(c) { }
 258
 259                 inline void operator()(NodeID u)
 260                 {
 261                         if (cond(u)) { tree.forall_children(*this)(u); func(u); };
 262                 }
 263         };
 264
 265         //! creator
 266         template<typename F>
 267         inline bottom_up_traversal_functor<F> bottom_up_traversal(F f) const
 268         {
 269                 return bottom_up_traversal_functor<F>(*this, f);
 270         }
 271
 272         //! creator
 273         template<typename F, typename Cond>
 274         inline bottom_up_traversal_functor<F, Cond> bottom_up_traversal(F f, Cond cond) const
 275         {
 276                 return bottom_up_traversal_functor<F, Cond>(*this, f, cond);
 277         }
 278
 279
 280         template<typename WSPairFuncType, typename DPairFuncType, typename DNodeFuncType, typename BranchCondType = true_condition>
 281         struct wspd_functor
 282         {
 283                 const LinearQuadtree& tree;
 284                 WSPairFuncType WSFunction;
 285                 DPairFuncType DPairFunction;
 286                 DNodeFuncType DNodeFunction;
 287                 BranchCondType BranchCondFunction;
 288
 289                 wspd_functor(const LinearQuadtree& t, WSPairFuncType& wsf, DPairFuncType& dpf, DNodeFuncType& dnf) : tree(t), WSFunction(wsf),  DPairFunction(dpf),  DNodeFunction(dnf) { }
 290
 291                 wspd_functor(const LinearQuadtree& t, WSPairFuncType& wsf, DPairFuncType& dpf, DNodeFuncType& dnf, BranchCondType& bc) : tree(t), WSFunction(wsf),  DPairFunction(dpf),  DNodeFunction(dnf), BranchCondFunction(bc) { }
 292
 293                 inline void operator()(NodeID u)
 294                 {
 295                         if (BranchCondFunction(u))
 296                         {
 297                                 if (tree.isLeaf(u) || (tree.numberOfPoints(u) <= WSPD_BOUND))
 298                                 {
 299                                         if (tree.numberOfPoints(u) > 1)
 300                                                 DNodeFunction(u);
 301                                 } else
 302                                 {
 303                                         tree.forall_children(*this)(u);
 304                                         tree.forall_ordered_pairs_of_children(*this)(u);
 305                                 }
 306                         }
 307                 }
 308
 309
 310                 inline void operator()(NodeID u, NodeID v)
 311                 {
 312                         if (tree.isWS(u, v))
 313                         {
 314                                 if ((tree.numberOfPoints(u) < M2L_MIN_BOUND) && (tree.numberOfPoints(v) < M2L_MIN_BOUND))
 315                                         DPairFunction(u, v);
 316                                 else
 317                                         WSFunction(u, v);
 318                         }
 319                         else
 320                         {
 321                                 if (((tree.numberOfPoints(u) <= WSPD_BRANCH_BOUND) && (tree.numberOfPoints(v) <= WSPD_BRANCH_BOUND)) ||
 322                                         (tree.isLeaf(u) || tree.isLeaf(v)))
 323                                 {
 324                                         DPairFunction(u, v);
 325                                 }
 326                                 else
 327                                 {
 328                                         if (tree.level(u) >= tree.level(v))
 329                                                 tree.forall_children(pair_call(*this, v))(u);
 330                                         else
 331                                                 tree.forall_children(pair_call(*this, u))(v);
 332                                 }
 333                         }
 334                 }
 335         };
 336
 337         template<typename A, typename B, typename C, typename ConditionType>
 338         inline wspd_functor<A, B, C, ConditionType> forall_well_separated_pairs(A a, B b, C c, ConditionType cond)
 339         {
 340                 return wspd_functor<A, B, C, ConditionType>(*this, a, b, c, cond);
 341         }
 342
 343         template<typename A, typename B, typename C>
 344         inline wspd_functor<A, B, C> forall_well_separated_pairs(A a, B b, C c)
 345         {
 346                 return wspd_functor<A, B, C>(*this, a, b, c);
 347         }
 348
 349         struct StoreWSPairFunctor
 350         {
 351                 LinearQuadtree& tree;
 352                 StoreWSPairFunctor(LinearQuadtree& t) : tree(t) { }
 353                 inline void operator()(NodeID a, NodeID b) { tree.addWSPD(a, b); }
 354         };
 355
 356         StoreWSPairFunctor inline StoreWSPairFunction() { return StoreWSPairFunctor(*this); }
 357
 358
 359         struct StoreDirectPairFunctor
 360         {
 361                 LinearQuadtree& tree;
 362                 StoreDirectPairFunctor(LinearQuadtree& t) : tree(t) { }
 363                 inline void operator()(NodeID a, NodeID b) { tree.addDirectPair(a, b); }
 364         };
 365
 366         StoreDirectPairFunctor inline StoreDirectPairFunction() { return StoreDirectPairFunctor(*this); }
 367
 368
 369         struct StoreDirectNodeFunctor
 370         {
 371                 LinearQuadtree& tree;
 372                 StoreDirectNodeFunctor(LinearQuadtree& t) : tree(t) { }
 373                 inline void operator()(NodeID a) { tree.addDirect(a); }
 374         };
 375
 376         StoreDirectNodeFunctor inline StoreDirectNodeFunction() { return StoreDirectNodeFunctor(*this); }
 377
 378         inline NodeID level(NodeID node) const
 379         {
 380                 return m_tree[node].level;
 381         }
 382
 383         inline NodeID nextNode(NodeID node) const
 384         {
 385                 return m_tree[node].next;
 386         }
 387
 388         inline void setNextNode(NodeID node, NodeID next)
 389         {
 390                 m_tree[node].next = next;
 391         }
 392
 393         inline void setLevel(NodeID node, __uint32 level)
 394         {
 395                 m_tree[node].level = level;
 396         }
 397
 398         inline PointID firstPoint(NodeID node) const
 399         {
 400                 return m_tree[node].firstPoint;
 401         }
 402
 403         inline void setFirstPoint(NodeID node, PointID firstPoint)
 404         {
 405                 m_tree[node].firstPoint = firstPoint;
 406         }
 407
 408         inline LQPoint& point(PointID pointID)
 409         {
 410                 return m_points[pointID];
 411         }
 412
 413         inline const LQPoint& point(PointID pointID) const
 414         {
 415                 return m_points[pointID];
 416         }
 417
 418         inline MortonNR mortonNr(PointID point) const
 419         {
 420                 return m_points[point].mortonNr;
 421         }
 422
 423         //! returns the number of children of node node. for an inner node this is 1..4 and
 424         //! can be accessed by child(i). For a leaf the number of points in this leaf is returned
 425         //! starting with point child(0)
 426         inline __uint32 numberOfChilds(NodeID node) const
 427         {
 428                 return m_tree[node].numChilds;
 429         }
 430
 431         //! sets the number of children of a node
 432         inline void setNumberOfChilds(NodeID node, __uint32 numChilds)
 433         {
 434                 m_tree[node].numChilds = numChilds;
 435         }
 436
 437         //! returns the i th child index of node node
 438         inline NodeID child(NodeID node, __uint32 i) const
 439         {
 440                 return m_tree[node].child[i];
 441         }
 442
 443         //! sets the i-th child index of node node
 444         inline void setChild(NodeID node, __uint32 i, NodeID c)
 445         {
 446                 m_tree[node].child[i] = c;
 447         }
 448
 449         //! returns true if the given node index is a leaf
 450         inline bool isLeaf(NodeID node) const
 451         {
 452                 return !m_tree[node].numChilds;
 453         }
 454
 455         //! sets the fence flag for node
 456         inline bool isFence(NodeID node) const
 457         {
 458                 return m_tree[node].fence;
 459         }
 460
 461         //! returns the number of points contained in the subtree of node
 462         inline __uint32 numberOfPoints(NodeID node) const
 463         {
 464                 return m_tree[node].numPoints;
 465         }
 466
 467         //! sets the number of nodes containted in node
 468         inline void setNumberOfPoints(NodeID node, __uint32 numPoints)
 469         {
 470                 m_tree[node].numPoints = numPoints;
 471         }
 472
 473         //! returns the index of the root
 474         inline NodeID root() const
 475         {
 476                 return m_root;
 477         }
 478
 479         //! returns the number of points in this tree
 480         inline __uint32 numberOfPoints() const
 481         {
 482                 return m_numPoints;
 483         }
 484
 485         //! returns the number of nodes in this tree
 486         inline __uint32 numberOfNodes() const
 487         {
 488                 return m_numInnerNodes + m_numLeaves;
 489         }
 490
 491         //! the upper bound for a compressed quadtree (2*numPoints)
 492         inline __uint32 maxNumberOfNodes() const
 493         {
 494                 return m_maxNumNodes;
 495         }
 496
 497         //! resets the tree
 498         void clear();
 499
 500         //! constructor. required tree mem will be allocated
 501         LinearQuadtree(__uint32 n, float* origXPos, float* origYPos, float* origSize);
 502
 503         //! destructor. tree mem will be released
 504         ~LinearQuadtree(void);
 505
 506         __uint64 sizeInBytes() const;
 507
 508         inline NodeID pointLeaf(PointID point) const
 509         {
 510                 return m_points[point].node;
 511         }
 512
 513         inline void setPointLeaf(PointID point, NodeID leaf)
 514         {
 515                 m_points[point].node = leaf;
 516         }
 517
 518         inline float pointX(PointID point) const { return m_pointXPos[point]; }
 519
 520         inline float pointY(PointID point) const { return m_pointYPos[point]; }
 521
 522         inline float pointSize(PointID point) const { return m_pointSize[point]; }
 523
 524         inline float* pointX() const { return m_pointXPos; }
 525
 526         inline float* pointY() const { return m_pointYPos; }
 527
 528         inline float* pointSize() const { return m_pointSize; }
 529
 530         inline float nodeX(NodeID node) const { return m_nodeXPos[node]; }
 531
 532         inline void setNodeX(NodeID node, float x) { m_nodeXPos[node] = x; }
 533
 534         inline float nodeY(NodeID node) const { return m_nodeYPos[node]; }
 535
 536         inline void setNodeY(NodeID node, float y) { m_nodeYPos[node] = y; }
 537
 538         inline float nodeSize(NodeID node) const { return m_nodeSize[node]; }
 539
 540         inline void setNodeSize(NodeID node, float size) { m_nodeSize[node] = size; }
 541
 542         void setPoint(PointID id, float x, float y, __uint32 ref)
 543         {
 544                 m_pointXPos[id] = x;
 545                 m_pointYPos[id] = y;
 546                 m_points[id].ref = ref;
 547         }
 548
 549         void updatePointPositionSize(PointID id)
 550         {
 551                 __uint32 ref = m_points[id].ref;
 552                 m_pointXPos[id] = m_origXPos[ref];
 553                 m_pointYPos[id] = m_origYPos[ref];
 554                 m_pointSize[id] = m_origSize[ref];
 555         }
 556
 557         void setPoint(PointID id, float x, float y, float r, __uint32 ref)
 558         {
 559                 m_pointXPos[id] = x;
 560                 m_pointYPos[id] = y;
 561                 m_pointSize[id] = r;
 562                 m_points[id].ref = ref;
 563         }
 564
 565         void setPoint(PointID id, float x, float y, float r)
 566         {
 567                 m_pointXPos[id] = x;
 568                 m_pointYPos[id] = y;
 569                 m_pointSize[id] = r;
 570         }
 571
 572         inline __uint32 refOfPoint(PointID id) const
 573         {
 574                 return m_points[id].ref;
 575         }
 576
 577         inline NodeID nodeOfPoint(PointID id) const
 578         {
 579                 return m_points[id].node;
 580         }
 581
 582         inline void nodeFence(NodeID node)
 583         {
 584                 m_tree[node].fence = true;
 585         }
 586
 587         inline bool isWS(NodeID a, NodeID b) const
 588         {
 589                 float s = 0.00000001f;
 590                 float dx = nodeX(a) - nodeX(b);
 591                 float dy = nodeY(a) - nodeY(b);
 592                 float d_sq = dx*dx+dy*dy;
 593                 float l = max(nodeSize(a), nodeSize(b));
 594                 return (d_sq >(s*0.5 + 1)*(s*0.5 + 1)* 2 * l * l);
 595         }
 596
 597         void computeWSPD();
 598
 599         void computeWSPD(NodeID n);
 600
 601         inline NodeID firstInnerNode() const { return m_firstInner; }
 602
 603         inline __uint32 numberOfInnerNodes() const { return m_numInnerNodes; }
 604
 605         inline NodeID firstLeaf() const { return m_firstLeaf; }
 606
 607         inline __uint32 numberOfLeaves() const { return m_numLeaves; }
 608
 609
 610         __uint32 numberOfWSP() const { return m_numWSP; }
 611
 612         __uint32 numberOfDirectPairs() const { return m_numNotWSP; }
 613
 614         __uint32 numberOfDirectNodes() const { return m_numDirectNodes; }
 615
 616         inline NodeID directNode(__uint32 i) const { return m_directNodes[i]; }
 617
 618         inline NodeID directNodeA(__uint32 i) const { return m_notWspd[i].a; }
 619
 620         inline NodeID directNodeB(__uint32 i) const { return m_notWspd[i].b; }
 621
 622
 623         WSPD* wspd() const{ return m_WSPD; };
 624
 625         void init(float min_x, float min_y, float max_x, float max_y);
 626         inline float minX() const { return m_min_x; }
 627         inline float minY() const { return m_min_y; }
 628         inline float maxX() const { return m_max_x; }
 629         inline float maxY() const { return m_max_y; }
 630         inline double scaleInv() const { return m_scaleInv; }
 631
 632
 633         inline void computeCoords(NodeID nodeIndex)
 634         {
 635                 __uint32 ix, iy;
 636                 __uint32 level = this->level(nodeIndex);
 637                 float s = (float)(m_cellSize * (1 << level));
 638                 this->setNodeSize(nodeIndex, s);
 639                 MortonNR mnr = this->mortonNr(this->firstPoint(nodeIndex));
 640                 mnr = mnr >> (level * 2);
 641                 mnr = mnr << (level * 2);
 642                 mortonNumberInv<__uint64, __uint32>(mnr, ix, iy);
 643                 this->setNodeX(nodeIndex, (float)((m_sideLengthPoints*((float)ix)-0.5)/m_sideLengthGrid + (float)m_min_x + (float)s*0.5f));
 644                 this->setNodeY(nodeIndex, (float)((m_sideLengthPoints*((float)iy)-0.5)/m_sideLengthGrid + (float)m_min_y + (float)s*0.5f));
 645         }
 646
 647         LQPoint* pointArray() { return m_points; }
 648
 649         PointID findFirstPointInCell(PointID somePointInCell) const;
 650
 651 private:
 652         //! helper function for allocating the array's
 653         void allocate(__uint32 n);
 654
 655         //! helper function for releasing memory
 656         void deallocate();
 657
 658         inline void initLeaf(NodeID leaf, PointID firstPoint, __uint32 numPoints, NodeID next)
 659         {
 660                 m_tree[leaf].numChilds = 0;
 661                 m_tree[leaf].next = next;
 662                 m_tree[leaf].fence = 0;
 663                 m_tree[leaf].level = 0;
 664                 m_tree[leaf].firstPoint = firstPoint;
 665                 m_tree[leaf].numPoints = numPoints;
 666         }
 667
 668         inline void initInnerNode(NodeID node, NodeID leftChild, NodeID rightChild, __uint32 level, NodeID next)
 669         {
 670                 m_tree[node].numChilds = 2;
 671                 m_tree[node].child[0] = leftChild;
 672                 m_tree[node].child[1] = rightChild;
 673                 m_tree[node].next = next;
 674                 m_tree[node].fence = 0;
 675                 m_tree[node].level = level;
 676                 m_tree[node].firstPoint = leftChild;
 677                 m_tree[node].numPoints = rightChild - leftChild;
 678         }
 679
 680         //! appends one child index. Assumes childCount < 4 and not leaf
 681         inline void nodeAppendChild(NodeID node, NodeID child)
 682         {
 683                 m_tree[node].child[m_tree[node].numChilds++] = child;
 684                 m_tree[node].numPoints += m_tree[child].numPoints;
 685         }
 686
 687         //! appends an successing point by simply increasing childcount of a leaf. Assumes isLeaf
 688         inline void leafAppendPoint(NodeID leaf, PointID point)
 689         {
 690                 m_points[point].node = leaf;
 691                 m_tree[leaf].numPoints++;
 692         }
 693
 694         //! adds a well-separated pair to the wspd
 695         void addWSPD(NodeID s, NodeID t);
 696
 697         //! add a direct pair to the array list of direct pairs
 698         void addDirectPair(NodeID s, NodeID t);
 699
 700         //! add a direct node to the array list of direct nodes
 701         void addDirect(NodeID s);
 702
 703         //! the x coordinate of the left most point
 704         float m_min_x;
 705
 706         //! the y coordinate of the bottom most point
 707         float m_min_y;
 708
 709         //! the x coordinate of the right most point
 710         float m_max_x;
 711
 712         //! the y coordinate of the top most point
 713         float m_max_y;
 714
 715         //! the height and width of a grid cell
 716         double m_cellSize;
 717
 718         //! the inverse scale to transform
 719         double m_scaleInv;
 720
 721         //! the maximum of height and width
 722         double m_sideLengthPoints;
 723
 724         //! the resulting side length of the grid (constant)
 725         double m_sideLengthGrid;
 726
 727         //! point x coord in graph order
 728         float*   m_origXPos;
 729
 730         //! point y coord in graph order
 731         float*   m_origYPos;
 732
 733         //! point size in graph order
 734         float*   m_origSize;
 735
 736         //! point x coord in tree order
 737         float*   m_pointXPos;
 738
 739         //! point y coord in tree order
 740         float*   m_pointYPos;
 741
 742         //! point size in tree order
 743         float*   m_pointSize;
 744
 745         //! node x coord
 746         float*   m_nodeXPos;
 747
 748
 749         //! node y coord
 750         float*   m_nodeYPos;
 751
 752         //! node size
 753         float*   m_nodeSize;
 754
 755         //! the main tree array containing all nodes (including leaves)
 756         LQNode*  m_tree;
 757
 758         //! the maximum number of nodes (2*n here instead of 2*n-1)
 759         __uint32 m_maxNumNodes;
 760
 761         //! the point order in tree order
 762         LQPoint* m_points;
 763
 764         //! number of points this quadtree is based on
 765         __uint32 m_numPoints;
 766
 767         __uint32 m_numWSP;
 768
 769         LQWSPair* m_notWspd;
 770         __uint32 m_numNotWSP;
 771
 772         NodeID* m_directNodes;
 773         __uint32 m_numDirectNodes;
 774
 775         //! the wspd of this quadtree
 776         WSPD* m_WSPD;
 777
 778         //! the root of the tree
 779         NodeID m_root;
 780
 781         //! first leaf in the leaf chain
 782         NodeID m_firstLeaf;
 783
 784         //! number of leaves in the chain
 785         __uint32 m_numLeaves;
 786
 787         //! first inner node in the inner node chain
 788         NodeID m_firstInner;
 789
 790         //! number of inner nodes in the chain
 791         __uint32 m_numInnerNodes;
 792
 793 };
 794
 795 inline void swap(ogdf::LinearQuadtree::LQPoint& b, ogdf::LinearQuadtree::LQPoint& a)
 796 {
 797         ogdf::LinearQuadtree::LQPoint t = a;
 798         a = b;
 799         b = t;
 800 }
 801
 802 inline bool LQPointComparer(const LinearQuadtree::LQPoint& a, const LinearQuadtree::LQPoint& b)
 803 {
 804         return a.mortonNr < b.mortonNr;
 805 }
 806
 807 } // end of namespace ogdf
 808
 809 #endif
 810