PQNode.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/List.h>
#include <ogdf/basic/pqtree/PQNodeRoot.h>
 
namespace ogdf {
 
template<class T, class X, class Y>
class PQTree;
template<class T, class X, class Y>
class PQLeafKey;
template<class T, class X, class Y>
class PQNodeKey;
template<class T, class X, class Y>
class PQInternalKey;
 
template<class T, class X, class Y>
class PQNode : public PQNodeRoot {
    friend class PQTree<T, X, Y>;
 
public:
    PQNode(int count, PQNodeKey<T, X, Y>* infoPtr);
 
 
    explicit PQNode(int count);
 
    virtual ~PQNode() {
        delete fullChildren;
        delete partialChildren;
    }
 
    bool changeEndmost(PQNode<T, X, Y>* oldEnd, PQNode<T, X, Y>* newEnd);
 
    bool changeSiblings(PQNode<T, X, Y>* oldSib, PQNode<T, X, Y>* newSib);
 
    bool endmostChild() const { return m_sibLeft == nullptr || m_sibRight == nullptr; }
 
    PQNode<T, X, Y>* getEndmost(PQNode<T, X, Y>* other) const {
        if (m_leftEndmost != other) {
            return m_leftEndmost;
        } else if (m_rightEndmost != other) {
            return m_rightEndmost;
        }
 
        return nullptr;
    }
 
    PQNode<T, X, Y>* getEndmost(SibDirection side) const {
        if (side == SibDirection::Left || side == SibDirection::NoDir) {
            return m_leftEndmost;
        } else if (side == SibDirection::Right) {
            return m_rightEndmost;
        }
 
        return nullptr;
    }
 
    PQNodeKey<T, X, Y>* getNodeInfo() const { return m_pointerToInfo; }
 
    PQNode<T, X, Y>* getSib(SibDirection side) const {
        if (side == SibDirection::Left) {
            return m_sibLeft;
        } else if (side == SibDirection::Right) {
            return m_sibRight;
        }
 
        return nullptr;
    }
 
    PQNode<T, X, Y>* getNextSib(PQNode<T, X, Y>* other) const {
        if (m_sibLeft != other) {
            return m_sibLeft;
        } else if (m_sibRight != other) {
            return m_sibRight;
        }
 
        return nullptr;
    }
 
    int identificationNumber() const { return m_identificationNumber; }
 
    int childCount() const { return m_childCount; }
 
    void childCount(int count) { m_childCount = count; }
 
    PQNode<T, X, Y>* parent() const { return m_parent; }
 
    PQNode<T, X, Y>* parent(PQNode<T, X, Y>* newParent) { return m_parent = newParent; }
 
    PQNodeType parentType() const { return m_parentType; }
 
    void parentType(PQNodeType newParentType) { m_parentType = newParentType; }
 
    int pertChildCount() const { return m_pertChildCount; }
 
    void pertChildCount(int count) { m_pertChildCount = count; }
 
    SibDirection putSibling(PQNode<T, X, Y>* newSib) {
        if (m_sibLeft == nullptr) {
            m_sibLeft = newSib;
            return SibDirection::Left;
        }
 
        OGDF_ASSERT(m_sibRight == nullptr);
        m_sibRight = newSib;
        return SibDirection::Right;
    }
 
    SibDirection putSibling(PQNode<T, X, Y>* newSib, SibDirection preference) {
        if (preference == SibDirection::Left) {
            return putSibling(newSib);
        }
 
        OGDF_ASSERT(preference == SibDirection::Right);
 
        if (m_sibRight == nullptr) {
            m_sibRight = newSib;
            return SibDirection::Right;
        }
 
        OGDF_ASSERT(m_sibLeft == nullptr);
        m_sibLeft = newSib;
        return SibDirection::Left;
    }
 
    PQNode<T, X, Y>* referenceChild() const { return m_referenceChild; }
 
    PQNode<T, X, Y>* referenceParent() const { return m_referenceParent; }
 
    bool setNodeInfo(PQNodeKey<T, X, Y>* pointerToInfo) {
        m_pointerToInfo = pointerToInfo;
        if (pointerToInfo != nullptr) {
            m_pointerToInfo->setNodePointer(this);
            return true;
        }
 
        return false;
    }
 
    virtual PQLeafKey<T, X, Y>* getKey() const = 0;
 
 
    virtual bool setKey(PQLeafKey<T, X, Y>* pointerToKey) = 0;
 
    virtual PQInternalKey<T, X, Y>* getInternal() const = 0;
 
    /*
     * setInternal() sets a specified pointer variable in a derived class
     * to the specified adress of \p pointerToInternal that is of type
     * PQInternalKey.
     *
     * If a derived class, such as PQLeaf,
     * is not supposed to store informations of type PQInternalKey,
     * setInternal() ignores the informations as long as
     * \p pointerToInternal = 0. The return value then is 1.
     * In case that \p pointerToInternal != 0, the return value is 0.
     *
     * If a derived class, such as PQInternalNode is
     * supposed to store informations of type PQInternalKey,
     * \p pointerToInternal has to be instantiated by the client. The
     * function setInternal() does
     * not instantiate the corresponding variable in the derived class.
     * The return value is always 1 unless \p pointerInternal was
     * equal to 0.
     */
    virtual bool setInternal(PQInternalKey<T, X, Y>* pointerToInternal) = 0;
 
