canciones.cpp

// Header 

template <class T, class P, class C> // P para funcion procesar y C para funcion comparar
class ArbolAVL {
	struct Nodo {
		T elem; // payload
		Nodo* izq;
		Nodo* der;
		int h; // altura: numero de ramas desde el nodo hasta la hoja más lejana

		Nodo(T elem = 0, Nodo* izq = nullptr, Nodo* der = nullptr, int h = 0)
			: elem(elem), izq(izq), der(der), h(h) {}
	};

	Nodo* raiz;
	P procesar; // templates de punteros a funciones o lambdas
	C comparar; // templates de punteros a funciones o lambdas

	Nodo* dummynull = nullptr;
public:
	ArbolAVL(P procesar, C comparar)
		: procesar(procesar), comparar(comparar), raiz(nullptr) {}
	bool insertar(T e) {
		return _insertar(raiz, e);
	}
	void enOrden() {
		_enOrden(raiz);
	}
	int altura() {
		_altura(raiz);
	}
	T buscar(T e) {
		return _buscar(raiz, e);
	}
	bool eliminar(T e) {
		Nodo*& nodo = _encontrar(raiz, e);
		if (nodo == nullptr) return false;
		Nodo* reemplazo = _encontrarReemplazo(nodo);
		if (reemplazo == nullptr) {
			delete nodo;
			nodo = nullptr;
		}
		else {
			reemplazo->izq = nodo->izq;
			reemplazo->der = nodo->der;
			Nodo* temp = nodo;
			nodo = reemplazo;
			delete temp;
		}
		return true;
	}
private:
	bool igualA(T a, T b) { return comparar(a, b) == 0; }
	bool menorQue(T a, T b) { return comparar(a, b) < 0; }
	bool menorIgualQue(T a, T b) { return comparar(a, b) <= 0; }
	bool mayorQue(T a, T b) { return comparar(a, b) > 0; }
	bool mayorIgualQue(T a, T b) { return comparar(a, b) >= 0; }

	void _rotarIzq(Nodo*& x, Nodo* y) { // p es el padre de x
		Nodo* temp = x;
		x = y;
		temp->der = y->izq;
		y->izq = temp;
	}
	void _rotarDer(Nodo*  x, Nodo*& y) { // p es el padre de y
		Nodo* temp = y;
		y = x;
		temp->izq = x->der;
		x->der = temp;
	}
	int _altura(Nodo* nodo) {
		if (nodo == nullptr) return -1;
		return nodo->h; // implementacion optima en tiempo
	}

	bool _insertar(Nodo*& nodo, T e) {
		if (nodo == nullptr) {
			nodo = new Nodo(); // h = 0
			nodo->elem = e;
		}
		else if (menorIgualQue(e, nodo->elem)) { // menorQue no permite duplicados a la izquierda
			_insertar(nodo->izq, e);
		}
		else /* if (mayorQue(e, nodo->elem)) */ { // descomentar para no aceptar duplicados
			_insertar(nodo->der, e);
		}
		int hi = _altura(nodo->izq);
		int hd = _altura(nodo->der);
		int d = hd - hi;
		if (d > 1) { // pesado a la derecha
			int hni = _altura(nodo->der->izq);
			int hnd = _altura(nodo->der->der);
			if (hni > hnd) { // zig zag derecha izquierda
				_rotarDer(nodo->der->izq, nodo->der);
			}
			_rotarIzq(nodo, nodo->der);
		}
		else if (d < -1) { // pesado a la izquierda
			int hni = _altura(nodo->izq->izq);
			int hnd = _altura(nodo->izq->der);
			if (hnd > hni) { // zig zag izquierda derecha
				_rotarIzq(nodo->izq, nodo->izq->der);
			}
			_rotarDer(nodo->izq, nodo);
		}
		hi = _altura(nodo->izq);
		hd = _altura(nodo->der);
		nodo->h = 1 + (hi > hd ? hi : hd);
		return true;
	}

