Iteradors quàntics a la classe List X66290

Típicament, executar ++ sobre un iterador que es troba al end de la llista produeix error d’execució, i executar -- sobre un iterador que es troba al begin de la llista també produeix error d’execució. Per començar, en aquest exercici modificarem la subclasse iterator de la classe List de manera que els errors d’execució abans esmentats ja no es produiran. Simplement, en tals casos els iteradors no es mouran.

Després modificarem la classe iterator afegint dos nous mètodes entangle i disentangle i canviant el comportament dels mètodes ++ i -- com descrivim a continuació.

El nou mètode entangle rebrà un altre iterator com a paràmetre (és a dir, un iterador del mateix tipus, tot i que potser apunta a un element d’una llista diferent). Una crida it0.entangle(it1) provocarà que it0 quedi enllaçat a it1 de manera que, a partir de llavors, sempre que executem it0++ o ++it0, l’iterador it1 també es desplaçarà cap al final de la seva llista corresponent (si no es troba ja al end). A més a més, sempre que executem it0-- o --it0, l’iterador it1 també es desplaçarà cap al principi de la seva llista corresponent (si no es troba ja al begin).

Aquest efecte no es propaga per una seqüència d’enllaços. Per exemple, si hem executat it0.entangle(it1) i it1.entangle(it2), executar it0++ mourà també it1 cap al final de la seva llista, però això no es propagarà a moure it2 cap al final de la seva llista.

Successius entangle sobre un mateix iterador fan que només l’últim estigui actiu. Per exemple, si hem executat it0.entangle(it1) i després it0.entangle(it2), llavors it0 està enllaçat a it2 però no a it1.

Una crida it0.disentangle() cancel.larà l’efecte de l’últim entangle actiu.

Fixeu-vos en aquest exemple per tal d’acabar d’entendre-ho:

List<int> l0, l1;
List<int>::iterator a, b, c, d;

l0.push_back(1);     // l0: 1,
l0.push_back(2);     // l0: 1,2,
l0.push_back(3);     // l0: 1,2,3,
l1.push_back(4);     // l1: 4,
l1.push_back(5);     // l1: 4,5,
l1.push_back(6);     // l1: 4,5,6,

a = l0.begin();      // l0: 1a,2,3,
b = l0.end();        // l0: 1a,2,3,b
c = l1.begin();      // l1: 4c,5,6,
d = l1.begin();      // l1: 4c,5,6,d

a--;                 // l0: 1a,2,3,b
a++;                 // l0: 1,2a,3,b
b++;                 // l0: 1,2a,3,b
b--;                 // l0: 1,2a,3b,
a.entangle(b);
a++;                 // l0: 1,2,3a,b
a++;                 // l0: 1,2,3,ab
a++;                 // l0: 1,2,3,ab
a--;                 // l0: 1,2,3ab,
b--;                 // l0: 1,2b,3a,
a--;                 // l0: 1b,2a,3,
a--;                 // l0: 1ab,2,3,
a--;                 // l0: 1ab,2,3,

a.entangle(c);
c.entangle(d);
a++;                 // l0: 1b,2a,3,  l1: 4,5c,6,d
c++;                 // l0: 1b,2a,3,  l1: 4,5,6c,d
c--;                 // l0: 1b,2a,3,  l1: 4,5c,6d,
c--;                 // l0: 1b,2a,3,  l1: 4c,5d,6,
a++;                 // l0: 1b,2,3a,  l1: 4,5cd,6,
a++;                 // l0: 1b,2,3,a  l1: 4,5d,6c,
a.disentangle();
a++;                 // l0: 1b,2,3,a  l1: 4,5d,6c,
a--;                 // l0: 1b,2,3a,  l1: 4,5d,6c,
c++;                 // l0: 1b,2,3a,  l1: 4,5,6d,c
c.disentangle();
c++;                 // l0: 1b,2,3a,  l1: 4,5,6d,c
c--;                 // l0: 1b,2,3a,  l1: 4,5,6cd,

