LinearQuadtreeBuilder.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/energybased/fast_multipole_embedder/FastUtils.h>
#include <ogdf/energybased/fast_multipole_embedder/LinearQuadtree.h>
 
namespace ogdf {
namespace fast_multipole_embedder {
 
class LinearQuadtreeBuilder {
public:
    explicit LinearQuadtreeBuilder(LinearQuadtree& treeRef)
        : firstInner(0)
        , firstLeaf(0)
        , lastInner(0)
        , lastLeaf(0)
        , numInnerNodes(0)
        , numLeaves(0)
        , tree(treeRef)
        , restoreChainLastNode(0) {
        n = tree.numberOfPoints();
    }
 
    void build();
 
    void prepareNodeAndLeaf(LinearQuadtree::PointID leafPos, LinearQuadtree::PointID nextLeafPos);
 
    void prepareTree(LinearQuadtree::PointID begin, LinearQuadtree::PointID end);
 
    void prepareTree();
 
    void mergeWithNext(LinearQuadtree::NodeID curr);
 
    LinearQuadtree::NodeID buildHierarchy(LinearQuadtree::NodeID curr, uint32_t maxLevel);
 
    void buildHierarchy();
 
    inline void restorePushBackChain(LinearQuadtree::NodeID curr) {
        if (restoreChainLastNode) {
            tree.setNextNode(restoreChainLastNode, curr);
        } else {
            firstInner = curr;
        }
        restoreChainLastNode = curr;
        numInnerNodes++;
    }
 
    inline void restoreChain(LinearQuadtree::NodeID curr) {
        if (tree.isLeaf(curr)) {
            return;
        } else {
            restoreChain(tree.child(curr, 0));
            tree.setFirstPoint(curr, tree.firstPoint(tree.child(curr, 0)));
            restorePushBackChain(curr);
            for (uint32_t i = 1; i < tree.numberOfChilds(curr); i++) {
                restoreChain(tree.child(curr, i));
            }
 
            uint32_t lastPoint = tree.firstPoint(tree.child(curr, tree.numberOfChilds(curr) - 1))
                    + tree.numberOfPoints(tree.child(curr, tree.numberOfChilds(curr) - 1));
            tree.setNumberOfPoints(curr, lastPoint - tree.firstPoint(curr));
        }
    }
 
    inline void restoreChain() {
        restoreChainLastNode = 0;
        numInnerNodes = 0;
        if (!tree.isLeaf(tree.root())) {
            restoreChain(tree.root());
        }
        if (restoreChainLastNode) {
            tree.setNextNode(restoreChainLastNode, 0);
        }
    }
 
    inline uint32_t CAL(LinearQuadtree::PointID a, LinearQuadtree::PointID b) {
        // 64 bit version
#if 0
        // FIXME: a < 0 is always true (PointID is unsigned int)
        if (a < 0) return 64;
#endif
        if (b >= tree.numberOfPoints()) {
            return 64;
        }
        uint32_t res = (32 - ((mostSignificantBit(tree.mortonNr(a) ^ tree.mortonNr(b))) / 2));
        return res;
    }
 
    LinearQuadtree::NodeID firstInner;
    LinearQuadtree::NodeID firstLeaf;
 
    LinearQuadtree::NodeID lastInner;
    LinearQuadtree::NodeID lastLeaf;
    uint32_t numInnerNodes;
    uint32_t numLeaves;
 
    LinearQuadtree& tree;
    LinearQuadtree::NodeID restoreChainLastNode;
    LinearQuadtree::PointID n;
};
 
}
}