/*
================================================================================
  RPL/2 (R) version 4.1.32
  Copyright (C) 1989-2020 Dr. BERTRAND Joël

  This file is part of RPL/2.

  RPL/2 is free software; you can redistribute it and/or modify it
  under the terms of the CeCILL V2 License as published by the french
  CEA, CNRS and INRIA.
 
  RPL/2 is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  FITNESS FOR A PARTICULAR PURPOSE.  See the CeCILL V2 License
  for more details.
 
  You should have received a copy of the CeCILL License
  along with RPL/2. If not, write to info@cecill.info.
================================================================================
*/


#include "rpl-conv.h"


/*
================================================================================
  Fonction d'affichage d'un arbre q-aire
================================================================================
  Entrées : pointeur sur une structure struct_processus
--------------------------------------------------------------------------------
  Sorties :
--------------------------------------------------------------------------------
  Effets de bord : néant
================================================================================
*/

static void
affichage_arbre(struct_processus *s_etat_processus, struct_arbre *s_arbre,
		int niveau)
{
	int							i;

	integer8					branche;

	struct_liste_chainee		*l_element_courant;

	unsigned char				*chaine;

	if (niveau == 0)
	{
		printf("--- Arbre $%016X\n", s_arbre);
	}

	// Affichage de la feuille (fonction ou donnée générale s'il n'y 
	// a pas de branche)

	l_element_courant = (*s_arbre).feuille;

	for(i = 0; i < niveau; i++)
	{
		printf("  ");
	}

	while(l_element_courant != NULL)
	{
		if ((chaine = formateur(s_etat_processus, 0,
				(*l_element_courant).donnee)) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return;
		}

		printf("%s ", chaine);
		free(chaine);

		l_element_courant = (*l_element_courant).suivant;
	}

	printf("\n");

	// Affichage des branches (arguments de la fonction dans la feuille)

	for(branche = 0; branche < (*s_arbre).nombre_branches; branche++)
	{
		affichage_arbre(s_etat_processus, (*s_arbre).branches[branche],
				niveau + 1);
	}

	if (niveau == 0)
	{
		printf("--- Fin de l'arbre\n");
	}

	return;
}


/*
================================================================================
  Fonction de transcription d'un arbre en liste chaînée
================================================================================
  Entrées : pointeur sur une structure struct_processus
--------------------------------------------------------------------------------
  Sorties :
--------------------------------------------------------------------------------
  Effets de bord : néant
================================================================================
*/

static struct_liste_chainee *
transcription_arbre(struct_processus *s_etat_processus, struct_arbre *s_arbre)
{
	integer8				i;

	struct_liste_chainee	*l_element_courant;
	struct_liste_chainee	*l_liste;
	struct_liste_chainee	*l_nouvelle_pile_locale;
	struct_liste_chainee	*l_pile_locale;

	l_pile_locale = NULL;

	for(i = 0; i < (*s_arbre).nombre_branches; i++)
	{
		if ((l_nouvelle_pile_locale = allocation_maillon(s_etat_processus))
				== NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return(NULL);
		}

		(*l_nouvelle_pile_locale).suivant = l_pile_locale;
		l_pile_locale = l_nouvelle_pile_locale;

		if (((*l_pile_locale).donnee = (void *) transcription_arbre(
				s_etat_processus, (*s_arbre).branches[i])) == NULL)
		{
			return(NULL);
		}
	}

	// Ajout des fonctions

	if ((*s_arbre).nombre_branches != 0)
	{
		free((*s_arbre).branches);
	}

	l_liste = (*s_arbre).feuille;
	free(s_arbre);

	// Chaînage des arguments

	while(l_pile_locale != NULL)
	{
		l_element_courant = (void *) (*l_pile_locale).donnee;

		if (l_element_courant == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_pile_vide;
			return(NULL);
		}

		while((*l_element_courant).suivant != NULL)
		{
			l_element_courant = (*l_element_courant).suivant;
		}

		(*l_element_courant).suivant = l_liste;
		l_liste = (void *) (*l_pile_locale).donnee;

		l_nouvelle_pile_locale = (*l_pile_locale).suivant;
		liberation_maillon(s_etat_processus, l_pile_locale);
		l_pile_locale = l_nouvelle_pile_locale;
	}

	return(l_liste);
}


