Tehnici de Programare in C++

		5. CLASE CONTAINER IN C++

	5.1 Colectii de obiecte

   O colectie (un container) este o clasa ce reuneste mai multe obiecte de un
tip sau altul. Problema este de a avea cite o singura clasa pentru o fiecare
structura (vector, lista, arbore, etc), indiferent de tipul datelor memorate 
in colectie, si nu cite o clasa separata pentru fiecare tip de date memorate.
   Numarul tipurilor de date in C++ nu este limitat, deoarece orice noua clasa
definita reprezinta un nou tip de date.
   Prima abordare pentru clasele container in C++ a fost aceea de a crea o
ierarhie de clase, astfel ca toate tipurile clasa sa fie derivate dintr-un
tip de baza ("Object") si deci sa fie compatibile si substituibile intre ele.
   Ideea este de a memora in container obiecte sau pointeri la obiecte de
tipul Object, care apoi vor fi inlocuite cu obiecte (pointeri la obiecte)
de un tip derivat din Object. Trebuie observat ca, in general, sunt necesare
conversii in ambele sensuri intre cele doua tipuri:
 - De la un tip T la tipul Object, cind se introduc date in container;
 - De la tipul Object la tipul T, cind se extrag date din container, pentru
a se putea folosi metodele clasei T asupra obiectelor scoase din container
(de exemplu, pentru afisarea lor).
   Sa consideram cea mai simpla structura de date - structura de vector. In
C++ avem teoretic doua posibilitati de a defini componentele unui vector:
 - Componente de tip Object :
      Object x[10];
 - Componente de tip Object* (pointeri la tipul Object):
      Object * x[10];
   Nu este permisa declararea de vectori cu componente referinte, dupa cum
nu se pot declara pointeri la referinte sau referinte la referinte.
   Memorarea de variabile de tip Object intr-un container nu permite
apelarea de functii polimorfice (virtuale), deci ramine numai solutia unei
colectii de pointeri la tipul de baza Object.
   Exemplu: O lista de pointeri la Object, un tip "String" derivat din
Object si un program care foloseste o lista de siruri (de obiecte String).

  // clasa de la baza ierarhiei
class Object {
public:
   virtual void print() { cout << this << ' ';}
   virtual int equals (Object& obj) { return this==&obj;}
} ;
   // operator utilizabil ptr. orice clasa derivata din Object
 inline int operator == (Object& ob1, Object& ob2) {
    return ob1.equals(ob2);
 }

  // un vector de pointeri la Object
class Vector {
  Object* * vec;   // adresa vector cu componente Object*
  int n, nmax;     // dimensiune efectiva si maxima vector
public:
  Vector (int size) {
    vec=new Object* [nmax=size]; n=0; }
  ~Vector() { delete [] vec; }
  void print ();
  void add (Object& obj) { vec[n++]= &obj; }
  int size() { return n;}
  Object & operator[] (int i) {
    assert (i<n); return *vec[i];
  }
};
   // afisare vector
void Vector::print () {
    for (int i=0; i<n; i++) {
      vec[i]->print(); cout <<"  ";
    }
  cout << "\n";
}
    // siruri de caractere
class String: public Object {
  char * str;
public:
  String (char * s) { str =new char[strlen(s)+1]; strcpy (str,s);}
  ~String() { delete str;}
  void print () { cout << str << ' ';}
  int equals (Object& obj) {
     String & strobj= *(String*) &obj;
     return strcmp (str, strobj.str)==0 ? 1:0;
  }
};
	// program de test
void main () {
 Vector a(10);
 String st[]={ "1","2","3","4","5"};
  for (int i=0;i<5;i++)
    a.add (st[i]);    // umplere vector
 cout << endl;
 a.print();           // afisare vector
 for (i=0;i<a.size();i++)
   a[i].print();
 if ( a[i] == st[2]) cout << "este\n";
 else cout << "nu este! \n";
}

	5.2 Distrugerea colectiilor de pointeri

   Memorarea de pointeri la obiecte intr-o clasa container creaza noi
probleme: 
 - eliminarea unui pointer din container implica sau nu si distrugerea
