WoMax Documentation

# Oracle_classes.cpp

Go to the documentation of this file.

    00001 /*-------------------------------------
    00002  * Oracle_classes.cpp
    00003  * Created on 09/03/09 by BenCello
    00004  *-------------------------------------*/
    00005
    00007
    00008 #include "Oracle_classes.hpp"
    00009
    00010 /* FO states functions */
    00011
    00012 O_state::O_state()
    00013 {
    00015         statenb = -1;
    00016         suff.first = NULL;
    00017         suff.second = -1;
    00018 }
    00019
    00020 O_state::O_state(int nb)
    00021 {
    00022         statenb = nb;
    00024         suff.first = NULL;
    00025         suff.second = -1;
    00026 }
    00027
    00028 O_state::O_state(const O_state & statein)
    00029 {
    00030         statenb = statein.statenb;
    00031         trans = statein.trans;
    00032         suff = statein.suff;
    00033         rsuff = statein.rsuff;
    00034 }
    00035
    00036 int O_state::get_statenb()
    00037 {
    00038         return statenb;
    00039 }
    00040
    00041 void O_state::set_statenb(int j)
    00042 {
    00043         statenb = j;
    00044 }
    00045
    00046 list<O_state*> O_state::get_trans()
    00047 {
    00049         return trans;
    00050 }
    00051
    00052 pair<O_state*,int> O_state::get_suffix()
    00053 {
    00054         return suff;
    00055 }
    00056
    00057 void O_state::set_suffix(O_state* suffin, int lrsin)
    00058 {
    00059         suff.first = suffin;
    00060         suff.second = lrsin;
    00061 }
    00062
    00063 list<pair<O_state*,int> > O_state::get_rsuff()
    00064 {
    00066         return rsuff;
    00067 }
    00068
    00069
    00070 // transition & suffix
    00071
    00072 void O_state::add_trans(O_state* destin)
    00073 {
    00074         trans.push_back(destin);
    00075 }
    00076
    00077 void O_state::add_rsuff(const pair<O_state*,int> & rsuffin)
    00078 {
    00079         rsuff.push_back(rsuffin);
    00080 }
    00081
    00085 O_state* O_state::rec_upSLT(list<O_state*>* path, int ctxtmin)
    00086 {
    00087         if (suff.second >= ctxtmin)
    00088         {
    00089                 path->push_front(suff.first);
    00090                 return suff.first->rec_upSLT(path, ctxtmin);
    00091         }
    00092         else
    00094                 return this;
    00095 }
    00096
    00101 list<pair<O_state*,int> >* O_state::rec_downSLT(list<pair<O_state*,int> >* SLTlist, int ctxtmin)
    00102 {
    00103         list<pair<O_state*,int> >::const_iterator rit;
    00104         for (rit = rsuff.begin(); rit != rsuff.end(); rit++)
    00105         {
    00106                 if ((*rit).second >= ctxtmin)
    00107                 {
    00108                         SLTlist->push_back((*rit));
    00109                         (*rit).first->rec_downSLT(SLTlist, ctxtmin);
    00110                 }
    00111         }
    00113         return SLTlist;
    00114 }
    00115
    00119 list<pair<O_state*,int> >* O_state::rec_sortSLT(list<pair<O_state*,int> >* SLTlist, int ctxtmin, int ctxt)
    00120 {
    00121         list<pair<O_state*,int> > sorted_rsuff = rsuff;
    00122         sorted_rsuff.sort(sort_rsuff);
    00123         list<pair<O_state*,int> >::reverse_iterator rit;
    00124         for (rit = sorted_rsuff.rbegin(); rit!=sorted_rsuff.rend(); ++rit)
    00125         {
    00126                 if ((*rit).second >= ctxtmin)
    00127                 {
    00128                         (*rit).first->rec_sortSLT(SLTlist,ctxtmin,min(ctxt,(*rit).second));
    00129                         pair<O_state*,int> node = (*rit);
    00130                         node.second=min(node.second,ctxt);
    00131                         SLTlist->push_back((node));
    00132                 }
    00133         }
    00135         return SLTlist;
    00136 }
    00137
    00141 list<pair<O_state*,int> >* O_state::sortedSLT(int ctxtmin, int nbMaxSol)
    00142 {
    00143         int NbSol;
    00144         list<pair<O_state*,int> > * solutions = new list<pair<O_state*,int> >;
    00145
    00146         rec_sortSLT(solutions,ctxtmin);
    00147         NbSol = solutions->size();
    00148
    00149         O_state * Node = this;
    00150         O_state * upNode = suff.first;
    00151         int currentCtxt = suff.second;
    00152         list<pair<O_state*,int> > sorted_rsuff;
    00153         while (NbSol<=nbMaxSol && Node->suff.second>=ctxtmin && upNode!=NULL)
    00154         {
    00155                 pair<O_state*,int> father = Node->suff;
    00156                 currentCtxt=father.second;
    00157                 solutions->push_back(father);
    00158                 sorted_rsuff = upNode->rsuff;
    00159                 sorted_rsuff.sort(sort_rsuff);
    00160                 list<pair<O_state*,int> >::reverse_iterator rit;
    00161                 for (rit = sorted_rsuff.rbegin(); (*rit).first!=Node; ++rit)
    00162                 {
    00163                         pair<O_state*,int> brother = (*rit);
    00164                         brother.second=currentCtxt;
    00165                         solutions->push_back(brother);
    00166                         (*rit).first->rec_sortSLT(solutions, ctxtmin, currentCtxt);
    00167                 }
    00168                 NbSol = solutions->size();
    00169                 if (NbSol>=nbMaxSol)
    00170                         break;
    00171                 else
    00172                 {
    00173                         for (++rit; rit!=sorted_rsuff.rend(); ++rit)
    00174                         {
    00175                                 pair<O_state*,int> brother = (*rit);
    00176                                 if (brother.second>=ctxtmin)
    00177                                 {
    00178                                         brother.second=min(brother.second,currentCtxt);
    00179                                         solutions->push_back(brother);
    00180                                         (*rit).first->rec_sortSLT(solutions, ctxtmin, min(brother.second,currentCtxt));
    00181                                 }
    00182                                 NbSol = solutions->size();
    00183                                 if (NbSol>=nbMaxSol)
    00184                                         break;
    00185                         }
    00186                 }
    00187                 upNode = upNode->suff.first;
    00188                 Node = Node->suff.first;
    00189         }
    00190         return solutions;
    00191 }
    00192
    00193
    00194 // operators overload
    00195
    00197
    00205 ostream & operator<< (ostream & out, O_state & statein)
    00206 {
    00207         list<O_state*>::const_iterator transit;
    00208         out<<"  {"<<endl;
    00209         out<<"          "<<statein.statenb<<endl;
    00210         for (transit = statein.trans.begin(); transit != statein.trans.end(); transit++)
    00211         {
    00212                 if (transit == statein.trans.begin())
    00213                         out<<"          "<<statein.statenb<<" -> "<<(*transit)->get_statenb()<<endl;
    00214                 else
    00215                         out<<"          "<<statein.statenb<<" -> "<<(*transit)->get_statenb()<<" [constraint = false]"<<endl;
    00216         }
    00217         out<<"          "<<endl;
    00218         if (statein.get_suffix().first != NULL)
    00219                 out<<"          "<<statein.statenb<<" -> "<<statein.suff.first->get_statenb()<<" [constraint = false, style = dotted]"<<endl;
    00220         out<<"  }"<<endl;
    00221         return(out);
    00222 }
    00223
    00224
    00225 bool sort_rsuff (pair<O_state*,int> rsuff1, pair<O_state*,int> rsuff2)
    00226 {
    00227         if (rsuff1.second==rsuff2.second)
    00228                 return ((rsuff1.first->get_statenb())<(rsuff2.first->get_statenb()));
    00229         else
    00230                 return (rsuff1.second<rsuff2.second);
    00231 }
    00232
    00233 /* FO functions */
    00234
    00235 O_oracle::O_oracle()
    00236 {
    00238         size = -1;
    00239 }
    00240
    00242 O_oracle::~O_oracle()
    00243 {
    00244         vector<O_state*>::iterator O_it;
    00245         for(O_it = state_vect.begin();O_it != state_vect.end();O_it++)
    00246                 delete *O_it;
    00247 }
    00248
    00250 void O_oracle::freestates()
    00251 {
    00252         vector<O_state*>::reverse_iterator O_it;
    00253         for(O_it = state_vect.rbegin();O_it != state_vect.rend();++O_it)
    00254         {
    00255                 delete *O_it;
    00256                 state_vect.pop_back();
    00257         }
    00258         size = state_vect.size();
    00259 }
    00260
    00261 int O_oracle::get_size()
    00262 {
    00263         return state_vect.size();
    00264 }
    00265
    00266 // initialisation
    00268 void O_oracle::start()
    00269 {
    00270         if(size <= 0)
    00271         {
    00272                 O_state * newstate = new O_state(0);
    00273                 state_vect.push_back(newstate);
    00274                 size = state_vect.size();
    00275         }
    00276 }
    00277
    00278 // operators overload
    00280 O_state * O_oracle::operator[] (int i) const
    00281 {
    00282         if (this!= NULL && size>0 && i<size)
    00283                 return(state_vect[i]);
    00284         else
    00285                 return NULL;
    00286 }
    00287
    00289
    00299 ostream & operator<< (ostream & out, const O_oracle & oraclein)
    00300 {
    00301         vector<O_state*>::const_iterator O_it;
    00302
    00303         out<<"digraph Oracle"<<endl;
    00304         out<<"{"<<endl;
    00305         out<<"  graph [rankdir=LR];"<<endl;
    00306         out<<"  node [shape=circle];"<<endl;
    00307         out<<"  nodesep = 0.2;"<<endl<<endl;
    00308
    00309         for(O_it = oraclein.state_vect.begin(); O_it != oraclein.state_vect.end(); O_it++)
    00310                 out<<**O_it<<endl;
    00311
    00312         out<<"}"<<endl;
    00313         return(out);
    00314 }
    00315