/* Pràctica de PS Quadrimestre Tardor 2004-2005 Autors: Daniel Clemente Laboreo Francesc Xavier Morales Pascual */ // particio.t: conjunts d'elements amb representant. Classe genèrica. // Aquest fitxer s'inclou (#include) a l'.hpp // Definir membres static template const char particio::nom_mod[9]; template const int particio::ElemInexistent; template const char particio::MsgElemInexistent[36]; template particio::particio() throw(error) : inici(new node), ngrups(0) { // Construeix una partició buida inici->next=NULL; // "inici" és el fantasma } template particio::particio(const particio& p) throw(error) : ngrups(p.ngrups) { // Constructora per còpia try { inici=copia_llista(p.inici); } catch (error e) { // Si falla algun new... destrueix_llista(inici); // Destrueix-ho tot throw; // I propaga l'excepció } } template particio::node* particio::copia_llista(const node* origen) throw(error) { // Funció recursiva per copiar una llista enllaçada if (origen==NULL) return NULL; // Cas directe node* nou=new node; // Es crea la memòria; si falla es surt de la funció nou->info=origen->info; nou->es_rep=origen->es_rep; nou->next=copia_llista(origen->next); // Crida recursiva return nou; } template void particio::destrueix_llista(const node* origen) { // Allibera la memòria ocupada per la llista enlaçada if (origen==NULL) return; // Res a esborrar destrueix_llista(origen->next); // Primer tota la resta... delete origen; // I després el node demanat return; } template particio& particio::operator=(const particio& p) throw(error) { node* aux=NULL; if (this != &p) { try { aux=copia_llista(p.inici); // Primer fa la còpia } catch(error e) { destrueix_llista(aux); // Cancel.lar còpia throw; } destrueix_llista(inici); // Esborra l'antiga inici=aux; // I enganxa la nova aquí ngrups=p.ngrups; } return *this; } template particio::~particio() throw() { destrueix_llista(inici); } template void particio::afegir(const T& x) throw(error) { // Buscar un element a la llista. Si no s'ha trobat, afegir-lo pel final. node* p=inici; while (p->next) // Mentre no arribi al final... { if(p->next->info == x) return; // L'hem trobat i no cal fer res p=p->next; } // Si arribem aquí és perquè no s'ha trobat. Afegir-lo just darrere de p (al final) node* nou=new node; // Si falla surt de la funció i no passa res dolent nou->info=x; nou->es_rep=true; // Es representa a sí mateix nou->next=NULL; p->next=nou; // I va després de l'últim ++ngrups; // S'ha creat un nou grup } template void particio::unir(const T& x, const T& y) throw(error) { // L'algorisme és: // 1. Buscar el primer element // 2. Buscar el grup on està el segon elemente // 3. Moure el segon grup darrere del primer // 4. Desmarcar el representant del primer // 5. Disiminuir el número de grups // NOTA: no sabem si trobarem abans x o y. Aquí: "el primer grup" vol dir el grup del què s'ha trobat primer, i "el segon grup" el de l'altre node* rep1; // Just darrere té el representant del primer grup node* inici2; // Just darrere té el primer element del segon grup node* rep2; // Just darrere té l'últim element del segon grup (el representant) node* p; // Punter per recórrer la llista bool trobatx; // cert: el primer en trobar-se ha sigut x. fals: ha sigut y if(x==y) return; // Massa fàcil... p=inici; while(p->next) { if (p->next->info==x || p->next->info==y) break; // Primera ocurrència p=p->next; } if ( ! p->next ) throw error(nom_mod, ElemInexistent, MsgElemInexistent); trobatx=(p->next->info==x); // Era x o y ? while( ! p->next->es_rep) p=p->next; // Avançar fins al representant // (el bucle acaba perquè l'últim element de la llista sempre té es_rep a 1) rep1=p; // Darrere d'ell vindrà el segon grup, que encara hem de trobar while(p->next) { if (p->es_rep) { // Si aquest és representant, al darrere té l'inici d'un nou grup inici2=p; // (però encara no sabem si serà aquest qui contendrà l'element buscat) } if ( (trobatx && p->next->info==y) || (!trobatx && p->next->info==x) ) break; p=p->next; } if ( ! p->next ) throw error(nom_mod, ElemInexistent, MsgElemInexistent); while( ! p->next->es_rep) p=p->next; // Avançar fins al representant rep2=p; // Representant del segon trobat // Ja estan tots els punters ben posats if (rep1==rep2) return; // No es poden unir si ja pertanyen al mateix grup // Ara hem de desenganxar el segon grup i posar-lo darrere del primer // Ordre: // rep1 inici2 rep2 // .1. .2. .3. .4. .5. .6. .7. .8. .9. .a. .b. .c. .d. .e. // |---GRUP1-------| |-------GRUP2-------| // Ha de quedar: // rep1 rep2 inici2 // .1. .2. .3. .4. .8. .9. .a. .b. .c. .5. .6. .7. .d. .e. // |---GRUP1-------| |-------GRUP2-------| // Això és complicat però pensant uns minuts (>180) es pot entendre: node* el_que_hem_tret=inici2->next; node* final_del_que_hem_tret=rep2->next; // Treure tot el grup 2, arreglant el salt inici2->next=rep2->next->next; node* ve_despres_de_grup1=rep1->next->next; // Darrere del grup 1 posem el nostre tros rep1->next->next=el_que_hem_tret; // Darrere del tros tret, posem el que venia després del grup 1 final_del_que_hem_tret->next=ve_despres_de_grup1; rep1->next->es_rep=false; // Deixem el representant del segon --ngrups; // Hi ha un grup menys perquè els hem unit } template const T& particio::representant(const T& x) const throw(error) { // 1. Trobar l'element T // 2. Avançar fins el seu representant node* p; p=inici; while (p->next) { if(p->next->info==x) break; p=p->next; } if ( ! p->next ) throw error(nom_mod, ElemInexistent, MsgElemInexistent); while( ! p->next->es_rep) p=p->next; // Avançar fins al representant return p->next->info; } template nat particio::size() const throw() { return ngrups; }