tree_instance.h

00001 /*
00002  *  Copyright (C) 2005 M.J. Zaki <zaki@cs.rpi.edu> Rensselaer Polytechnic Institute
00003  *  Written by parimi@cs.rpi.edu
00004  *  Updated by chaojv@cs.rpi.edu, alhasan@cs.rpi.edu, salems@cs.rpi.edu
00005  *
00006  *  This program is free software; you can redistribute it and/or
00007  *  modify it under the terms of the GNU General Public License
00008  *  as published by the Free Software Foundation; either version 2
00009  *  of the License, or (at your option) any later version.
00010  *
00011  *  This program is distributed in the hope that it will be useful,
00012  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  *  GNU General Public License for more details.
00015  *
00016  *  You should have received a copy of the GNU General Public License along
00017  *  with this program; if not, write to the Free Software Foundation, Inc.,
00018  *  59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
00019  */
00020 // struct for one instance i.e. occurrence of tree
00021 
00022 #ifndef _TREE_INSTANCE_H
00023 #define _TREE_INSTANCE_H
00024 
00025 #include <vector>
00026 #include <sstream>
00027 using namespace std;
00028 
00029 template<template<typename> class MATCH_LABEL_T, class order>
00030 class tree_instance;
00031 
00032 template<template<typename> class ST, typename T>
00033 bool cousin_test(const tree_instance<ST, T>& i1, const tree_instance<ST, T>& i2);
00034 
00035 template<template<typename> class MATCH_LABEL_T, class order>
00036 ostream& operator<< (ostream& ostr, const tree_instance<MATCH_LABEL_T, order>& inst);
00037 
00039 template<template<typename> class ST, typename T>
00040 bool cousin_test(const tree_instance<ST, proplist<ordered, T> >& i1, const tree_instance<ST, proplist<ordered, T> >& i2) {
00041   if(!i1.match_label(i2._ml))
00042     return false;
00043   
00044   if(i1.less_than(i2))
00045     return true;
00046   
00047   return false;
00048 }//end cousin_test() for unordered trees
00049 
00058 template<template<typename> class MATCH_LABEL_T, class order>
00059 class tree_instance
00060 {
00061  public:
00062   typedef MATCH_LABEL_T<int> ML;
00063   typedef tree_instance<MATCH_LABEL_T, order> TREE_INSTANCE;
00064   
00065   tree_instance() {} // default constructor
00066   
00067   tree_instance(const int& lx, const int& ux, const int& d=0, bool ind=0): _lb(lx), _ub(ux), _depth(d), _is_induced(ind) {}
00068   tree_instance(ML& ml, const int& lx, const int& ux, const int& d=0, bool ind=0): _ml(ml), _lb(lx), _ub(ux), _depth(d), _is_induced(ind) {}
00069   tree_instance(const TREE_INSTANCE& i2, const int& lx, const int& d=0, bool ind=0): _ml(i2._ml), _lb(i2._lb), _ub(i2._ub), _depth(d), _is_induced(ind)
00070     { _ml.push_back(lx);}//end constructor
00071   
00072   const int& lower() const {return _lb;}
00073   const int& upper() const {return _ub;}
00074 
00076   bool less_than(const TREE_INSTANCE& i2) const {
00077     if (_ub<i2._lb)
00078       return true;
00079     
00080     return false;
00081   }//end less_than()
00082 
00084   bool contains(const TREE_INSTANCE& i2) const {
00085     if(_lb<i2._lb && _ub>=i2._ub)
00086       return true;
00087     
00088     return false;
00089   }//end contains()
00090   
00092   bool match_label(const ML& ml2) const {
00093     if(_ml.size()!=ml2.size())
00094       return false;
00095     
00096     typename ML::const_iterator it1=_ml.begin(), it2=ml2.begin();
00097     
00098     while(it1!=_ml.end() && it2!=ml2.end()) {
00099       if(*it1 != *it2)
00100         return false;
00101       it1++;
00102       it2++;
00103     }
00104     
00105     return true;
00106   }//end match_label()
00107   
00108   friend bool cousin_test<>(const TREE_INSTANCE&, const TREE_INSTANCE&);
00109   
00110   friend ostream& operator<< <>(ostream&, const TREE_INSTANCE&);
00111   
00113   bool child_test(const TREE_INSTANCE& i2) const {
00114     if(!match_label(i2._ml))
00115       return false;
00116     
00117     if(contains(i2))
00118       return true;
00119     
00120     return false;
00121   }//end child_test()
00122   
00124   int depth_diff(const TREE_INSTANCE& i2) const
00125     { return(i2._depth - _depth);}
00126 
00127   bool induced() const { return _is_induced;}
00128 
00129   const int& depth() const { return _depth;}
00130   int get_lb()  const{ return _lb;}
00131   int get_ub() const { return _ub;}
00132   int get_depth() const {return _depth;}
00133   
00134   typename ML::const_iterator  get_ml_begin() const {return _ml.begin();}
00135   typename ML::const_iterator  get_ml_end() const {return _ml.end();}
00136    
00137   int get_ml_size() const {return _ml.size();}
00138   private:
00139   ML _ml;
00140   int _lb;
00141   int _ub;
00142   int _depth;
00143   bool _is_induced;
00144 
00145 };//end class tree_instance
00146 
00148 template<template<typename> class ST, typename T>
00149 bool cousin_test(const tree_instance<ST, T>& i1, const tree_instance<ST, T>& i2) {
00150   if(!i1.match_label(i2._ml))
00151     return false;
00152   
00153   if(i1.less_than(i2) || i2.less_than(i1))
00154     return true;
00155   
00156   return false;
00157 }//end cousin_test() for ordered trees
00158 
00159 template<template<typename> class MATCH_LABEL_T, class order>
00160 ostream& operator<< (ostream& ostr, const tree_instance<MATCH_LABEL_T, order>& inst) {
00161   ostr<<"[("<<inst._lb<<", "<<inst._ub<<") ";
00162   typename MATCH_LABEL_T<int>::const_iterator it=inst._ml.begin();
00163   while(it!=inst._ml.end())
00164     ostr<<*it++<<" ";
00165   ostr<<inst._depth<<" "<<inst._is_induced;
00166   ostr<<"]";
00167   return ostr;
00168 }//end friend operator<<
00169 
00170 #endif

Generated on Wed Jul 26 14:01:08 2006 for DMTL by  doxygen 1.4.7