/*
================================================================================
  Fonction de simplification d'un arbre
================================================================================
  Entrées : pointeur sur une structure struct_processus
--------------------------------------------------------------------------------
  Sorties :
--------------------------------------------------------------------------------
  Effets de bord : néant
================================================================================
*/

static int
ordonnancement_branches(const void *a1, const void *a2)
{
	struct_arbre	**_a1;
	struct_arbre	**_a2;

	_a1 = (struct_arbre **) a1;
	_a2 = (struct_arbre **) a2;

	if (((**_a1).feuille != NULL) && ((**_a2).feuille != NULL))
	{
		// Si les types sont identiques, on ne change rien.

		if ((*(*(**_a1).feuille).donnee).type ==
				(*(*(**_a2).feuille).donnee).type)
		{
			return(0);
		}

		// On rejette les nombres à la fin.

		if (((*(*(**_a1).feuille).donnee).type == INT) ||
				((*(*(**_a1).feuille).donnee).type == REL) ||
				((*(*(**_a1).feuille).donnee).type == CPL))
		{
			return(1);
		}
		else
		{
			return(-1);
		}
	}

	return(0);
}


static int
ordonnancement_instructions_neg(const void *a1, const void *a2)
{
	struct_arbre	**_a1;

	_a1 = (struct_arbre **) a1;

	if ((**_a1).feuille != NULL)
	{
		// On rejette NEG à la fin de l'arbre.

		if ((*(*(**_a1).feuille).donnee).type == FCT)
		{
			if (strcmp((*((struct_fonction *) (*(*(**_a1).feuille).donnee)
					.objet)).nom_fonction, "NEG") == 0)
			{
				return(1);
			}
			else
			{
				return(-1);
			}
		}
		else
		{
			return(0);
		}
	}

	return(0);
}


