PQTree.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_TREE_H
#define OGDF_PQ_TREE_H


#include <string.h>

#include <ogdf/basic/Stack.h>
#include <ogdf/basic/Queue.h>
#include <ogdf/basic/Array.h>

#include <ogdf/internal/planarity/PQNode.h>
#include <ogdf/internal/planarity/PQInternalNode.h>
#include <ogdf/internal/planarity/PQLeaf.h>
#include <ogdf/internal/planarity/PQLeafKey.h>
#include <ogdf/internal/planarity/PQInternalKey.h>
#include <ogdf/internal/planarity/PQNodeKey.h>
 

namespace ogdf {


template<class T,class X,class Y>

class PQTree
{
public:

    PQTree();

    virtual ~PQTree() { Cleanup(); }

    bool addNewLeavesToTree(
        PQInternalNode<T,X,Y>        *father,
        SListPure<PQLeafKey<T,X,Y>*> &leafKeys);

    void emptyNode(PQNode<T,X,Y>* nodePtr);

    virtual void front(
        PQNode<T,X,Y>* nodePtr,
        SListPure<PQLeafKey<T,X,Y>*> &leafKeys);

    virtual void CleanNode(PQNode<T,X,Y>* /* nodePtr */) { }

    virtual void Cleanup();

    virtual void clientDefinedEmptyNode(PQNode<T,X,Y>* nodePtr) {
        emptyNode(nodePtr);
    }

    virtual void emptyAllPertinentNodes();

    virtual int  Initialize(SListPure<PQLeafKey<T,X,Y>*> &leafKeys);

    virtual bool Reduction(SListPure<PQLeafKey<T,X,Y>*> &leafKeys);

    PQNode<T,X,Y>* root() const {
        return m_root;
    }

    void writeGML(const char *fileName);
    void writeGML(ostream &os);


protected:


    PQNode<T,X,Y>* m_root;                     

    PQNode<T,X,Y>* m_pertinentRoot;

    PQNode<T,X,Y>* m_pseudoRoot;   


    int m_identificationNumber;      

    int m_numberOfLeaves;

    List<PQNode<T,X,Y>*> *m_pertinentNodes; 
   

    virtual bool Bubble(SListPure<PQLeafKey<T,X,Y>*> &leafKeys);

    virtual bool Reduce(SListPure<PQLeafKey<T,X,Y>*> &leafKeys);

    virtual bool templateL1(PQNode<T,X,Y> *nodePtr,
                               bool isRoot);

    virtual bool templateP1(PQNode<T,X,Y> *nodePtr,
                               bool isRoot);

    virtual bool templateP2(PQNode<T,X,Y> **nodePtr);

    virtual bool templateP3(PQNode<T,X,Y> *nodePtr);

    virtual bool templateP4(PQNode<T,X,Y> **nodePtr);
      
    virtual bool templateP5(PQNode<T,X,Y> *nodePtr);

    virtual bool templateP6(PQNode<T,X,Y> **nodePtr);

    virtual bool templateQ1(PQNode<T,X,Y> *nodePtr, bool isRoot); 
      
    virtual bool templateQ2(PQNode<T,X,Y> *nodePtr, bool isRoot);

    virtual bool templateQ3(PQNode<T,X,Y> *nodePtr);
      

   
    virtual bool addNodeToNewParent(PQNode<T,X,Y>* parent,
                                        PQNode<T,X,Y>* child);

    virtual bool addNodeToNewParent(PQNode<T,X,Y>* parent,
                                        PQNode<T,X,Y>* child,
                                        PQNode<T,X,Y>* leftBrother,
                                        PQNode<T,X,Y>* rightBrother);

    virtual bool checkIfOnlyChild(PQNode<T,X,Y> *child,
                                      PQNode<T,X,Y> *parent);

    virtual void destroyNode(PQNode<T,X,Y> *nodePtr) {
        nodePtr->status(TO_BE_DELETED);
    }

    virtual void exchangeNodes(PQNode<T,X,Y> *oldNode,
                                 PQNode<T,X,Y> *newNode);

    virtual void linkChildrenOfQnode(PQNode<T,X,Y> *installed,
                                       PQNode<T,X,Y> *newChild);

    virtual void removeChildFromSiblings(PQNode<T,X,Y>* nodePtr);

    virtual int  removeNodeFromTree(PQNode<T,X,Y>* parent,
                                      PQNode<T,X,Y>* child);

   
    List<PQNode<T,X,Y>*>* fullChildren(PQNode<T,X,Y>* nodePtr) {
        return nodePtr->fullChildren;
    }


    List<PQNode<T,X,Y>*>*  partialChildren(PQNode<T,X,Y>* nodePtr) {
        return nodePtr->partialChildren;
    }

    virtual PQNode<T,X,Y>* clientLeftEndmost(PQNode<T,X,Y>* nodePtr) const {
        return nodePtr->m_leftEndmost;
    }

    virtual PQNode<T,X,Y>* clientRightEndmost(PQNode<T,X,Y>* nodePtr) const {
        return nodePtr->m_rightEndmost;
    }

    virtual PQNode<T,X,Y>* clientNextSib(PQNode<T,X,Y>* nodePtr,
                                         PQNode<T,X,Y>* other) const {
        return nodePtr->getNextSib(other);
    }

    virtual PQNode<T,X,Y>* clientSibLeft(PQNode<T,X,Y>* nodePtr) const {
        return nodePtr->m_sibLeft;
    }

    virtual PQNode<T,X,Y>* clientSibRight(PQNode<T,X,Y>* nodePtr) const {
        return nodePtr->m_sibRight;
    }

    virtual int clientPrintNodeCategorie(PQNode<T,X,Y>* nodePtr);

    virtual const char* clientPrintStatus(PQNode<T,X,Y>* nodePtr);

    virtual const char* clientPrintType(PQNode<T,X,Y>* nodePtr);

private:
      
    bool checkChain(
        PQNode<T,X,Y> *nodePtr,
        PQNode<T,X,Y> *firstFull,
        PQNode<T,X,Y> **seqStart,
        PQNode<T,X,Y> **seqEnd);

    void copyFullChildrenToPartial(
        PQNode<T,X,Y> *nodePtr,
        PQNode<T,X,Y> *partialChild);

    PQNode<T,X,Y>* createNodeAndCopyFullChildren(List<PQNode<T,X,Y>*> *fullNodes);

    void printNode(
        char *filename,
        int number,
        PQNode<T,X,Y>* father,
        PQNode<T,X,Y>* son);  

    void removeBlock(PQNode<T,X,Y> *nodePtr, bool isRoot);

    void sortExceptions(int Exceptions[], int arraySize);
};



/************************************************************************
                      addNewLeavesToTree
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::addNewLeavesToTree(
    PQInternalNode<T,X,Y> *father,
    SListPure<PQLeafKey<T,X,Y>*> &leafKeys)
{
    if (!leafKeys.empty())
    {
        OGDF_ASSERT(!father->m_childCount) 
        // Father has children. Brothers expected

        
        SListIterator<PQLeafKey<T,X,Y>*> it = leafKeys.begin();
        PQLeafKey<T,X,Y>* newKey = *it; //leafKeys[0];

        PQNode<T,X,Y>* aktualSon = OGDF_NEW PQLeaf<T,X,Y>(m_identificationNumber++,EMPTY,newKey);
        PQNode<T,X,Y>* firstSon = aktualSon;
        firstSon->m_parent = father;
        firstSon->m_parentType = father->type();
        father->m_childCount++;
        PQNode<T,X,Y>* oldSon = firstSon;

        for (++it; it.valid(); ++it)
        {
            newKey = *it; //leafKeys[i];
            aktualSon = OGDF_NEW PQLeaf<T,X,Y>(m_identificationNumber++,
                                         EMPTY,newKey);
            aktualSon->m_parent = father;
            aktualSon->m_parentType = father->type();
            father->m_childCount++;
            oldSon->m_sibRight = aktualSon;
            aktualSon->m_sibLeft = oldSon;
            oldSon = aktualSon;
        }
        if (father->type() == PQNodeRoot::PNode)
        {
            firstSon->m_sibLeft = oldSon;
            oldSon->m_sibRight = firstSon;
            father->m_referenceChild = firstSon;
            firstSon->m_referenceParent = father;
        }
        else if (father->type() == PQNodeRoot::QNode)
        {
            father->m_leftEndmost = firstSon;
            father->m_rightEndmost = oldSon;
        }
        return true; 
    }
     
    return false;
}



/************************************************************************
                      addNodeToNewParent
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::addNodeToNewParent(
    PQNode<T,X,Y>* parent,
    PQNode<T,X,Y>* child)
{
    OGDF_ASSERT(parent->type() == PQNodeRoot::PNode && parent->type() == PQNodeRoot::QNode)
        //parent type not valid.

    if (child != 0)
    {
        OGDF_ASSERT(parent->m_childCount == 0)   
            //when adding new nodes: Brothers expected.
        child->m_parent = parent;
        child->m_parentType = parent->type();
        parent->m_childCount++;

        /*
        Set the reference pointers in case that [[parent]] is a $P$-node.
        If [[parent]] is a $Q$-node, this chunk sets the endmost children 
        of [[parent]]. Since [[child]] is the only child of [[parent]] 
        both endmost pointers are set to [[child]].
        */
        if (parent->type() == PQNodeRoot::PNode)
        {
            child->m_sibLeft = child;
            child->m_sibRight = child;
            parent->m_referenceChild = child;
            child->m_referenceParent = parent;
        }
        else if (parent->type() == PQNodeRoot::QNode)
        {
            parent->m_leftEndmost = child;
            parent->m_rightEndmost = child;
        }
        
        return true;
    }

    return false;
}


/************************************************************************
                      addNodeToNewParent
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::addNodeToNewParent(
    PQNode<T,X,Y>* parent,
    PQNode<T,X,Y>* child,
    PQNode<T,X,Y>* leftBrother,
    PQNode<T,X,Y>* rightBrother)
{
   
    if (parent != 0)
    {
        OGDF_ASSERT(parent->type() == PQNodeRoot::PNode || parent->type() == PQNodeRoot::QNode)
            //parent type not valid
        if ((leftBrother == 0) && (rightBrother == 0))
            return addNodeToNewParent(parent,child);
        else if (child != 0)
        {
            child->m_parent = parent;
            child->m_parentType = parent->type();
            parent->m_childCount++;

            if (parent->type() == PQNodeRoot::PNode)
            {
                /*
                The parent is a $P$-node with children.
                Either [[leftBrother]] or [[rightBrother]] stores 
                a pointer to an existing child of [[parent]] and [[parent]] 
                is a $P$-node. In case that two brothers are stored, an 
                arbitrary one is choosen to be the next sibling of [[child]].
                This brother is stored in [[brother]]. The pointer [[sister]]
                denotes a pointer to an arbitrary sibling of [[brother]].
                */
                PQNode<T,X,Y>* brother = (leftBrother != 0) ? leftBrother : rightBrother;
                PQNode<T,X,Y>* sister = brother->m_sibRight;
                child->m_sibLeft = brother;
                child->m_sibRight = sister;
                brother->m_sibRight = child;
                sister->m_sibLeft = child;
                return true;
            }
      
            else if (leftBrother == 0)
            {
                /*
                The parent is a $Q$-node with children.
                The [[leftBrother]] is a [[0]]-pointer while the 
                [[rightBrother]] denotes an existing child of [[parent]].
                The node [[rightBrother]] {\bf must be} one of the two endmost 
                children of [[parent]]. If this is not the case, the chunk 
                detects this, halts the procedure [[addNewLeavesToTree]] 
                printing an error message and returning [[0]].
                If [[rightBrother]] is endmost child of [[parent]], then 
                this chunk adds [[child]] at the one end where
                [[rightBrother]] hides. The node [[child]] is then made the
                new endmost child of [[parent]] on the corresponding side.
                */
                if (rightBrother == parent->m_leftEndmost)
                {
                    parent->m_leftEndmost = child;
                    child->m_sibRight = rightBrother;
                    rightBrother->putSibling(child,LEFT);
                    return true;
                }

                // missing second brother?
                OGDF_ASSERT(rightBrother == parent->m_rightEndmost);
                parent->m_rightEndmost = child;
                child->m_sibLeft = rightBrother;
                rightBrother->putSibling(child,LEFT);
                return true;
            }

            else if (rightBrother == 0)
            {
                /*
                The parent is a $Q$-node with children. 
                The [[rightBrother]] is a [[0]]-pointer while the 
                [[leftBrother]] denotes an existing child of [[parent]]. The 
                node [[leftBrother]] {\bf must be} one of the two endmost 
                children of [[parent]]. If this is not the case, the chunk 
                detects this, halts the procedure [[addNodeToNewParent]] 
                printing an error message and returning [[0]].
                If [[leftBrother]] is endmost child of [[parent]], then this 
                chunk adds [[child]] at the one end where [[leftBrother]] 
                hides. The node [[child]] is then made new endmost child of 
                [[parent]] on the corresponding side.
                */
                if (leftBrother == parent->m_rightEndmost)
                {
                    parent->m_rightEndmost = child;
                    child->m_sibLeft = leftBrother;
                    leftBrother->putSibling(child,RIGHT);
                    return true;
                }

                // missing second brother?
                OGDF_ASSERT(leftBrother == parent->m_leftEndmost);
                parent->m_leftEndmost = child;
                child->m_sibRight = leftBrother;
                leftBrother->putSibling(child,RIGHT);
                return true;
            }

            else
            {
                /*
                The parent is a $Q$-node with children. 
                Both the [[rightBrother]] and the [[leftBrother]] denote 
                existing children of [[parent]]. In this case, [[leftBrother]] 
                and [[rightBrother]] must be immideate siblings. If this is 
                not the case, this will be detected during the function call
                [[changeSiblings]] of the class [[PQNode.h]] (see 
                \ref{PQNode.changeSiblings}) in the first two lines of this 
                chunk. If the chunk recognizes the failure of 
                [[changeSiblings]] it halts the procedure 
                [[addNewLeavesToTree]], printing an error message and 
                returning [[0]].
                If the two brothers are immediate siblings, this chunk 
                adds [[child]] between the two brothers as interior child of 
                the $Q$-node [[parent]].
                */
#ifdef OGDF_DEBUG
                bool ok =
#endif
                    rightBrother->changeSiblings(leftBrother,child) && leftBrother->changeSiblings(rightBrother,child);

                // brothers are not siblings?
                OGDF_ASSERT(ok);
                
                if (leftBrother->m_sibRight == child)
                {
                    child->m_sibLeft = leftBrother;
                    child->m_sibRight = rightBrother;
                }
                else 
                {
                    child->m_sibLeft = rightBrother;
                    child->m_sibRight = leftBrother;
                }
                return true;
            }
        }
        else
            return false;
    }
    else if (leftBrother != 0 && rightBrother != 0)
    {
        /*
        The parent is a $Q$-node with children. 
        Both the [[rightBrother]] and the [[leftBrother]] denote 
        existing children of [[parent]]. In this case, [[leftBrother]] 
        and [[rightBrother]] must be immideate siblings. If this is 
        not the case, this will be detected during the function call
        [[changeSiblings]] of the class [[PQNode.h]] (see 
        \ref{PQNode.changeSiblings}) in the first two lines of this 
        chunk. If the chunk recognizes the failure of 
        [[changeSiblings]] it halts the procedure 
        [[addNewLeavesToTree]], printing an error message and 
        returning [[0]].
        If the two brothers are immediate siblings, this chunk 
        adds [[child]] between the two brothers as interior child of 
        the $Q$-node [[parent]].
        */
#ifdef OGDF_DEBUG
        bool ok =
#endif
            rightBrother->changeSiblings(leftBrother,child) && leftBrother->changeSiblings(rightBrother,child);

        // brothers are not siblings?
        OGDF_ASSERT(ok);

        if (leftBrother->m_sibRight == child)
        {
            child->m_sibLeft = leftBrother;
            child->m_sibRight = rightBrother;
        }
        else 
        {
            child->m_sibLeft = rightBrother;
            child->m_sibRight = leftBrother;
        }
        return true;
    }       
    
    return true;
}



