NodoTrieS.cpp

Ir a la documentación de este archivo.
00001 // vim: set expandtab tabstop=8 shiftwidth=8 foldmethod=marker:
00044 #include <iostream>
00045 #include <iomanip>
00046 #include <list>
00047 #include <vector>
00048 #include <set>
00049 #include <fstream>
00050 #include <istream>
00051 #include <sstream>
00052 
00053 using namespace std;
00054 
00055 #include "Pos.hpp"
00056 #include "NodoTrieS.hpp"
00057 
00058 
00059 NodoTrieS::NodoTrieS(string cad, NodoTrieS *hijo_menor,
00060                      NodoTrieS *hermano_mayor, set<Pos> cpos)
00061 {
00062         ASSERT(cad.size() <= MAXCAD);
00063         this->cad = cad;
00064         this->hijo_menor = hijo_menor;
00065         this->hermano_mayor = hermano_mayor;
00066         this->cpos = cpos;
00067 }
00068 
00069 
00075 NodoTrieS::NodoTrieS(string cad, NodoTrieS *hijo_menor,
00076                      NodoTrieS *hermano_mayor, Pos p)
00077 {
00078         ASSERT(cad.size() <= MAXCAD);
00079         this->cad = cad;
00080         this->hijo_menor = hijo_menor;
00081         this->hermano_mayor = hermano_mayor;
00082         if (p.numd >= 0 && p.numb >= 0) {
00083                 cpos.insert(p);
00084         }
00085 }
00086 
00087 
00088 NodoTrieS::~NodoTrieS()
00089 {
00090         //cerr << "Elimina cad=" << cad <<endl;
00091         cad.clear();
00092         delete hijo_menor;
00093         delete hermano_mayor;
00094         cpos.clear();
00095 }
00096 
00097 
00101 set<Pos>
00102         NodoTrieS::busca(string pal)
00103 {
00104 
00105         if (cad.size()==pal.size() && cad == pal) {
00106                 return cpos;
00107         } else if (cad.size()<pal.size() &&
00108                         pal.substr(0, cad.size())==cad
00109                         && hijo_menor!=NULL) {
00110                 return hijo_menor->busca(pal.substr(cad.size()));
00111         } else if (cad < pal && hermano_mayor!=NULL) {
00112                 return hermano_mayor->busca(pal);
00113         }
00114         return set<Pos>();
00115 }
00116 
00117 
00138 void
00139 NodoTrieS::inserta(string pal, Pos p)
00140 {
00141         ASSERT(pal != "");
00142         ASSERT(pal.size() <= MAXCAD);
00143         ASSERT(p.numd >= 0 && p.numb >= 0);
00144 
00145         //cerr << "OJO " << "inserta("<< pal << ", "<< p << ")" << endl;
00146         if (pal == cad) {
00147                 //cerr << "  OJO pal == cad"<<endl;
00148                 cpos.insert(p);
00149                 return;
00150         }
00151         string pcml = prefijo_comun_mas_largo(pal, cad);
00152         if (pcml != "") {
00153                 string rcad = cad.substr(pcml.size());
00154                 string rpal = pal.substr(pcml.size());
00155                 //cerr << "  OJO pcml=" << pcml << ", rcad=" << rcad << ", rpal=" << rpal << endl;
00156                 if (rcad == "") {
00157                         //cerr << "  OJO rcad == ''" << endl;
00158                         if (hijo_menor==NULL) {
00159                                 hijo_menor = new
00160                                              NodoTrieS(rpal, NULL, NULL, p);
00161                         } else {
00162                                 hijo_menor->inserta(rpal, p);
00163                         }
00164                         return;
00165                 } else if (rpal == "") {
00166                         //cerr << "    OJO rpal == ''" << endl;
00167 
00168                         NodoTrieS *nhijo = new NodoTrieS(rcad, hijo_menor,
00169                                                          NULL, cpos);
00170                         cad = pcml;
00171                         hijo_menor = nhijo;
00172                         /* hermano_mayor igual */
00173                         cpos.clear();
00174                         cpos.insert(p);
00175                         return;
00176                 } else  if (rcad < rpal) {
00177                         //cerr << "    OJO rcad<rpal" << endl;
00178                         NodoTrieS *nh2=new NodoTrieS(rpal, NULL, NULL, p);
00179                         NodoTrieS *nh1=new NodoTrieS(rcad, hijo_menor,
00180                                                      nh2, cpos);
00181                         cad = pcml;
00182                         hijo_menor = nh1;
00183                         /* hermano_mayor igual */
00184                         cpos.clear();
00185                         return;
00186                 } else { /* rpal<rcad */
00187                         //cerr << "    OJO rpal<rcad" << endl;
00188                         NodoTrieS *nh2=new NodoTrieS(rcad, hijo_menor,
00189                                                      NULL, cpos);
00190                         NodoTrieS *nh1=new NodoTrieS(rpal, NULL, nh2, p);
00191 
00192                         cad = pcml;
00193                         hijo_menor = nh1;
00194                         /* hermano_mayor igual */
00195                         cpos.clear();
00196                         return;
00197                 }
00198         } else { /* pcml == "" */
00199                 //cerr << "  OJO pcml == ''" << endl;
00200                 if (pal < cad) {
00201                         //cerr << "    OJO pal<cad" << endl;
00202                         NodoTrieS *nh = new NodoTrieS(cad, hijo_menor,
00203                                                       hermano_mayor, cpos);
00204                         cad = pal;
00205                         hijo_menor = NULL;
00206                         hermano_mayor = nh;
00207                         cpos.clear();
00208                         cpos.insert(p);
00209                         return;
00210                 }
00211                 /* cad<pal */
00212                 else if (hermano_mayor==NULL) {
00213                         //cerr << "    OJO cad<pal y h_m==NULL" << endl;
00214                         if (cad == "") {
00215                                 ASSERT(hijo_menor==NULL);
00216                                 /* Primer nodo del árbol después de crear
00217                                  * con constructora por defecto.
00218                                  */
00219                                 //cerr << "    OJO estaba vacío" << endl;
00220                                 cad = pal;
00221                                 cpos.insert(p);
00222                                 return;
00223                         }
00224                         NodoTrieS *nh = new NodoTrieS(pal, NULL, NULL, p);
00225                         hermano_mayor = nh;
00226                         return;
00227                 } else { /* cad<pal y hermano_mayor!=NULL */
00228                         //cerr << "    OJO cad<pal y h_m!=NULL" << endl;
00229                         hermano_mayor->inserta(pal, p);
00230                         return;
00231                 }
00232         }
00233 }
00234 
00235 
00236 void
00237 NodoTrieS::aDotty(std::ostream &os, string pref, bool primero, bool mayor)
00238 {
00239         static int numcluster = 0;
00240         if (primero) {
00241                 os << "digraph \"rdsgc\" {" << endl << endl;
00242                 os << "    rankdir=LR;" << endl;
00243         }
00244         if (cad != "") {
00245                 if (mayor) {
00246                         NodoTrieS *n = this;
00247                         while (n!=NULL) {
00248                                 os << '"' << pref << n->cad
00249                                 << "\" [label=\"" << n->cad
00250                                 << " " << n->cpos << "\"]" << endl;
00251                                 n = n->hermano_mayor;
00252                         }
00253                         n = this->hermano_mayor;
00254                         if (n!=NULL) {
00255                                 numcluster++;
00256                                 os << "subgraph cluster" << numcluster
00257                                 << " {"<<endl;
00258                                 NodoTrieS *a = this;
00259                                 while (n!=NULL) {
00260                                         os << '"' << pref << a->cad <<
00261                                         "\" -> \"" << pref
00262                                         << n->cad << "\" [color=\"red\"]"
00263                                         << endl;
00264                                         a = n;
00265                                         n = n->hermano_mayor;
00266                                 }
00267                                 os << "}" << endl << endl;
00268                         }
00269                 }
00270                 if (hijo_menor!=NULL) {
00271                         os << '"' << pref << cad << "\" -> \""
00272                         << pref << cad << hijo_menor->cad
00273                         << '"' << endl;
00274                         hijo_menor->aDotty(os, pref+cad, false, true);
00275                 }
00276                 if (hermano_mayor!=NULL) {
00277                         hermano_mayor->aDotty(os, pref, false, false);
00278                 }
00279         } else {
00280                 throw "  # Nodo con cadena vacía no procesado";
00281         }
00282         if (primero) {
00283                 os << "}" << endl;
00284         }
00285 }
00286 
00287 string
00288 NodoTrieS::preorden()
00289 {
00290         string r = cad;
00291 
00292         if (hijo_menor!=NULL) {
00293                 r+=hijo_menor->preorden();
00294         }
00295         if (hermano_mayor!=NULL) {
00296                 r+=hermano_mayor->preorden();
00297         }
00298         return r;
00299 }
00300 
00301 
00309 NodoTrieS *
00310 mezcla(NodoTrieS *a1, NodoTrieS *a2)
00311 {
00312         NodoTrieS *n1, *n2, *t;
00313         NodoTrieS *res = NULL;
00314         NodoTrieS **r=&res;
00315         string c;
00316 
00317         while (a1!=NULL || a2!=NULL) {
00318                 c = "";
00319                 if (a1!=NULL && a2!=NULL) {
00320                         c = prefijo_comun_mas_largo(a1->cad, a2->cad);
00321                 }
00322                 //cerr << " prefijo c="<<c<<endl;
00323                 if (c == "") {
00324                         if (a2==NULL || (a1!=NULL && a1->cad<a2->cad)) {
00325                                 //cerr << "a1 primero" <<endl;
00326                                 *r = new NodoTrieS(a1->cad, a1->hijo_menor,
00327                                                    NULL, a1->cpos);
00328                                 r=&((*r)->hermano_mayor);
00329                                 t = a1;
00330                                 a1=a1->hermano_mayor;
00331                                 t->hijo_menor = NULL;
00332                                 t->hermano_mayor = NULL;
00333                                 delete t;
00334                         } else { /*a2!=NULL && (a1==NULL || a2->cad < a1->cad) */
00335                                 //cerr << "a2 primero" <<endl;
00336                                 *r = new NodoTrieS(a2->cad, a2->hijo_menor,
00337                                                    NULL, a2->cpos);
00338                                 r=&((*r)->hermano_mayor);
00339                                 t = a2;
00340                                 a2=a2->hermano_mayor;
00341                                 t->hijo_menor = NULL;
00342                                 t->hermano_mayor = NULL;
00343                                 delete t;
00344                         }
00345                 } else if (a1->cad == a2->cad) { // c != "" && a1!=NULL && a2!=NULL
00346                         //cerr << "iguales" <<endl;
00347                         set<Pos> cpos;
00348                         insert_iterator<set<Pos> >
00349                         cpos_ins(cpos, cpos.begin());
00350 
00351                         NodoTrieS *m = mezcla(a1->hijo_menor, a2->hijo_menor);
00352                         a1->hijo_menor = NULL;
00353                         a2->hijo_menor = NULL;
00354                         set_union(a1->cpos.begin(), a1->cpos.end(),
00355                                   a2->cpos.begin(), a2->cpos.end(),
00356                                   cpos_ins);
00357                         /* http://h30097.www3.hp.com/cplus/set_union_3c__std.htm*/
00358                         *r = new NodoTrieS(a1->cad, m, NULL, cpos);
00359                         r=&((*r)->hermano_mayor);
00360                         t = a1;
00361                         a1=a1->hermano_mayor;
00362                         t->hermano_mayor = NULL;
00363                         delete t;
00364                         t = a2;
00365                         a2=a2->hermano_mayor;
00366                         t->hermano_mayor = NULL;
00367                         delete t;
00368                 } else { // c != "" && a1!=NULL && a2!=NULL && a1->cad != a2->cad
00369                         string r1=a1->cad.substr(c.size());
00370                         string r2=a2->cad.substr(c.size());
00371                         ASSERT(r1!="" || r2!="");
00372                         //cerr << "hay posfijo r1="<<r1<<" r2="<<r2<<endl;
00373                         if (r1=="") {
00374                                 //cerr << "r1 vacio"<<endl;
00375                                 a2->cad = r2;
00376                                 n2=a2;
00377                                 a2=a2->hermano_mayor;
00378                                 n2->hermano_mayor = NULL;
00379                                 NodoTrieS *m = mezcla(a1->hijo_menor, n2);
00380                                 a1->hijo_menor = NULL;
00381                                 n2=NULL;
00382                                 *r = new NodoTrieS(c, m, NULL, a1->cpos);
00383                                 r=&((*r)->hermano_mayor);
00384                                 t = a1;
00385                                 a1=a1->hermano_mayor;
00386                                 t->hermano_mayor = NULL;
00387                                 t->hijo_menor = NULL;
00388                                 delete t;
00389                         } else if (r2=="") {
00390 
00391                                 //cerr << "r2 vacio"<<endl;
00392                                 n1=a1;
00393                                 a1=a1->hermano_mayor;
00394                                 n1->cad = r1;
00395                                 n1->hermano_mayor = NULL;
00396                                 NodoTrieS *m = mezcla(n1, a2->hijo_menor);
00397                                 n1=NULL;
00398                                 a2->hijo_menor = NULL;
00399                                 *r = new NodoTrieS(c, m, NULL, a2->cpos);
00400                                 r=&((*r)->hermano_mayor);
00401                                 t = a2;
00402                                 a2=a2->hermano_mayor;
00403                                 t->hermano_mayor = NULL;
00404                                 t->hijo_menor = NULL;
00405                                 delete t;
00406                         } else if (r1 < r2) {
00407                                 //cerr << "r1<r2"<<endl;
00408                                 a1->cad = r1;
00409                                 a2->cad = r2;
00410                                 n1=a1;
00411                                 a1=a1->hermano_mayor;
00412                                 n2=a2;
00413                                 a2=a2->hermano_mayor;
00414                                 n2->hermano_mayor = NULL;
00415                                 n1->hermano_mayor = n2;
00416                                 *r = new NodoTrieS(c, n1, NULL, set<Pos>());
00417                                 r=&((*r)->hermano_mayor);
00418                         } else { /* r2<r1 */
00419                                 //cerr << "r2<r1"<<endl;
00420                                 a1->cad = r1;
00421                                 a2->cad = r2;
00422                                 n1=a1;
00423                                 a1=a1->hermano_mayor;
00424                                 n2=a2;
00425                                 a2=a2->hermano_mayor;
00426                                 n2->hermano_mayor = n1;
00427                                 n1->hermano_mayor = NULL;
00428                                 *r = new NodoTrieS(c, n2, NULL, set<Pos>());
00429                                 r=&((*r)->hermano_mayor);
00430                         }
00431                 }
00432         }
00433         /*cerr << "Sale de función con trie iniciado con ";
00434         if (res!=NULL) {
00435                 cerr <<"res="<<res<<"("<<res->cad<<")"<<endl;
00436                 long p = 0;
00437                 res->escribePlanoStream(cerr, p) ;
00438                 cerr << endl;
00439         } */
00440         return res;
00441 }
00442 
00443 
00444 
00445 void
00446 NodoTrieS::renumeraDocs(vector<long> renum)
00447 {
00448         set<Pos>::iterator i;
00449         set<Pos> opos(cpos);
00450 
00451         cpos.clear();
00452         for (i = opos.begin(); i != opos.end(); i++) {
00453                 ASSERT(i->numd > 0);
00454                 ASSERT((unsigned long)i->numd <= renum.size());
00455                 cpos.insert(Pos(renum[i->numd - 1] + 1, i->numb));
00456         }
00457         if (hermano_mayor != NULL) {
00458                 hermano_mayor->renumeraDocs(renum);
00459         }
00460         if (hijo_menor != NULL) {
00461                 hijo_menor->renumeraDocs(renum);
00462         }
00463 }
00464 
00465 
00466 
00468 void leeTexto(const char *na, long ndoc, NodoTrieS &t, bool normalizaPal)
00469 {
00470         ASSERT(na!=NULL && na[0] != '\0' && strlen(na)<FILENAME_MAX);
00471         ASSERT(ndoc >= 0);
00472 
00473         string pal;
00474         //clog<<"Leyendo de "<<na<<endl;
00475         // Error si no existe
00476         ifstream fs(na);
00477 
00478         long p;
00479         do {
00480                 p = fs.tellg();
00481                 //clog << "OJO p=" << p << endl;
00482                 fs >> pal;
00483                 if (pal.size() >= MAXCAD) {
00484                         pal = pal.substr(0, MAXCAD);
00485                 }
00486                 if (!fs.eof()) {
00487                         //clog<<"Leida "<<pal<<endl;
00488                         if (p >= 0) {
00489                                 string r;
00490                                 if (normalizaPal) {
00491                                         r = normaliza(pal);
00492                                 } else {
00493                                         r = pal;
00494                                 }
00495                                 if (r.size()>0) {
00496 
00497                                         // tellg comienza en 0 toca + 1
00498                                         t.inserta(r, Pos(ndoc, p + 1));
00499                                         //clog<<"  Insertada"<<endl;
00500                                 }
00501                         }
00502                 }
00503         } while (!fs.eof());
00504         fs.close();
00505 }
00506 
00507 
00512 bool es_signo_punt(unsigned char c)
00513 {
00514         if (c < '0' || (c > '9' && c < 'A') || (c > 'Z' && c < 'a')) {
00515                 //clog << c << "si es signo de puntuación" << endl;
00516                 return true;
00517         }
00518 
00519         return false;
00520 }
00521 
00531 void
00532 NodoTrieS::insertaConEtiqueta(string c, string etiqueta,
00533                               long numdoc, long pini)
00534 
00535 {
00536         ASSERT(c != "");
00537         ASSERT(etiqueta != "");
00538         string::iterator i;
00539         string o = "";
00540         int p, inio;
00541         for (p = pini, inio = 0, i = c.begin(); i != c.end(); p++ , i++) {
00542                 //clog << "insertaConEtiqueta: " << *i << endl;
00543                 if (*i == '.') {
00544                         //clog << "OJO Punto: " << *i << endl;
00545                         if (o.length() > 0) {
00546                                 string ot =
00547                                         normaliza(etiqueta) + string(":") + o;
00548                                 if (ot.length() >= MAXCAD) {
00549                                         ot = ot.substr(0, MAXCAD);
00550                                         //clog << "OJO Cortamos 1" << endl;
00551                                 }
00553                                 inserta(ot, Pos(numdoc, p));
00554                         }
00555                         o += ".";
00556                         //inio = p + 1;
00557                         //o = "";
00558                 } else if (isspace(*i) || es_signo_punt(*i)) {
00559                         //clog << "Espacio o punct: " << *i << ", o.length()=" << o.length() << endl;
00560                         if (o.length() > 0) {
00561                                 o = normaliza(etiqueta) + string(":") + o;
00562                                 //clog << "tras unidr o.length()=" << o.length() << " y MAXCAD=" << MAXCAD << endl;
00563 
00564                                 if (o.length() >= MAXCAD) {
00565                                         o = o.substr(0, MAXCAD);
00566                                         //clog << "OJO Cortamos" << endl;
00567                                 }
00569                                 inserta(o, Pos(numdoc, p));
00570                         }
00571                         inio = p + 1;
00572                         o = "";
00573                 } else if (o.length() < (MAXCAD - etiqueta.length() -1)) {
00574                         //clog << o << endl;
00575                         o += normalizaCaracter(*i);
00576                         //clog << o << endl;
00577                 }
00578         }
00579         if (o.length() > 0) {
00580                 // Insertar palabra anterior si hay
00581                 o = normaliza(etiqueta) + string(":") + o;
00582                 if (o.length() >= MAXCAD) {
00583                         o = o.substr(0, MAXCAD);
00584                 }
00585                 //clog << o << endl;
00586                 inserta(o, Pos(numdoc, p));
00587         }
00588 }
Generado el Wed Jan 6 06:58:22 2010 para Mt77 por  doxygen 1.5.4