PCNode.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/basic.h>
#include <ogdf/basic/memory.h>
#include <ogdf/basic/pctree/PCEnum.h>
#include <ogdf/basic/pctree/PCTreeForest.h>
#include <ogdf/basic/pctree/util/IntrusiveList.h>
 
#include <array>
#include <cstddef>
#include <iosfwd>
#include <new>
#include <utility>
#include <vector>
 
namespace ogdf::pc_tree {
class PCTree;
struct OGDF_EXPORT PCNodeChildrenIterable;
struct OGDF_EXPORT PCNodeNeighborsIterable;
 
class OGDF_EXPORT PCNode : public IntrusiveList<PCNode>::node {
    friend OGDF_EXPORT std::ostream&(operator<<)(std::ostream&, const ogdf::pc_tree::PCTree*);
    friend OGDF_EXPORT std::ostream&(operator<<)(std::ostream&, const ogdf::pc_tree::PCNode*);
 
    friend class PCTree;
    friend class PCTreeForest;
    friend struct PCNodeChildrenIterable;
    friend struct PCNodeNeighborsIterable;
 
public:
    struct TempInfo {
        PCNode *predPartial = nullptr, *nextPartial = nullptr;
        PCNode* tpPred = nullptr;
        PCNode* tpPartialPred = nullptr;
        size_t tpPartialHeight = 0;
        PCNode* tpSucc = nullptr;
        std::vector<PCNode*> fullNeighbors;
        PCNode *ebEnd1 = nullptr, *fbEnd1 = nullptr, *fbEnd2 = nullptr, *ebEnd2 = nullptr;
 
        void replaceNeighbor(PCNode* oldNeigh, PCNode* newNeigh) {
            if (tpPred == oldNeigh) {
                tpPred = newNeigh;
            }
            if (tpPartialPred == oldNeigh) {
                tpPartialPred = newNeigh;
            }
            if (tpSucc == oldNeigh) {
                tpSucc = newNeigh;
            }
            if (ebEnd1 == oldNeigh) {
                ebEnd1 = newNeigh;
            }
            if (ebEnd2 == oldNeigh) {
                ebEnd2 = newNeigh;
            }
            if (fbEnd1 == oldNeigh) {
                fbEnd1 = newNeigh;
            }
            if (fbEnd2 == oldNeigh) {
                fbEnd2 = newNeigh;
            }
        }
 
        void clear() {
            nextPartial = predPartial = nullptr;
            tpPred = tpPartialPred = tpSucc = nullptr;
            ebEnd1 = fbEnd1 = fbEnd2 = ebEnd2 = nullptr;
            tpPartialHeight = 0;
            fullNeighbors.clear();
        }
    };
 
    using LeafUserData = std::array<void*, sizeof(TempInfo) / sizeof(void*)>;
 
private:
    // index in registry
    size_t m_id;
 
    // global
    PCTreeForest* m_forest;
 
    // private
    UnionFindIndex m_nodeListIndex = UNIONFINDINDEX_EMPTY;
    PCNodeType m_nodeType;
    PCNode* m_parentPNode = nullptr;
    mutable UnionFindIndex m_parentCNodeId = UNIONFINDINDEX_EMPTY;
    PCNode* m_sibling1 = nullptr;
    PCNode* m_sibling2 = nullptr;
    PCNode* m_child1 = nullptr;
    PCNode* m_child2 = nullptr;
    size_t m_childCount = 0;
    mutable NodeLabel m_label = NodeLabel::Unknown;
    mutable size_t m_timestamp = 0;
 
    // leaves need no temp info, so they can easily store user data
    union {
        mutable TempInfo m_temp;
        LeafUserData m_userData;
    };
 
    PCNode(PCTreeForest* forest, size_t id, PCNodeType nodeType)
        : IntrusiveList<PCNode>::node(), m_id(id), m_forest(forest), m_nodeType(nodeType) {
        if (nodeType == PCNodeType::Leaf) {
            new (&m_userData) LeafUserData;
        } else {
            new (&m_temp) TempInfo;
        }
    }
 
    ~PCNode() {
        if (m_nodeType == PCNodeType::Leaf) {
            m_userData.~array();
        } else {
            m_temp.~TempInfo();
        }
    }
 
public:
 
    void appendChild(PCNode* child, bool begin = false);
 
    void insertBetween(PCNode* sib1, PCNode* sib2);
 
    void detach();
 
    void replaceWith(PCNode* repl);
 
    void mergeIntoParent();
 
    void flip() { std::swap(m_child1, m_child2); }
 
private:
    void replaceSibling(PCNode* oldS, PCNode* newS);
 
    void rotateChildOutside(bool child1 = true);
 
    void replaceOuterChild(PCNode* oldC, PCNode* newC);
 
    void setParent(PCNode* parent);
 
    void forceDetach();
 
    void changeType(PCNodeType newType) {
        if (m_nodeType == PCNodeType::Leaf && newType != PCNodeType::Leaf) {
            m_userData.~array();
            new (&m_temp) TempInfo;
        } else if (m_nodeType != PCNodeType::Leaf && newType == PCNodeType::Leaf) {
            m_temp.~TempInfo();
            new (&m_userData) LeafUserData;
        }
        m_nodeType = newType;
    }
 
 
public:
 
    PCNode* getNextSibling(const PCNode* pred) const;
 