obiectului adresat de pointer?
 - ce memorie se elibereaza la distrugerea unui obiect container?
   O posibilitate este sa se distruga mai intii obiectele ale caror adrese
se pastrau in container si apoi sa se distruga obiectul container. Este
insa posibil ca adresa unui aceluiasi obiect sa fie memorata in mai multe
locuri (variabile separate sau componente dintr-o colectie).
   O alta posibilitate este de a elibera numai memoria ocupata de obiectul
container, dar atunci se pierd adresele unor obiecte alocate dinamic si
nu se mai poate recupera memoria ocupata de aceste obiecte.
   Deoarece numai utilizatorul unui container poate sti daca obiectele
sunt sau nu in "proprietatea" ("ownership") containerului, s-a decis ca 
programatorul sa spuna ce trebuie facut la distrugerea unui container si/sau
la eliminarea unui pointer din container.
   O posibilitate este sa se memoreze in clasa container o variabila
care sa arate dreptul containerului asupra obiectelor reunite; aceasta
variabila este initializata la construirea unui obiect container si este
utilizata la distrugerea acelui obiect. Exemplu:
  // vector cu drept de decizie asupra obiectelor din lista
enum bool {no=0,yes=1};
  // un vector de pointeri la Object
class Vector {
  Object* *vec;   // adresa vector cu componente Object*
  int n, nmax;     // dimensiune efectiva si maxima vector
  bool own;       // daca are sau nu drept de proprietate
public:
  Vector (int size, bool Owns= yes) {
    nmax=size; n=0; vec= new Object*[nmax];
    own=Owns; }
  ~Vector ();
  void print ();
  void add (Object& obj) { vec[n++]= &obj; }
  Object& operator [] (int i) {
   assert (i<n); return * vec[i];
  }
  int size() {return n;}
};
  // destructor inteligent
Vector::~Vector () {
  if (vec==NULL) return;
  if (own ==yes)
    for (int i=0;i<n;i++)
      delete vec[i];
  delete vec;
}

   Exemplul urmator arata un caz de utilizare a parametrului "Owns":
   