static void
simplification_arbre(struct_processus *s_etat_processus,
		struct_arbre *s_arbre)
{
	integer8				i;
	integer8				j;
	integer8				nouveaux_elements;

	struct_arbre			*s_branche;

	struct_liste_chainee	*l_element_courant;
	struct_liste_chainee	*l_element_suivant;

	struct_objet			*s_objet;

	if ((*(*(*s_arbre).feuille).donnee).type != FCT)
	{
		// L'objet formant le noeud n'est pas une fonction. Il n'y a aucune
		// simplification possible.

		return;
	}

	// Transformation des soustractions que l'on remplace par
	// une addition de l'opposé. Si l'on a une soustraction,
	// on greffe donc une instruction NEG dans l'arbre.
	// Note : à cet instant, l'instruction '-' ne peut avoir que deux
	// opérandes.

	if (strcmp((*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
			.nom_fonction, "-") == 0)
	{
		if ((*s_arbre).nombre_branches != 2)
		{
			(*s_etat_processus).erreur_execution = d_ex_simplification;
			return;
		}

		liberation(s_etat_processus, (*((*s_arbre).feuille)).donnee);

		if (((*((*s_arbre).feuille)).donnee = allocation(s_etat_processus,
				FCT)) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return;
		}

		if (((*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
				.nom_fonction = malloc(2 * sizeof(unsigned char))) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return;
		}

		strcpy((*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
				.nom_fonction, "+");
		(*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
				.nombre_arguments = 1;

		if ((s_branche = malloc(sizeof(struct_arbre))) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return;
		}

		if (((*s_branche).branches = malloc(sizeof(struct_arbre *))) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return;
		}

		if (((*s_branche).feuille = allocation_maillon(s_etat_processus))
				== NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return;
		}

		(*(*s_branche).feuille).suivant = NULL;

		if (((*(*s_branche).feuille).donnee = allocation(s_etat_processus, FCT))
				== NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return;
		}

		if (((*((struct_fonction *) (*(*(*s_branche).feuille).donnee).objet))
				.nom_fonction = malloc(4 * sizeof(unsigned char))) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return;
		}

		strcpy((*((struct_fonction *) (*(*(*s_branche).feuille).donnee).objet))
				.nom_fonction, "NEG");
		(*((struct_fonction *) (*(*(*s_branche).feuille).donnee).objet))
				.nombre_arguments = 1;
		(*s_branche).branches[0] = (*s_arbre).branches[1];
		(*s_branche).nombre_branches = 1;
		(*s_arbre).branches[1] = s_branche;
	}

	// La feuille est une fonction, on peut envisager la simplification
	// de l'arbre. Pour cela, on descend d'un niveau pour greffer
	// de nouvelles branches.

	if (strcmp((*((struct_fonction *) (*(*(*s_arbre).feuille).donnee).objet))
			.nom_fonction, "+") == 0)
	{
		qsort((*s_arbre).branches, (size_t) (*s_arbre)
				.nombre_branches, sizeof(struct_arbre *),
				ordonnancement_instructions_neg);

		for(i = 0; i < (*s_arbre).nombre_branches; i++)
		{
			s_objet = (*((*((*s_arbre).branches[i])).feuille)).donnee;

			if ((*s_objet).type == FCT)
			{
				if (strcmp((*((struct_fonction *) (*s_objet).objet))
						.nom_fonction, "-") == 0)
				{
					simplification_arbre(s_etat_processus,
							(*s_arbre).branches[i]);
					s_objet = (*((*((*s_arbre).branches[i])).feuille)).donnee;
				}

				if (strcmp((*((struct_fonction *) (*s_objet).objet))
						.nom_fonction, "+") == 0)
				{
					simplification_arbre(s_etat_processus,
							(*s_arbre).branches[i]);

					/*
					 On greffe.
+
  +
    2
    SIN
      3
  10

					 doit donner :
+
  2
  SIN
    3
  10
					*/

					nouveaux_elements = (*(*s_arbre).branches[i])
							.nombre_branches;

					if (((*s_arbre).branches = realloc((*s_arbre).branches,
							((unsigned) ((*s_arbre).nombre_branches
							+ nouveaux_elements))
							* sizeof(struct_arbre *))) == NULL)
					{
						(*s_etat_processus).erreur_systeme =
								d_es_allocation_memoire;
						return;
					}

					for(j = 0; j < nouveaux_elements; j++)
					{
						(*s_arbre).branches[(*s_arbre).nombre_branches++] =
								(*(*s_arbre).branches[i]).branches[j];
					}

					l_element_courant = (*s_arbre).feuille;
					(*s_arbre).feuille = (*(*s_arbre).branches[i]).feuille;

					l_element_suivant = (*s_arbre).feuille;
					while((*l_element_suivant).suivant != NULL)
					{
						l_element_suivant = (*l_element_suivant).suivant;
					}

					(*l_element_suivant).suivant = l_element_courant;
					free((*(*s_arbre).branches[i]).branches);
					free((*s_arbre).branches[i]);

					// Retrait de la branche
				
					for(j = i + 1; j < (*s_arbre).nombre_branches; j++)
					{
						(*s_arbre).branches[j - 1] = (*s_arbre).branches[j];
					}

					(*s_arbre).nombre_branches--;

					// Réorganisation des valeurs numériques en queue.

					qsort((*s_arbre).branches, (size_t) (*s_arbre)
							.nombre_branches, sizeof(struct_arbre *),
							ordonnancement_branches);
				}
			}
		}

		if (((*s_arbre).branches = realloc((*s_arbre).branches,
				((unsigned) (*s_arbre).nombre_branches)
				* sizeof(struct_arbre *))) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return;
		}
	}

	return;
}


/*
================================================================================
  Fonction 'simplification' (ne libère pas les paramètres)
================================================================================
  Entrées : pointeur sur une structure struct_processus
--------------------------------------------------------------------------------
  Sorties :
--------------------------------------------------------------------------------
  Effets de bord : néant
================================================================================
*/

struct_objet *
simplification(struct_processus *s_etat_processus, struct_objet *s_objet)
{
	struct_objet				*s_objet_simplifie;

	integer8					i;
	integer8					nombre_arguments;

	struct_arbre				*s_arbre;

	struct_liste_chainee		*l_element_courant;

	// Attention : l_liste_locale et l_ancienne_liste_locale ne contiennent pas
	// un pointeur sur une struct_objet, mais sur une struct_arbre.

	struct_liste_chainee		*l_liste_locale;
	struct_liste_chainee		*l_ancienne_liste_locale;

	if ((*s_objet).type == ALG)
	{
		/*
		 * Transcription de l'expression algébrique en arbre q-aire
		 */

		l_liste_locale = NULL;
		l_element_courant = (*s_objet).objet;

		while(l_element_courant != NULL)
		{
			switch((*(*l_element_courant).donnee).type)
			{
				// Toutes les fonctions (intrinsèques, extrinsèques et
				// utilisateurs).

				case FCT:
				{
					// Il s'agit d'un objet de type ALG. Nous pouvons donc
					// sauter les délimiteurs d'expression.

					if ((l_element_courant != (*s_objet).objet) &&
							((*l_element_courant).suivant != NULL))
					{
						nombre_arguments = (*((struct_fonction *)
								(*(*l_element_courant).donnee).objet))
								.nombre_arguments;

						// Si le nombre d'arguments vaut 0, la fonction
						// apparaît en notation algébrique comme une fonction
						// infixe.

						if (nombre_arguments == 0)
						{
							nombre_arguments = 2;
						}

						if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
						{
							(*s_etat_processus).erreur_systeme =
									d_es_allocation_memoire;
							return(NULL);
						}

						(*s_arbre).nombre_branches = nombre_arguments;

						if (((*s_arbre).feuille = allocation_maillon(
								s_etat_processus)) == NULL)
						{
							(*s_etat_processus).erreur_systeme =
									d_es_allocation_memoire;
							return(NULL);
						}

						(*(*s_arbre).feuille).donnee = copie_objet(
								s_etat_processus, (*l_element_courant).donnee,
								'P');
						(*(*s_arbre).feuille).suivant = NULL;

						if (((*s_arbre).branches = malloc(((size_t) (*s_arbre)
								.nombre_branches) * sizeof(struct_arbre *)))
								== NULL)
						{
							(*s_etat_processus).erreur_systeme =
									d_es_allocation_memoire;
							return(NULL);
						}

						for(i = nombre_arguments - 1; i >= 0; i--)
						{
							if (l_liste_locale == NULL)
							{
								(*s_etat_processus).erreur_execution =
										d_ex_manque_argument;
								return(NULL);
							}

							(*s_arbre).branches[i] = (struct_arbre *)
									(*l_liste_locale).donnee;

							l_ancienne_liste_locale = l_liste_locale;
							l_liste_locale = (*l_liste_locale).suivant;

							liberation_maillon(s_etat_processus,
									l_ancienne_liste_locale);
						}

						// Introduction de l'arbre dans la pile locale

						l_ancienne_liste_locale = l_liste_locale;

						if ((l_liste_locale = allocation_maillon(
								s_etat_processus)) == NULL)
						{
							(*s_etat_processus).erreur_systeme =
									d_es_allocation_memoire;
							return(NULL);
						}

						(*l_liste_locale).suivant = l_ancienne_liste_locale;
						(*l_liste_locale).donnee = (void *) s_arbre;
					}

					break;
				}

				default:
				{
					l_ancienne_liste_locale = l_liste_locale;

					if ((l_liste_locale = allocation_maillon(s_etat_processus))
							== NULL)
					{
						(*s_etat_processus).erreur_systeme =
								d_es_allocation_memoire;
						return(NULL);
					}

					(*l_liste_locale).suivant = l_ancienne_liste_locale;

					if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
					{
						(*s_etat_processus).erreur_systeme =
								d_es_allocation_memoire;
						return(NULL);
					}

					if (((*s_arbre).feuille = allocation_maillon(
							s_etat_processus)) == NULL)
					{
						(*s_etat_processus).erreur_systeme =
								d_es_allocation_memoire;
						return(NULL);
					}

					(*(*s_arbre).feuille).donnee = copie_objet(
							s_etat_processus, (*l_element_courant).donnee, 'P');
					(*(*s_arbre).feuille).suivant = NULL;
					(*s_arbre).nombre_branches = 0;
					(*s_arbre).branches = NULL;

					(*l_liste_locale).donnee = (void *) s_arbre;
					break;
				}
			}

			l_element_courant = (*l_element_courant).suivant;
		}

		// Toute l'expression a été balayée. On ne doit plus avoir qu'un
		// seul niveau dans la pile locale, ce niveau contenant l'arbre
		// à réduire.

		if (l_liste_locale == NULL)
		{
			(*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
			return(NULL);
		}
		else if ((*l_liste_locale).suivant != NULL)
		{
			(*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
			return(NULL);
		}

		s_arbre = (void *) (*l_liste_locale).donnee;

		liberation_maillon(s_etat_processus, l_liste_locale);
		l_liste_locale = NULL;

		/*
		 * Simplification de l'arbre
		 */

		affichage_arbre(s_etat_processus, s_arbre, 0);
		simplification_arbre(s_etat_processus, s_arbre);
		affichage_arbre(s_etat_processus, s_arbre, 0);

		if ((*s_etat_processus).erreur_systeme != d_es)
		{
			return(NULL);
		}

		/*
		 * Transcription de l'arbre q-aire simplifié en expression algébrique.
		 * Seule une fonction récursive permet de faire cette conversion
		 * simplement.
		 */

		l_liste_locale = transcription_arbre(s_etat_processus, s_arbre);

		if ((s_objet_simplifie = allocation(s_etat_processus, ALG))
				== NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return(NULL);
		}

		// Ajout des délimiteurs '<<' et '>>' à la liste d'instructions

		if (((*s_objet_simplifie).objet = allocation_maillon(s_etat_processus))
				== NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return(NULL);
		}

		l_element_courant = (*s_objet_simplifie).objet;

		if (((*l_element_courant).donnee = allocation(s_etat_processus,
				FCT)) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return(NULL);
		}

		(*((struct_fonction *) (*(*l_element_courant).donnee).objet))
				.nombre_arguments = 0;
		(*((struct_fonction *) (*(*l_element_courant).donnee).objet))
				.fonction = instruction_vers_niveau_superieur;

		if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
				.nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return(NULL);
		}

		strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
				.nom_fonction, "<<");

		(*l_element_courant).suivant = l_liste_locale;

		while((*l_element_courant).suivant != NULL)
		{
			l_element_courant = (*l_element_courant).suivant;
		}

		if (((*l_element_courant).suivant =
				allocation_maillon(s_etat_processus)) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return(NULL);
		}

		l_element_courant = (*l_element_courant).suivant;
		(*l_element_courant).suivant = NULL;

		if (((*l_element_courant).donnee = allocation(s_etat_processus,
				FCT)) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return(NULL);
		}

		(*((struct_fonction *) (*(*l_element_courant).donnee).objet))
				.nombre_arguments = 0;
		(*((struct_fonction *) (*(*l_element_courant).donnee).objet))
				.fonction = instruction_vers_niveau_inferieur;

		if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
				.nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
		{
			(*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
			return(NULL);
		}

		strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
				.nom_fonction, ">>");
	}
	else
	{
		s_objet_simplifie = copie_objet(s_etat_processus, s_objet, 'P');
	}

	return(s_objet_simplifie);
}

// vim: ts=4