//==========================================================================
//
//   pq_node.h
//
//==========================================================================
// $Id: pq_node.h,v 1.11 2000/01/05 16:32:39 raitner Exp $

#ifndef PQ_NODE_H
#define PQ_NODE_H

#include <GTL/GTL.h>
#include <GTL/symlist.h>
#include <GTL/graph.h>

#include <list>
#include <iostream>

__GTL_BEGIN_NAMESPACE

class pq_tree;
class p_node;
class q_node; 
class pq_leaf;
class direction_indicator;

/**
 * @internal
 */
class GTL_EXTERN pq_node 
{
protected:
    typedef symlist<pq_node*>::iterator iterator;

    enum PQ_KIND {P_NODE, Q_NODE, LEAF, DIR};
    enum PQ_MARK {UNMARKED, QUEUED, BLOCKED, UNBLOCKED};

    pq_node (node n_, int id_) :  
	pert_children (0), pert_leaves (0), mark (UNMARKED), 
	n (n_), id (id_) { }

    virtual ~pq_node ();

    // Used to identify nodes
    virtual PQ_KIND kind () const = 0;

    // called whenever a son is known to be partial during reduction phase 
    virtual void partial (iterator) { };

    // called whenever a son is known to be full during reduction phase 
    virtual void full (iterator) { };

    // Used to write a description of this node into a GML file.
    virtual void write (ostream&, int) = 0;

    // reset node for next reduction
    virtual void clear () 
	{ mark = UNMARKED; pert_leaves = 0; pert_children = 0; }

    // type-casts 
    virtual p_node* P() = 0;
    virtual q_node* Q() = 0;
    virtual direction_indicator* D() = 0;
    virtual pq_leaf* L() = 0;

    //
    // Data used in reductions
    //

    // number of pertinent children; is calculated during bubble-up phase
    // and gets decreased whenever a pertinent child is matched in reduction 
    // phase, such that it can be assured that this node is matched _after_ all 
    // its pertinent children were correctly matched.
    int pert_children;

    // number of pertinent leaves in the subtree rooted at this node; is 
    // calculated in the reduction phase and is used to determine the root 
    // of the pertinent subtree, i.e. the last node for template matchings. 
    int pert_leaves;

    // For Q-nodes it is not acceptable to maintain father pointers for 
    // _all_ sons (cf. Booth, Luecker); fortunatly this isn't neccessary and 
    // the father pointer is only valid if is_endmost is true. For the sons of a 
    // Q-node is_endmost is only true for the first and the last son. For the 
    // sons of P-nodes ths flag is always true.
    bool is_endmost;

    // The main operations on PQ-trees are performed bottom up so each node should 
    // know its father; Because of complexity issuses this isn't always possible and 
    // thus father is valid iff is_endmost is true.
    pq_node* father;

    // Describes the role this node plays in the reduction at the moment; four states 
    // are possible:
    // 
    // (1) UNMARKED: node wasn't touched so far.
    // (2) BLOCKED: during bubble-up phase this node got queued, but as yet it 
    //     was not possible to get a valid father pointer.
    // (3) UNBLOCKED: node was touched during bubble-up and it either had a valid 
    //     father pointer or one could be borrowed from one of its siblings.
    // (4) QUEUED: node has been put into the queue.
    PQ_MARK mark;

    // list of sons.
    symlist<pq_node*> sons;

    // position in the list of sons of node's father.
    iterator pos;

    // position in the list of nodes to be cleared in reset. Each node touched in 
    // bubble-up phase is stored in the list of nodes to be cleared. As they get 
    // matched in the reduction phase they are cleared and deleted from this list.
    // But even if the reduction is successful not all nodes touched in the first 
    // phase really get matched.
    list<pq_node*>::iterator lpos;

    //
    // Application specific data (should become template parameter)
    //

    node n;
    int id;
    node up;
    int up_id;

    //
    // Friends
    //

    friend class q_node; 
    friend class p_node;
    friend class pq_tree;
    friend class planarity;

    GTL_EXTERN friend ostream& operator<< (ostream&, const pq_tree&);
};


/**
 * @internal
 */