/************************************************************************
                           Bubble
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::Bubble(SListPure<PQLeafKey<T,X,Y>*> &leafKeys)
{
    Queue<PQNode<T,X,Y>*> processNodes;

    /*
    Enter the [[Full]] leaves into the queue [[processNodes]].
    In a first step the pertinent leaves have to be identified in the tree
    and entered on to the queue [[processNodes]]. The identification of
    the leaves can be done with the help of a pointer stored in every 
    [[PQLeafKey]] (see \ref{PQLeafKey}) in constant time for every element. 
    */
    SListIterator<PQLeafKey<T,X,Y>*> it;
    for (it  = leafKeys.begin(); it.valid(); ++it) 
    {
        PQNode<T,X,Y>* checkLeaf = (*it)->nodePointer(); //leafKeys[i]->nodePointer();
        checkLeaf->mark(QUEUED);
        processNodes.append(checkLeaf);
        m_pertinentNodes->pushFront(checkLeaf);
    }

    int blockCount       = 0;
    int numBlocked       = 0;
    int offTheTop        = 0;
    int blockedSiblings  = 0;
    PQNode<T,X,Y>* checkSib = 0;
    Stack<PQNode<T,X,Y>*> blockedNodes;

    while ((processNodes.size() + blockCount + offTheTop) > 1)
    {
        if (processNodes.size() == 0)
            /* 
            No consecutive sequence possible.
            The queue [[processNodes]] does not contain any nodes for
            processing and the sum of [[blockCount]] and [[offTheTop]] is
            greater than 1. If the queue is empty, the root of the pertinent 
            subtree was already processed. Nevertheless, there are blocked 
            nodes since [[offTheTop]] is either be [[0]] or [[1]], hence 
            [[blockCount]] must be at least [[1]]. Such blocked nodes cannot 
            form a consecutive sequence with all nodes in the set 
            [[leafKeys]]. Observe that this chunk finishes the function 
            [[Bubble]]. Hence every memory allocated by the function [[Bubble]] 
            has to be deleted here as well.        
            */
            return false;
        /*
        If there are still nodes to be processed in which case the queue
        [[processNodes]] is not empty, we get the next node from the queue.
        By default this node has to be marked as blocked.
        */
        PQNode<T,X,Y>* checkNode = processNodes.pop();
        blockedNodes.push(checkNode);
        checkNode->mark(BLOCKED);
        blockedSiblings = 0;

        /*
        Check if node is adjacent to an unblocked node.
        After getting the node [[checkNode]] from the queue, its siblings are 
        checked, whether they are unblocked. If they are, then they have a 
        valid pointer to their parent and the parent pointer of [[checkNode]] 
        is updated.
        */
        if ((checkNode->m_parentType != PQNodeRoot::PNode) && (checkNode != m_root))
                                            // checkNode is son of a QNode.
                                            // Check if it is blocked.
        {
            if (clientSibLeft(checkNode) == 0)
                                            // checkNode is endmost child of
                                            // a QNode. It has a valid pointer
                                            // to its parent.
            {
                checkNode->mark(UNBLOCKED);
                if (clientSibRight(checkNode) && 
                    clientSibRight(checkNode)->mark() == BLOCKED)
                    blockedSiblings++;
            }

            else if (clientSibRight(checkNode) == 0)
                                            // checkNode is endmost child of
                                            // a QNode. It has a valid pointer
                                            // to its parent.
            {
                checkNode->mark(UNBLOCKED);
                if (clientSibLeft(checkNode) && 
                    clientSibLeft(checkNode)->mark() == BLOCKED)
                    blockedSiblings++;
            }
             

            else
                                            // checkNode is not endmost child of
                                            // a QNode. It has not a valid 
                                            // pointer to its parent.
            {
                if (clientSibLeft(checkNode)->mark() == UNBLOCKED)
                                            // checkNode is adjacent to an
                                            // unblocked node. Take its parent.
                {
                    checkNode->mark(UNBLOCKED);
                    checkNode->m_parent = clientSibLeft(checkNode)->m_parent;
                }
                else if (clientSibLeft(checkNode)->mark() == BLOCKED)
                    blockedSiblings++;

                if (clientSibRight(checkNode)->mark() == UNBLOCKED)
                                            // checkNode is adjacent to an 
                                            // unblocked node. Take its parent.
                {
                    checkNode->mark(UNBLOCKED);
                    checkNode->m_parent = clientSibRight(checkNode)->m_parent;
                }
                else if (clientSibRight(checkNode)->mark() == BLOCKED)
                    blockedSiblings++;
            }
        }
         
        else                                // checkNode is son of a PNode
                                            // and children of P_NODEs
                                            // cannot be blocked.
            checkNode->mark(UNBLOCKED);

        if (checkNode->mark() == UNBLOCKED)
        {
            PQNode<T,X,Y>* parent = checkNode->m_parent;

            /*
            Get maximal consecutive set of blocked siblings.
            This chunk belongs to the procedure [[bubble]].
            The node [[checkNode]] is [[UNBLOCKED]].
            If the parent of [[checkNode]] is a $Q$-Node, then we check the
            siblings [[checkSib]] of [[checkNode]] whether they are 
            [[BLOCKED]]. If they are blocked,  they have to be marked 
            [[UNBLOCKED]] since they are adjacent to the [[UNBLOCKED]] node 
            [[checkNode]]. We then have to proceed with the siblings of 
            [[checkSib]] in order to find [[BLOCKED]] nodes
            adjacent to [[checkSib]]. This is repeated until no [[BLOCKED]]
            nodes are found any more.

            Observe that while running through the children of the $Q$-Node
            (referred by the pointer [[parent]]), their parent pointers, 
            as well as the [[pertChildCount]] of [[parent]] are updated. 
            Furthermore we reduce simultaneously the count [[numBlocked]].  
            */
            if (blockedSiblings > 0)
            {
                if (clientSibLeft(checkNode) != 0)
                {
                    checkSib = clientSibLeft(checkNode);
                    PQNode<T,X,Y>* oldSib = checkNode;
                    while (checkSib->mark() == BLOCKED)
                    {
                        checkSib->mark(UNBLOCKED);
                        checkSib->m_parent = parent;
                        numBlocked--;
                        parent->m_pertChildCount++;
                        PQNode<T,X,Y>* holdSib = clientNextSib(checkSib,oldSib);
                        oldSib = checkSib;
                        checkSib = holdSib;
                            //Blocked node as endmost child of a QNode.
                    }
                }

                if (clientSibRight(checkNode) != 0)
                {
                    checkSib = clientSibRight(checkNode);
                    PQNode<T,X,Y>* oldSib = checkNode;
                    while (checkSib->mark() == BLOCKED)
                    {
                        checkSib->mark(UNBLOCKED);
                        checkSib->m_parent = parent;
                        numBlocked--;
                        parent->m_pertChildCount++;
                        PQNode<T,X,Y>* holdSib = clientNextSib(checkSib,oldSib);
                        oldSib = checkSib;
                        checkSib = holdSib;
                            //Blocked node as endmost child of a QNode.
                    }
                }
            }// if (blockedSiblings > 0)


            /*
            Process parent of [[checkNode]]
            After processing the siblings of the [[UNBLOCKED]] [[checkNode]]
            the parent has to be processed. If [[checkNode]] is the root
            of the tree we do nothing except setting the flag [[offTheTop]].
            If it is not the root and [[parent]] has not been placed onto the
            queue [[processNodes]], the [[parent]] is placed on to 
            [[processNodes]].

            Observe that the number [[blockCount]] is updated. Since 
            [[checkNode]] was [[UNBLOCKED]] all perinent nodes adjacent 
            to that node became [[UNBLOCKED]] as well. Therefore the number 
            of blocks is reduced by the number of [[BLOCKED]] siblings of 
            [[checkNode]].
            */
            if (parent == 0)
                                           // checkNode is root of the tree.
                offTheTop = 1;
            else
                                           // checkNode is not the root.
            {
                parent->m_pertChildCount++;
                if (parent->mark() == UNMARKED)
                {
                    processNodes.append(parent);
                    m_pertinentNodes->pushFront(parent);
                    parent->mark(QUEUED);
                }
            }

            blockCount -= blockedSiblings;
            blockedSiblings = 0;

        }//if (checkNode->mark() == UNBLOCKED)

        else
        {
            /*
            Process blocked [[checkNode]]
            Since [[checkNode]] is [[BLOCKED]], we cannot continue 
            processing at this point in the Tree. We have to wait until 
            this node becomes unblocked. So only the variables 
            [[blockCount]] and [[numBlocked]] are updated. 
            */
            blockCount += 1 - blockedSiblings;
            numBlocked++;
        }

    }//while ((processNodes.size() + blockCount + offTheTop) > 1)

    if (blockCount == 1)
    {
        /*
        If [[blockCount]] $= 1$ enter [[m_pseudoRoot]] to the tree
        In case that the root of the pertinent subtree is a $Q$-node 
        with empty children on both sides and the pertinent children 
        in the middle, it is possible that the $PQ$-tree is reducible. 
        But since the sequence of pertinent children of the $Q$-node is 
        blocked, the procedure is not able to find the parent of its 
        pertinent children. This is due to the fact that the interior
        children of a $Q$-node do not have a valid parent pointer.

        So the root of the pertinent subtree is not known, hence cannot be 
        entered into the processing queue used in the function call [[Reduce]]
        (see \ref{Reduce}). To solve this problem a special node only designed 
        for this cases is used: [[m_pseudoRoot]]. It simulates the root of the 
        pertinent subtree. This works out well, since for this node the only 
        possible template maching is [[templateQ3]] (see \ref{templateQ3}), 
        where no pointers to the endmost children of a $Q$-node are used. 
        */
        while (!blockedNodes.empty())
        {
            PQNode<T,X,Y>* checkNode = blockedNodes.pop();
            if (checkNode->mark() == BLOCKED)
            {
                checkNode->mark(UNBLOCKED);
                checkNode->m_parent = m_pseudoRoot;
                m_pseudoRoot->m_pertChildCount++;              
                OGDF_ASSERT(!checkNode->endmostChild())
                    //Blocked node as endmost child of a QNode.
            }
        }
    }

    return true;
}


