DTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/energybased/dtree/utils.h>
 
#include <algorithm>
 
namespace ogdf {
namespace energybased {
namespace dtree {
 
template<typename IntType, int Dim>
class DTree {
public:
    static constexpr int MaxNumChildrenPerNode = (1 << Dim);
 
    explicit DTree(int numPoints)
        : m_maxLevel((sizeof(IntType) << 3) + 1), m_numPoints(0), m_rootIndex(-1) {
        allocate(numPoints);
    }
 
    ~DTree() { deallocate(); }
 
    struct Point {
        IntType x[Dim];
    };
 
    struct MortonEntry {
        IntType mortonNr[Dim]; 
        int ref; 
 
        bool operator<(const MortonEntry& other) const {
            return mortonComparerLess<IntType, Dim>(mortonNr, other.mortonNr);
        }
 
        bool operator==(const MortonEntry& other) const {
            return mortonComparerEqual<IntType, Dim>(mortonNr, other.mortonNr);
        }
    };
 
    struct Node {
        // quadtree related stuff
        int level; 
        int next; 
        int child[MaxNumChildrenPerNode]; 
        int numChilds; 
        int firstPoint; 
        int numPoints; 
    };
 
    inline const Node& node(int i) const { return m_nodes[i]; };
 
    inline Node& node(int i) { return m_nodes[i]; };
 
    inline int numChilds(int i) const { return m_nodes[i].numChilds; };
 
    inline int child(int i, int j) const { return m_nodes[i].child[j]; };
 
    inline int numPoints(int i) const { return m_nodes[i].numPoints; };
 
    inline int point(int i, int j) const { return m_mortonOrder[m_nodes[i].firstPoint + j].ref; };
 
    void setPoint(int i, int d, IntType value);
 
    inline int numPoints() const { return m_numPoints; };
 
    inline int maxNumNodes() const { return m_numPoints * 2; };
 
    const Point& point(int i) const { return m_points[i]; }
 
    void prepareMortonOrder();
 
    void sortMortonNumbers();
 
    void prepareNodeLayer();
 
    inline void mergeWithNext(int curr);
 
    inline void adjustPointInfo(int curr);
 
    int linkNodes(int curr, int maxLevel);
 
    void linkNodes();
 
    void build();
 
    int countPoints(int curr) const;
 
    int countPoints() const { return countPoints(m_rootIndex); };
 
    int rootIndex() const { return m_rootIndex; };
 
private:
    void allocate(int n);
 
    void deallocate();
 