class GTL_EXTERN p_node : public pq_node 
{
private:
    p_node (node, int);
    p_node (node, int, symlist<pq_node*>&);
    
    //
    // pq_node interface
    // 

    void partial (iterator);
    void full (iterator);
    PQ_KIND kind () const 
	{ return P_NODE; }
    void write (ostream&, int);
    void clear ();
    // type-casts 
    p_node* P()
    { return this; }
    q_node* Q()
    { assert (false); return 0; }
    direction_indicator* D()
    { assert (false); return 0; }
    pq_leaf* L()
    { assert (false); return 0; }

    //
    // Additional
    //

    // whenever a child is known to be full, it is moved from the list of 
    // sons to this list.
    symlist<pq_node*> full_sons;

    // whenever a child is known to be partial, it is moved from the list of 
    // sons to this list.
    symlist<pq_node*> partial_sons;

    // number of children
    int child_count;

    // number of partial children
    int partial_count;

    // number of full children
    int full_count;

    //
    // Friends 
    //

    friend class planarity;
    friend class pq_tree;
};


/**
 * @internal
 */
class GTL_EXTERN q_node : public pq_node 
{
private:
    q_node (node, int);

    //
    // pq_node interface
    // 

    void partial (iterator);
    void full (iterator);
    PQ_KIND kind () const 
	{ return Q_NODE; }
    void write (ostream&, int);
    void clear ();
    // type-casts 
    p_node* P()
    { assert (false); return 0; }
    q_node* Q()
    { return this; }
    direction_indicator* D()
    { assert (false); return 0; }
    pq_leaf* L()
    { assert (false); return 0; }

    //
    // Additional
    //

    // determines pert_begin and pert_end the first time a full or partial 
    // child is found.
    void pertinent (iterator);
    
    // in Q2 and Q3 matchings the sons of partial children have to be merged 
    // into the list of sons of this node at the partial node's position
    q_node* merge (iterator);
    
    // deprecated !!
    void turn (); 

    // first son full or partial viewed from the beginning of the list of sons
    iterator pert_begin;    

    // last son full or partial; usually this is the last son.
    iterator pert_end;

    // positions of the partial nodes among the sons. Normally only two partial
    // sons are allowed, but the third one is needed in planarity testing. 
    iterator partial_pos[3];

    // true when all the pertinent children are consecutive; íf false pert_begin 
    // lies in one block of pertinent children and pert_end in another, such that 
    // --pert_end is empty and between the two blocks.
    bool pert_cons;

    // number of partial children
    int partial_count;

    // number of full children
    int full_count;
    
    //
    // Friends 
    //

    friend class planarity;
    friend class pq_tree;
};


/**
 * @internal
 */
class GTL_EXTERN pq_leaf : public pq_node 
{
public:
    pq_leaf (int, int, edge, node);

private:
    PQ_KIND kind () const 
	{ return LEAF; }
    void write (ostream&, int);
    // type-casts 
    p_node* P()
    { assert (false); return 0; }
    q_node* Q()
    { assert (false); return 0; }
    direction_indicator* D()
    { assert (false); return 0; }
    pq_leaf* L()
    { return this; }
    
    //
    // Additional
    //

    int other_id;
    edge e;

    //
    // Friends 
    //

    friend class planarity;
    friend class pq_tree;
};


/**
 * @internal
 */
class direction_indicator : public pq_node 
{
private:
    direction_indicator (node n_, int id_) : pq_node (n_, id_) { };

    //
    // pq_node interface
    // 
    
    PQ_KIND kind () const 
	{ return DIR; }
    void write (ostream& os, int);
    // type-casts 
    p_node* P()
    { assert (false); return 0; }
    q_node* Q()
    { assert (false); return 0; }
    direction_indicator* D()
    { return this; }
    pq_leaf* L()
    { assert (false); return 0; }
    
    //
    // Additional
    //

    bool direction;	

    //
    // Friends 
    //

    friend class planarity;
    friend class pq_tree;
};

__GTL_END_NAMESPACE

#endif

//--------------------------------------------------------------------------
//   end of file
//--------------------------------------------------------------------------
    

Documentation generated by raitner@hyperion on Tue Mar 7 09:40:04 CET 2000
Kdoc