TrieSDisco.cpp

Ir a la documentación de este archivo.
00001 // vim: set expandtab tabstop=8 shiftwidth=8 foldmethod=marker:
00013 #include <iostream>
00014 #include <iomanip>
00015 #include <list>
00016 #include <vector>
00017 #include <fstream>
00018 #include <istream>
00019 #include <sstream>
00020 
00021 
00022 using namespace std;
00023 
00024 
00025 #include "TrieSDisco.hpp"
00026 
00027 stringstream *depuraos = NULL;
00028 
00029 
00030 long
00031 precalcula_escribe_actual(int longcad, set<Pos> *cpos)
00032 {
00033         long t = longcad;
00034         t += 1;          // {
00035         t += longNDesp(0); // pos hermano mayor
00036         t += longNDesp(0); // pos hijo menor
00037         t += longPos(cpos);
00038         //clog << "OJO precalcular_escribe_actual(" << longcad <<
00039         //                ", " << cpos << ") da " << t << endl;
00040         return t;
00041 }
00042 
00043 
00044 /*
00045  * cadena
00046  * {
00047  * pos a siguiente hermano (el hermano final se marca con \n)
00048  * pos a hijo mayor o 0 si no hay
00049  * (p1,d1),...(p_k_,d_k)
00050  * }
00051  * @param desp Desplazamiento inicial en stream
00052  * @param dhijo Distancia al hijo menor
00053  * @return Posición donde comienza ''apuntador'' aa hijo menor
00054  */
00055 long
00056 escribeNodo(iostream &os, string c, set<Pos> *cpos,
00057                     long dhijos, long desp)
00058 {
00059         ASSERT(c.length() > 0);
00060         ASSERT(c.length() <= MAXCAD);
00061         ASSERT(dhijos >= 0);
00062 
00063         //clog << "escribeNodo(os, " << c << ", " << (cpos!=NULL ? cpos->size() : 0) << ", " << dhijos << ", " << desp << ")" << endl;
00064         long pih = 0;
00065 
00066         long pini = os.tellp();
00067         //clog << "pini=" << pini << endl;
00068         os << c << FINCADENA;
00069         long dhermano = (pini >= 0 ? pini : 0) + desp +
00070                         precalcula_escribe_actual(c.length(), cpos); //+ 1;
00071         //clog << "dhermano=" << dhermano << endl;
00072         escribeNDesp(os, dhermano);
00073         long phijo = 0;
00074         if (dhijos > 0) {
00075                 phijo = ((pini >= 0) ? pini : 0) + desp + dhijos;
00076         }
00077         //clog << "phijo=" << phijo << endl;
00078         pih = os.tellp();
00079         //clog << "pih=" << pih << endl;
00080         escribeNDesp(os, phijo);
00081         escribePos(os, cpos);
00082 
00083         if (depuraos != NULL) {
00084                 clog << "escribeNodo: '" << depuraos->str() << "'" << endl;
00085         }
00086         return pih;
00087 }
00088 
00089 
00090 long escribeCopiaNodo(iostream &os, istream &is, long &phijo,
00091                       vector<long>* renum)
00092 {
00093 
00094         long ret = 0;
00095 
00096         long pini = is.tellg();
00097         //clog << "\nescribeCopiaNodo is.tellg() = " << is.tellg();
00098         string cad = leeCad(is);
00099         //clog << " cad='" << cad << "'";
00100         if (cad != "") {
00101                 long phermano = leeNDesp(is);
00102                 //clog << " phermano=" << phermano;
00103                 phijo = leeNDesp(is);
00104                 long dhijo = 0;
00105                 if (phijo > 0) {
00106                         dhijo = phijo - pini;
00107                 }
00108                 //clog << " phijo=" << phijo;
00109                 set<Pos> *cpos = leePos(is, renum);
00110                 //clog << " cpos=" << *cpos;
00111                 ASSERT(phijo == 0 || (long)is.tellg() <= phijo);
00112                 //clog << " is.tellg() = " << is.tellg();
00113                 ASSERT(phermano == 0 || (long)is.tellg() <= phermano);
00114                 ret = escribeNodo(os, cad, cpos, dhijo);
00115                 delete cpos;
00116                 cpos = NULL;
00117         }
00118 
00119         //clog << " ret=" << ret << endl;
00120         return ret;
00121 }
00122 
00123 
00124 
00125 long
00126 escribeCopiaSubarbol(iostream &os, istream &is, bool conHermanos,
00127                      vector<long>* renum)
00128 {
00129 
00130         long prini = os.tellp();
00131         //clog << "OJO escribeCopiaSubarbol prini=" << prini << endl;
00132         //clog << "OJO is.tellg()=" << is.tellg() << endl;
00133 
00134         string cad;
00135         long n; // Cantidad de nodos hermanos
00136         vector<long> dhijo;
00137         vector<long> pih;
00138 
00139         cad = leeCad(is);
00140         //clog << "OJO cad=" << cad << endl;
00141         /* INV: cad es cadena leida del nodo por copiar
00142          * "cursor" de is está a continuación de la cadena leída 
00143          * n es cantidad de nodos hermanos ya leidos
00144          * dhijo tiene lista de apuntadores a hijos 
00145          * pih es vector de posiciones de apuntadores a hijos escritos en os
00146          */
00147         for (n = 0; cad != "" && (conHermanos || n == 0); n++) {
00148                 //clog << "OJO is.tellg()=" << is.tellg() << endl;
00149                 long phermano = leeNDesp(is);
00150                 //clog << "OJO prini=" << prini << " phermano=" << phermano << endl;
00151                 long h = leeNDesp(is);
00152                 //clog << "OJO prini=" << prini << " h=" << h << endl;
00153                 set<Pos> *cpos = leePos(is, renum);
00154                 //clog << "OJO prini=" << prini << " cpos=" << *cpos << endl;
00155                 //clog << "OJO prini=" << prini << " is.tellg=" << is.tellg() << endl;
00156                 ASSERT(h == 0 || (long)is.tellg()<=h);
00157                 ASSERT(phermano == 0 || (long)is.tellg()<=phermano);
00158                 //clog << "OJO paso ASSERT" << endl;
00159                 dhijo.push_back(h);
00160                 long tp = escribeNodo(os, cad, cpos, 0);
00161                 //clog << "OJO prini=" << prini << " tp=" << tp << endl;
00162                 pih.push_back(tp);
00163                 //clog << "OJO 2 prini=" << prini << ", os.tellp=" << os.tellp() << endl;
00164                 delete cpos;
00165                 cpos = NULL;
00166                 if (depuraos!=NULL) {
00167                         //clog << depuraos->str() << endl;
00168                 }
00169                 if (conHermanos) {
00170                         cad = leeCad(is);
00171                         //clog << "OJO conHermanos cad=" << cad << endl;
00172                 }
00173         }
00174         if (n > 0) {
00175                 os << endl;
00176                 //clog << "OJO dhijo[0]=" << dhijo[0] << " " << dhijo.size() << endl;
00177         }
00178         long i;
00179         /* INV: n cantidad de nodos hermanos por copiar
00180          * "cursor" de os está al final
00181          * dhijo[i] tiene posición  en is del hijo menor del i-esimo nodo
00182          * pih[i] es posición en os donde está el hexadecimal con posición
00183          *      de hijo menor del i-esimo nodo.
00184          */
00185         long pini, pfin;
00186         for (i = 0; i < n; i++) {
00187                 if (dhijo[i] > 0) {
00188                         //clog << "OJO en hijos prini=" << prini << " dhijo[" << i << "]=" << dhijo[i] << endl;
00189                         is.seekg(dhijo[i]);
00190                         pini = escribeCopiaSubarbol(os, is, true, renum);
00191                         //clog << "OJO prini=" << prini << " pini=" << pini << endl;
00192                         pfin = os.tellp();
00193                         //clog << "OJO pfin=" << pfin <<endl;
00194                         os.seekp(pih[i]);
00195                         //clog << "OJO pih[i]=" << pih[i] <<endl;
00196                         escribeNDesp(os, pini);
00197                         //clog << "OJO escribiendo pini=" << pini <<endl;
00198                         os.seekp(pfin);
00199                 }
00200         }
00201 
00202         return prini;
00203 }
00204 
00205 
00206 long
00207 mezclaRec(istream &is1, istream &is2, iostream &os,
00208           bool conHermanos1, bool conHermanos2,
00209           vector<long> *renum1, vector<long> *renum2)
00210 {
00211 
00212         string cad1;
00213         string cad2;
00214         long numhermanos; // Número de hermanos escritos en os
00215         long n1=0; // Número de hermanos revisados en is1
00216         long n2=0; // Número de hermanos revisados en is2
00217         long phermano1; // Posición de hermano en is1
00218         long phermano2; // Posición de hermano en is2
00219 
00220         // Posibles operaciones con hijos en is1 e is2 para producir hijo(s)
00221         // en os
00222         const int O_COPIA1=1,
00223                            O_COPIA2=2,
00224                                     O_MEZCLA_H1H2=3,
00225                                                   O_MEZCLA_H1=4,
00226                                                               O_MEZCLA_H2=5,
00227                                                                           O_COPIA_PRIMERO_1=6,
00228                                                                                             O_COPIA_PRIMERO_2=7;
00229 
00230         ;
00231         vector<long> dhijo1(0); // apuntadores a hijos de nodos en is1
00232         vector<long> dhijo2(0); // apuntadores a hijos de nodos en is2
00233         vector<string> resto1(0); // Cadenas con las que comenazarán hijos
00234         vector<string> resto2(0); // Cadenas con las que comenzarían hijos
00235         vector<int> opera(0); // operación por realizar a hijos en 2da parte
00236         vector<long> pih(0); // posiciones de apuntadores a hijos en os
00237 
00238         long prini = os.tellp();
00239         //clog << "OJO mezclaRec prini=" << prini << ", is1.tellg()=" << is1.tellg() << ", is2.tellg()=" << is2.tellg() << endl;
00240         //clog << "peek1=" << is1.peek() << endl;
00241         //clog << "peek2=" << is2.peek() << endl;
00242         for (cad1=leeCad(is1), cad2=leeCad(is2), numhermanos = 0;
00243                         (cad1!="" && (conHermanos1 || n1==0)) ||
00244                         (cad2!="" && (conHermanos2 || n2==0));
00245                         numhermanos++) {
00246                 //clog << "OJO mezclaRec prini=" << prini << ", cad1=" << cad1 << ", cad2= "<< cad2 << endl;
00247                 dhijo1.push_back(-1);
00248                 dhijo2.push_back(-1);
00249                 resto1.push_back("");
00250                 resto2.push_back("");
00251                 opera.push_back(-1);
00252                 pih.push_back(-1);
00253 
00254                 if (!conHermanos1 && n1 >= 1) {
00255                         cad1="";
00256                 }
00257                 if (!conHermanos2 && n2 >= 1) {
00258                         cad2="";
00259                 }
00260                 /* INV:
00261                  * cad1 es cadena en nodo de is1
00262                  * cad2 es cadena en nodo de is2
00263                  * cursor de is1 está a continuación de cad1 
00264                  *      (sobre inicio de posiciones)
00265                  * cursor de is2 está a continuación de cad2 
00266                  * conHermanos1 es true si debe continuar con hermanos en is1
00267                  * conHermanos2 es true si debe seguir con hermanos en is2
00268                  */
00269                 string c = "";
00270                 if (cad1 != "" && cad2 != "") {
00271                         c = prefijo_comun_mas_largo(cad1, cad2);
00272                 }
00273                 //clog << " prefijo c="<<c<<endl;
00274                 if (c == "") { // No hay prefijo comun
00275                         resto1[numhermanos] = "";
00276                         resto2[numhermanos] = "";
00277                         if (cad2=="" || (cad1!="" && cad1<cad2)) {
00278                                 // e.g AMOR y BUENO  o
00279                                 //     ""   y BUENO
00280                                 //clog<< "se copia nodo de is1" <<endl;
00281                                 phermano1 = leeNDesp(is1);
00282                                 dhijo1[numhermanos] = leeNDesp(is1);
00283                                 dhijo2[numhermanos] = -1;
00284                                 set<Pos> *cpos = leePos(is1, renum1);
00285                                 opera[numhermanos] = O_COPIA1;
00286                                 pih[numhermanos] =
00287                                         escribeNodo(os, cad1, cpos, 0);
00288                                 delete cpos;
00289                                 cpos = NULL;
00290                                 cad1 = leeCad(is1);
00291                                 n1++;
00292                                 // cad2 quieto
00293                                 // en la recursión hijos de cad1
00294                                 //quedamos en el siguiente hermano mayor en is1
00295                         } else { /*cad2!="" && (cad1=="" || cad1 >= cad2) */
00296                                 // e.g BUENO y AMOR o
00297                                 //      ""   y AMOR
00298                                 ASSERT(cad1 == "" || (cad1 > cad2));
00299                                 //clog << "se copia nodo de is2" <<endl;
00300                                 dhijo1[numhermanos] = -1;
00301                                 phermano2 = leeNDesp(is2);
00302                                 dhijo2[numhermanos] = leeNDesp(is2);
00303                                 //clog << "phermano2=" << phermano2 << ", phijo=" << dhijo2[numhermanos] << endl;
00304                                 set<Pos> *cpos = leePos(is2, renum2);
00305                                 opera[numhermanos] = O_COPIA2;
00306                                 pih[numhermanos] =
00307                                         escribeNodo(os, cad2, cpos, 0);
00308                                 delete cpos;
00309                                 cpos = NULL;
00310                                 cad2=leeCad(is2);
00311                                 n2++;
00312                         }
00313                 } else if (cad1 == cad2) { // Hay prefijo c != "" && cad1!="" && cad2!=""
00314                         phermano1 = leeNDesp(is1);
00315                         phermano2 = leeNDesp(is2);
00316                         dhijo1[numhermanos] = leeNDesp(is1);
00317                         dhijo2[numhermanos] = leeNDesp(is2);
00318                         //clog << "iguales" <<endl;
00319                         set<Pos> cpos;
00320                         insert_iterator<set<Pos> >
00321                         cpos_ins(cpos, cpos.begin());
00322                         set<Pos> *cpos1 = leePos(is1, renum1);
00323                         set<Pos> *cpos2 = leePos(is2, renum2);
00324 
00325                         set_union(cpos1->begin(), cpos1->end(),
00326                                   cpos2->begin(), cpos2->end(),
00327                                   cpos_ins);
00328                         pih[numhermanos] = escribeNodo(os, cad2, &cpos, 0);
00329                         delete cpos1;
00330                         cpos1=NULL;
00331                         delete cpos2;
00332                         cpos2=NULL;
00333                         //En hijos NodoTrieS *m=mezcla(a1->hijo_menor, a2->hijo_menor);
00334                         resto1[numhermanos] = "";
00335                         resto2[numhermanos] = "";
00336                         opera[numhermanos] = O_MEZCLA_H1H2;
00337                         cad1 = leeCad(is1);
00338                         n1++;
00339                         cad2 = leeCad(is2);
00340                         n2++;
00341                 } else { // hay prefijo c != "" && cad1!="" && cad2!="" && cad1!=cad2
00342                         string r1 = cad1.substr(c.size());
00343                         string r2 = cad2.substr(c.size());
00344                         resto1[numhermanos] = r1;
00345                         resto2[numhermanos] = r2;
00346                         ASSERT(r1 != "" || r2 != "");
00347                         //clog << "hay posfijo r1="<<r1<<" r2="<<r2<<endl;
00348                         if (r1=="") {
00349                                 // e.g BUENO BUENOS
00350                                 ASSERT(r2 != "");
00351                                 //clog << "r1 vacio"<<endl;
00352                                 // debe mezclar hijo de is1 con un sólo
00353                                 // nodo de is2 pero is2 comenzando en el
00354                                 // posfijo r2
00355 
00356                                 phermano1 = leeNDesp(is1);
00357                                 phermano2 = leeNDesp(is2);
00358                                 dhijo1[numhermanos] = leeNDesp(is1);
00359                                 dhijo2[numhermanos] = (long)is2.tellg() -
00360                                                       MAXLNUMERO - 1 - (long)r2.size();
00361                                 /*                              (void)leeNDesp(is2);
00362                                                                 saltaPos(is2); */
00363                                 is2.seekg(phermano2); // Salta al sig en is2
00364                                 set<Pos> *cpos1 = leePos(is1, renum1);
00365                                 //clog << "OJO is2.tellg()="<< is2.tellg() << endl;
00366                                 pih[numhermanos] = escribeNodo(os, c, cpos1, 0);
00367                                 opera[numhermanos] = O_MEZCLA_H1;
00368                                 delete cpos1;
00369                                 cpos1=NULL;
00370                         } else if (r2 == "") {
00371                                 // e.g BUENOS BUENO
00372                                 ASSERT(r1 != "");
00373                                 //clog << "r2 vacio"<<endl;
00374                                 //
00375                                 phermano1 = leeNDesp(is1);
00376                                 dhijo1[numhermanos] = (long)is1.tellg() -
00377                                                       MAXLNUMERO - 1 - (long)r1.size();
00378                                 phermano2 = leeNDesp(is2);
00379                                 dhijo2[numhermanos] = leeNDesp(is2);
00380                                 is1.seekg(phermano1);
00381                                 /*saltaPos(is1);
00382                                 leeNDesp(is1); */
00383                                 set<Pos> *cpos2 = leePos(is2, renum2);
00384                                 //clog << "OJO en nodo dhijo2[numhermanos]=" << dhijo2[numhermanos] << endl;
00385                                 pih[numhermanos] = escribeNodo(os, c, cpos2, 0);
00386                                 // Recursion NodoTrieS *m=mezcla(n1, a2->hijo_menor);
00387                                 delete cpos2;
00388                                 cpos2=NULL;
00389                                 opera[numhermanos] = O_MEZCLA_H2;
00390                         } else if (r1 < r2) {
00391                                 // e.g BUENA BUENO
00392                                 //clog << "r1<r2"<<endl;
00393 
00394                                 phermano1 = leeNDesp(is1);
00395                                 //clog << "phermano1=" << phermano1 <<endl;
00396                                 phermano2 = leeNDesp(is2);
00397                                 //clog << "phermano2=" << phermano2 <<endl;
00398                                 pih[numhermanos] = escribeNodo(os, c, NULL, 0);
00399                                 //clog << "pih=" << pih[numhermanos] <<endl;
00400                                 dhijo1[numhermanos] = (long)is1.tellg() -
00401                                                       MAXLNUMERO - 1 - (long)r1.size();
00402                                 //clog << "dhijo1=" << dhijo1[numhermanos] <<endl;
00403                                 dhijo2[numhermanos]=(long)is2.tellg() -
00404                                                     MAXLNUMERO - 1 - (long)r2.size();
00405                                 //clog << "dhijo2=" << dhijo2[numhermanos] <<endl;
00406                                 is1.seekg(phermano1);
00407                                 is2.seekg(phermano2);
00408                                 opera[numhermanos] = O_COPIA_PRIMERO_1;
00409                                 //a1->cad=r1;
00410                                 //a2->cad=r2;
00411                                 // El hijo de este nodo debe ser
00412                                 // a1 con hermano mayor a2
00413                                 //*r=new NodoTrieS(c, n1, NULL, set<Pos>());
00414                         } else { /* r1 >= r2 */
00415                                 // e.g BUENO BUENA
00416                                 //clog << "r2 <= r1"<<endl;
00417                                 phermano1 = leeNDesp(is1);
00418                                 phermano2 = leeNDesp(is2);
00419                                 pih[numhermanos] = escribeNodo(os, c, NULL, 0);
00420                                 dhijo1[numhermanos] = (long)is1.tellg() -
00421                                                       MAXLNUMERO - 1 - (long)r1.size();
00422                                 dhijo2[numhermanos] = (long)is2.tellg() -
00423                                                       MAXLNUMERO - 1 - (long)r2.size();
00424                                 //saltaPos(is1); leeNDesp(is1);
00425                                 is1.seekg(phermano1);
00426                                 //saltaPos(is2); leeNDesp(is2);
00427                                 is2.seekg(phermano2);
00428                                 opera[numhermanos] = O_COPIA_PRIMERO_2;
00429                         }
00430                         cad1=leeCad(is1);
00431                         n1++;
00432                         //clog << "lee cad1=" << cad1 << endl;
00433                         cad2=leeCad(is2);
00434                         n2++;
00435                         //clog << "lee cad2=" << cad2 << endl;
00436                 }
00437         }
00438         os << endl;
00439         //clog << "Termina hermanos, pasa a hijos" << endl;
00440 
00441         // Desplazamientos en os
00442         long pini, pfin;
00443         long hijo1=0, hijo2=0;
00444         long ph1, ph2, pnh1, pnh2;
00445         for (int n = 0; n < numhermanos; n++) {
00446                 pini = 0; // Posición donde queda hijo en os
00447                 switch (opera[n]) {
00448                 case O_COPIA1:
00449                         //clog << "COPIA1" <<endl;
00450                         if (dhijo1[n] > 0) {
00451                                 is1.seekg(dhijo1[n]);
00452                                 pini = escribeCopiaSubarbol(os, is1,
00453                                                             true, renum1);
00454                         }
00455                         break;
00456 
00457                 case O_COPIA2:
00458                         //clog << "COPIA2" <<endl;
00459                         if (dhijo2[n] > 0) {
00460                                 //clog << "dhijo2[" << n << "]=" <<
00461                                 //dhijo2[n] << endl;
00462                                 is2.seekg(dhijo2[n]);
00463                                 pini = escribeCopiaSubarbol(os, is2,
00464                                                             true, renum2);
00465                         }
00466                         break;
00467 
00468                 case O_MEZCLA_H1H2:
00469                         //clog << "MEZCLA_H1H2" <<endl;
00470                         if (depuraos!=NULL) {
00471                                 //clog << depuraos->str() << endl;
00472                         }
00473 
00474 
00475                         if (dhijo1[n] > 0 && dhijo2[n] > 0) {
00476                                 is1.seekg(dhijo1[n]);
00477                                 is2.seekg(dhijo2[n]);
00478                                 pini = mezclaRec(is1, is2, os,
00479                                                  true, true, renum1, renum2) ;
00480                         } else if (dhijo1[n] > 0) {
00481                                 ASSERT(dhijo2[n] == 0);
00482                                 is1.seekg(dhijo1[n]);
00483                                 pini = escribeCopiaSubarbol(os, is1,
00484                                                             true, renum1);
00485                         } else if (dhijo2[n] > 0) {
00486                                 //clog << "OJO dhijo2[n]=" <<dhijo2[n]<< endl;
00487                                 ASSERT(dhijo1[n] == 0);
00488                                 is2.seekg(dhijo2[n]);
00489                                 //clog << "OJO is2.peek=" << (char)is2.peek()<< endl;
00490                                 pini = escribeCopiaSubarbol(os, is2,
00491                                                             true, renum2);
00492                                 //clog << "OJO pini=" << pini << endl;
00493                         }
00494                         break;
00495                 case O_MEZCLA_H1:
00496                         //clog << "MEZCLA_H1" <<endl;
00497                         ASSERT(dhijo2[n] != 0);
00498 
00499                         //clog << "OJO dhijo2[n]=" << dhijo2[n] << endl;
00500                         is2.seekg(dhijo2[n]);
00501                         if (dhijo1[n] > 0) {
00502                                 is1.seekg(dhijo1[n]);
00503                                 pini = mezclaRec(is1, is2, os,
00504                                                  true, false, renum1, renum2) ;
00505                         } else {
00506                                 pini = escribeCopiaSubarbol(os, is2,
00507                                                             false, renum2);
00508                         }
00509                         break;
00510 
00511                 case O_MEZCLA_H2:
00512                         //clog << "MEZCLA_H2" <<endl;
00513                         ASSERT(dhijo1[n] != 0);
00514 
00515                         is1.seekg(dhijo1[n]);
00516                         //clog << "dhijo2[n]=" << dhijo2[n] <<  endl;
00517                         if (dhijo2[n] > 0) {
00518                                 is2.seekg(dhijo2[n]);
00519                                 pini = mezclaRec(is1, is2, os,
00520                                                  false, true, renum1, renum2) ;
00521                         } else {
00522                                 pini = escribeCopiaSubarbol(os, is1,
00523                                                             false, renum1);
00524                         }
00525                         break;
00526 
00527                 case O_COPIA_PRIMERO_1:
00528                         //clog << "COPIA_PRIMERO_1" <<endl;
00529                         ASSERT(dhijo1[n] != 0);
00530                         ASSERT(dhijo2[n] != 0);
00531 
00532                         is1.seekg(dhijo1[n]);
00533                         is2.seekg(dhijo2[n]);
00534                         pini = os.tellp();
00535 
00536                         // pos no es NULL en los siguientes,
00537                         // más bien copiar de is1 e is2 e hijos
00538                         // después.
00539                         pnh1=escribeCopiaNodo(os, is1, hijo1, renum1);
00540                         pnh2=escribeCopiaNodo(os, is2, hijo2, renum2);
00541                         os << endl;
00542                         ph1=os.tellp();
00543                         if (hijo1 > 0) {
00544                                 is1.seekg(hijo1);
00545                                 (void)escribeCopiaSubarbol(os, is1,
00546                                                            true, renum1);
00547                         }
00548                         ph2=os.tellp();
00549                         if (hijo2 > 0) {
00550                                 is2.seekg(hijo2);
00551                                 escribeCopiaSubarbol(os, is2,
00552                                                      true, renum2);
00553                         }
00554                         pfin = os.tellp();
00555                         if (hijo1 > 0) {
00556                                 os.seekp(pnh1);
00557                                 escribeNDesp(os, ph1);
00558                         }
00559                         if (hijo2 > 0) {
00560                                 os.seekp(pnh2);
00561                                 escribeNDesp(os, ph2);
00562                         }
00563                         os.seekp(pfin);
00564 
00565                         break;
00566 
00567                 case O_COPIA_PRIMERO_2:
00568                         //clog << "COPIA_PRIMERO_2" <<endl;
00569                         ASSERT(dhijo1[n] != 0);
00570                         ASSERT(dhijo2[n] != 0);
00571 
00572                         is1.seekg(dhijo1[n]);
00573                         is2.seekg(dhijo2[n]);
00574                         pini = os.tellp();
00575 
00576                         pnh2=escribeCopiaNodo(os, is2, hijo2, renum2);
00577                         pnh1=escribeCopiaNodo(os, is1, hijo1, renum1);
00578                         os << endl;
00579                         ph2=os.tellp();
00580                         if (hijo2 > 0) {
00581                                 is2.seekg(hijo2);
00582                                 escribeCopiaSubarbol(os, is2,
00583                                                      true, renum2);
00584                         }
00585                         ph1=os.tellp();
00586                         if (hijo1 > 0) {
00587                                 is1.seekg(hijo1);
00588                                 escribeCopiaSubarbol(os, is1,
00589                                                      true, renum1);
00590                         }
00591                         pfin = os.tellp();
00592                         if (hijo2 > 0) {
00593                                 os.seekp(pnh2);
00594                                 escribeNDesp(os, ph2);
00595                         }
00596                         if (hijo1 > 0) {
00597                                 os.seekp(pnh1);
00598                                 escribeNDesp(os, ph1);
00599                         }
00600                         os.seekp(pfin);
00601 
00602                         break;
00603 
00604                 default:
00605                         throw std::string("Falla: estado desconocido");
00606                         break;
00607                 }
00608                 pfin = os.tellp();
00609                 //clog << "OJO pfin=" << pfin << endl;
00610                 //clog << "OJO n=" << n << ", pih[n]=" << pih[n]<< endl;
00611                 os.seekp(pih[n]);
00612                 escribeNDesp(os, pini);
00613                 os.seekp(pfin);
00614         }
00615         //clog << "Termina hijos" << endl;
00616         return prini;
00617 }
00618 
00619 
00620 
00624 set<Pos> *
00625         buscaPlanoStream(std::istream &is, string pal) throw(char *)
00626 {
00627         string cad;
00628         set<Pos> *cpos;
00629 
00630         cad = leeCad(is);
00631         //clog<<"OJO cad = "<<cad <<endl;
00632         if (cad.size() == pal.size() && cad == pal) {
00633                 //clog<<"OJO encontrado";
00634                 (void)leeNDesp(is);
00635                 (void)leeNDesp(is);
00636                 cpos = leePos(is, NULL);
00637                 return cpos;
00638         } else if (cad != "" &&
00639                         cad.size() < pal.size() &&
00640                         pal.substr(0, cad.size()) == cad) {
00641                 leeNDesp(is); // hermano
00642                 long hijo = leeNDesp(is);
00643                 /*hijo = 0;
00644                 saltaPos(is); */
00645                 //clog<<"OJO por buscar entre hijos a partir de " << hijo << endl;
00646                 //is>>hijo;
00647                 if (hijo > 0) {
00648                         is.seekg(hijo);
00649                         return buscaPlanoStream(is, pal.substr(cad.size()));
00650                 }
00651         } else if (cad != "" && cad < pal) {
00652                 //clog<<"OJO pasar a hermano mayor"<<endl;
00653                 // salta cpos e hijo
00654                 long hermano = leeNDesp(is);
00655                 is.seekg(hermano);
00656                 //saltaPos(is);
00657 
00658                 return buscaPlanoStream(is, pal);
00659         }
00660         //clog<<"OJO no se encontró" << endl;
00661         return NULL;
00662 }
00663 
00664 
00665 
00666 void verificaIndice(istream &is)
00667 {
00668         char rec[MAXLURL];
00669         is.seekg(0);
00670         is.getline(rec, MAXLURL);
00671         if (rec != MARCAIND) {
00672                 throw errorFormato(is, string("Se esperaba `") + MARCAIND + string("' pero se encontro") + rec);
00673         }
00674 }
00675 
00676 set<Pos> *
00677         buscaPlano(char *na, char *nrel, string pal, vector<Doc> &docs)
00678 {
00679         set<Pos> *r;
00680         //      long iddocs = leeNDesp(is);
00681         string enc;
00682 
00683 
00684         fstream is(na, ios_base::in);
00685         verificaIndice(is);
00686         try {
00687                 r = buscaPlanoStream(is, pal);
00688         } catch (string m) {
00689                 throw errorFormato(is, m);
00690         }
00691         is.close();
00692 
00693         leeRelacion(nrel, docs);
00694         /*      for (int i=0; i<idocs.size(); i++) {
00695                         clog << i << " " << idocs[i] << endl;
00696                 }  */
00697 
00698         return r;
00699 }
00700 
00701 
00702 unsigned long
00703 leeRelacion(char *nrel,  vector<Doc> &docs)
00704 {
00705         ASSERT(nrel != NULL);
00706         ASSERT(nrel[0] != '\0');
00707 
00708         string s = "", m = "";
00709         char rec[MAXLURL];
00710 
00711         fstream is(nrel, ios_base::in);
00712         if (!is) {
00713                 stringstream ss;
00714                 ss << "No pudo abrirse relación " << nrel;
00715                 throw ss.str();
00716         }
00717         is.seekg(0);
00718         is.getline(rec, 100);
00719         if (rec != MARCAREL) {
00720                 throw errorFormato(is,
00721                                    string("Se esperaba marca de relación para prototipo 3") + rec);
00722         }
00723         docs = leeDocs(is);
00724         is.close();
00725 
00726         return docs.size();
00727 }
00728 
00729 
00730 void escribeRelacion(char *nrel, vector<Doc> &docs, vector<long> *reord)
00731 {
00732         ASSERT(nrel != NULL);
00733         ASSERT(strlen(nrel) > 0 && strlen(nrel) < MAXLURL);
00734         ASSERT(reord == NULL || reord->size() == docs.size());
00735 
00736         fstream os(nrel, ios_base::out);
00737         os << MARCAREL << endl ;
00738         escribeDocs(os, docs, reord);
00739         os.close();
00740 }
00741
Generado el Wed Jan 6 06:58:22 2010 para Mt77 por  doxygen 1.5.4