	void _enOrden(Nodo* nodo) {
		if (nodo == nullptr) return;
		_enOrden(nodo->izq);
		procesar(nodo->elem);
		_enOrden(nodo->der);
	}
	T _buscar(Nodo* nodo, T e) { // template funcional
		if (nodo == nullptr) return 0;
		if (igualA(e, nodo->elem)) {
			return nodo->elem;
		}
		else {
			return _buscar(
				mayorQue(e, nodo->elem) ? nodo->der : nodo->izq, e);
		}
	}
	Nodo* _extraerMayor(Nodo*& nodo) {
		if (nodo == nullptr) return nullptr;
		if (nodo->der == nullptr) {
			Nodo* temp = nodo;
			nodo = nodo->izq;
			temp->izq = nullptr;
			return temp;
		}
		else {
			return _extraerMayor(nodo->der);
		}
	}
	Nodo* _extraerMenor(Nodo*& nodo) {
		if (nodo == nullptr) return nullptr;
		if (nodo->izq == nullptr) {
			Nodo* temp = nodo;
			nodo = nodo->der;
			temp->der = nullptr;
			return temp;
		}
		else {
			return _extraerMenor(nodo->izq);
		}
	}
	Nodo*& _encontrar(Nodo*& nodo, T e) { // template funcional
		if (nodo == nullptr) return dummynull;
		if (igualA(e, nodo->elem)) {
			return nodo;
		}
		else {
			return _encontrar(menorQue(e, nodo->elem) ? nodo->izq : nodo->der, e);
		}
	}
	Nodo* _encontrarReemplazo(Nodo*& nodo) {
		Nodo* reemp = _extraerMayor(nodo->izq);
		if (reemp == nullptr) {
			reemp = _extraerMenor(nodo->der);
		}
		return reemp;
	}
};


// Source.cpp 

#include "Header.h"
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <functional>
#include <fstream>

#define MAX 20

using namespace std;

class Cancion {
	string titulo;
	string artista;
	int anio;
public:
	Cancion(string titulo = "", string artista = "", int anio = 1970) : 
		titulo(titulo), artista(artista), anio(anio) {}

	string getTitulo() { return titulo; }
	string getArtista() { return artista; }
	int getAnio() { return anio; }
};

typedef function<void(Cancion*)> LambdaProc;// P pocesar
typedef function<int(Cancion*, Cancion*)> LambdaComp;// Comparar
typedef ArbolAVL<Cancion*, LambdaProc, LambdaComp> Arbolito;

void indexar(vector<Cancion*> canciones, Arbolito* arbol) {
	for_each(canciones.begin(), canciones.end(), [arbol](Cancion* c) { arbol->insertar(c); });
}
void leer(vector<Cancion*>&vec) {
	ifstream Arch("canciones.csv");
	if (Arch.is_open()) {
		string nombre;
		while (getline(Arch, nombre, ',')) {
			{
				string artista;	getline(Arch, artista,',');
				string an; getline(Arch, an);
				int anio = atoi(an.c_str());

				vec.push_back(new Cancion(nombre, artista, anio));
			}
		}
	}
	Arch.close();
}

void guardar(vector<Cancion*>vec) {
	ofstream Arch;
	Arch.open("canciones.csv");
	if (Arch.good())
	{
		for (int i = 0; i < vec.size(); i++)
		{
			Arch << vec[i]->getTitulo() << ","<< vec[i]->getArtista()<<","<<vec[i]->getAnio()<<endl;
		}
	}
	Arch.close();
}

int main() {
	vector<Cancion*> canciones;

	srand(time(0));
	cout << "Insertando elementos!" << endl;
	leer(canciones);
	auto mostrar = [](Cancion* c) {cout << c->getTitulo()<<", "<<c->getArtista()<<", "<<c->getAnio()<<endl; };
	auto comparar = [](Cancion* a, Cancion* b) { return a->getAnio() - b->getAnio(); }; // comparando por año
	
	Arbolito* arbol = new Arbolito(mostrar, comparar); // arbolito para indexar

	cout << "Indexando!" << endl;
	indexar(canciones, arbol);

	Cancion* dummy = new Cancion("", "", 2010);

	Cancion* cancion = arbol->buscar(dummy);
	delete dummy;

	if (cancion != nullptr) {
		cout << "Encontrado!" << endl;
		cout << "Cancion: " << cancion->getTitulo() << endl
		     << "Artista: " << cancion->getArtista() << endl;
	}
	//arbol->enOrden();
	guardar(canciones);

	cout << "Borrando todo!" << endl;
	for (int i = 0; i < canciones.size(); ++i) {
		delete canciones[i];
	}
	cout << "Bye bye!" << endl;
	cin.get();
	return 0;
}