/************************************************************************
                          checkChain
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::checkChain(
    PQNode<T,X,Y> *nodePtr,
    PQNode<T,X,Y> *firstFull,
    PQNode<T,X,Y> **seqStart, 
    PQNode<T,X,Y> **seqEnd)
{
    bool notFull = false;
    int fullCount = nodePtr->fullChildren->size();
    fullCount--;                    // firstFull does have a FULL label.

    /*
    Start at the [[firstFull]] child sweeping through the full children on 
    the left side of [[firstfull]]. It stops as soon as a nonfull child is 
    detected. The last found full child is stored in [[seqEnd]].
    */
    PQNode<T,X,Y> *leftNext = clientSibLeft(firstFull);
    (*seqEnd) = firstFull;
    if (leftNext != 0)
    {
        if (leftNext->status() == FULL) {
            fullCount--;

            PQNode<T,X,Y> *leftOld = firstFull;
            PQNode<T,X,Y> *checkNode = leftNext;
    
            while (fullCount > 0 && !notFull)
                                       // There are still full children to be
                                       // counted, and no empty child has been
                                       // encountered on this side.
            {
                leftNext = clientNextSib(checkNode,leftOld);
                if (leftNext != 0 && leftNext->status() == FULL)
                    fullCount--;
                else
                    notFull = true;
                leftOld = checkNode;
                checkNode = leftNext;
            }

            if (checkNode != 0 && checkNode->status() == FULL)
                (*seqEnd)  = checkNode;

            else {
                //searching consecutive sequence in Q2 or Q3.
                OGDF_ASSERT(leftOld != 0 && leftOld->status() == FULL);
                (*seqEnd) = leftOld;
            }

        } else {
            (*seqEnd) = firstFull;
        }
    }

    /*
    Start at the [[firstFull]] child sweeping through the full children on 
    the right side of [[firstfull]]. It stops as soon as a nonfull child is 
    detected.
    */
    notFull = false;
    PQNode<T,X,Y> *rightNext = clientSibRight(firstFull);
    (*seqStart) = firstFull;
    if(rightNext != 0)
    {
        if (rightNext->status() == FULL) {
            fullCount--;

            PQNode<T,X,Y> *rightOld = firstFull;
            PQNode<T,X,Y> *checkNode = rightNext;

            while (fullCount > 0 && !notFull)
                                       // There are still full children to be
                                       // counted, and no empty child has been
                                       // encountered on this side.
            {
                rightNext = clientNextSib(checkNode,rightOld);
                if (rightNext != 0 && rightNext->status() == FULL)
                    fullCount--;
                else
                    notFull = true;
                rightOld = checkNode;
                checkNode = rightNext;
            }
            if (checkNode != 0 && checkNode->status() == FULL)
                (*seqStart) = checkNode;

            else {
                OGDF_ASSERT(rightOld != 0 && rightOld->status() == FULL);
                (*seqStart) = rightOld;
                     //searching consecutive seqeuence in Q2 or Q3.
            }

        } else {
            (*seqStart) = firstFull;
        }
    }



    if (firstFull == (*seqEnd))
    {
        PQNode<T,X,Y> *checkNode = (*seqEnd);
        (*seqEnd) = (*seqStart);
        (*seqStart) = checkNode;
    }
      
    if (fullCount == 0)
                                    // All full children occupy a consecutive
                                    // sequence.
        return true;
    else
        return false;
}


/************************************************************************
                          checkIfOnlyChild
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::checkIfOnlyChild(
    PQNode<T,X,Y> *child,
    PQNode<T,X,Y> *parent)

{
    if ((parent->type() == PQNodeRoot::PNode && parent->m_childCount == 1)
        || (parent->type() == PQNodeRoot::QNode && parent->m_leftEndmost == child
            && parent->m_rightEndmost == child))
    {
        removeChildFromSiblings(child);
        child->m_parent = parent->m_parent;
        if (parent->m_parent != 0)         // parent is not the root.
            exchangeNodes(parent,child);
        else
        {
            exchangeNodes(parent,child);
            m_root = child;
        }
        destroyNode(parent);
        return true;
    }
    else
        return false;
}


/************************************************************************
                         Cleanup
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::Cleanup()
{
    PQNode<T,X,Y>*  nextSon   = 0;
    PQNode<T,X,Y>*  lastSon   = 0;
    PQNode<T,X,Y>*  oldSib    = 0;
  
    Queue<PQNode<T,X,Y>*> helpqueue;

    if (m_root != 0)
    {
        emptyAllPertinentNodes();
        
        /*
        Process the [[m_root]] of the [[PQTree]]. Before deleting [[m_root]],
        pointers to all its children are stored in the queue [[helpqueue]].
        */
        if (m_root->type() == PQNodeRoot::PNode)
        {
            if (m_root->m_referenceChild != 0) 
            {
                PQNode<T,X,Y>* firstSon = m_root->m_referenceChild;
                helpqueue.append(firstSon);

                if (firstSon->m_sibRight != 0)
                    nextSon = firstSon->m_sibRight;
                while (nextSon != firstSon)
                {
                    helpqueue.append(nextSon);
                    nextSon = nextSon->m_sibRight;
                }
            }
        }
        else if (m_root->type() == PQNodeRoot::QNode)
        {  
            PQNode<T,X,Y>* firstSon = m_root->m_leftEndmost;
            helpqueue.append(firstSon);
            
            lastSon = m_root->m_rightEndmost;
            helpqueue.append(lastSon);

            nextSon = lastSon->getNextSib(oldSib);
            oldSib = lastSon;
            while (nextSon != firstSon)
            {
                helpqueue.append(nextSon);
                PQNode<T,X,Y>* holdSib = nextSon->getNextSib(oldSib);
                oldSib = nextSon;
                nextSon = holdSib;
            }
        }


        CleanNode(m_root);
        delete m_root;

        while (!helpqueue.empty())
        {
            PQNode<T,X,Y>* checkNode = helpqueue.pop();

            /*
            Process an arbitrary node [[checkNode]] of the [[PQTree]].
            Before deleting [[checkNode]],
            pointers to all its children are stored in the queue [[helpqueue]].
            */
            if (checkNode->type() == PQNodeRoot::PNode)
            {  
                if (checkNode->m_referenceChild != 0) 
                {
                    PQNode<T,X,Y>* firstSon = checkNode->m_referenceChild;
                    helpqueue.append(firstSon);

                    if (firstSon->m_sibRight != 0)
                        nextSon = firstSon->m_sibRight;
                    while (nextSon != firstSon)
                    {
                        helpqueue.append(nextSon);
                        nextSon = nextSon->m_sibRight;
                    }
                }
            }
            else if (checkNode->type() == PQNodeRoot::QNode)
            {
                oldSib = 0;

                PQNode<T,X,Y>*firstSon = checkNode->m_leftEndmost;
                helpqueue.append(firstSon);

                lastSon = checkNode->m_rightEndmost;
                helpqueue.append(lastSon);

                nextSon = lastSon->getNextSib(oldSib);
                oldSib = lastSon;
                while (nextSon != firstSon)
                {
                    helpqueue.append(nextSon);
                    PQNode<T,X,Y>* holdSib = nextSon->getNextSib(oldSib);
                    oldSib = nextSon;
                    nextSon = holdSib;
                }
            }

            CleanNode(checkNode);
            delete checkNode;
        }
    }

    CleanNode(m_pseudoRoot);
    delete m_pseudoRoot;

    delete m_pertinentNodes;

    m_root = 0;
    m_pertinentRoot = 0;
    m_pseudoRoot = 0;
    m_pertinentNodes = 0;

    m_numberOfLeaves = 0;
    m_identificationNumber = 0;
}


/************************************************************************
                        clientPrintNodeCategorie
************************************************************************/ 

template<class T,class X,class Y>
int PQTree<T,X,Y>::clientPrintNodeCategorie(PQNode<T,X,Y>* nodePtr) 
{
    return (nodePtr != 0) ? 1 : 0;
        // 1 is the standard node categrie in the Tree Interface.
}


/************************************************************************
                        clientPrintStatus
************************************************************************/ 

template<class T,class X,class Y>
const char* PQTree<T,X,Y>::clientPrintStatus(PQNode<T,X,Y>* nodePtr) 
{
    return (nodePtr != 0) ? "ERROR" : "ERROR: clientPrintStatus: NO NODE ACCESSED";            
}


/************************************************************************
                        clientPrintType
************************************************************************/ 

template<class T,class X,class Y>
const char*  PQTree<T,X,Y>::clientPrintType(PQNode<T,X,Y>* nodePtr) 
{
    return (nodePtr != 0) ? "ERROR" : "ERROR: clientPrintType: NO NODE ACCESSED";
}


/************************************************************************
                         Constructor
************************************************************************/ 


template<class T,class X,class Y> PQTree<T,X,Y>::PQTree()
{
    m_root = 0;
    m_pertinentRoot = 0;
    m_pseudoRoot = 0;

    m_numberOfLeaves = 0;
    m_identificationNumber = 0;

    m_pertinentNodes = 0;
}



/************************************************************************
                     copyFullChildrenToPartial
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::copyFullChildrenToPartial(PQNode<T,X,Y> *nodePtr,
                                              PQNode<T,X,Y> *partialChild)
{
    if (nodePtr->fullChildren->size() > 0)
                                        // There are some full children to
                                        // be copied.
    {
        nodePtr->m_childCount = nodePtr->m_childCount -
                                nodePtr->fullChildren->size();

        PQNode<T,X,Y> *newNode = createNodeAndCopyFullChildren(nodePtr->fullChildren);

                                         // Introduce newNode as endmost
                                         // child of the partial Q-node.
        partialChild->m_childCount++;
        partialChild->fullChildren->pushFront(newNode);

        if (clientLeftEndmost(partialChild)->status() == FULL)
        {
            PQNode<T,X,Y> *checkNode = partialChild->m_leftEndmost;
            partialChild->m_leftEndmost = newNode;
            linkChildrenOfQnode(checkNode,newNode);
         
        }
        else {
            // ERROR: Endmostchild not found?
            OGDF_ASSERT(clientRightEndmost(partialChild)->status() == FULL);
        
            PQNode<T,X,Y> *checkNode = partialChild->m_rightEndmost;
            partialChild->m_rightEndmost = newNode; 
            linkChildrenOfQnode(checkNode,newNode);
        }
            
        newNode->m_parent = partialChild;
        newNode->m_parentType = PQNodeRoot::QNode;
    }
}


/************************************************************************
                     createNodeAndCopyFullChildren
************************************************************************/ 

template<class T,class X,class Y>
PQNode<T,X,Y>* PQTree<T,X,Y>::createNodeAndCopyFullChildren(
                                List<PQNode<T,X,Y>*> *fullNodes)
{
    PQNode<T,X,Y>  *newNode    = 0;

    if (fullNodes->size() == 1)
    {
        /*
        There is just one full child. So no new $P$-node is created. The
        full child is copied as child to the [[partialChild]].
        */
        newNode = fullNodes->popFrontRet();
        removeChildFromSiblings(newNode);
    }
   
    else
    {
        /*
        This chunk belongs to the function [[createNodeAndCopyFullChildren]].
        There is more than one full child, so a new $P$-node is created.
        This chunk first allocates the memory for the new $P$-node that will
        be stored in [[newNode]]. Then it pops the nodes out of the stack 
        [[fullNodes]] and introduces them as sons of [[newNode]].
        Popping the nodes out of the stack implies at the same time
        that they are removed from the [[fullChildren]] stack of the
        $P$-node of their parent.
        */
        newNode = OGDF_NEW PQInternalNode<T,X,Y>(m_identificationNumber++,PQNodeRoot::PNode,FULL);
        m_pertinentNodes->pushFront(newNode);
        newNode->m_pertChildCount = fullNodes->size();
        newNode->m_childCount = fullNodes->size();

        /*
        The first node is copied separately, since we need the pointer to it 
        for setting the pointers to the siblings of the next full nodes.
        */
        PQNode<T,X,Y> *firstSon = fullNodes->popFrontRet();
        removeChildFromSiblings(firstSon);
        newNode->fullChildren->pushFront(firstSon);
        firstSon->m_parent = newNode;
        firstSon->m_parentType = newNode->type();
        PQNode<T,X,Y> *oldSon = firstSon;


        /*
        All remaining nodes that are stored in the stack [[fullNodes]] are
        introduced as children of the new $P$-node [[newNode]]. Observe
        that the children of a $P$-node must form a doubly linked list.
        Hence the last node and the [[firstSon]] must be linked via their 
        siblings pointers.
        */
        while (!fullNodes->empty())
        {
            PQNode<T,X,Y> *checkSon = fullNodes->popFrontRet();
            removeChildFromSiblings(checkSon);
            newNode->fullChildren->pushFront(checkSon);
            oldSon->m_sibRight = checkSon;
            checkSon->m_sibLeft = oldSon;
            checkSon->m_parent = newNode;
            checkSon->m_parentType = newNode->type();
            oldSon = checkSon;
        }
        firstSon->m_sibLeft = oldSon;
        oldSon->m_sibRight = firstSon;
        newNode->m_referenceChild = firstSon;
        firstSon->m_referenceParent = newNode;
    }
   
    return newNode;
}


