pq_tree.h

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

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   pq_tree.h
//
//==========================================================================
// $Id: pq_tree.h,v 1.20 2008/02/03 18:17:08 chris Exp $

#ifndef PQ_TREE_H
#define PQ_TREE_H

#include <GTL/GTL.h>
#include <GTL/pq_node.h>
#include <GTL/embedding.h>
#include <GTL/debug.h>

#include <list>
#include <iostream>

__GTL_BEGIN_NAMESPACE
    
class GTL_EXTERN pq_tree 
{
public:
    typedef symlist<pq_node*> sons_list;

    typedef symlist<pq_node*>::iterator sons_iterator;

    pq_tree() : root(0), pert_root(0), pseudo(0), fail(0)
    {
    }
    
    pq_tree(int id, node n, const list<pq_leaf*>& le);

    ~pq_tree();

    bool reduce(list<pq_leaf*>& leaves);

    void replace_pert(int id,
                      node n,
                      const list<pq_leaf*>& le,
                      planar_embedding* em = 0,
                      list<direction_indicator>* dirs = 0);
    
    void get_frontier (planar_embedding& em, list<direction_indicator>& dirs);

    void reset ();

    pq_node* get_fail()
    {
        return fail;
    }

    bool is_fail_root()
    {
        return failed_at_root;
    }

    sons_iterator remove_dir_ind(q_node* q_fail, sons_iterator s_it);

    bool integrity_check () const;

//    p_node* insert_P (pq_node*, sons_list&);

//    q_node* insert_Q (pq_node*, sons_list&);

//    pq_leaf* insert_leaf (pq_node*);

//    void insert (pq_node*, pq_node*);
private:
    bool bubble_up (list<pq_leaf*>& leaves);
    
    void dfs(pq_node* p,
             planar_embedding& em,
             list<direction_indicator>& dirs);

    pq_node* leads_to_blocked(pq_node* le);

    
    bool leads_to(pq_node* le, pq_node* other);


    pq_node* where_bubble_up_failed(list<pq_leaf*>& leaves); 


    pq_node* blocked_in_subtree(pq_node* n);


    //
    // Template Matchings
    //

    //---------------------------------------------------------- P-Templates
    
    bool P1 (p_node* x, bool);

    bool P2 (p_node* x);

    bool P3 (p_node* x);

    bool P4 (p_node* x);

    bool P5 (p_node* x);

    bool P6 (p_node* x);

    //---------------------------------------------------------- Q-Templates
    
    bool Q1 (q_node* x, bool);

    bool Q2 (q_node* x, bool);

    bool Q3 (q_node* x);


    //
    // Data
    //

    list<pq_node*> clear_me;

    pq_node* root;

    pq_node* pert_root;

    q_node* pseudo;

    pq_node* fail;

    bool failed_at_root;

    int pert_leaves_count;

    //
    // Friends
    //

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

__GTL_END_NAMESPACE

#endif

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