Oracle_classes.cpp

Go to the documentation of this file.

/*-------------------------------------
 * Oracle_classes.cpp
 * Created on 09/03/09 by BenCello
 *-------------------------------------*/


#include "Oracle_classes.hpp"

/* FO states functions */

O_state::O_state()
{
        statenb = -1;
        suff.first = NULL;
        suff.second = -1;
}

O_state::O_state(int nb)
{
        statenb = nb;
        suff.first = NULL;
        suff.second = -1;
}

O_state::O_state(const O_state & statein)
{
        statenb = statein.statenb;
        trans = statein.trans;
        suff = statein.suff;
        rsuff = statein.rsuff;
}

int O_state::get_statenb()
{
        return statenb;
}

void O_state::set_statenb(int j)
{
        statenb = j;
}

list<O_state*> O_state::get_trans()
{
        return trans;
}

pair<O_state*,int> O_state::get_suffix()
{
        return suff;
}

void O_state::set_suffix(O_state* suffin, int lrsin)
{
        suff.first = suffin;
        suff.second = lrsin;
}

list<pair<O_state*,int> > O_state::get_rsuff()
{
        return rsuff;
}


// transition & suffix

void O_state::add_trans(O_state* destin)
{
        trans.push_back(destin);
}

void O_state::add_rsuff(const pair<O_state*,int> & rsuffin)
{
        rsuff.push_back(rsuffin);
}

O_state* O_state::rec_upSLT(list<O_state*>* path, int ctxtmin)
{
        if (suff.second >= ctxtmin)
        {
                path->push_front(suff.first);
                return suff.first->rec_upSLT(path, ctxtmin);
        }
        else
                return this;
}

list<pair<O_state*,int> >* O_state::rec_downSLT(list<pair<O_state*,int> >* SLTlist, int ctxtmin)
{
        list<pair<O_state*,int> >::const_iterator rit;
        for (rit = rsuff.begin(); rit != rsuff.end(); rit++)
        {
                if ((*rit).second >= ctxtmin)
                {
                        SLTlist->push_back((*rit));
                        (*rit).first->rec_downSLT(SLTlist, ctxtmin);
                }
        }
        return SLTlist;
}

list<pair<O_state*,int> >* O_state::rec_sortSLT(list<pair<O_state*,int> >* SLTlist, int ctxtmin, int ctxt)
{
        list<pair<O_state*,int> > sorted_rsuff = rsuff;
        sorted_rsuff.sort(sort_rsuff);
        list<pair<O_state*,int> >::reverse_iterator rit;
        for (rit = sorted_rsuff.rbegin(); rit!=sorted_rsuff.rend(); ++rit)
        {
                if ((*rit).second >= ctxtmin)
                {
                        (*rit).first->rec_sortSLT(SLTlist,ctxtmin,min(ctxt,(*rit).second));
                        pair<O_state*,int> node = (*rit);
                        node.second=min(node.second,ctxt);
                        SLTlist->push_back((node));
                }
        }
        return SLTlist;
}