/************************************************************************
                 emptyAllPertinetNodes
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::emptyAllPertinentNodes()
{
    PQNode<T,X,Y> *nodePtr;

    while(!m_pertinentNodes->empty())
    {
        nodePtr = m_pertinentNodes->popFrontRet();
        switch (nodePtr->status())
        {
            case TO_BE_DELETED:
                if (nodePtr == m_root)
                    m_root = 0;
                CleanNode(nodePtr);
                //if (nodePtr)
                delete nodePtr;
                break;

            case FULL:
                emptyNode(nodePtr);
                break;

            case PARTIAL:
                emptyNode(nodePtr);
                break;

            default:
                clientDefinedEmptyNode(nodePtr);
                break;
        }
    }
    m_pseudoRoot->m_pertChildCount = 0;
    m_pseudoRoot->m_pertLeafCount = 0;
    m_pseudoRoot->fullChildren->clear();
    m_pseudoRoot->partialChildren->clear();
    m_pseudoRoot->status(EMPTY);
    m_pseudoRoot->mark(UNMARKED);
}


/************************************************************************
                        emptyNode
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::emptyNode(PQNode<T,X,Y> *nodePtr)
{
    nodePtr->status(EMPTY);
    nodePtr->m_pertChildCount = 0;
    nodePtr->m_pertLeafCount = 0;
    nodePtr->fullChildren->clear();
    nodePtr->partialChildren->clear();
    nodePtr->mark(UNMARKED);
}


/************************************************************************
                     exchangeNodes
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::exchangeNodes(
    PQNode<T,X,Y> *oldNode,
    PQNode<T,X,Y> *newNode)
{
    if (oldNode->m_referenceParent != 0)
    {
        /*
        The node [[oldNode]] is connected to its parent
        via the reference pointer of the doubly linked list. The [[newNode]]
        will be the new reference child and is linked via the reference
        pointers to the $P$-node.
        */
        oldNode->m_referenceParent->m_referenceChild = newNode;
        newNode->m_referenceParent = oldNode->m_referenceParent;
        oldNode->m_referenceParent = 0;
    }

    else if (oldNode->endmostChild())
    {
        /*
        The [[oldNode]] is endmost child of a Q-node. So its parent 
        contains an extra pointer to [[oldNode]]. Link the parent of 
        [[oldNode]] to [[newNode]] via this pointer and make [[newNode]] 
        endmost child of its new parent.
        */
        if (oldNode->m_parent->m_leftEndmost == oldNode)
            oldNode->m_parent->m_leftEndmost = newNode;
        else if (oldNode->m_parent->m_rightEndmost == oldNode)
            oldNode->m_parent->m_rightEndmost = newNode;
    }

    if ((oldNode->m_sibLeft == oldNode) && (oldNode->m_sibRight == oldNode))
    {
        /*
        Two possible cases are occured.
        \begin{enumerate}
        \item [[oldNode]] is the only child of a $P$-node. In order to
        implement the doubly linked list of children of the $P$-node, the sibling
        pointers of [[newNode]] are set to [[newNode]].
        \item [[oldNode]] is the [[m_root]] of the $PQ$-tree. Since
        by our definition of the $PQ$-tree the sibling pointers of the
        [[m_root]] point to the root itself, (i.e. to make sure that 
        checking for the endmost child property is also valid for the root)
        the sibling pointers of [[newNode]] are set to [[newNode]] as well.
        \end{enumerate}
        */
        oldNode->m_sibLeft = 0;
        oldNode->m_sibRight = 0;
        if (oldNode->m_parent == 0)
        {
            newNode->m_sibLeft = newNode;
            newNode->m_sibRight = newNode;
        }
        else
        {
            newNode->m_sibLeft = newNode;
            newNode->m_sibRight = newNode;
        }
    }
    else 
    {
        OGDF_ASSERT(!(oldNode->m_sibLeft == oldNode))
        //sibling pointers of old node are not compatible
        OGDF_ASSERT(!(oldNode->m_sibRight == oldNode))
        //sibling pointers of old node are not compatible.
    }
    /*
    Manage the exchange of [[oldNode]] and [[newNode]] according to
    [[oldNode]]'s siblings. The chunk checks both siblings of
    [[oldNode]] and resets the sibling pointers of [[oldNode]]'s siblings
    as well as the sibling pointers of [[newNode]].
    */
    if (oldNode->m_sibLeft != 0)
    {
        if (oldNode->m_sibLeft->m_sibRight == oldNode)
            oldNode->m_sibLeft->m_sibRight = newNode;
        else {
            // Sibling was not connected to child?
            OGDF_ASSERT(oldNode->m_sibLeft->m_sibLeft == oldNode);
            oldNode->m_sibLeft->m_sibLeft = newNode;
        }
        newNode->m_sibLeft = oldNode->m_sibLeft;
        oldNode->m_sibLeft = 0;
    }

    if (oldNode->m_sibRight != 0)
    {
        if (oldNode->m_sibRight->m_sibLeft == oldNode)
            oldNode->m_sibRight->m_sibLeft = newNode;
        else {
            // Sibling was not connected to child?
            OGDF_ASSERT(oldNode->m_sibRight->m_sibRight == oldNode);
            oldNode->m_sibRight->m_sibRight = newNode;
        }
        newNode->m_sibRight = oldNode->m_sibRight;
        oldNode->m_sibRight = 0;
    }
      
    newNode->m_parentType = oldNode->m_parentType;
    newNode->m_parent = oldNode->m_parent;
}


/************************************************************************
                        front
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::front(
    PQNode<T,X,Y>* nodePtr,
    SListPure<PQLeafKey<T,X,Y>*> &leafKeys)
{   
    Queue<PQNode<T,X,Y>*> helpqueue;
    helpqueue.append(nodePtr);
  
    while (!helpqueue.empty())
    {
        PQNode<T,X,Y>* checkNode = helpqueue.pop();

        if (checkNode->type() == PQNodeRoot::leaf)
            leafKeys.pushBack(checkNode->getKey());      
        else
        {
            PQNode<T,X,Y>*  firstSon  = 0;
            PQNode<T,X,Y>*  nextSon   = 0;
            PQNode<T,X,Y>*  oldSib    = 0;
            PQNode<T,X,Y>*  holdSib   = 0;

            if (checkNode->type() == PQNodeRoot::PNode)
            {  
                OGDF_ASSERT(checkNode->m_referenceChild) 
                firstSon = checkNode->m_referenceChild;
            }
            else if (checkNode->type() == PQNodeRoot::QNode)
            {
                OGDF_ASSERT(checkNode->m_leftEndmost)
                firstSon = checkNode->m_leftEndmost;
            }               
            helpqueue.append(firstSon);
            nextSon = firstSon->getNextSib(oldSib);
            oldSib = firstSon;
            while (nextSon && nextSon != firstSon)
            {
                helpqueue.append(nextSon);
                holdSib = nextSon->getNextSib(oldSib);
                oldSib = nextSon;
                nextSon = holdSib;
            }
        }
    }
}


/************************************************************************
                         Initialize
************************************************************************/ 

template<class T,class X,class Y> 
int PQTree<T,X,Y>::Initialize(SListPure<PQLeafKey<T,X,Y>*> &leafKeys)
{
    m_pertinentNodes = OGDF_NEW List<PQNode<T,X,Y>*>;

    if (!leafKeys.empty())
    {
        PQInternalNode<T,X,Y> *newNode2 = OGDF_NEW PQInternalNode<T,X,Y>(-1,PQNodeRoot::QNode,PARTIAL);
        m_pseudoRoot = newNode2;

        if (leafKeys.begin() != leafKeys.end()) // at least two elements
        {
            PQInternalNode<T,X,Y> *newNode = OGDF_NEW PQInternalNode<T,X,Y>(m_identificationNumber++,PQNodeRoot::PNode,EMPTY);
            m_root = newNode;
            m_root->m_sibLeft = m_root;
            m_root->m_sibRight = m_root;
            return addNewLeavesToTree(newNode,leafKeys);
        }
        PQLeaf<T,X,Y> *newLeaf = OGDF_NEW PQLeaf<T,X,Y>(m_identificationNumber++,EMPTY,*leafKeys.begin());
        m_root = newLeaf;
        m_root->m_sibLeft = m_root;
        m_root->m_sibRight = m_root;
        return 1;
    }    

    return 0;
}


