#include <stdlib.h>
#include <stdio.h>
#include "tree.h"
#include <string.h>

void setCharCode(Node* tree)
{
	if (tree->left != NULL)
        strcat(tree->left->code,"0" );
	if (tree->right != NULL)
		strcat(tree->right->code, "1");
	if (tree->left != NULL)
		setCharCode(tree->left);
	if (tree->right != NULL)
		setCharCode(tree->right);
}


int compNodeByFreq(const void* a, const void* b)
{
	Node *na, *nb;
	na = *(Node**)a;
	nb = *(Node**)b;
	if (na->freq < nb->freq)
		return -1;
	else if (na->freq > nb->freq)
		return 1;
	return 0;
}

Node* createNode(int freq, char c)
{
	Node* new = malloc(sizeof(*new));
	new->freq = freq;
	new->c = c;
	new->code[0] = '\0';
	new->left = NULL;
	new->right = NULL;

	return new;
}

void initNodes(int* tabFreq, Node** outNodeArray, int* outSize)
{
	int j = 0;
	for (int i = 0; i < TAB_FREQ_SIZE; i++)
	{
		if (tabFreq[i] != 0) {
			outNodeArray[j] = createNode(tabFreq[i], i);
			j++;
		}
	}
	*outSize = j;
}


void printNodeArray(Node** outNodeArray, int outSize)
{
	for(int i = 0; i < outSize; i++)
	{
		printf("%d\n", outNodeArray[i]->freq);
	}
}


Node* joinNode(Node* n1, Node* n2)
{
	Node* fusion = malloc(sizeof(Node));
	fusion->freq = n1->freq + n2->freq;
	if(n1->freq < n2->freq)
	{
		fusion->left = n1;
		fusion->right = n2;
	}
		
	else
	{
		fusion->left = n2;
		fusion->right = n1;
	}
	return fusion;
}

Node* generateTree(Node** outNodeArray, int outSize)
{
    int currSize = outSize;
    Node* newFusion;
    int i =0;
    while(currSize > 1)
    {
        newFusion = joinNode(outNodeArray[0+i], outNodeArray[1+i]);
        outNodeArray[0+i]=createNode(-1, 0);
        outNodeArray[1+i]=newFusion;
        qsort(outNodeArray, outSize, sizeof(Node*), compNodeByFreq);
        currSize--;
        i++;
    }
    outNodeArray[outSize-1]->code[0] = '\0';
	return outNodeArray[outSize-1];
}


void affichage_arborescence_version1(Node * arbre, int offset)
{
	if(arbre != NULL)
	{
		// Etape 1 - afficher la valeur
		printf("\n");
		afficher_offset(offset);
		if( offset != 0 ) // tous les éléments sauf la racine
		{
			printf("|-");
		}
		printf("%d\t", arbre->freq);
        printf("Code : %s", arbre->code);
		
		// Etape 2 - appel récursif avec sous-arbre gauche
		
			// Si à gauche (et uniquement à gauche) c'est NULL on affiche "|-x" maintenant,
			// car ne sera pas atteint via la récursivité (cf. if général)
			if( !est_feuille(arbre) && (arbre->left == NULL) )
			{
				printf("\n");
				afficher_offset(offset+1);
				printf("|-x");
			}
		affichage_arborescence_version1(arbre->left, offset+1);
		
		// Etape 3 - appel récursif avec sous-arbre de droite
		
			// Si à doite (et uniquement à droite) c'est NULL on affiche "|-x" maintenant,
			// car ne sera pas atteint via la récursivité (cf. if général)
			if( !est_feuille(arbre) && (arbre->right == NULL) )
			{
				printf("\n");
				afficher_offset(offset+1);
				printf("|-x");
			}
		affichage_arborescence_version1(arbre->right, offset+1);
	}
	//else <=> arrêt de la récursivité
}


bool est_feuille(Node* element)
{
	bool feuille = false;
	
	if( element != NULL )
	{
		if( (element->left == NULL) && (element->right == NULL) )
		{
			feuille = true;
		}
	}
	
	return feuille;
}

void afficher_offset(int offset)
{
	for(int i = 0 ; i < offset ; i++)
	{
		printf("  "); // 2 espaces
	}
}