    PCNode* getOtherOuterChild(const PCNode* child) const;
 
    PCNode* getNextNeighbor(const PCNode* pred, const PCNode* curr) const;
 
    void proceedToNextNeighbor(PCNode*& pred, PCNode*& curr) const;
 
    PCNode* getParent() const;
 
    PCNodeChildrenIterable children();
 
    PCNodeNeighborsIterable neighbors(PCNode* first = nullptr);
 
 
public:
 
    bool isDetached() const {
        if (m_parentCNodeId == UNIONFINDINDEX_EMPTY && m_parentPNode == nullptr) {
            return true;
        } else {
            OGDF_ASSERT(m_parentCNodeId == UNIONFINDINDEX_EMPTY || m_parentPNode == nullptr);
            return false;
        }
    }
 
    bool isValidNode(const PCTreeForest* ofForest = nullptr) const;
 
    bool isLeaf() const { return m_nodeType == PCNodeType::Leaf; }
 
    bool isParentOf(const PCNode* other) const {
        OGDF_ASSERT(other != nullptr);
        OGDF_ASSERT(m_forest == other->m_forest);
        return other->getParent() == this;
    }
 
    bool isSiblingOf(const PCNode* other) const {
        OGDF_ASSERT(other != nullptr);
        OGDF_ASSERT(m_forest == other->m_forest);
        return this->getParent() == other->getParent();
    }
 
    bool isSiblingAdjacent(const PCNode* sibling) const {
        OGDF_ASSERT(isSiblingOf(sibling));
        OGDF_ASSERT(this != sibling);
        return m_sibling1 == sibling || m_sibling2 == sibling;
    }
 
    bool areNeighborsAdjacent(const PCNode* neigh1, const PCNode* neigh2) const;
 
    bool isChildOuter(const PCNode* child) const {
        OGDF_ASSERT(isParentOf(child));
        return m_child1 == child || m_child2 == child;
    }
 
    bool isOuterChild() const { return m_sibling1 == nullptr || m_sibling2 == nullptr; }
 
 
public:
 
    const TempInfo& constTempInfo() const {
        checkTimestamp();
        OGDF_ASSERT(!isLeaf());
        return m_temp;
    }
 
    bool isFull() const { return getLabel() == NodeLabel::Full; }
 
    NodeLabel getLabel() const {
        // this operation does not reset the temp info
        return m_forest->m_timestamp == m_timestamp ? m_label : NodeLabel::Empty;
    }
 
    void setLabel(NodeLabel l) {
        checkTimestamp();
        m_label = l;
    }
 
private:
    // these methods are slightly faster if we already called checkTimestamp()
    inline NodeLabel getLabelUnchecked() const {
        OGDF_ASSERT(m_forest->m_timestamp == m_timestamp);
        return m_label;
    }
 
    inline void setLabelUnchecked(NodeLabel l) {
        OGDF_ASSERT(m_forest->m_timestamp == m_timestamp);
        m_label = l;
    }
 
public:
    LeafUserData& leafUserData() {
        OGDF_ASSERT(isLeaf());
        return m_userData;
    }
 
    const LeafUserData& leafUserData() const {
        OGDF_ASSERT(isLeaf());
        return m_userData;
    }
 
private:
    void checkTimestamp() const;
 
    TempInfo& tempInfo() {
        checkTimestamp();
        OGDF_ASSERT(!isLeaf());
        return m_temp;
    }
 
    size_t addFullNeighbor(PCNode* fullNeigh) {
        checkTimestamp();
        OGDF_ASSERT(!isLeaf());
        OGDF_ASSERT(fullNeigh->isFull());
        m_temp.fullNeighbors.push_back(fullNeigh);
        return m_temp.fullNeighbors.size();
    }
 
    PCNode*& getFullNeighInsertionPoint(PCNode* nonFullNeigh) {
        checkTimestamp();
        OGDF_ASSERT(!isLeaf());
        OGDF_ASSERT(nonFullNeigh != nullptr);
        if (nonFullNeigh == m_temp.ebEnd1) {
            OGDF_ASSERT(areNeighborsAdjacent(m_temp.ebEnd1, m_temp.fbEnd1));
            return m_temp.fbEnd1;
        } else {
            OGDF_ASSERT(nonFullNeigh == m_temp.ebEnd2);
            OGDF_ASSERT(areNeighborsAdjacent(m_temp.ebEnd2, m_temp.fbEnd2));
            return m_temp.fbEnd2;
        }
    }
 
 
public:
    size_t index() const { return m_id; }
 
    PCNodeType getNodeType() const { return m_nodeType; }
 
    size_t getChildCount() const { return m_childCount; }
 
    size_t getDegree() const { return isDetached() ? m_childCount : m_childCount + 1; }
 
    PCNode* getChild1() const { return m_child1; }
 
    PCNode* getChild2() const { return m_child2; }
 
    PCNode* getOnlyChild() const {
        OGDF_ASSERT(m_childCount == 1);
        return m_child1;
    }
 
    PCNode* getSibling1() const { return m_sibling1; }
 
    PCNode* getSibling2() const { return m_sibling2; }
 
    PCTreeForest* getForest() const { return m_forest; }
 
 
    OGDF_NEW_DELETE
};
 
OGDF_EXPORT void proceedToNextSibling(PCNode*& pred, PCNode*& curr);
}