/************************************************************************
                       linkChildrenOfQnode
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::linkChildrenOfQnode(
    PQNode<T,X,Y> *installed, 
    PQNode<T,X,Y> *newChild)
{
    if ((installed != 0) && (newChild != 0))
    {
        if (installed->m_sibLeft == 0)
        {
            installed->m_sibLeft = newChild;
            if (newChild->m_sibRight == 0)
                newChild->m_sibRight = installed;
            else
                newChild->m_sibLeft = installed;
        }
        else {
            // endmost child with 2 siblings encountered?
            OGDF_ASSERT(installed->m_sibRight == 0);

            installed->m_sibRight = newChild;
            if (newChild->m_sibLeft == 0)
                newChild->m_sibLeft = installed;
            else
                newChild->m_sibRight = installed;
        }
    }
}



/************************************************************************
                 writeGML
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::writeGML(const char *fileName)
{
    ofstream os(fileName);
    writeGML(os);
}

template<class T,class X,class Y>
void PQTree<T,X,Y>::writeGML(ostream &os)
{
    Array<int> id(0,m_identificationNumber,0);
    int nextId = 0;

    SListPure<PQNode<T,X,Y>*> helpQueue;
    SListPure<PQNode<T,X,Y>*> secondTrace;

    os.setf(ios::showpoint);
    os.precision(10);

    os << "Creator \"ogdf::PQTree::writeGML\"\n";
    os << "directed 1\n";

    os << "graph [\n";

    PQNode<T,X,Y>*  checkNode = m_root;
    PQNode<T,X,Y>*  firstSon  = 0;
    PQNode<T,X,Y>*  nextSon   = 0;
    PQNode<T,X,Y>*  lastSon   = 0;
    PQNode<T,X,Y>*  oldSib    = 0;
    PQNode<T,X,Y>*  holdSib   = 0;  

    if (checkNode->type() != PQNodeRoot::leaf)
        secondTrace.pushBack(checkNode);

    while (checkNode)
    {
        os << "node [\n";

        os << "id " << (id[checkNode->m_identificationNumber] = nextId++) << "\n";

        os << "label \"" << checkNode->m_identificationNumber;
        if (checkNode->getKey() != 0)
            os << checkNode->getKey()->print();
        os << "\"\n";

        os << "graphics [\n";
        if (m_root->status() == FULL)
        {
            if (checkNode->type() == PQNodeRoot::PNode)
                os << "fill \"#FF0000\"\n";
            else if (checkNode->type() == PQNodeRoot::QNode)
                os << "fill \"#0000A0\"\n";
            else if (checkNode->type() == PQNodeRoot::leaf)
                os << "fill \"#FFFFE6\"\n";
        }
        else if (m_root->status() == EMPTY)
        {
            if (checkNode->type() == PQNodeRoot::PNode)
                os << "fill \"#FF0000\"\n";
            else if (checkNode->type() == PQNodeRoot::QNode)
                os << "fill \"#0000A0\"\n";
            else if (checkNode->type() == PQNodeRoot::leaf)
                os << "fill \"#00FF00\"\n";
        }
        else if (m_root->status() == PARTIAL)
        {
            if (checkNode->type() == PQNodeRoot::PNode)
                os << "fill \"#FF0000\"\n";
            else if (checkNode->type() == PQNodeRoot::QNode)
                os << "fill \"#0000A0\"\n";
            else if (checkNode->type() == PQNodeRoot::leaf)
                os << "fill \"#FFFFE6\"\n";
        }
        else if (m_root->status() == PERTINENT)
        {
            if (checkNode->type() == PQNodeRoot::PNode)
                os << "fill \"#FF0000\"\n";
            else if (checkNode->type() == PQNodeRoot::QNode)
                os << "fill \"#0000A0\"\n";
            else if (checkNode->type() == PQNodeRoot::leaf)
                os << "fill \"#FFFFE6\"\n";
        }

        os << "]\n"; // graphics
        os << "]\n"; // node

        if (checkNode->type() == PQNodeRoot::PNode)
        {  
            if (checkNode->m_referenceChild != 0) 
            {
                firstSon = checkNode->m_referenceChild;
                helpQueue.pushBack(firstSon);
    
                if (firstSon->m_sibRight != 0)
                nextSon = firstSon->m_sibRight;
                while (nextSon != firstSon)
                {
                    helpQueue.pushBack(nextSon);
                    nextSon = nextSon->m_sibRight;
                }
            }
        }
        else if (checkNode->type() == PQNodeRoot::QNode)
        {
            oldSib = 0;
            holdSib = 0;

            firstSon = checkNode->m_leftEndmost;
            helpQueue.pushBack(firstSon);
      
            lastSon = checkNode->m_rightEndmost;
            if ( firstSon != lastSon)
            {
                helpQueue.pushBack(lastSon);
                nextSon = lastSon->getNextSib(oldSib);
                oldSib = lastSon;
                while (nextSon != firstSon)
                {
                    helpQueue.pushBack(nextSon);
                    holdSib = nextSon->getNextSib(oldSib);
                    oldSib = nextSon;
                    nextSon = holdSib;
                }
            }
        }
        if (!helpQueue.empty())
        {
            checkNode = helpQueue.popFrontRet();
            if (checkNode->type() != PQNodeRoot::leaf)
                secondTrace.pushBack(checkNode);
        }
        else
            checkNode = 0;
    }


    SListIterator<PQNode<T,X,Y>*> it;

    for (it = secondTrace.begin(); it.valid(); it++)
    {
        checkNode = *it;
        if (checkNode->type() == PQNodeRoot::PNode)
        {  
            if (checkNode->m_referenceChild != 0) 
            {
                firstSon = checkNode->m_referenceChild;
                os << "edge [\n";
                os << "source " << id[checkNode->m_identificationNumber] << "\n";
                os << "target " << id[firstSon->m_identificationNumber] << "\n";
                os << "]\n"; // edge
    
                if (firstSon->m_sibRight != 0)
                nextSon = firstSon->m_sibRight;
                while (nextSon != firstSon)
                {
                    os << "edge [\n";
                    os << "source " << id[checkNode->m_identificationNumber] << "\n";
                    os << "target " << id[nextSon->m_identificationNumber] << "\n";
                    os << "]\n"; // edge
                    nextSon = nextSon->m_sibRight;
                }
            }
        }
        else if (checkNode->type() == PQNodeRoot::QNode)
        {
            oldSib = 0;
            holdSib = 0;

            firstSon = checkNode->m_leftEndmost;      
            lastSon = checkNode->m_rightEndmost;

            os << "edge [\n";
            os << "source " << id[checkNode->m_identificationNumber] << "\n";
            os << "target " << id[lastSon->m_identificationNumber] << "\n";
            os << "]\n"; // edge
            if ( firstSon != lastSon)
            {
                nextSon = lastSon->getNextSib(oldSib);
                os << "edge [\n";
                os << "source " << id[checkNode->m_identificationNumber] << "\n";
                os << "target " << id[nextSon->m_identificationNumber] << "\n";
                os << "]\n"; // edge

                oldSib = lastSon;
                while (nextSon != firstSon)
                {
                    holdSib = nextSon->getNextSib(oldSib);
                    oldSib = nextSon;
                    nextSon = holdSib;
                    os << "edge [\n";
                    os << "source " << id[checkNode->m_identificationNumber] << "\n";
                    os << "target " << id[nextSon->m_identificationNumber] << "\n";
                    os << "]\n"; // edge

                }
            }
        }
    }
    os << "]\n"; // graph
}



/************************************************************************
                            Reduce
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::Reduce(SListPure<PQLeafKey<T,X,Y>*> &leafKeys)
{
    int                   pertLeafCount = 0;
    Queue<PQNode<T,X,Y>*> processNodes;

    /*
    In a first step the pertinent leaves have to be identified in the tree
    and are entered on to the queue [[processNodes]]. The identification of
    the leaves can be done with the help of a pointer stored in every 
    [[PQLeafKey]] in constant time for every element.   
    */
    SListIterator<PQLeafKey<T,X,Y>*> it;
    for (it = leafKeys.begin(); it.valid(); ++it)
    {
        PQNode<T,X,Y>* checkLeaf = (*it)->nodePointer();
        checkLeaf->status(FULL);
        checkLeaf->m_pertLeafCount = 1;
        processNodes.append(checkLeaf);
        pertLeafCount++;
    }

    PQNode<T,X,Y>* checkNode = processNodes.top();
    while ((checkNode != 0) && (processNodes.size() > 0))
    {
        checkNode = processNodes.pop();

        if (checkNode->m_pertLeafCount < pertLeafCount)
        { 
            /*
            Application of the template matchings to a pointer [[checkNode]] 
            storing the adress of a node that is {\bf not the root} of the 
            pertinent subtree. Before applying the template matchings to 
            [[checkNode]], some values of the parent of [[checkNode]] are 
            updated. The number of the parents pertinent children stored in 
            [[pertChildCount]] is count down by one. In case that 
            [[checkNode->m_parent->m_pertChildCount == 0]], we know that all 
            pertinent children of the parent have been processed. Since the 
            parent then is allowed to be processed as well, 
            [[checkNode->m_parent]] is stored in the queue [[processNodes]].
            */
            checkNode->m_parent->m_pertLeafCount = 
                                        checkNode->m_parent->m_pertLeafCount
                                        + checkNode->m_pertLeafCount;

            checkNode->m_parent->m_pertChildCount--;
            if (!checkNode->m_parent->m_pertChildCount)
                processNodes.append(checkNode->m_parent);
            if (!templateL1(checkNode,0))
            if (!templateP1(checkNode,0))
            if (!templateP3(checkNode))
            if (!templateP5(checkNode))
            if (!templateQ1(checkNode,0))
            if (!templateQ2(checkNode,0))
                checkNode= 0;
        }
        else
        {
            /*
            application of the template matchings to a pointer [[checkNode]] 
            that stores the adress of a node that {\bf is the root} of the 
            pertinent subtree. In a case that a template matching was 
            successfully applied, the pointer [[checkNode]] stores after the 
            application the adress of the root of pertinent subtree. This 
            includes nodes that have been newly introduced as root of the 
            perinent subtree during the application. If no template matching 
            was successfully applied [[checkNode]] is a [[0]] pointer.
            */
            if (!templateL1(checkNode,1))
            if (!templateP1(checkNode,1))
            if (!templateP2(&checkNode))
            if (!templateP4(&checkNode))
            if (!templateP6(&checkNode))
            if (!templateQ1(checkNode,1))
            if (!templateQ2(checkNode,1))
            if (!templateQ3(checkNode))
                checkNode = 0;
        }
    }

    m_pertinentRoot = checkNode;
    return (m_pertinentRoot != 0);
}



/************************************************************************
                         Reduction
************************************************************************/ 

template<class T,class X,class Y> 
bool PQTree<T,X,Y>::Reduction(SListPure<PQLeafKey<T,X,Y>*> &leafKeys)
{
    bool success = Bubble(leafKeys);

    if (!success)
        return false;
    else
        return Reduce(leafKeys);

}