    virtual PQNodeMark mark() const = 0;
 
    virtual void mark(PQNodeMark) = 0;
 
 
    virtual PQNodeStatus status() const = 0;
 
    virtual void status(PQNodeStatus) = 0;
 
 
    virtual PQNodeType type() const = 0;
 
    virtual void type(PQNodeType) = 0;
 
 
protected:
    // Stores the number of children of the node.
    int m_childCount;
 
    int m_debugTreeNumber;
 
    int m_identificationNumber;
 
    PQNodeType m_parentType;
 
    int m_pertChildCount;
 
    int m_pertLeafCount;
 
    PQNode<T, X, Y>* m_firstFull;
 
    PQNode<T, X, Y>* m_leftEndmost;
 
    PQNode<T, X, Y>* m_parent;
 
    PQNode<T, X, Y>* m_referenceChild;
 
    PQNode<T, X, Y>* m_referenceParent;
 
    PQNode<T, X, Y>* m_rightEndmost;
 
    PQNode<T, X, Y>* m_sibLeft;
 
    PQNode<T, X, Y>* m_sibRight;
 
    PQNodeKey<T, X, Y>* m_pointerToInfo;
 
 
    List<PQNode<T, X, Y>*>* fullChildren;
 
    List<PQNode<T, X, Y>*>* partialChildren;
};
 
/*
The function [[changeEndmost]] replaces the old endmost child [[oldEnd]] of
the node by a new child [[newEnd]].
If the node is a $Q$-node, then it must have two valid
pointers to its endmost children. If one of the endmost children is [[oldEnd]],
it is replaced by [[newEnd]].
The function [[changeEndmost]] returns [[1]] if it succeeded in
replacing [[oldEnd]] by [[newEnd]]. Otherwise the function returns
[[0]], leaving with an error message.
*/
template<class T, class X, class Y>
bool PQNode<T, X, Y>::changeEndmost(PQNode<T, X, Y>* oldEnd, PQNode<T, X, Y>* newEnd) {
    if (m_leftEndmost == oldEnd) {
        m_leftEndmost = newEnd;
        return true;
    } else if (m_rightEndmost == oldEnd) {
        m_rightEndmost = newEnd;
        return true;
    }
    return false;
}
 
/*
The function [[changeSiblings]] replaces the old sibling [[oldSib]] of the
node by a new sibling [[newSib]].
 
If the node has [[oldSib]] as sibling, then it changes the
sibling pointer that references to [[oldSib]] and places [[newSib]]
at its position.
 
The function [[changeSiblings]] returns [[1]] if it succeeded in replacing
[[oldSib]] by [[newSib]]. Otherwise the function returns
[[0]], leaving with an error message.
*/
template<class T, class X, class Y>
bool PQNode<T, X, Y>::changeSiblings(PQNode<T, X, Y>* oldSib, PQNode<T, X, Y>* newSib) {
    if (m_sibLeft == oldSib) {
        m_sibLeft = newSib;
        return true;
    } else if (m_sibRight == oldSib) {
        m_sibRight = newSib;
        return true;
    }
    return false;
}
 
/*
The (first) constructor combines the node with its information and
will automatically set the [[m_nodePointer]] (see \ref{basicKey}) of
the element of type [[PQNodeKey]] (see \ref{PQNodeKey}).
*/
template<class T, class X, class Y>
PQNode<T, X, Y>::PQNode(int count, PQNodeKey<T, X, Y>* infoPtr) {
    m_identificationNumber = count;
    m_childCount = 0;
    m_pertChildCount = 0;
    m_pertLeafCount = 0;
    m_debugTreeNumber = 0;
    m_parentType = PQNodeType::Undefined;
 
    m_parent = nullptr;
    m_firstFull = nullptr;
    m_sibLeft = nullptr;
    m_sibRight = nullptr;
    m_referenceChild = nullptr;
    m_referenceParent = nullptr;
    m_leftEndmost = nullptr;
    m_rightEndmost = nullptr;
 
    fullChildren = new List<PQNode<T, X, Y>*>;
    partialChildren = new List<PQNode<T, X, Y>*>;
 
    m_pointerToInfo = infoPtr;
    infoPtr->setNodePointer(this);
}
 
/*
The (second) constructor is called,
if no information is available or neccessary.
*/
template<class T, class X, class Y>
PQNode<T, X, Y>::PQNode(int count) {
    m_identificationNumber = count;
    m_childCount = 0;
    m_pertChildCount = 0;
    m_pertLeafCount = 0;
    m_debugTreeNumber = 0;
    m_parentType = PQNodeType::Undefined;
 
    m_parent = nullptr;
    m_firstFull = nullptr;
    m_sibLeft = nullptr;
    m_sibRight = nullptr;
    m_referenceChild = nullptr;
    m_referenceParent = nullptr;
    m_leftEndmost = nullptr;
    m_rightEndmost = nullptr;
 
    fullChildren = new List<PQNode<T, X, Y>*>;
    partialChildren = new List<PQNode<T, X, Y>*>;
 
    m_pointerToInfo = nullptr;
}
 
}