list<pair<O_state*,int> >* O_state::sortedSLT(int ctxtmin, int nbMaxSol)
{
        int NbSol;
        list<pair<O_state*,int> > * solutions = new list<pair<O_state*,int> >;
        
        rec_sortSLT(solutions,ctxtmin);
        NbSol = solutions->size();
        
        O_state * Node = this;
        O_state * upNode = suff.first;
        int currentCtxt = suff.second;
        list<pair<O_state*,int> > sorted_rsuff;
        while (NbSol<=nbMaxSol && Node->suff.second>=ctxtmin && upNode!=NULL)
        {
                pair<O_state*,int> father = Node->suff;
                currentCtxt=father.second;
                solutions->push_back(father);
                sorted_rsuff = upNode->rsuff;
                sorted_rsuff.sort(sort_rsuff);
                list<pair<O_state*,int> >::reverse_iterator rit;
                for (rit = sorted_rsuff.rbegin(); (*rit).first!=Node; ++rit)
                {
                        pair<O_state*,int> brother = (*rit);
                        brother.second=currentCtxt;
                        solutions->push_back(brother);
                        (*rit).first->rec_sortSLT(solutions, ctxtmin, currentCtxt);
                }
                NbSol = solutions->size();
                if (NbSol>=nbMaxSol)
                        break;
                else
                {
                        for (++rit; rit!=sorted_rsuff.rend(); ++rit)
                        {
                                pair<O_state*,int> brother = (*rit);
                                if (brother.second>=ctxtmin)
                                {
                                        brother.second=min(brother.second,currentCtxt);
                                        solutions->push_back(brother);
                                        (*rit).first->rec_sortSLT(solutions, ctxtmin, min(brother.second,currentCtxt));
                                }
                                NbSol = solutions->size();
                                if (NbSol>=nbMaxSol)
                                        break;
                        }
                }
                upNode = upNode->suff.first;
                Node = Node->suff.first;
        }
        return solutions;
}


// operators overload


ostream & operator<< (ostream & out, O_state & statein)
{
        list<O_state*>::const_iterator transit;
        out<<"  {"<<endl;
        out<<"          "<<statein.statenb<<endl;
        for (transit = statein.trans.begin(); transit != statein.trans.end(); transit++)
        {
                if (transit == statein.trans.begin())
                        out<<"          "<<statein.statenb<<" -> "<<(*transit)->get_statenb()<<endl;
                else
                        out<<"          "<<statein.statenb<<" -> "<<(*transit)->get_statenb()<<" [constraint = false]"<<endl;
        }
        out<<"          "<<endl;
        if (statein.get_suffix().first != NULL)
                out<<"          "<<statein.statenb<<" -> "<<statein.suff.first->get_statenb()<<" [constraint = false, style = dotted]"<<endl;
        out<<"  }"<<endl;
        return(out);
}


bool sort_rsuff (pair<O_state*,int> rsuff1, pair<O_state*,int> rsuff2)
{
        if (rsuff1.second==rsuff2.second)
                return ((rsuff1.first->get_statenb())<(rsuff2.first->get_statenb()));
        else
                return (rsuff1.second<rsuff2.second);
}

/* FO functions */

O_oracle::O_oracle()
{
        size = -1;
}

O_oracle::~O_oracle()
{
        vector<O_state*>::iterator O_it;
        for(O_it = state_vect.begin();O_it != state_vect.end();O_it++)
                delete *O_it;
}

void O_oracle::freestates()
{
        vector<O_state*>::reverse_iterator O_it;
        for(O_it = state_vect.rbegin();O_it != state_vect.rend();++O_it)
        {
                delete *O_it;
                state_vect.pop_back();
        }
        size = state_vect.size();
}

int O_oracle::get_size()
{
        return state_vect.size();
}

// initialisation
void O_oracle::start()
{
        if(size <= 0)
        {
                O_state * newstate = new O_state(0);
                state_vect.push_back(newstate);
                size = state_vect.size();
        }
}

// operators overload
O_state * O_oracle::operator[] (int i) const
{
        if (this!= NULL && size>0 && i<size)
                return(state_vect[i]);
        else
                return NULL;
}


ostream & operator<< (ostream & out, const O_oracle & oraclein)
{       
        vector<O_state*>::const_iterator O_it;
        
        out<<"digraph Oracle"<<endl;
        out<<"{"<<endl;
        out<<"  graph [rankdir=LR];"<<endl;
        out<<"  node [shape=circle];"<<endl;
        out<<"  nodesep = 0.2;"<<endl<<endl;
                
        for(O_it = oraclein.state_vect.begin(); O_it != oraclein.state_vect.end(); O_it++)
                out<<**O_it<<endl;
        
        out<<"}"<<endl;
        return(out);
}