POO - Laborator 5
		Clase si functii template

Clasele template reprezinta un important mecanism de realizare a polimorfismului. 
Sa consideram extensia de mai jos a clasei stack la un tip generic oarecare T (acest 
tip poate fi elementar sau definit de utilizator printr-o clasa).
Trebuie remarcata sintaxa care contine cuvintele template <class T> in fata definitie 
clasei si in fata definitiei functiilor (a celor care contin tipul generic T).
De asemenea, se observa ca tipul in cauza (atunci cind apare ca parametru al unei functii),
nu mai este stack ci stack<T>, adica stiva parametrizata dupa tipul generic T.
Acelasi lucru la operatorul de rezolutie: clasa careia ii apartin functiile este stack<T>.
De obseravt de asemenea ca in definitia clasei se utilizeaza numele stack (s-a precizat deja
ca e o clasa template prin linia template <class T>.
Implementarea functiilor este practic aceeasi ca la stiva particulara.
La o asemenea definitie de clasa si functii template, trebuie sa analizam atent functiile
scrise si sa vedem ce restrictii (cerinte) se pun asuprta tipului T, in urma acestor functii, in 
situatia in care T ar fi un tip abstract (definit de noi).
De exemplu, in functia operator<< exista linia:

	dev << s.p[i] < " ";

in care s.p[i] este de tip T. Tragem concluzia ca T trebuie sa poata fi trimis la 
un dispozitiv de iesire, adica sa fie tip elementar sau sa aiba supradefinit operator de afisare.
Similar, in functia pop se executa o operatie de genul:

	return p[sp--];

unde p[sp--] este de tip T, ca si functia pop. Asta presupune o operatie de copiere a unui 
obiect de tip T, care va fi intors prin numele functiei. Deci, daca T e definit prin clasa, 
obligatoriu rtebuie sa aiba constructor de copiere.
La functia push, se executa instructiunea:

	p[++sp] = el;

care este o atribuire de obiecte de tip T. Trebuie deci sa avem un operator de atribuire (=), poate
chiar cel implicit (in situatia in care nu folosim alocare dinamica de memorie).
In concluzie, tipul generic T trebuie sa aibe:
	- constructor de copiere
	- operator=
	- operator<<

Programul principal de mai jos declara doua stive de intregi si doua de char*. A se vedea sintaxa 
declaratiilor. Se declara si tablouri de int si char*. Prin push si pop, se inverseaza ordinea 
elementelor din aceste tablouri.

Se defineste apoi cu typedef tipul STI (stiva de intregi sau stack<int>) si se declara o stiva de STI.
Cum STI este un tip generic, el poate foarte bine sa participe pe post de T in declaratia unei clase.
Semnificatia este de "stiva de stive de intregi". Daca analizam restrictiile de mai sus, observam ca STI
indeplineste toate cele 3 conditii enuntate.
Se afiseaza "stiva de stive" ssi la consola. Aceasta va presupune apelul functiei cu prototipul:
	ostream& operator<<(ostream&, stack<STI> &);
iar in aceasta functie, fiecare instructiune:
	dev << s.p[i] << " ";
va conduce la apelul functiei cu prototipul:
	ostream& operator<<(ostream&,  <stack<int>&);
Acest lucru se poate verifica prin mesaje explicite la consola.
In continuare se inverseaza prin push si pop stivele de intregi sti si stj si se verifica acest lucru 
prin afisare inainte si dupa operatie.

 Tema
======

1) Se va rula programul de mai jos, completindu-l cu declaratii de stive cu alte tipuri decit int si char *.
2) Se va defini un tip de date (de exemplu o structura) care sa nu indeplineasca una sau mai multe din 
conditiile puse tipului T si se va incerca definirea unei stive de acest tip. Ce se va intimpla?
3) Sa se deseneze o schema grafica in care sa se ilustreze locatiile de memorie
ocupate de stiva ssi dupa cele doua push-uri. 

#include <assert.h>
#include <iostream.h>

template <class T>
class stack {
	T *p;
	int nrmax;
	int nrcrt;
	int sp;
public:
	stack(int = 100);
	~stack();
	stack(stack &);
	void push(T);
	T pop(void);
	int empty(void);
	int full (void);
	stack & operator= (stack &);
	friend ostream& operator<<(ostream&, stack &);
};

template <class T> ostream& operator<<(ostream& dev, stack<T>& s)
{
	for (int i=0; i < s.nrcrt; i++)
		dev << s.p[i] << " ";
	dev << "\n";
	return dev;
}

template <class T> stack<T>::stack(int n = 100)
{
	p = new T[n];
	nrmax = n; nrcrt = 0; sp = -1;
}

template <class T> stack<T>::stack(stack <T> & s)
{
	p = new T[s.nrmax];
	nrmax = s.nrmax; nrcrt = s.nrcrt;
	sp = s.sp;
	for (int i = 0; i < nrcrt; i++)
		p[i] = s.p[i];
}

template <class T> stack<T>::~stack()
{
	delete [] p;
}

template <class T> void stack<T>::push(T el)
{
	assert(nrcrt < nrmax);
	p[++sp] = el;
	nrcrt++;
}

template <class T> T stack<T>::pop(void)
{
	assert(nrcrt > 0);
	nrcrt--;
	return p[sp--];
}

template <class T> int stack<T>::full(void)
{
	return (nrcrt == nrmax);
}

template <class T> int stack<T>::empty(void)
{
	return (nrcrt == 0);
}

template <class T> stack<T> & stack<T>::operator=(stack <T> & s)
{
	T *q = new T[s.nrmax];
	assert(q != NULL);
	nrmax = s.nrmax;
	nrcrt = s.nrcrt;
	sp = s.sp;
	for (int i = 0; i < nrcrt; i++)
		q[i] = s.p[i];
	delete [] p;
	p = q;
	return *this;
}

typedef stack<int> STI;

void main(void)
{
	stack<int> si;
	stack<char *> ss;

	int i, a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, };
	char *s[10] = { "1", "2", "3", "4","5","6","7","8","9","10", };

	for(i = 0; i < 10; i++) {
		si.push(a[i]);
		ss.push(s[i]);
	}

	stack<int> sj(si);
	stack<char *> st;
	st = ss;

	i = 0;
	while (!sj.empty())
		a[i++] = sj.pop();

	i = 0;
	while (!st.empty())
		s[i++] = st.pop();

	for(i = 0; i < 10; i++)
		cout << a[i] << " ";
	cout << "\n";

	for(i = 0; i < 10; i++)
		cout << "\"" << s[i] << "\" ";
	cout << "\n";

	sj.push(21); sj.push(22);

	stack<STI> ssi;
	ssi.push (si); ssi.push(sj);

	cout << "si: " << si;
	cout << "sj: " << sj;

	cout << "Stiva de stive: ";
	cout << ssi << "\n";   		// Se va apela operatorul << pentru
						// elementele componente

	si = ssi.pop(); sj = ssi.pop();	// Inversam si cu sj

	cout << "si: " << si;
	cout << "sj: " << sj;
}