PQNode.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif


#ifndef OGDF_PQ_NODE_H
#define OGDF_PQ_NODE_H


#include <ogdf/basic/List.h>
#include <ogdf/internal/planarity/PQNodeRoot.h>


namespace ogdf {


//Status Definitions
#define EMPTY          1
#define PARTIAL        2
#define FULL           3
#define PERTINENT      4
#define TO_BE_DELETED  5

//Mark Definitions for Bubble Phase
#define UNMARKED       0
#define QUEUED         1
#define BLOCKED        2
#define UNBLOCKED      3

enum SibDirection {
    NODIR, LEFT, RIGHT
};

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);

    
    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() {
        return (m_sibLeft == 0 || m_sibRight == 0);
    }
 
    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 0;
    }

    PQNode<T,X,Y>* getEndmost(int side) const {
        if (side == LEFT || side == 0)
            return m_leftEndmost;
        else if(side == RIGHT) 
            return m_rightEndmost;
        
        return 0;
    }

    PQNodeKey<T,X,Y>* getNodeInfo() const {return m_pointerToInfo;};

    PQNode<T,X,Y>* getSib(int side) const {
        if (side == LEFT)
            return m_sibLeft;
        else if (side == RIGHT) 
            return m_sibRight;
        
        return 0;
    };

    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 0;
    }


    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;
    }

    int parentType() const { return m_parentType; }

    void parentType(int 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 == 0) {
            m_sibLeft = newSib;
            return LEFT;
        }
        
        OGDF_ASSERT(m_sibRight == 0);
        m_sibRight = newSib;
        return RIGHT;
    }

    SibDirection putSibling(PQNode<T,X,Y>* newSib,
                    int preference)
    {
        if (preference == LEFT)
            return putSibling(newSib);

        OGDF_ASSERT(preference == RIGHT);
        
        if (m_sibRight == 0)
        {
            m_sibRight = newSib;
            return RIGHT;
        }

        OGDF_ASSERT(m_sibLeft == 0);
        m_sibLeft = newSib;
        return 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 != 0)
        {    
            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 \a 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
     * \a pointerToInternal = 0. The return value then is 1.
     * In case that \a pointerToInternal != 0, the return value is 0.
     *
     * If a derived class, such as PQInternalNode is 
     * supposed to store informations of type PQInternalKey,
     * \a 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 \a pointerInternal was
     * equal to 0.
     */
    virtual bool setInternal(PQInternalKey<T,X,Y>* pointerToInternal) = 0;

    virtual int mark() const = 0;          
    
    virtual void mark(int) = 0;


    virtual int status() const = 0;        
    
    virtual void status(int) = 0;


    virtual PQNodeType type() const = 0;          

    virtual void type(PQNodeType) = 0;
      

protected:

   
    int m_childCount;
    
    int m_debugTreeNumber;
    
    int m_identificationNumber;

    int 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 = 0;

   m_parent = 0;
   m_firstFull = 0;
   m_sibLeft = 0;
   m_sibRight = 0;
   m_referenceChild = 0;
   m_referenceParent = 0;
   m_leftEndmost = 0;
   m_rightEndmost = 0;   

   fullChildren = OGDF_NEW List<PQNode<T,X,Y>*>;
   partialChildren = OGDF_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 = 0;

   m_parent = 0;
   m_firstFull = 0;
   m_sibLeft = 0;
   m_sibRight = 0;
   m_referenceChild = 0;
   m_referenceParent = 0;
   m_leftEndmost = 0;
   m_rightEndmost = 0;   

   fullChildren = OGDF_NEW List<PQNode<T,X,Y>*>;
   partialChildren = OGDF_NEW List<PQNode<T,X,Y>*>;

   m_pointerToInfo = 0;
}

}

#endif