Ajustar els salts de ++ i -- a la classe List X57590

Típicament, l’operador ++ dels iteradors de la classe List els desplaça una unitat cap al final de la llista, i l’operador -- dels iteradors de la classe List els desplaça una unitat cap al principi de la llista.

En aquest exercici modificarem i extendrem la classe List. Afegirem dos nous mètodes que permetran modificar com es desplacen els iteradors, en sentit i nombre d’unitats, quan els hi apliquem els operadors ++ i --. Aquests dos nous mètodes s’anomenen changePlusMove i changeMinusMove, i tots dos reben un iterador it per referència i un enter x. El valor absolut de x indica quantes unitats es desplaça it quan se li aplica l’operador. A més, si x és positiu, l’iterador s’ha de desplaçar cap al seu sentit habitual (cap al final de la llista en el cas de changePlusMove i ++, i cap al principi de la llista en el cas de changeMinusMove i --). En canvi, si x és negatiu, llavors el sentit del moviment és l’oposat a l’habitual.

A més a més, modificarem el comportament d’aquests operadors de manera que no produeixen error quan mirem de desplaçar-los més enllà dels límits. En tals casos, simplement no es mouran. Per exemple, si un iterador es troba al end de la llista i mirem de desplaçar-lo una o més unitats cap al final, simplement no es mourà, sense produïr error. I si un iterador es troba al principi de la llista i mirem de desplaçar-lo una o més unitats cap al principi, simplement no es mourà, sense produir error.

Fixeu-vos en el següent exemple de programa i el seu comportament descrit en els seus comentaris.

List<string> l;                        // l:
l.push_back("a");                      // l: a
l.push_back("b");                      // l: a,b
l.push_back("c");                      // l: a,b,c
l.push_back("d");                      // l: a,b,c,d
l.push_back("e");                      // l: a,b,c,d,e
l.push_back("f");                      // l: a,b,c,d,e,f
l.push_back("g");                      // l: a,b,c,d,e,f,g
l.push_back("h");                      // l: a,b,c,d,e,f,g,h
List<string>::iterator it = l.begin(); // l: (a),b,c,d,e,f,g,h
it++;                                  // l: a,(b),c,d,e,f,g,h
l.changePlusMove(it, 2);
it++;                                  // l: a,b,c,(d),e,f,g,h
it--;                                  // l: a,b,(c),d,e,f,g,h
it++;                                  // l: a,b,c,d,(e),f,g,h
l.changePlusMove(it, 5);
it++;                                  // l: a,b,c,d,e,f,g,h()
it++;                                  // l: a,b,c,d,e,f,g,h()
l.changePlusMove(it, -1);
it++;                                  // l: a,b,c,d,e,f,g,(h)
it++;                                  // l: a,b,c,d,e,f,(g),h
l.changePlusMove(it, -3);
it++;                                  // l: a,b,c,(d),e,f,g,h
it++;                                  // l: (a),b,c,d,e,f,g,h
it++;                                  // l: (a),b,c,d,e,f,g,h
it--;                                  // l: (a),b,c,d,e,f,g,h
l.changeMinusMove(it, -2);
it--;                                  // l: a,b,(c),d,e,f,g,h
l.changeMinusMove(it, -3);
it--;                                  // l: a,b,c,d,e,(f),g,h
it--;                                  // l: a,b,c,d,e,f,g,h()
it--;                                  // l: a,b,c,d,e,f,g,h()
l.changeMinusMove(it, 1);
it--;                                  // l: a,b,c,d,e,f,g,(h)
it--;                                  // l: a,b,c,d,e,f,(g),h

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 de buscar dins list.hh les següents línies:

// Pre: 
// Post: Modifica el comportament de l'operador ++ aplicat a aquest iterador it de manera
//       que a partir d'aquest moment es desplaça x unitats cap al final.
// Descomenteu les següents dues linies i implementeu el mètode:
// void changePlusMove(iterator &it, int x) {
// }

// Pre: 
// Post: Modifica el comportament de l'operador -- aplicat a aquest iterador it de manera
//       que a partir d'aquest moment es desplaça x unitats cap al principi.
// Descomenteu les següents dues linies i implementeu el mètode:
// void changeMinusMove(iterator &it, int x) {
// }

Descomenteu les linies que s’indiquen i implementeu els mètodes. També caldrà que modifiqueu altres parts convenientment per tal de poder recordar si a un iterador en concret se li ha modificat el seu moviment i com. També haureu d’adaptar els operadors ++ i -- convenientment.

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 té una seqüència d’instruccions del següent tipus que s’aniran aplicant sobre la llista i dos iteradors que se suposen situats inicialment al principi (i final) de la llista:

push_front s (s és string)
push_back s (s és string)
pop_front
pop_back
it1 = begin
it1 = end
it1 = erase it1
it1++
it1--
++it1
--it1
*it1 = s (s és string)
insert it1 s (s és string)
cout << *it1
changePlusMove it1 x (x és enter)
changeMinusMove it1 x (x és enter)
it2 = begin
it2 = end
it2 = erase it2
it2++
it2--
++it2
--it2
*it2 = x (x és string)
insert it2 x (x és string)
cout << *it2
changePlusMove it2 x (x és enter)
changeMinusMove it2 x (x és enter)
cout << l

Se suposa que la seqüència d’entrada serà correcta, és a dir, que no es produeixen errors d’execució si s’apliquen correctament sobre una llista i dos iteradors amb les condicions abans esmentades.

El programa principal que us oferim ja s’encarrega de llegir aquestes entrades i fer les crides als corresponents mètodes de la classe list. Només cal que implementeu el mètode sum abans esmentat.

Sortida

Per a cada instrucció cout << *it1 o cout << *it2 s’escriurà el contingut apuntat per l’iterador it1 o it2, respectivament. Per a cada instrucció cout << l s’escriurà el contingut de tota la llista. El programa que us oferim ja fa això. Només cal que feu els canvis abans esmentats.

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 cada operació té cost constant o proporcional al nombre de desplaçaments necessaris a aplicar sobre els operadors (en els casos ++ i --), 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.