/************************************************************************
                          removeBlock
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::removeBlock(PQNode<T,X,Y> *nodePtr,bool isRoot)

{
    /*
    For every
    partial child we keep a set of pointers. Since there are at most
    two partial children, we initialize two sets. Every set contains
    besides a pointer to the partial child four pointers to its endmost 
    children, sorted according to their full or empty labels and pointers 
    to the immediate siblings of the partial child, also sorted according
    to their full or empty labels.
    */
    PQNode<T,X,Y> *partial_1 = 0;
    
    /*
    Pointer to the full endmost child (more
    precisely: to the endmost child appearing on the full side) of
    [[partial_1]]. In case that ignored nodes are used, this [[endfull_1]]
    may store the adress of an ignored node.
    */
    PQNode<T,X,Y> *endfull_1 = 0;
    
    /*
    Pointer to the empty endmost child  (more
    precisely: to the endmost child appearing on the empty side) of
    [[partial_1]]. In case that ignored nodes are used, this [[endempty_1]]
    may store the adress of an ignored node.
    */
    PQNode<T,X,Y> *endempty_1 = 0;
    
    /*
    Pointer to the first {\it non ignored} node 
    with full status. [[realfull_1]] is identical to [[endfull_1]] if no
    ignored nodes appear at the full end of the first partial child.    
    */
    PQNode<T,X,Y> *realfull_1 = 0;
    
    /*
    Pointer to the first {\it non ignored} node 
    with empty status. [[realempty_1]] is identical to [[endempty_1]] if no
    ignored nodes appear at the empty end of the first partial child.  
    */
    PQNode<T,X,Y> *realempty_1 = 0;

    // Pointer to the second partial child.
    PQNode<T,X,Y> *partial_2 = 0;
    
    /*
    Pointer to the full endmost child (more
    precisely: to the endmost child appearing on the full side) of
    [[partial_2]]. In case that ignored nodes are used, this [[endfull_2]]
    may store the adress of an ignored node.
    */
    PQNode<T,X,Y> *endfull_2 = 0;

    /*
    Pointer to the empty endmost child  (more
    precisely: to the endmost child appearing on the empty side) of
    [[partial_2]]. In case that ignored nodes are used, this [[endempty_2]]
    may store the adress of an ignored node.
    */
    PQNode<T,X,Y> *endempty_2 = 0;
    
    /*
    Pointer to the first {\it non ignored} node 
    with full status. [[realfull_2]] is identical to [[endfull_2]] if no
    ignored nodes appear at the full end of the first partial child. 
    */
    PQNode<T,X,Y> *realfull_2 = 0;
    
    /*
    Pointer to the first {\it non ignored} node 
    with empty status. [[realempty_2]] is identical to [[endempty_2]] if no
    ignored nodes appear at the empty end of the first partial child.  
    */
    PQNode<T,X,Y> *realempty_2 = 0;
      
    /*
    Pointer to a full sibling of
    [[partial_1]], if it exists. In case that ignored nodes are used 
    this [[sibfull_1]] stores the direct sibling of [[partial_1]]
    on the side where the full siblings are. Hence [[sibfull_1]] may
    store an ignored node.
    */
    PQNode<T,X,Y> *sibfull_1 = 0; 
    
    /*
    Pointer to a partial sibling of
    [[partial_1]], if it exists. In case that ignored nodes are used 
    this [[sibpartial_1]] stores the direct sibling of [[partial_1]]
    on the side where a partial sibling is. Hence [[sibpartial_1]] may
    store an ignored node.
    */
    PQNode<T,X,Y> *sibpartial_1 = 0;
    
    /*
    Pointer to an empty sibling of
    [[parial_1]], if it exists. In case that ignored nodes are used 
    this [[sibempty_1]] stores the direct sibling of [[partial_1]]
    on the side where the empty siblings are. Hence [[sibempty_1]] may
    store an ignored node.
    */
    PQNode<T,X,Y> *sibempty_1 = 0;  
    
    /*
    Pointer only used in case that [[partial_1]] has
    no non-ignored siblings on one side. [[partial_1]] then is endmost child
    of [[nodePtr]], but ignored children may appear between [[partial_1]]
    and the end of sequence of children of [[nodePtr]]. The
    [[nonstatussib_1]] then stores the adress of the endmost ignored child.
    Observe that it is not valid for a $Q$-node to have only one
    non-ignored child and several ignored children. Hence this situation
    is only allowed to appear {\bf once} on one side of [[partial_1]]. 
    Every other situation results in an error message.  
    */
    PQNode<T,X,Y> *nonstatussib_1 = 0;

    /*
    Pointer to a full sibling of
    [[partial_2]], if it exists. In case that ignored nodes are used 
    this [[sibfull_2]] stores the direct sibling of [[partial_2]]
    on the side where the full siblings are. Hence [[sibfull_2]] may
    store an ignored node.
    */
    PQNode<T,X,Y> *sibfull_2 = 0;   
    
    /*
    Pointer to a partial sibling of
    [[partial_2]], if it exists. In case that ignored nodes are used 
    this [[sibpartial_2]] stores the direct sibling of [[partial_2]]
    on the side where a partial sibling is. Hence [[sibpartial_2]] may
    store an ignored node.
    */
    PQNode<T,X,Y> *sibpartial_2 = 0;
    
    /*
    Pointer to an empty sibling of
    [[parial_2]], if it exists. In case that ignored nodes are used 
    this [[sibempty_2]] stores the direct sibling of [[partial_2]]
    on the side where the empty siblings are. Hence [[sibempty_2]] may
    store an ignored node.
    */
    PQNode<T,X,Y> *sibempty_2 = 0;  
    
    /*
    Pointer only used in case that [[partial_2]] has
    no non-ignored siblings on one side. [[partial_2]] then is endmost child
    of [[nodePtr]], but ignored children may appear between [[partial_2]]
    and the end of sequence of children of [[nodePtr]]. The
    [[nonstatussib_2]] then stores the adress of the endmost ignored child.
    Observe that it is not valid for a $Q$-node to have only one
    non-ignored child and several ignored children. Hence this situation
    is only allowed to appear {\bf once} on one side of [[partial_2]]. 
    Every other situation results in an error message.
    */
    PQNode<T,X,Y> *nonstatussib_2 = 0;

    PQNode<T,X,Y> *helpptr        = 0;

    PQNode<T,X,Y> *checkVarLeft   = 0; 

    PQNode<T,X,Y> *checkVarRight  = 0;

    /*
    [[endmostcheck]] is [[1]], if [[partial_1]] is the endmost
    child of [[nodePtr]]. Per default, [[endmostcheck]] is [[0]].
    */
    int endmostcheck = 0;
   
   
    nodePtr->status(PARTIAL);
    if (!isRoot)
        nodePtr->m_parent->partialChildren->pushFront(nodePtr);
      
    if (!nodePtr->partialChildren->empty())
                                                // Get a partial child.
    {
        partial_1 = nodePtr->partialChildren->popFrontRet();

                                                // Get the full and empty 
                                                // endmost children of the 
                                                // partial child [[partial_1]].
        checkVarLeft = clientLeftEndmost(partial_1);
        checkVarRight = clientRightEndmost(partial_1);
        if (checkVarLeft->status() == FULL)
        {
            endfull_1  = partial_1->m_leftEndmost;
            realfull_1 = checkVarLeft;
        }
        else {
            // partial child with no full endmost child detected?
            OGDF_ASSERT(checkVarRight->status() == FULL);
        
            endfull_1  = partial_1->m_rightEndmost;
            realfull_1 = checkVarRight;
        }

        if (checkVarLeft->status() == EMPTY)
        {
            endempty_1  = partial_1->m_leftEndmost;
            realempty_1 = checkVarLeft;
        }
        else {
            // partial child with no empty endmost child detected?
            OGDF_ASSERT(checkVarRight->status() == EMPTY);
        
            endempty_1  = partial_1->m_rightEndmost;
            realempty_1 = checkVarRight;
        }

                                                // Get the immediate 
                                                // siblings of the partial 
                                                // child [[partial_1]].
        if (clientSibLeft(partial_1) != 0)
        {
            if (clientSibLeft(partial_1)->status() == FULL)
                sibfull_1 = partial_1->m_sibLeft;
            else if (clientSibLeft(partial_1)->status() == EMPTY)
                sibempty_1 = partial_1->m_sibLeft;
            else if (clientSibLeft(partial_1)->status() == PARTIAL)
                sibpartial_1 = partial_1->m_sibLeft;
        }
        else 
            nonstatussib_1 = partial_1->m_sibLeft;

        if (clientSibRight(partial_1) != 0)
        {
            if (clientSibRight(partial_1)->status() == FULL)
                sibfull_1 = partial_1->m_sibRight;
            else if (clientSibRight(partial_1)->status() == EMPTY)
                sibempty_1 = partial_1->m_sibRight;
            else if (clientSibRight(partial_1)->status() == PARTIAL)
                sibpartial_1 = partial_1->m_sibRight;
        }
        else {
            // partial child detected with no siblings of valid status?
            OGDF_ASSERT(nonstatussib_1 == 0);
            nonstatussib_1 = partial_1->m_sibRight;
        }
    }


    if (!nodePtr->partialChildren->empty())
                                            // There is a second partial child.
    {
        partial_2 = nodePtr->partialChildren->popFrontRet();
                                            // Get the full and empty endmost 
                                            // children of the partial 
                                            // child [[partial_2]].
        
        checkVarLeft = clientLeftEndmost(partial_2);
        checkVarRight = clientRightEndmost(partial_2);
        if (checkVarLeft->status() == FULL)
        {
            endfull_2 = partial_2->m_leftEndmost;
            realfull_2 = checkVarLeft;
        }
        else {
            // partial child with no full endmost child detected?
            OGDF_ASSERT(checkVarRight->status() == FULL);
        
            endfull_2 = partial_2->m_rightEndmost;
            realfull_2 = checkVarRight;
        }

        if (checkVarLeft->status() == EMPTY)
        {
            endempty_2 = partial_2->m_leftEndmost;
            realempty_2 = checkVarLeft;
        }
        else {
            // partial child with no empty endmost child detected?
            OGDF_ASSERT(checkVarRight->status() == EMPTY);
        
            endempty_2 = partial_2->m_rightEndmost;
            realempty_2 = checkVarRight;
        }
                                                // Get the immediate siblings 
                                                // of the partial child 
                                                // [[partial_2]].
        if (clientSibLeft(partial_2) != 0)
        {
            if (clientSibLeft(partial_2)->status() == FULL)
                sibfull_2 = partial_2->m_sibLeft;
            else if (clientSibLeft(partial_2)->status() == EMPTY)
                sibempty_2 = partial_2->m_sibLeft;
            else if (clientSibLeft(partial_2)->status() == PARTIAL)
                sibpartial_2 = partial_2->m_sibLeft;
        }
        else 
            nonstatussib_2 = partial_2->m_sibLeft;


        if (clientSibRight(partial_2) != 0)
        {
            if (clientSibRight(partial_2)->status() == FULL)
                sibfull_2 = partial_2->m_sibRight;
            else if (clientSibRight(partial_2)->status() == EMPTY)
                sibempty_2 = partial_2->m_sibRight;
            else if (clientSibRight(partial_2)->status() == PARTIAL)
                sibpartial_2 = partial_2->m_sibRight;
        }
        else {
            OGDF_ASSERT(nonstatussib_2 == 0);
            nonstatussib_2 = partial_2->m_sibRight;
        }
    }


    if (partial_1 != 0 && partial_2 != 0)
    
    /*
    Connect the endmost
    children of the partial children [[partial_1]] and [[partial_2]] correctly
    with their new siblings. In doing this, all children of the partial
    children become children of [[nodePtr]]. The reader should observe that
    the parent pointers of the interior children of [[partial_1]] and 
    [[partial_2]] are not updated in order to hit the linear time complexity.

    When including the children of the partial children to the children
    of [[nodePtr]], it is taken care that all full children
    form a consecutive sequence afterwards. If neccessary the pointers to the
    endmost children of [[nodePtr]] are updated.
    */
    {
        if (sibfull_1 != 0 && sibfull_2 != 0)
                                          // There are full children  between
                                          // the 2 partial nodes.
                                          // Connect the full children
                                          // between the 2 partial children
                                          // with the full endmost children
                                          // of the 2 partial nodes.
        {
            sibfull_1->changeSiblings(partial_1,endfull_1);
            endfull_1->putSibling(sibfull_1);
            sibfull_2->changeSiblings(partial_2,endfull_2);
            endfull_2->putSibling(sibfull_2);
        }

        else if (sibpartial_1 != 0 && sibpartial_2 != 0)
                                          // There are no full children between
                                          // the 2 partial nodes. Connect the
                                          // full endmost children of the
                                          // partial nodes as siblings.
        {
            if (partial_1 == sibpartial_2 && partial_2 == sibpartial_1)
                                          // Regular Case.
            {
                endfull_1->putSibling(endfull_2);
                endfull_2->putSibling(endfull_1);
            }
                                          // Only ignored children between 
                                          // partial_1 and partial_2. 
            else
            {
                endfull_1->putSibling(sibpartial_1);
                sibpartial_1->changeSiblings(partial_1,endfull_1);
                endfull_2->putSibling(sibpartial_2);
                sibpartial_2->changeSiblings(partial_2,endfull_2);
            }
         
        }
                                            // Include the children of the 
                                            // partial children with their
                                            // full nodes inbetween into
                                            // the sequence of the children of
                                            // Q-node nodePtr.
        if (sibempty_1 == 0)
                                            // partial_1 is endmost child of
                                            // nodePtr. Make the empty endmost
                                            // child of partial_1 be the new 
                                            // endmost child of nodePtr.
        {
            if (nonstatussib_1 == 0)
                                            // Regular case.
            {
                nodePtr->changeEndmost(partial_1,endempty_1);
            }
            else
                                          // Only ignored children between 
                                          // partial_1 and one end of nodePtr. 
            {
                nonstatussib_1->changeSiblings(partial_1,endempty_1);
                endempty_1->putSibling(nonstatussib_1);
            }
            endempty_1->m_parent = nodePtr;
            realempty_1->m_parent = nodePtr;
        }
                                     
        else
                                            // partial_1 is not endmost child.
        {
            sibempty_1->changeSiblings(partial_1,endempty_1);
            endempty_1->putSibling(sibempty_1);
        }


        if (sibempty_2 == 0)
                                            // partial_2 is endmost child of
                                            // nodePtr. Make the empty endmost
                                            // child of partial_2 be the new 
                                            // endmost child of nodePtr.
        {
            if (nonstatussib_2 == 0)
                                            // Regular case.
            {
                nodePtr->changeEndmost(partial_2,endempty_2);
            }
            else
                                            // Only ignored children between 
                                            // partial_1 and one end of 
                                            // nodePtr. 
            {
                nonstatussib_2->changeSiblings(partial_2,endempty_2);
                endempty_2->putSibling(nonstatussib_2);
            }
            endempty_2->m_parent = nodePtr;
            realempty_2->m_parent = nodePtr;
        }
                                     
        else
                                            // partial_2 is not endmost child.
        {
            sibempty_2->changeSiblings(partial_2,endempty_2);
            endempty_2->putSibling(sibempty_2);
        }

                                            // Copy the full children of 
                                            // partial_1 and partial_2 to 
                                            // nodePtr.
        while (!partial_2->fullChildren->empty())
        {
            helpptr = partial_2->fullChildren->popFrontRet();
            nodePtr->fullChildren->pushFront(helpptr);
        }
        nodePtr->m_childCount = nodePtr->m_childCount +partial_2->m_childCount - 1;
                                    
        destroyNode(partial_2);

        while (!partial_1->fullChildren->empty())
        {
            helpptr = partial_1->fullChildren->popFrontRet();
            nodePtr->fullChildren->pushFront(helpptr);
        }
        nodePtr->m_childCount = nodePtr->m_childCount +partial_1->m_childCount - 1;

        destroyNode(partial_1);
    }

    
    else if (partial_1 != 0)

    /*
    Connect the endmost
    children of the partial child [[partial_1]] correctly
    with their new siblings. In doing this, all children of the partial
    child become children of [[nodePtr]]. The reader should observe that
    the parent pointers of the interior children of [[partial_1]] 
    are not updated in order to hit the linear time complexity.

    When including the children of [[partial_1]] to the children
    of [[nodePtr]], it is taken care that all full children
    form a consecutive sequence afterwards. If necessary the pointers to the
    endmost children of [[nodePtr]] are updated.    
    */
    
    {
        if ((clientLeftEndmost(nodePtr) == partial_1) ||
            (clientRightEndmost(nodePtr) == partial_1))
                                            // partial_1 is endmost child.
            endmostcheck = 1;
               
        if (sibfull_1 != 0)
                                            // There are full children on one
                                            // side of the partial node.
                                            // Connect the full children with
                                            // the full endmost child of 
                                            // partial_1.
        {
            sibfull_1->changeSiblings(partial_1,endfull_1);
            endfull_1->putSibling(sibfull_1);
        }

        else if (!endmostcheck)
                                            // There are not any full children
                                            // and partial_1 is not endmost.
                                            // So get the 2nd empty sibling
                                            // of partial_1 and connect it
                                            // to the full endmost child
                                            // of partial_1.
        {
            if (partial_1->m_sibLeft != sibempty_1)
                sibempty_2 = partial_1->m_sibLeft;
            else
                sibempty_2 = partial_1->m_sibRight;

            sibempty_2->changeSiblings(partial_1,endfull_1);
            endfull_1->putSibling(sibempty_2);
        }

        else
                                            // partial_1 is endmost child
                                            // and there are no full children.
                                            // Make the full endmost child of 
                                            // partial_1 be the endmostchild
                                            // of nodePtr.
        {

            if (nonstatussib_1 == 0)
                                            // Regular case.
            {
                nodePtr->changeEndmost(partial_1,endfull_1);
            }
            else
                                            // Only ignored children between 
                                            // partial_1 and one end of 
                                            // nodePtr. 
            {
                nonstatussib_1->changeSiblings(partial_1,endfull_1);
                endfull_1->putSibling(nonstatussib_1);
            }
            endfull_1->m_parent = nodePtr;
            realfull_1->m_parent = nodePtr;

        }

        if (sibempty_1 == 0)
                                            // There are no empty children.
                                            // partial_1 is endmost child of
                                            // nodePtr. Make the empty endmost
                                            // child of partial_1 be the new 
                                            // endmost child of nodePtr.
        {
            if (nonstatussib_1 == 0)
                                            // Regular case.
            {
                nodePtr->changeEndmost(partial_1,endempty_1);
            }
            else
                                            // Only ignored children between 
                                            // partial_1 and one end of 
                                            // nodePtr. 
            {
                nonstatussib_1->changeSiblings(partial_1,endempty_1);
                endempty_1->putSibling(nonstatussib_1);
            }
            endempty_1->m_parent = nodePtr;
            realempty_1->m_parent = nodePtr;
        }
                                     
        else
                                            // There are empty children. So 
                                            // connect the empty endmost child
                                            // of partial_1 with sibempty_1.
        {
            sibempty_1->changeSiblings(partial_1,endempty_1);
            endempty_1->putSibling(sibempty_1);
        }

        while (!partial_1->fullChildren->empty())
        {
            helpptr = partial_1->fullChildren->popFrontRet();
            nodePtr->fullChildren->pushFront(helpptr);
        }

        nodePtr->m_childCount = nodePtr->m_childCount + partial_1->m_childCount - 1;
        destroyNode(partial_1);

    }
    // else nodePtr does not have partial children. Then nothing is to do. 
}


/************************************************************************
                     removeChildFromSiblings
************************************************************************/ 

