Algoritmica si iteratori in C++

O "tema" interesanta pentru iubitorii de algoritmica:

Sa se scrie o clasa generica BinaryTree<T> ce poata fi folosita in urmatorul mod:

BinaryTree<int> t;
t.push(1);
t.push(2);
t.push(3);
t.remove(2);
cout << t.size() << endl;
for (BinaryTree<int>::iterator it = t.begin(PreOrder); it != t.end(); it++)
{
   cout << *it << endl;
}
for (BinaryTree<int>::iterator it = t.begin(InOrder); it != t.end(); it++)
{
   cout << *it << endl;
}
for (BinaryTree<int>::iterator it = t.begin(PostOrder); it != t.end(); it++)
{
   cout << *it << endl;
}

Clasa va pune la dispozitie 3 tipuri iteratori (avand BinaryTree<T>::iterator drept clasa de baza), pentru cele 3 tipuri de traversari.
Cand se apeleaza begin(), se specifica metoda dorita de traversare cu ajutorul unei valori dintr-un enum.
Sa existe si o functie begin() ce nu accepta nici un parametru, si care va folosi o oarecare metoda de traversare.

Bafta & spor.
Solutiile partiale sunt si ele acceptate, pentru a se putea discuta pe seama lor.

Am incercat eu o varianta, insa cel putin deocamdata mi-a iesit asa ceva.

//main.cpp
#include <iostream>
#include "BinaryTree.h"
int main()
{
BinaryTree<int> t;
t.push(6);
t.push(4);
t.push(2);
t.push(5);
t.push(7);
t.push(8);
t.remove(2);
std::cout<<"Tree of size: "<<t.size()<<"\n";
std::cout<<"Preorder: ";
for(auto it = t.begin_preord(); it != t.end_preord(); it++)
{
std::cout<<*it<<" ";
}
std::cout<<"\n";
std::cout<<"Inorder: ";
for(auto it = t.begin_inord(); it != t.end_inord(); it++)
{
std::cout<<*it<<" ";
}
std::cout<<"\n";
std::cout<<"Postorder: ";
for(auto it = t.begin_postord(); it != t.end_postord(); it++)
{
std::cout<<*it<<" ";
}
std::cout<<"\n";
return 0;
}

Am incarcat fisierele aici: https://github.com/S...ntrol/softpedia deoarece sunt destul de multe linii de cod.
BinaryTree.h este varianta care merge. BinaryTree2.h nu merge, insa ar fi varianta mai preferabila OOP, care ar rezolva problema polimorfismului in cazul iteratorilor.

Operatia push am implementat-o astfel incat sa incerce sa formeze un arbore complet (parcurg arborele cu un BFS pana cand gasesc primul loc "liber" si inserez un nod acolo).
Operatia remove poate sa stearga o frunza sau un nod care are un singur copil (uneste parintele cu acel copil si sterge nodul). In cazul in care trebuie sa stearga un nod ce are 2 copii, va ignora acest lucru (mi s-a parut cam ambigua partea asta.. adica acest BinaryTree nu e nici si heap si nici BST, deci practic ar fi cam nedefinita o astfel de stergere). Nodul de sters va fi cautat printr-un DFS (am zis sa mai variez, daca anterior am folosit BFS ).

Destructorul pentru arbore l-am facut parcurgand arborele printr-un DFS.

In cazul iteratorilor, am facut cate unul pentru fiecare tip de traversare, ei difera cam numai prin constructor si prin supraincarcarea lui ++ prefixat.
Pentru a face traversarile, am folosit o stiva (am senzatia ca se putea face eficient, avand in vedere ca am si legatura la parinte, daca tineam un vector de noduri vizitate).
Practic, cand se apeleaza begin, voi face primul pas din fiecare parcurgere prin apelul constructorului, iar apoi, la fiecare ++ se va face cate un nou pas din parcurgere.
La postfixata am "trisat" un pic, am folosit 2 stive si practic in constructor deja voi avea intreaga parcurgere in a doua stiva, iar cand apelez ++ o sa preiau cate un nod din acea stiva.

Am intampinat cateva probleme:
- Nu am reusit sa separ declaratiile de functii de definitii (intr-un .h si .cpp). Mergea numai daca la finalul .cpp-ului indicam ce va fi acel tip <T>.
- Am incercat sa fac o clasa abstracta Iterator (BinaryTree2.h) si cate un IteratorPreOrd, IteratorPostOrd, IteratorInOrd care sa mosteneasca acea clasa, ca sa pot sa am acel polimorfism
din cerinta lui Dani

for (BinaryTree<int>::iterator it = t.begin(PreOrder); it != t.end(); it++)

Am implementat in Iterator toate metodele cu exceptia constructorilor si a lui ++ prefixat. ++ prefixat am facut-o pure virtual in Iterator.
Iar in begin am folosit un factory pattern pentru a alege intre iteratori.

Problema este ca BinaryTree<int>::iterator it = t.begin(PreOrder) nu prea merge. Eu ma gandeam ca problema se pune ca in Java, sa declar o variabila de tipul clasei abstracte (Iterator) si sa o instantiez ca altceva (IteratorPreOrder)... insa acel begin returneaza un obiect de tip Iterator (chiar daca apelez constructorul pentru IteratorPreOrder, va fi sliced la Iterator pentru ca Iterator e tipul functiei) si da eroare de "cannot allocate an object of abstract type"

Eu unul as inregistra strategiile de iterare din exteriorul clasei BinaryTree, nu le-as face inner classes, si nicidecum nu le-as hardcoda. Pentru gruparea intr-un pachet exista namespaces.

Prefer composition over <X> (inheritance).

^^Iteratorii se transmit traditional prin valoare, n-are rost sa incerci sa-i folosesti polimorfic.

Mersi pentru incercare.
Nu poti separa .h de .cpp in cazul templates, decat daca particularizezi T pentru anumite valori. Asta fiindca template-ul e, prin definitie, un sablon, iar compilatorul are nevoie de cod pentru a genera cod nou.

Treaba cu polimorfismul si pasarea prin valoare mi-a scapat (prea mult managed code in ultimul timp). In cazul asta eu as vedea solutia urmatoare: BinaryTree<T>::iterator ramane o clasa simpla, interna, iar la construire va primi si o instanta a TraversalStrategy.
Asa extinzi practic aceasta noua clasa, iar astea le poti plasa oriunde, nu neaparat drept clase interne.

Multumesc pentru sugestii tuturor. Asa este, compunerea ar fi o varianta mult mai in regula . Eu am mers pe gandirea "is a" vs "has a", insa se pare ca nu prea a mers din pricina faptului ca nu aveam nevoie de la bun inceput de acel Iterator abstract; asa ca pentru "A is a B" nu exista B in prealabil xD.

O idee interesant ce mi-a venit citind un alt topic:

Sa se dezvolte un iterator ce ajuta la parcurgerea unei matrici in spirala. Ceva in genul

int a[][3] = 
{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
};
//3, 3 = dimensiuni
//1, 1 = punct de pornire
for (SpiralIterator<int> it = beginSpiral(a, 3, 3, 1, 1); it != endSpiral(a); it++)
{
   cout << *it << ' '; 
}

Quote

Se poate incepe bine-mersi si din margine.

Edited by dani.user, 06 July 2014 - 15:11.