00001 #include "unification.h"
00002 #include "exception.h"
00003 #include "display.h"
00004 #include "parser.h"
00005 #include "config.h"
00006 #include "automata.h"
00007 #include <math.h>
00008 #include <typeinfo>
00009
00010
00011 bool Automata::isIntersect(Automata *au,int size)
00012 {
00013 int *mask1 = this->si->step.front()->bits;
00014 int *mask2 = au->si->step.front()->bits;
00015 int i;
00016 for(i=0;i<size;i++)
00017 if((mask1[i]!=-1)&&(mask2[i]!=-1))
00018 return true;
00019 return false;
00020 }
00021
00022 State::State(int v, bool s,Automata *a)
00023 {
00024 automata = a;
00025 value = v;
00026 si = s;
00027 }
00028
00029 void State::addTransition(Transition* t)
00030 {
00031 step.push_back(t);
00032 }
00033
00034 void State::display(ostream &o)
00035 {
00036 if (si)
00037 o << "INITIAL STATE" << endl;
00038 else
00039 o << "State : " << value << endl;
00040 }
00041
00042 Transition::Transition(State* next, int* b)
00043 {
00044 st = next;
00045 bits = b;
00046 }
00047
00048 void Transition::display(int bits_size)
00049 {
00050 (*mycout) << " BITS : ";
00051 for (int j=0 ; j < bits_size ; j++) {
00052 if (bits[j] == -1 ) {
00053 (*mycout) << "?";
00054 } else {
00055 (*mycout) << bits[j];
00056 }
00057 }
00058 (*mycout) << endl;
00059 }
00060
00069 Automata::Automata(Condition* n, std::map <int, int>* numvars) {
00070
00071 if(typeid(*n)==typeid(CondA)) {
00072 #ifdef DEBUG
00073 (*mycout) << "CondA" << " de type : " << typeid (*n).name() << endl;
00074 #endif
00075 cvalue = ((CondA*)n)->a;
00076 a.push_back(1);
00077 nvars = 1;
00078 } else if(typeid(*n)==typeid(CondANplusB)) {
00079 #ifdef DEBUG
00080 (*mycout) << "CondANplusB" << " de type : " << typeid (*n).name() << endl;
00081 #endif
00082 cvalue = ((CondANplusB*)n)->b;
00083 nvars = 2;
00084 a.push_back(1);
00085 a.push_back(- ((CondANplusB*)n)->a );
00086 } else if(typeid(*n)==typeid(CondNplusN)) {
00087 #ifdef DEBUG
00088 (*mycout) << "CondNplusN" << " de type : " << typeid (*n).name() << endl;
00089 #endif
00090 cvalue = 0;
00091 nvars = 3;
00092 a.push_back(1);
00093 a.push_back(-1);
00094 a.push_back(-1);
00095 } else {
00096 #ifdef DEBUG
00097 (*mycout) << "CondN" << " de type : " << typeid (*n).name() << endl;
00098 #endif
00099 cvalue = 0;
00100 nvars = 2;
00101 a.push_back(1);
00102 a.push_back(-1);
00103 }
00104
00112 si = new State(INT_MIN, true,this);
00113 State* final_st = new State(cvalue, false,this);
00114 vector<State*> table_of_st;
00115 table_of_st.push_back(final_st);
00116 list<State*> active_st;
00117 active_st.push_back(final_st);
00118 int bits_size = numvars->size();
00119
00120 while(!active_st.empty()) {
00121 State* tmpst = active_st.front();
00122 active_st.pop_front();
00123 #ifdef DEBUG
00124 (*mycout) << "I just poped : ";
00125 tmpst->display(*mycout);
00126 #endif
00127 for (int i = 0 ; i < (pow(2.f, nvars)) ; i++){
00128 int decal = i;
00129 int* bits;
00130 bits = new int[bits_size];
00131 int *prebits = new int[nvars];
00132 for (int j=0 ; j < nvars ; j++) {
00133 prebits[j] = (0x0001 & decal);
00134
00135 decal = decal >> 1;
00136
00137
00138 }
00139
00140 for (int k=0 ; k < bits_size ; k++) bits[k] = -1;
00141
00142 if(typeid(*n)==typeid(CondA)) {
00143 bits[((*numvars)[n->n1->id])] = prebits[0];
00144 } else if(typeid(*n)==typeid(CondANplusB)) {
00145 bits[((*numvars)[n->n1->id])] = prebits[0];
00146 bits[((*numvars)[((CondANplusB*)n)->n2->id])] = prebits[1];
00147 } else if(typeid(*n)==typeid(CondNplusN)) {
00148 bits[((*numvars)[n->n1->id])] = prebits[0];
00149 bits[((*numvars)[((CondNplusN*)n)->n2->id])] = prebits[1];
00150 bits[((*numvars)[((CondNplusN*)n)->n3->id])] = prebits[2];
00151 } else {
00152 bits[((*numvars)[n->n1->id])] = prebits[0];
00153 bits[((*numvars)[((CondN*)n)->n2->id])] = prebits[1];
00154 }
00155
00156 #ifdef DEBUG
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171 #endif
00172
00173 int ab;
00174 if(typeid(*n)==typeid(CondA)) {
00175 ab = - (a[0]*bits[(*numvars)[n->n1->id]]);
00176 } else if(typeid(*n)==typeid(CondANplusB)) {
00177 ab = - (a[0]*bits[(*numvars)[n->n1->id]] +
00178 a[1]*bits[(*numvars)[((CondANplusB*)n)->n2->id]]);
00179 } else if(typeid(*n)==typeid(CondNplusN)) {
00180 ab = -(a[0]*bits[(*numvars)[n->n1->id]] +
00181 a[1]*bits[(*numvars)[((CondNplusN*)n)->n2->id]] +
00182 a[2]*bits[(*numvars)[((CondNplusN*)n)->n3->id]]);
00183 } else {
00184 ab = -(a[0]*bits[(*numvars)[n->n1->id]] +
00185 a[1]*bits[(*numvars)[((CondN*)n)->n2->id]]);
00186 }
00187 #ifdef DEBUG
00190 #endif
00191
00192 if (ab == tmpst->value) {
00193 Transition* tr = new Transition(tmpst,bits);
00194 si->addTransition(tr);
00195 #ifdef DEBUG
00196 (*mycout) << "Link to initial" << endl;
00197 (*mycout) << " si -> " << tmpst->value << endl;
00198 tr->display(bits_size);
00199 #endif
00200 }
00201
00202 double g0;
00203 if(typeid(*n)==typeid(CondA)) {
00204 g0 = ((double)(tmpst->value - (a[0]*bits[(*numvars)[n->n1->id]])) ) / 2;
00205 } else if(typeid(*n)==typeid(CondANplusB)) {
00206 g0 = ((double)(tmpst->value - (a[0]*bits[(*numvars)[n->n1->id]] +
00207 a[1]*bits[(*numvars)[((CondANplusB*)n)->n2->id]])) ) / 2;
00208 } else if(typeid(*n)==typeid(CondNplusN)) {
00209 g0 = (double)(tmpst->value - (a[0]*bits[(*numvars)[n->n1->id]] +
00210 a[1]*bits[(*numvars)[((CondNplusN*)n)->n2->id]] +
00211 a[2]*bits[(*numvars)[((CondNplusN*)n)->n3->id]])) / 2;
00212 } else {
00213 g0 = (double)(tmpst->value - (a[0]*bits[(*numvars)[n->n1->id]] +
00214 a[1]*bits[(*numvars)[((CondN*)n)->n2->id]])) / 2;
00215 }
00216 #ifdef DEBUG
00218 #endif
00219
00220 double double_g0;
00221 if (!modf(g0, &double_g0)) {
00222 int int_g0 = int(double_g0);
00223 bool found = false;
00224
00225 vector<State*>::iterator my_it = table_of_st.begin();
00226 while (my_it != table_of_st.end()) {
00227 if ((*my_it)->value == int_g0) {
00228 found = true;
00229 Transition* tr = new Transition(tmpst,bits);
00230 (*my_it)->addTransition(tr);
00231 #ifdef DEBUG
00232 (*mycout) << " " << (*my_it)->value << " -> " << tmpst->value << endl;
00233 tr->display(bits_size);
00234 #endif
00235 }
00236 my_it++;
00237 }
00238
00239
00240 if (!found) {
00241 State* newst = new State(int_g0,false,this);
00242 table_of_st.push_back(newst);
00243 active_st.push_back(newst);
00244 Transition* tr = new Transition(tmpst,bits);
00245 newst->addTransition(tr);
00246 #ifdef DEBUG
00247 (*mycout) << " " << newst->value << " -> " << tmpst->value << endl;
00248 tr->display(bits_size);
00249 #endif
00250 }
00251 }
00252
00253 }
00254 }
00255 }
00256
00257 Automata::Automata(Condition* n) {
00258 }
00259
00260 Automata::~Automata(){
00261 }
00262
00263 void Automata::display(ostream &o) {
00264 o << "Automata of value : " << cvalue << " and with a : ";
00265 si->display(*mycout);
00266 }
00267
00268