template<class T,class X,class Y>
void PQTree<T,X,Y>::removeChildFromSiblings(PQNode<T,X,Y>* nodePtr)
{
    if (nodePtr->m_referenceParent != 0)
    {
        /*
        Checksif [[nodePtr]] is connected with its parent via the reference
        pointers (see \ref{PQNode}). If so, the next sibling of [[nodePtr]]
        will be the the new reference child.
        */
        nodePtr->m_referenceParent->m_referenceChild = nodePtr->m_sibRight;
        nodePtr->m_sibRight->m_referenceParent = nodePtr->m_referenceParent;
        if (nodePtr->m_referenceParent->m_referenceChild == nodePtr)
            nodePtr->m_referenceParent->m_referenceChild = 0;
        nodePtr->m_referenceParent = 0;
    }
    else if (nodePtr->endmostChild())
    {  
        /*
        Check if [[nodePtr]] is the endmost child of a $Q$-node.
        If so, the next sibling of [[nodePtr]] will be the the new endmost
        child of the $Q$-node. Observe that the sibling then gets a valid
        pointer to its parent.
        */
        PQNode<T,X,Y> *sibling = nodePtr->getNextSib(0);
        if (nodePtr->m_parent->m_leftEndmost == nodePtr)
            nodePtr->m_parent->m_leftEndmost = sibling;
        else if (nodePtr->m_parent->m_rightEndmost == nodePtr)
            nodePtr->m_parent->m_rightEndmost = sibling;
        if (sibling != 0)
            sibling->m_parent = nodePtr->m_parent;
    }

    /*
    Remove [[nodePtr]] from its immediate siblings and links the
    siblings via the [[sibRight]] and [[sibLeft]] pointers.
    */
    if ((nodePtr->m_sibRight != 0) && (nodePtr->m_sibRight != nodePtr))
    {
        if (nodePtr->m_sibRight->m_sibLeft == nodePtr)
            nodePtr->m_sibRight->m_sibLeft = nodePtr->m_sibLeft;
        else {
            // Sibling was not connected to child?
            OGDF_ASSERT(nodePtr->m_sibRight->m_sibRight == nodePtr);
            nodePtr->m_sibRight->m_sibRight = nodePtr->m_sibLeft;
        }
    }
    if ((nodePtr->m_sibLeft != 0) && (nodePtr->m_sibLeft != nodePtr))
    {
        if (nodePtr->m_sibLeft->m_sibRight == nodePtr)
            nodePtr->m_sibLeft->m_sibRight = nodePtr->m_sibRight;
        else {
            // Sibling was not connected to child?
            OGDF_ASSERT(nodePtr->m_sibLeft->m_sibLeft == nodePtr);
            nodePtr->m_sibLeft->m_sibLeft = nodePtr->m_sibRight;
        }
    }

    nodePtr->m_sibRight = 0;
    nodePtr->m_sibLeft = 0;
}


/************************************************************************
                 removeNodeFromTree
************************************************************************/ 

template<class T,class X,class Y>
int PQTree<T,X,Y>::removeNodeFromTree(PQNode<T,X,Y>* parent,PQNode<T,X,Y>* child)
{
    if (parent !=0)
    {
        removeChildFromSiblings(child);
        parent->m_childCount--;
        if ((child->status() == FULL) || (child->status() == PARTIAL))
            parent->m_pertChildCount--;
        return parent->m_childCount;
    }
    else
    {
        //parent is invalid 0-pointer.
        return -1;
    }   
}


/************************************************************************
                       sortExceptions
************************************************************************/

template<class T,class X,class Y>
void PQTree<T,X,Y>::sortExceptions(int Exceptions[],int arraySize)
{
    bool changed = true;
    while (changed)
    {
        changed = false;
        for (int i = 0; i < (arraySize-1); i++)
        {
            if (Exceptions[i] > Exceptions[i+1])
            {
                swap(Exceptions[i],Exceptions[i+1]);
                changed = true;
            }
        }
    }
}


/************************************************************************
                          templateL1
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateL1(PQNode<T,X,Y> *nodePtr, bool isRoot)
{
    if ((nodePtr->type() == PQNodeRoot::leaf) && (nodePtr->status() == FULL))
    {
        if (!isRoot)
            nodePtr->m_parent->fullChildren->pushFront(nodePtr);
        return true;
    }
    
    return false;
}


/************************************************************************
                          templateP1
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateP1(PQNode<T,X,Y> *nodePtr,
                               bool isRoot)
{
    if (nodePtr->type() != PQNodeRoot::PNode ||
        nodePtr->fullChildren->size() != nodePtr->m_childCount)
        return false;
    else
    {
        nodePtr->status(FULL);
        if (!isRoot)
            nodePtr->m_parent->fullChildren->pushFront(nodePtr);

        return true;
    }
}


/************************************************************************
                          templateP2
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateP2(PQNode<T,X,Y> **nodePtr)
{
    if ((*nodePtr)->type() != PQNodeRoot::PNode ||
        (*nodePtr)->partialChildren->size() > 0)
        return false;

    (*nodePtr)->m_childCount =
        (*nodePtr)->m_childCount - (*nodePtr)->fullChildren->size() + 1;
                                   // Gather all full children of nodePtr
                                   // as children of the new P-node.
                                   // Delete them from nodePtr.

    PQNode<T,X,Y> *newNode = createNodeAndCopyFullChildren((*nodePtr)->fullChildren);
                                   // Correct parent-pointer and
                                   // sibling-pointers of the new P-node.
                                   
    newNode->m_parent = (*nodePtr);
    newNode->m_sibRight = (*nodePtr)->m_referenceChild->m_sibRight;
    newNode->m_sibLeft = newNode->m_sibRight->m_sibLeft;
    newNode->m_sibLeft->m_sibRight = newNode;
    newNode->m_sibRight->m_sibLeft = newNode;
    newNode->m_parentType = PQNodeRoot::PNode;
                                   // The new P-node now is the root of
                                   // the pertinent subtree.
    (*nodePtr) = newNode;

    return true;
}


/************************************************************************
                          templateP3
************************************************************************/ 

/*
 * The function templateP3() implements the template matching for a
 * P-node with full \b and empty children that is \b not the root of
 * the pertinent subtree.
 * The function requires as input any pointer to a node stored in
 * \ nodePtr. If the node stored in \a nodePtr is a P-node with
 * no partial children,
 * templateP3() considers itself responsible for the node and will
 * apply the template matching \b P3 to \a nodePtr.
 * Observe that the user calling this function has to make sure that
 * \a nodePtr is partial and is not the root of the pertinent subtree.
 *
 * If templateP3() was responsible for \a nodePtr and the
 * reduction was successful, the return value is 1. Otherwise
 * the return value is 0.
 *
 * The function templateP3() creates
 * a new full P-node, stored in \a newPnode and copies the full children
 * of \a nodePtr to \a newPnode. \a nodePtr keeps all empty children
 * and will be labeled empty. A new partial Q-node will be created and stored
 * in \a newQnode. \a newQnode is placed at the position of \a nodePtr
 * in the tree and gets two children: \a nodePtr itself and the newly
 * created \a newPnode.
 *
 * The function templateP3() uses a few variables.
 *   - \a newPnode is the pointer to the new P-node, or, in case
 *     that \a nodePtr has only one full child, is the pointer of this child.
 *   - \a newQnode is the pointer to the new Q-node.
 *   - \a newNode is used for the proper allocation of the new
 *     Q-node.
 *   - \a emptyNode is a pointer to any empty child of nodePtr.
 */

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateP3(PQNode<T,X,Y> *nodePtr)
{
    if (nodePtr->type() != PQNodeRoot::PNode || nodePtr->partialChildren->size() > 0)
        return false;

    /*
    Create a new partial $Q$-node stored in [[newQnode]].
    It replaces [[nodePtr]] by the Q-node [[newQnode]] in the $PQ$-tree
    and makes [[nodePtr]] endmost child of [[newQnode]].
    This is done by updating parent-pointers and sibling-pointers. 
    */
    PQInternalNode<T,X,Y> *newNode = OGDF_NEW PQInternalNode<T,X,Y>(m_identificationNumber++,PQNodeRoot::QNode,PARTIAL);
    PQNode<T,X,Y>         *newQnode = newNode;
    m_pertinentNodes->pushFront(newQnode);

    exchangeNodes(nodePtr,newQnode);
    nodePtr->m_parent = newQnode;
    nodePtr->m_parentType = PQNodeRoot::QNode;

    newQnode->m_leftEndmost = (nodePtr);
    newQnode->m_childCount = 1;
  
    /*
    Create a new full $P$-node stored in [[newPnode]].
    It copies the full children of [[nodePtr]] to [[newPnode]].
    The new $P$-node will then be included into the tree as child of
    the new $Q$-node [[newQnode]].
    */
    if (nodePtr->fullChildren->size() > 0)
    {
        nodePtr->m_childCount = nodePtr->m_childCount -
                                nodePtr->fullChildren->size();
                                
        PQNode<T,X,Y> *newPnode = createNodeAndCopyFullChildren(nodePtr->fullChildren);
        newPnode->m_parentType = PQNodeRoot::QNode;

                                       // Update newQnode.
        newQnode->m_childCount++;
        newQnode->fullChildren->pushFront(newPnode);
                                       // Update sibling pointers.
        nodePtr->m_sibRight = newPnode;
        newPnode->m_sibLeft = nodePtr;
        newQnode->m_rightEndmost = newPnode;
        newPnode->m_parent = newQnode;
    }

                                  // Check if nodePtr contains
                                  // only one son. If so, nodePtr
                                  // will be deleted from the tree.
    PQNode<T,X,Y> *emptyNode = nodePtr->m_referenceChild;
    checkIfOnlyChild(emptyNode,nodePtr);
                                  // Update partialchildren stack of
                                  // the parent of the new Q-node.
    newQnode->m_parent->partialChildren->pushFront(newQnode);      

    return true;
}


/************************************************************************
                          templateP4
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateP4(PQNode<T,X,Y> **nodePtr)
{
    if ((*nodePtr)->type() != PQNodeRoot::PNode   ||
        (*nodePtr)->partialChildren->size() != 1)
        return false;
      
    PQNode<T,X,Y> *partialChild = (*nodePtr)->partialChildren->popFrontRet();
    copyFullChildrenToPartial(*nodePtr,partialChild);
                                  // If nodePtr does not have any
                                  // empty children, then it has to
                                  // be deleted and the partial node
                                  // is occupying its place in the tree.
    checkIfOnlyChild(partialChild,*nodePtr);
                                  // The partial child now is
                                  // root of the pertinent subtree.
    *nodePtr = partialChild;

    return true;
}


/************************************************************************
                          templateP5
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateP5(PQNode<T,X,Y> *nodePtr)
{
    if ((nodePtr->type() != PQNodeRoot::PNode) ||
        (nodePtr->partialChildren->size() != 1))
        return false;
      
    /*
    Remove [[partialChild]] from the children of [[nodePtr]]. The node
    [[partialChild]] then occupies the position of [[nodePtr]] in the 
    $PQ$-tree which is done in the function call [[exchangeNodes]] 
    (\ref{exchangeNodes}). The chunk then removes all full children from 
    [[nodePtr]] and adds them as children of a new $P$-node as endmost
    child of [[partialChild]]. This is done in the function call
    [[copyFullChildrenToPartial]] (\ref{copyFullChildrenToPartial}).
    When this chunk has finished, [[nodePtr]] has only empty children.
    */
    int emptyChildCount = nodePtr->m_childCount - 
                        nodePtr->fullChildren->size() - 1;
    PQNode<T,X,Y> *partialChild = nodePtr->partialChildren->popFrontRet();
    nodePtr->m_parent->partialChildren->pushFront(partialChild);
    removeChildFromSiblings(partialChild);
    exchangeNodes(nodePtr,partialChild);
    copyFullChildrenToPartial(nodePtr,partialChild);

    if (emptyChildCount > 0)
    {
        /*
        Check if [[nodePtr]] has just one empty child. If so, the child 
        is stored in [[emptyNode]] in order to be added to the empty
        side of the partial $Q$-node [[partialChild]]. If [[nodePtr]] 
        has more than one empty child, [[nodePtr]] is stored in 
        [[emptyNode]] in order to be added to the empty
        side of the partial $Q$-node [[partialChild]].
        */
        PQNode<T,X,Y> *emptyNode;
        if (emptyChildCount == 1)
        {
            emptyNode = nodePtr->m_referenceChild;
            removeChildFromSiblings(emptyNode);

        } else {
            emptyNode = nodePtr;
            emptyNode->m_childCount = emptyChildCount;
        }

        /*
        Check at which side of [[partialChild]]
        the empty children hide. [[emptyNode]] stores the empty node
        that is added to the empty side of [[partialChild]].
        */
        PQNode<T,X,Y> *checkNode;
        if (clientLeftEndmost(partialChild)->status() == EMPTY)
        {
            checkNode = partialChild->m_leftEndmost;
            partialChild->m_leftEndmost = emptyNode;
        }
        else {
            // Endmostchild not found?
            OGDF_ASSERT(clientRightEndmost(partialChild)->status() == EMPTY);
        
            checkNode = partialChild->m_rightEndmost;
            partialChild->m_rightEndmost = emptyNode;
        }

        linkChildrenOfQnode(checkNode,emptyNode);
        emptyNode->m_parent = partialChild;
        emptyNode->m_parentType = PQNodeRoot::QNode;
        partialChild->m_childCount++;
    }
                                   // If nodePtr did not have any empty
                                   // children it has to be deleted.
    if (emptyChildCount <= 1)
        destroyNode(nodePtr);

    return true;
}