    int m_maxLevel;
    Point* m_points = nullptr; 
    int m_numPoints; 
    MortonEntry* m_mortonOrder = nullptr; 
    Node* m_nodes = nullptr; 
    int m_rootIndex; 
};
 
template<typename IntType, int Dim>
void DTree<IntType, Dim>::allocate(int n) {
    m_numPoints = n;
    m_points = new Point[m_numPoints];
    m_mortonOrder = new MortonEntry[m_numPoints];
    m_nodes = new Node[m_numPoints * 2];
};
 
template<typename IntType, int Dim>
void DTree<IntType, Dim>::deallocate() {
    delete[] m_points;
    delete[] m_mortonOrder;
    delete[] m_nodes;
};
 
template<typename IntType, int Dim>
void DTree<IntType, Dim>::setPoint(int i, int d, IntType value) {
    // set i-th point d coord to value
    m_points[i].x[d] = value;
}
 
template<typename IntType, int Dim>
void DTree<IntType, Dim>::prepareMortonOrder() {
    // loop over the point order
    for (int i = 0; i < m_numPoints; i++) {
        // set i's ref to i
        m_mortonOrder[i].ref = i;
 
        // generate the morton number by interleaving the bits
        interleaveBits<IntType, Dim>(m_points[i].x, m_mortonOrder[i].mortonNr);
    }
}
 
template<typename IntType, int Dim>
void DTree<IntType, Dim>::sortMortonNumbers() {
    // just sort them
    std::sort(m_mortonOrder, m_mortonOrder + m_numPoints);
}
 
template<typename IntType, int Dim>
void DTree<IntType, Dim>::prepareNodeLayer() {
    Node* leafLayer = m_nodes;
    Node* innerLayer = m_nodes + m_numPoints;
 
#if 0
    int last = 0;
#endif
    for (int i = 0; i < m_numPoints;) {
        Node& leaf = leafLayer[i];
        Node& innerNode = innerLayer[i];
        // i represents the current node on both layers
        int j = i + 1;
 
        // find the next morton number that differs or stop when j is equal to m_numPoints
        while ((j < m_numPoints) && (m_mortonOrder[i] == m_mortonOrder[j])) {
            j++;
        }
        // j is the index of the next cell (node)
 
        // init the node on the leaf layer
        leaf.firstPoint = i; //< node sits above the first point of the cell
        leaf.numPoints =
                j - i; //< number of points with equal morton numbers (number of points in grid cell)
        leaf.numChilds = 0; //< it's a leaf
        leaf.level = 0; //< it's a leaf
        leaf.next = j; //< this leaf hasnt been created yet but we use indices so its ok
 
        if (j < m_numPoints) {
            // Note: the n-th inner node is not needed because we only need n-1 inner nodes to cover n leaves
            // if we reach the n-1-th inner node, the variable last is set for the last time
#if 0
            last = i;
#endif
            // init the node on the inner node layer
            innerNode.child[0] = i; //< node sits above the first leaf
            innerNode.child[1] = j; //< this leaf hasnt been created yet but we use indices so its ok
            innerNode.numChilds = 2; //< every inner node covers two leaves in the beginning
            innerNode.level = lowestCommonAncestorLevel<IntType, Dim>(m_mortonOrder[i].mortonNr,
                    m_mortonOrder[j].mortonNr);
            innerNode.next = m_numPoints + j; // the inner node layer is shifted by n
        } else {
            // no next for the last
            innerLayer[i].next = 0;
            // this is important to make the recursion stop
            innerLayer[i].level = m_maxLevel + 1;
        }
 
        // advance to the next cell
        i = j;
    };
        // here we set the successor of the n-1-th inner node to zero to avoid dealing with the n-th inner node
#if 0
    innerLayer[last].next = 0;
#endif
};
 
template<typename IntType, int Dim>
inline void DTree<IntType, Dim>::mergeWithNext(int curr) {
    int next = node(curr).next;
    // Cool: since we never touched node(next) before
    // it is still linked to only two leaves,
    node(curr).child[node(curr).numChilds++] = node(next).child[1];
 
    // thus we don't need this ugly loop:
    //   for (int i=1; i<node(next).numChilds; i++)
    //      node(curr).child[node(curr).numChilds++] = node(next).child[i];
    node(curr).next = node(next).next;
};
 
template<typename IntType, int Dim>
inline void DTree<IntType, Dim>::adjustPointInfo(int curr) {
    // adjust the first such that it matched the first child
    node(curr).firstPoint = node(node(curr).child[0]).firstPoint;
 
    // index of the last child
    const int lastChild = node(curr).child[node(curr).numChilds - 1];
 
    // numPoints is lastPoint + 1 - firstPoint
    node(curr).numPoints =
            node(lastChild).firstPoint + node(lastChild).numPoints - node(curr).firstPoint;
}
 
template<typename IntType, int Dim>
int DTree<IntType, Dim>::linkNodes(int curr, int maxLevel) {
    // while the subtree is smaller than maxLevel
    while (node(curr).next && node(node(curr).next).level < maxLevel) {
        // get next node in the chain
        int next = node(curr).next;
        // First case: same level => merge, discard next
        if (node(curr).level == node(next).level) {
            mergeWithNext(curr);
        } else if (node(curr).level < node(next).level) {
            // Second case: next is higher => become first child
            // set the first child of next to the current node
            node(next).child[0] = curr;
 
            // adjust the point info of the curr
            adjustPointInfo(curr);
 
            // this is the only case where we advance curr
            curr = next;
        } else { // Third case: next is smaller => construct a maximal subtree starting with next
            int r = linkNodes(next, node(curr).level);
            node(curr).child[node(curr).numChilds - 1] = r;
            node(curr).next = node(r).next;
        };
    };
    // adjust the point info of the curr
    adjustPointInfo(curr);
 
    // we are done with this subtree, return the root
    return curr;
};
 
template<typename IntType, int Dim>
void DTree<IntType, Dim>::linkNodes() {
    m_rootIndex = linkNodes(m_numPoints, m_maxLevel);
};
 
template<typename IntType, int Dim>
int DTree<IntType, Dim>::countPoints(int curr) const {
    if (m_nodes[curr].numChilds) {
        int sum = 0;
        for (int i = 0; i < m_nodes[curr].numChilds; i++) {
            sum += countPoints(m_nodes[curr].child[i]);
        };
 
        return sum;
    } else {
        return m_nodes[curr].numPoints;
    }
};
 
template<typename IntType, int Dim>
void DTree<IntType, Dim>::build() {
    // prepare the array with the morton numbers
    prepareMortonOrder();
 
    // sort the morton numbers
    sortMortonNumbers();
 
    // prepare the node layer
    prepareNodeLayer();
 
    linkNodes();
};
 
}
}
}