D’entre els fitxers que s’adjunten en aquest exercici, trobareu list.hh, a on hi ha una implementació de la classe genèrica List. Haureu d’implementar els dos nous mètodes entangle i disentangle dins list.hh a la part pública de la classe iterator (podeu trobar les capçaleres comentades dins list.hh), i modificar els dos mètodes ++ i els dos mètodes -- convenientment (en realitat només cal modificar el pre-increment i el pre-decrement perquè el post-increment i post-decrement criden als primers). Necessitareu també algun atribut addicional per tal de recordar si l’iterador té un entangle actiu i amb qui, amb les convenients inicialitzacions.

Més concretament, heu de fer els canvis que s’indiquen en algunes parts del codi de list.hh:

  // Iterators mutables
  class iterator {
    friend class List;
    private:
      List *plist;
      Item *pitem;
      // Add what it takes to know if the iterator is entangled to another iterator and which one.
      
  public:
      
    iterator() {
      // Add initialization of new attributes.
    }
    
    public:
    
    // Adapt this function so that moving beyond boundaries does not trigger error,
    // but leaves the iterator unchanged instead.
    // Also, add the necessary adaptations so that, the (possible) entangled iterator
    // moves accordingly.    
    // Preincrement
    iterator operator++()
    /* Pre: el p.i apunta a un element E de la llista,
       que no és el end() */
    /* Post: el p.i apunta a l'element següent a E 
       el resultat és el p.i. */
    {
      if (pitem == &(plist->itemsup)) {
        cerr << "Error: ++iterator at the end of list" << endl;
        exit(1);
      }
      pitem = pitem->next;
      return *this;
    }
    
 ...

    // Adapt this function so that moving beyond boundaries does not trigger error,
    // but leaves the iterator unchanged instead.
    // Also, add the necessary adaptations so that, the (possible) entangled iterator
    // moves accordingly.
    // Predecrement
    iterator operator--()
    /* Pre: el p.i apunta a un element E de la llista que
       no és el begin() */
    /* Post: el p.i apunta a l'element anterior a E,
       el resultat és el p.i. */
    {
      if (pitem == plist->iteminf.next) {
       cerr << "Error: --iterator at the beginning of list" << endl;
       exit(1);
      }
      pitem = pitem->prev;
      return *this;
    }

 ...
    
    // Pre: 'it' != 'this'
    // Post: Once executed, any move (++ or --) on 'this' will affect 'it' the same way.
    //       Any previous entangle or disentangle is cancelled.
    // Remove comment marks and implement this function:
    // void entangle(iterator &it) {
    // }
      
    // Pre: 'this' is entangled
    // Post: Previous entangle is cancelled.
    // Remove comment marks and implement this function:
    // void disentangle() {
    // }

 ...

No cal decidir que passa amb assignacions entre iteradors existents, doncs no es consideraran en els jocs de proves.

D’entre els fitxers que s’adjunten a l’exercici també hi ha main.cc (programa principal), i el podeu compilar directament, doncs inclou list.hh. Només cal que pugeu list.hh al jutge.

Entrada

L’entrada del programa comença amb una declaració d’unes quantes llistes (l0, l1, ...) i uns quants iteradors (a,b,c,...), i després té una seqüència de comandes sobre les llistes i els iteradors declarats. Com que ja us oferim el main.cc, no cal que us preocupeu d’implementar la lectura d’aquestes entrades. Només cal que implementeu la extensió de la classe iterator abans esmentada.

Per simplificar, no hi haurà comandes que eliminin elements de les llistes, com pop_back, pop_front i erase. Podeu suposar que les comandes no fan coses extranyes, com fer que un iterador estigui enllaçat per entangle a si mateix, i que sempre que un iterador sigui mogut (directament o indirectament per entangle), aquest estarà apuntant a alguna posició d’alguna llista. Podeu suposar que les comandes faran disentangles només sobre iteradors que tinguin un entangle actiu. Però pot ser el cas que es faci un entangle sobre una iterador que ja tingui un entangle actiu. Com mencionavem abans, en aquestes situacions només l’últim entangle aplica.

Sortida

Per a cada comanda d’escriptura sobre la sortida s’escriurà el resultat corresponent. El main.cc que us oferim ja fa això. Només cal que implementeu la extensió de la classe iterator abans esmentada.

Observació

Avaluació sobre 10 punts:

• Solució lenta: 5 punts.
• solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, on totes les operacions tenen cost constant (excepte l’escriptura de tota la llista per la sortida, que té cost lineal), i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.