/************************************************************************
                          templateP6
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateP6(PQNode<T,X,Y> **nodePtr)
{
    //PQNode<T,X,Y>  *partial_1       = 0;
    //PQNode<T,X,Y>  *partial_2       = 0;
    //PQNode<T,X,Y>  *fullEnd_1       = 0;
    //PQNode<T,X,Y>  *fullEnd_2       = 0;
    //PQNode<T,X,Y>  *emptyEnd_2      = 0;
    //PQNode<T,X,Y>  *realEmptyEnd_2  = 0;   

    if ((*nodePtr)->type() != PQNodeRoot::PNode   ||
        (*nodePtr)->partialChildren->size() != 2)
        return false;
      
    /*
    Get the partial children of [[nodePtr]] and removes the second 
    partial child stored in [[partial_2]] from the children of 
    [[nodePtr]]. If there are any full children of [[nodePtr]], the 
    chunk removes them from the children of [[nodePtr]] and copies them 
    as children to a new $P$-node. This new $P$-node is then made
    endmost child of [[partial_1]].
    */
    PQNode<T,X,Y> *partial_1 = (*nodePtr)->partialChildren->popFrontRet();
    PQNode<T,X,Y> *partial_2 = (*nodePtr)->partialChildren->popFrontRet();

    removeChildFromSiblings(partial_2);
    (*nodePtr)->m_childCount--;
    copyFullChildrenToPartial(*nodePtr,partial_1);

    /*
    Check the endmost children of the two partial children of [[nodePtr]]
    and stores them at approriate places, remembering what kind of type
    the endmost children are.       
    */
    PQNode<T,X,Y> *fullEnd_1;
    if (clientLeftEndmost(partial_1)->status() == FULL)
        fullEnd_1 = partial_1->m_leftEndmost;
    else {
        // partial child with no FULL endmost child detected?
        OGDF_ASSERT(clientRightEndmost(partial_1)->status() == FULL);
        fullEnd_1 = partial_1->m_rightEndmost;
    }

    PQNode<T,X,Y> *fullEnd_2      = 0;
    PQNode<T,X,Y> *emptyEnd_2     = 0;
    PQNode<T,X,Y> *realEmptyEnd_2 = 0;   
    if (clientLeftEndmost(partial_2)->status() == FULL)
        fullEnd_2 = partial_2->m_leftEndmost;
    else {
        // partial child with no FULL or EMPTY endmost child detected?
        OGDF_ASSERT(clientLeftEndmost(partial_2)->status() == EMPTY);
    
        emptyEnd_2 = partial_2->m_leftEndmost;
        realEmptyEnd_2 = clientLeftEndmost(partial_2);
    }

    if (clientRightEndmost(partial_2)->status() == FULL)
        fullEnd_2 = partial_2->m_rightEndmost;
    else {
        // partial child with no FULL or EMPTY endmost child detected?
        OGDF_ASSERT(clientRightEndmost(partial_2)->status() == EMPTY);
    
        emptyEnd_2 = partial_2->m_rightEndmost;
        realEmptyEnd_2 = clientRightEndmost(partial_2);
    }

    OGDF_ASSERT(fullEnd_2 != emptyEnd_2)
        //partial child with same type of endmost child detected

    /*
    The children of [[partial_2]] are removed from their parent and
    added as children to [[partial_1]]. This is done by resetting the
    sibling pointers of the two endmost children of [[partial_1]] and
    [[partial_2]] and the endmost child pointers of [[partial_1]].
    Observe that the parent pointers are not updated. The node
    [[partial_2]] is deleted.
    */
    while (!partial_2->fullChildren->empty())
        partial_1->fullChildren->pushFront(partial_2->fullChildren->popFrontRet());
    linkChildrenOfQnode(fullEnd_1,fullEnd_2);
    if (partial_1->m_leftEndmost == fullEnd_1)
        partial_1->m_leftEndmost = emptyEnd_2;
    else
        partial_1->m_rightEndmost = emptyEnd_2;

    emptyEnd_2->m_parent = partial_1;
    emptyEnd_2->m_parentType = PQNodeRoot::QNode;

    realEmptyEnd_2->m_parent = partial_1;
    realEmptyEnd_2->m_parentType = PQNodeRoot::QNode;

    partial_1->m_childCount = partial_1->m_childCount +
                            partial_2->m_childCount;
    destroyNode(partial_2);



                                  // If nodePtr does not have any
                                  // empty children, then it has to
                                  // be deleted and the partial node
                                  // is occupying its place in the tree.
    checkIfOnlyChild(partial_1,*nodePtr);
                                // partial_1 is now root of the
                                // pertinent subtree.
    *nodePtr = partial_1;

    return true;
}


/************************************************************************
                          templateQ1
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateQ1(PQNode<T,X,Y> *nodePtr, bool isRoot)
{
    if (nodePtr->type() == PQNodeRoot::QNode &&
        nodePtr != m_pseudoRoot &&
        clientLeftEndmost(nodePtr)->status() == FULL &&
        clientRightEndmost(nodePtr)->status() == FULL)
    {
        PQNode<T,X,Y>* seqStart = 0;
        PQNode<T,X,Y>* seqEnd = 0;
        if (checkChain(nodePtr,clientLeftEndmost(nodePtr),&seqStart,&seqEnd))
        {
            nodePtr->status(FULL);
            if (!isRoot)
                nodePtr->m_parent->fullChildren->pushFront(nodePtr);
            return true;
        }
    }

    return false;
}


/************************************************************************
                          templateQ2
************************************************************************/ 

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateQ2(PQNode<T,X,Y> *nodePtr,bool isRoot)
{
    if (nodePtr->type() != PQNodeRoot::QNode ||
        nodePtr->partialChildren->size() > 1)
        return false;

    bool sequenceCons = false;
    if (nodePtr->fullChildren->size() > 0)
    {
        /*
        Get a full endmost child of
        the $Q$-node [[nodePtr]] if there exists one.
        */
        PQNode<T,X,Y> *fullNode = 0;
        if (nodePtr->m_leftEndmost != 0)
        {
            fullNode = clientLeftEndmost(nodePtr);
            if (fullNode->status() != FULL) 
                fullNode = 0;
        }
        if (nodePtr->m_rightEndmost != 0  && fullNode == 0)
        {
            fullNode = clientRightEndmost(nodePtr);
            if (fullNode->status() != FULL)
                fullNode = 0;
        }

        /*
        In case that a full endmost child of [[nodePtr]] exists, this 
        child has been stored in [[fullNode]] and the chunk checks by 
        calling the function [[checkChain]] (\ref{checkChain}), if all
        full children of [[nodePtr]] form a consecutive sequence.
        In case that the full children
        of [[nodePtr]] form a consecutive sequence the
        return value of [[checkChain]] is [[1]]. If a partial child
        stored in [[partialChild]] exists, the chunk checks if
        [[partialChild]] is adjacent to the sequence of full children.
        If the latter case is [[1]], the flag [[sequenceCons]] is 
        set to [[1]] and the function [[templateQ2]] is allowed to 
        reduce the pertient children of [[nodePtr]].
        */
        PQNode<T,X,Y> *sequenceBegin = 0;
        PQNode<T,X,Y> *sequenceEnd   = 0;
        if (fullNode != 0)
            sequenceCons = checkChain(nodePtr,fullNode,&sequenceBegin,&sequenceEnd);

        if (sequenceCons && (nodePtr->partialChildren->size() == 1))
        {
            PQNode<T,X,Y> *partialChild = nodePtr->partialChildren->front();
            sequenceCons = false;

            if (clientSibLeft(sequenceEnd) == partialChild ||
                clientSibRight(sequenceEnd) == partialChild)
                sequenceCons = true;
        }
    }
    else
    {
        if (!nodePtr->partialChildren->empty())
        {
            /*
            If the $Q$-node [[nodePtr]] has no full children but one 
            partial child this chunk checks, if the partial child is 
            endmost child of the [[nodePtr]]. If this is not the case, 
            [[nodePtr]] cannot be reduced by the template matching 
            {\bf Q2}.
            */
            //nodePtr->partialChildren->startAtBottom();
            //partialChild = nodePtr->partialChildren->readNext();
            PQNode<T,X,Y> *partialChild = nodePtr->partialChildren->front();
            if ((clientLeftEndmost(nodePtr) == partialChild) ||
                (clientRightEndmost(nodePtr) == partialChild))
                sequenceCons = true; 
        }
    }

    if (sequenceCons)
        removeBlock(nodePtr,isRoot);

    return sequenceCons;
}


/************************************************************************
                          templateQ3
************************************************************************/ 

/*
 * The function templateQ3() implements the template matching for
 * Q-nodes with empty and/or partial children at both ends and a sequence
 * of full and/or partial children in the middle. The Q-node must be the
 * root of the pertinent subtree.
 * The function requires as input any pointer to a node stored in
 * \a nodePtr. If the node stored in \a nodePtr is a Q-node 
 * with empty and/or partial children at both ends and a sequence
 * full or partial children in the middle,
 * templateQ3() considers itself responsible for the node and will
 * apply the template matching \b Q3 to \a nodePtr.
 * Observe that the user calling this function has to make sure that
 * \a nodePtr is the root of the pertinent subtree.
 *
 * If templateQ3() was responsible for \a nodePtr and the
 * reduction was successful, the return value is 1. Otherwise
 * the return value is 0.
 *
 * Below a short description is given of all different cases that
 * may occure and are handled by the function templateQ3(), \b regardless
 * whether the Q-node \a nodePtr is the root of the pertinent subtree or not.
 * The description is somewhat trunkated and should be understood as a
 * stenographic description of the labels of the children of \a nodePtr
 * when running through the children from one side to the other. Of course
 * we leave the mirror-images out.
 *   - empty, full, empty
 *   - empty, partial, full, partial, empty
 *   - empty, partial, full, empty
 *   - empty, partial, full, partial
 *   - partial, full, partial
 *   - empty, partial, partial, empty
 *   - empty, partial, partial
 *   - partial, partial
 *
 * The function templateQ3() uses the following variables.
 *   - \a fullChild is a pointer to an arbitrary full child of \a nodePtr.
 *   - \a fullStart is a pointer to the first full child of a
 *     consecutive sequence of full children.
 *   - \a fullEnd is a pointer to the last full child of a
 *     consecutive sequence of full children.
 *   - \a partial_1 is a pointer to the first partial child of \a nodePtr.
 *   - \a partial_2 is a pointer to the second partial child of \a nodePtr.
 *   - \a conssequence is 1 if the pertinent children of
 *     \a nodePtr form a consecutive sequence with at most one partial
 *     child at every end of the sequence.
 *   - \a found is a help variable.
 *
 * templateQ3() first checks if one of the above mentioned cases
 * occures and then applies the neccessary template matching.
 * No special action has to be performed for the full nodes. If there exist
 * one or two partial children which will be stored in \a partial_1
 * or \a partial_2, their children
 * are made children of \a nodePtr. So to say, \a partial_1 and
 * partial_2 are lifted up to the Q-node \a nodePtr
 * and the occurance of their children
 * is fixed within the children of \a nodePtr.
 */

template<class T,class X,class Y>
bool PQTree<T,X,Y>::templateQ3(PQNode<T,X,Y> *nodePtr)                      
{
    if (nodePtr->type() != PQNodeRoot::QNode || nodePtr->partialChildren->size() >= 3)
        return false;   
      
    bool conssequence = false; 
    bool found        = false;
   
    /*
    Check ifthe
    pertinent children of [[nodePtr]] form a consecutive sequence. We
    differ between two cases:
    \begin{enumerate}
    \item There exist full children of [[nodePtr]]. First check with
    the function [[checkChain]] (\ref{checkChain}) if the full children
    form a consecutive sequence. In case that the check was
    successful, check if each partial child is adjacent to a full child.
    If both checks were successful, the pertient children form a
    consecutive sequence.
    \item There do not exist full children. Check if the partial
    children (there are at most two of them) form a consecutive sequence.
    If the test was successful, the pertinent children form a
    consecutive sequence.
    */
    
    if (!nodePtr->fullChildren->empty())
    {
        /*
        A consecutive
        sequence of full children has been detected, containing all full
        children of [[nodePtr]]. The chunk checks if each partial child 
        of [[nodePtr]] is adjacent to a full child. Observe that the 
        function [[templateQ3]] only reaches this chunk when [[nodePtr]] 
        has less than three partial children.
        */
        PQNode<T,X,Y> *fullChild = nodePtr->fullChildren->front();
        PQNode<T,X,Y> *fullStart = 0;
        PQNode<T,X,Y> *fullEnd   = 0;  
        conssequence = checkChain(nodePtr,fullChild,&fullStart,&fullEnd);
        if (conssequence)
        {
            ListIterator<PQNode<T,X,Y>*> it;
            for (it = nodePtr->partialChildren->begin(); it.valid(); ++it)
            {
                PQNode<T,X,Y> *partial_1 = *it;
                found = false;
                if ((clientSibLeft(fullStart) == partial_1)  ||
                    (clientSibRight(fullStart) == partial_1) ||
                    (clientSibLeft(fullEnd) == partial_1)    ||
                    (clientSibRight(fullEnd) == partial_1)     )
                    found = true;
                if (!found)
                    conssequence = found;
            }
        }
    }

    else if (nodePtr->partialChildren->size() == 2)
    {
        /*
        In case that the node [[nodePtr]] does not have any full children,
        this chunk checks if the partial children are adjacent.
        */
        PQNode<T,X,Y> *partial_1 = nodePtr->partialChildren->front();
        PQNode<T,X,Y> *partial_2 = nodePtr->partialChildren->back();
        if ((clientSibLeft(partial_1) == partial_2)  ||
            (clientSibRight(partial_1) == partial_2)   )
            found = true;
        conssequence = found;
    }

    if (conssequence)
        removeBlock(nodePtr,true);

    return conssequence;
}


}

#endif