pq_node.h

Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file pq_node.h

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   pq_node.h
//
//==========================================================================
// $Id: pq_node.h,v 1.15 2003/04/03 11:48:26 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;

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

    virtual PQ_KIND kind() const = 0;

    virtual void partial(iterator)
    {
    }

    virtual void full(iterator)
    {
    }

    virtual void write(ostream&, int) = 0;

    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
    //

    int pert_children;

    int pert_leaves;

    bool is_endmost;

    pq_node* father;

    PQ_MARK mark;

    symlist<pq_node*> sons;

    iterator pos;

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


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
    //

    symlist<pq_node*> full_sons;

    symlist<pq_node*> partial_sons;

    int child_count;

    int partial_count;

    int full_count;

    //
    // Friends 
    //

    friend class planarity;

    friend class pq_tree;

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


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
    //

    void pertinent(iterator);
    
    q_node* merge (iterator);
    
    void turn (); 

    iterator pert_begin;    

    iterator pert_end;

    iterator partial_pos[3];

    bool pert_cons;

    int partial_count;

    int full_count;
    
    //
    // Friends 
    //

    friend class planarity;

    friend class pq_tree;
};


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


class GTL_EXTERN 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
//--------------------------------------------------------------------------