/*
Hem decidit implementar aquest algoritme mitjan¨ant els BST ja que es una estructura que funciona molt be per a fer insercions
ordenadament.
(n=nombre de noms insertats)
En tot l'algorisme fem 2*n assignacions que tenen cost Theta(h) i fem dos llistats. El cost dels llistats es Theta(n), com que
son costosos aprofitem un dels llistats per crear el segon bst, amb un cost de Theta(h) per a cada insercio.
COST TOTAL= 2*Theta(n*h) + 2*Theta(n) = Theta(n*h) per la regla de la suma

Podriem haver realitzat l'algorisme utilitzant per exemple una taula de hash pero en cas que hi haguessin hagut colisions
el cost de fer les insersions seria mes elevat perque hauriem de mantenir una llista ordenada.
*/




#include <iostream>
using namespace std;
#define null 0;


/*Definim l'estructura del Binary Search Tree*/
struct Node
{
	string nom; 
	int saldo; 
	Node* fesq; // Punter al fill esquerre 
	Node* fdre; // Punter al fill dret 
	Node (string n, int s, Node* fe, Node* fd) 
	: nom(n), saldo(s), fesq(fe), fdre(fd) { } 
}; 


/*Aquesta operacio inserta un node amb clau "nom" i info "saldo" penjant del node p*/
/*La difer¸ncia amb el BST normal es que quan troba que la clau ja existeix no sobreescriu la informaci—, la suma*/
/*Ordena per NOM*/
void assignarnom (Node*& p, string nom, int saldo) 
{ 
	if (p) //si el node on volem insertar no es null
	{
		if (nom < p->nom) //si el nom que volem assignar al nou node es inferior a l'arrel
		{
			assignarnom(p->fesq,nom,saldo);		//cridem recursivament per insertar al subarbre esquerre
		}
		else if (nom > p->nom) //si el nom que volem assignar al nou node es mes gran que el de l'arrel
		{ 
			assignarnom(p->fdre,nom,saldo);		//cridem recursivament per insertar al subarbre dret
		}	
		else //en cas que ja existeixi una persona amb aquest nom
		{ 
			p->saldo = p->saldo+saldo;	//li actualitzem el saldo (sumantlo a l'actual)
		} 
	} 
	else 
	{ 
		p = new Node(nom,saldo,0,0);	//si arribem a un node buit, alla hi afegim el nou node
	} 
} 


/*Aquesta operacio inserta un node amb clau "nom" i info "saldo" penjant del node p*/
/*La difer¸ncia amb el BST normal es que no tracta apart el cas que ja existeixi. Si la clau a insertar es mes gran 
  o igual crida recursivament per assignar al fill esquerre*/
/*Ordena per SALDO*/
void assignarsaldo (Node*& p, string nom, int saldo) 
{ 
	if (p) //si el node on volem insertar no es null
	{ 
		if (saldo < p->saldo) //si el saldo que volem assignar al nou node es inferior a l'arrel
		{ 
			assignarsaldo(p->fesq,nom,saldo); //cridem recursivament per insertar al subarbre esquerre
		}
		else if (saldo >= p->saldo) //si el saldo que volem assignar al nou node es mes gran o igual que el de l'arrel
		{ 
			assignarsaldo(p->fdre,nom,saldo); //afegim per la dreta
		}	
	} 
	else 
	{ 
		p = new Node(nom,saldo,0,0);	//si arribem a un node buit, alla hi afegim el nou node
	} 
}


/*Aquesta operacio llista en preordre el BST ordenat per nom, i al mateix temps genera el BST ordenat per saldo*/
void llistarpernom(Node* p, Node *s)
{
	if (p)	//si no es null
	{
		llistarpernom(p->fesq, s);	//llistem el subarbre esquerre
		if (p->nom!="")	
		{
			cout << p->nom;			//escrivim la informacio
			cout << " ";
			cout << p->saldo << endl;
			assignarsaldo(s, p->nom, p->saldo);		//insertem el primer node a l'arbre
		}	
		llistarpernom(p->fdre,s);	//listem el subarbre dret
	}
}


/*Aquesta operacio llista en preordre el BST ordenat per saldo*/
void llistarpersaldo(Node* p)
{
	if (p)	//si no es null
	{
		llistarpersaldo(p->fesq); //llistem el subarbre esquerre
		if (p->nom!="")
		{
			cout << p->nom;	//escrivim la informacio
			cout << " ";
			cout << p->saldo << endl;
		}
		llistarpersaldo(p->fdre);	//llistem el subarbre dret
	}
}


int main() 
{
	string nom1, nom2;	//inicialitzem les variables per llegir de l'entrada
	int diners;
	struct Node *s;	//creem l'arrel de l'arbre on insertarem els saldos
	s=new Node("", 0, 0, 0); //inicialitzem l'arrel amb un nom null
	struct Node *no;	//creem l'arrel de l'arbre on insertarem els noms
	no=new Node("", 0, 0, 0);	//inicialitzem l'arrel amb un nom null
	while (cin >> nom1 >> nom2 >> diners)	//mentre entrin dades per l'entrada estandar
	{
		assignarnom(no, nom1, -diners);		//actualitzem o creem el node amb nom nom1 i li restem diners
		assignarnom(no, nom2, diners);		////actualitzem o creem el node amb nom nom1 i li sumem diners
	}
	llistarpernom(no, s);	//cridem a la funcio que llista en inordre i li passem l'arrel del BST on volem que insereixi els saldos
	cout << "--------------------" << endl;	//pintem els 20 guions
	llistarpersaldo(s);	//finalment llistem en inordre el BST que ens ha generat l'operacio anterior
}