void main () {
 Vector a(10,yes);
 char* vs[]={"unu","doi","trei"};
 for (int i=0;i<3;i++) {
   a.add (* new String(vs[i]));  // siruri alocate dinamic
 }

   In exemplul urmator este folosita varianta "no" pentru "Owns":

void main () {
 Vector a(10,no);
 String vs[]={"unu","doi","trei"};
 for (int i=0;i<3;i++) {
   a.add (vs[i]);  // siruri alocate de compilator
 }

   O alta posibilitate este sa se prevada metode diferite pentru cele doua
situatii:
 - Metoda "detach" elimina un pointer din container, dar nu distruge obiectul
de la adresa continuta in pointer ("desprinde" obiectul de container).
 - Metoda "destroy" face in plus fata de "detach" si distrugerea obiectului
de la adresa eliminata din container.
   O a treia posibilitate este ca metoda "detach" ("remove") sa aiba un 
parametru de tip "bool" care sa arate ce se face cu obiectul detasat de 
container: ramine alocat sau se elimina din memorie.


	5.3 Clase container abstracte si concrete

   Nu exista un consens asupra gruparii diferitelor colectii concrete in
colectii abstracte si fiecare biblioteca de clase container foloseste
propria sa ierarhizare si grupare a acestor clase.
   Ideea comuna este ca putem stabili citeva tipuri abstracte de date,
care au aceleasi operatii (metode), dar ca fiecare tip abstract poate fi
implementat in citeva moduri, prin diferite structuri de date concrete.
   De exemplu, tipul abstract "lista" ("List") corespunde unei colectii 
de obiecte nu neaparat distincte, in care se permite selectarea unui element
din lista dupa pozitia sa (un indice intreg). Cele mai frecvente operatii cu
o lista sunt adaugarea unui element la sfirsitul listei si extragerea (sau
modificarea) obiectului dintr-o pozitie data.
   Clasa abstracta "List" ofera o interfata comuna programelor care folosesc
liste, indiferent de modul concret cum sunt ele realizate. Mai mult,
se recomanda ca programele de aplicatii sa foloseasca numai variabile de
tip "List" sau "List*" (sa se programeze la nivel de interfata si nu de clasa
concreta).
  // clasa abstracta ptr liste
class List: public Object {
public:
  virtual void add (Object & p)=0;
  virtual int size()=0;
  virtual Object& get(int i)=0;
};

  // o lista vector
class Vector:public List {
  Object* * vec;   // adresa vector cu componente Object*
  int n, nmax;     // dimensiune efectiva si maxima vector
public:
  Vector (int size) { vec=new Object* [nmax=size]; n=0; }
  ~Vector() { delete [] vec; }
  void print ();
  void add (Object& obj) { vec[n++]= &obj; }
  int size() { return n;}
  Object& get(int i) {
    assert (i <n); return *vec[i];
  }
};
  // o lista inlantuita
class LinkLst: public List {
  struct Nod {
    Object* ptr;     // un nod contine un pointer la Object
    Nod * leg;       // legatura la nodul urmator
    Nod (Object& obj) { ptr=&obj; leg=NULL;} // constructor
  };
private:
   Nod * first;        // list head
public:
   LinkLst() {first = new Nod( *new Object);};
   ~LinkLst() ;
   void add (Object&);
   void print() ;
   int size();
   Object& get(int i);
};

   Functia urmatoare cauta un obiect dat intr-o lista de obiecte, indiferent
de tipul concret al obiectelor sau de implementarea listei:

 // cautare obiect intr-o lista
int find (List* lst, Object& obj) {
  for (int i=0;i< lst->size();i++)
     if (obj== lst->get(i))
       return 1;
  return 0;
}

   Parametrul ce specifica lista nu poate fi de tip "List" deoarece "List"
este o clasa abstracta si nu poate fi instantiata. Am preferat utilizarea
unei functii "get" in locul operatorului [] pentru selectia elementului
din pozitia "i" deoarece utilizarea operatorului [] cu un pointer este
susceptibila de o utilizare gresita. Comparatia trebuia scrisa astfel:
    if (obj == (*lst)[i])
si nu in forma urmatoare (corecta sintactic dar cu efect diferit):
    if (obj == lst[i])    
   Se poate defini si un operator de selectie, alaturi de functia "get"
pentru situatiile cind se foloseste un obiect de tip "List" si nu un
pointer la tipul "List".
   Sa presupunem ca din clasa abstracta "List" sunt derivate clasele concrete
"Vector" si "LinkLst". Programul urmator creaza cite o lista din fiecare
tip, le afiseaza si cauta in una din liste un obiect de tip "String".

void main () {
 List* list1= new Vector(20);
 List* list2 = new LinkLst;
 String a[5]={"1","2","3","4","5"};
 cout << endl;
 for (int i=0;i<5;i++) {
   list1->add(a[i]);  list2->add(a[i]);
 }
 list1->print();  list2->print();
 if (find (list1,String("3")))
   cout << "este \n";
 else
   cout << "nu este \n";
}

   Functiile "add", "print" si "get" sunt comune oricarui tip de lista, chiar
daca implementarea lor este diferita.
    // functia Vector::get
  Object& Vector:: get (int i) {
    assert (i <n); return *vec[i];
  }
   // dimensiune vector
  inline Vector::int size() { return n;}

    // functia LinkLst::get
 Object& LinkLst::get (int i) {
   Nod * p= first->leg;
   while ( i-- && p !=NULL)
     p=p->leg;
   return * p->ptr;
 }
  // dimensiune lista
int LinkLst::size() {
 int sz=0;
 Nod * p= first->leg;
 while (p !=NULL) {
    ++sz; p=p->leg;
 }
 return sz;
}

   Pentru alegerea unui tip sau altul de lista este suficient sa modificam
linia in care se initializeaza variabila de tip "List*", restul programului
ramine la fel. Schimbarea implementarii poate fi necesara din motive de 
eficienta sau pentru afisarea in ordine a elementelor multimii (daca s-ar 
folosi o lista inlantuita ordonata).


	5.4 Clase iterator

   In exemplele anterioare, parcurgerea unei liste (pentru afisare sau
pentru comparare) folosea functia "get" si un indice, dar exista alte
structuri de date pentru care nu este aplicabil accesul pozitional la
elementele colectiei (de ex. un arbore sau un tabel de dispersie).
   De aceea s-a cautat o forma mai generala (si mai abstracta) pentru
enumerarea elementelor unei colectii, care sa nu depinda de modul concret
de adresare a elementelor colectiei (prin indici sau pointeri).
   Un iterator este un mecanism de parcurgere (vizitare) a componentelor
unei colectii si are rolul de a abstractiza acest proces de enumerare a
elementelor colectiei, independent de modul concret cum este implementata
colectia (ca vector, ca lista cu pointeri, ca tabel de dispersie, ca arbore).
   Un iterator are 3 sau 4 componente :
 - O functie de initializare, care realizeaza pozitionarea pe primul element
din colectie (pe inceputul colectiei);
 - O functie de verificare a sfirsitului colectiei ;
 - O functie de avans la elementul urmator din colectie (de incrementare a
pozitiei curente).
 - O functie de extragere a elementului din pozitia curenta.
   De multe ori operatia de extragere a elementului curent este combinata
cu operatia de avans la elementul urmator, intr-o singura functie.
   Un iterator poate fi privit ca un "super-pointer" sau ca un cursor ce
se poate deplasa pas cu pas in cadrul unei colectii.
   In C++ avem posibilitatea ca o parte din functiile unui iterator sa 
fie exprimate prin operatori: operator de incrementare (++) si operatori
de indirectare (* sau -> pentru un "smart-pointer").
   In principiu, avem doua posibilitati de realizare a unui iterator pentru
o colectie:
 - ca iterator intern, implementat prin citeva metode ale colectiei
 - ca iterator extern, implementat printr-un obiect dintr-o clasa de tip
iterator.
   Iteratorul realizat ca o clasa separata de clasa colectie permite ca
pentru o aceeasi colectie sa avem mai multi iteratori, in pozitii diferite.
   Clasa iterator trebuie sa aiba acces la date din clasa colectie, deci
trebuie declarata ca o clasa prietena (pentru a nu face publice toate datele
clasei container).
   In continuare se exemplifica clase iterator pentru vectori si liste.

  // iterator ptr. vectori
class VecIter {
  Vector& avec;
  int crt;    // pozitie curenta in vector
public:
  VecIter (Vector* v): avec (*v) { crt=0;}
  operator int () { return crt<avec.n? 1:0 ; }
  Object*  operator ++() {
    assert ( crt < avec.n);
     return  avec.vec[crt++];
  }
};
  // iterator ptr. liste
class LinkIter {
  LinkLst& alst;
  LinkLst::Nod* crt;    // pozitie curenta in lista
public:
  LinkIter (LinkLst* list): alst (*list) { crt= list->first->leg;}
  operator int () { return crt != NULL ? 1:0 ; }
  Object*  operator ++() {
    assert ( crt != NULL);
    Object* p= crt->ptr;
    crt=crt->leg;
     return p ;
  }
};

  // exemplu de utilizare iterator ptr afisare 
 Vector a (10);
 ... // adaugare la vector
 Iterator * it=  new VecIter (&a);
 while ( *it !=0)
    (++ *it)->print();
 cout << "\n lista cu iterator: \n";

   Observind ca ambele clase iterator contin aceleasi metode (la care se
mai pot adauga si alte metode comune), este normal sa ne punem problema
definirii unei clase abstracte "Iterator", din care sa fie derivate
clasele concrete operator.

  // clasa absracta (interfata) ptr iteratori
class Iterator {
public:
  virtual operator int()=0;
  virtual Object* operator++()=0;
};
  // clase iterator concrete
class VecIter: public Iterator { .. }
class LinkIter: public Iterator {...}

   Existenta unei clase iterator generale, pentru parcurgerea oricarei
colectii de obiecte, permite scrierea unor algoritmi "generici" sub forma
unor functii aplicabile oricarei colectii : sortare colectie, cautare
intr-o colectie, compararea a doua colectii, determinarea valorilor extreme
dintr-o colectie, copierea unei colectii, etc. Exemplu:
  // algoritm generic: cautare obiect in lista
int search (List* list, Object key) {
  Iterator * it = list->iterator();
  while (*it !=0 )
    if ( (*it).equals (key) )
      return 1;
    else
      ++ (*it);
  return 0;
}