#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graphe_adj_type.h"
#include "graphe_poids_type.h"
#include "graphe_liste_type.h"
#include "util_adj.h"
#include "util_poids.h"
#include "graphe.h"

GRAPHE liste_to_graphe(GRAPHE_LISTE g)
{
  GRAPHE res;
  res=init_adj_mat(1);
  return res;
}

SOMMET *trouve_noeud(GRAPHE_LISTE g,int num)
{
  SOMMET *visitor;
  visitor=g.sommets;
  while (visitor != NULL)
    {
      if (visitor -> num == num)
	return visitor;
      visitor = visitor -> suivant;
    }
  printf("Error:noeud numéro %d non trouve dans le graphe\n", num);
  exit(-1);
}

SOMMET *new_sommet(int num,ARC *arc)
{
  SOMMET *new;
  new=(SOMMET *)malloc(sizeof(SOMMET));
  new->num=num;
  new->arcs=arc;
  return new ;
}

/* add a new sommet (sorted sommet list) */
GRAPHE_LISTE add_sommmet(GRAPHE_LISTE g, SOMMET *s)
{
  SOMMET *visitor;
  int num=s->num;
  visitor=g.sommets;
  if (visitor==NULL)
    {
      g.sommets=s;
      return g;
    }
  else
    {
      while (visitor -> suivant != NULL)
	{
	  if (visitor -> num < num )
	    visitor = visitor -> suivant;
	  else
	    break;
	}
      s -> suivant = visitor -> suivant;
      visitor -> suivant = s;
      return g;
    }
}
  

ARC *add_arc(ARC *arcs,SOMMET *s)
{
  ARC *visitor_arc, *new;
  int num=s->num;
  new=(ARC *)malloc(sizeof(ARC));
  new->voisin = s;
      
  visitor_arc=arcs;
  if (visitor_arc==NULL)
    {
      new -> arc_suivant=NULL;
      return new;
    }
  else
    {
      if (visitor_arc -> voisin -> num > num)
	{
	  new -> arc_suivant = visitor_arc;
	  return new;
	}
      while (visitor_arc -> arc_suivant != NULL)
	{
	  if (visitor_arc -> voisin -> num < num )
	    visitor_arc = visitor_arc -> arc_suivant;
	  else
	    break;
	}
      new -> arc_suivant = visitor_arc -> arc_suivant;
      visitor_arc -> arc_suivant = new;
      return arcs;
    }
}
  
  
  

GRAPHE_LISTE graphe_to_liste(GRAPHE g)
{
  GRAPHE_LISTE res;
  SOMMET *s;
  int N;
  N=g.nb_sommets;
  res.nb_sommets=0;
  res.sommets=NULL;
  
  for (int i=0;i<N;i++)
    {
      s=new_sommet(i+1,NULL);
      res=add_sommmet(res,s);
      res.nb_sommets++;
    }
  SOMMET *visitor=res.sommets;
  while (visitor!=NULL)
    {
      int num=visitor -> num;
      ARC *visitor_arc=NULL;
      for (int j=0; j<N; j++)
	{
	  if (g.adj[num-1][j]==1)
	    {
	      SOMMET *voisin=trouve_noeud(res,j+1);
	      visitor_arc=add_arc(visitor_arc,voisin);
	    }
	}
      visitor -> arcs = visitor_arc;
      visitor=visitor -> suivant;
    }
  
  return res;
}

void affiche_graphe_liste(FILE *fich,GRAPHE_LISTE g)
{
  SOMMET *visitor;
  
  fprintf(fich,"%d Noeuds dans le graphe:\n",g.nb_sommets);
  visitor=g.sommets;
  while (visitor!=NULL)
    {
      fprintf(fich," %4d, ",visitor->num);
      visitor=visitor->suivant;
    }
  fprintf(fich,"\n\n Liste des voisins:\n");
  visitor=g.sommets;
  while (visitor!=NULL)
    {
      ARC *visitor_arc;
      fprintf(fich, " Sommet %4d: \n",visitor->num);
      visitor_arc=visitor->arcs;
      while(visitor_arc!=NULL)
	{
	  fprintf(fich," %d -> %d , ",visitor->num,
		  visitor_arc -> voisin -> num);
	  visitor_arc=visitor_arc->arc_suivant;
	}
      fprintf(fich,"\n\n");
      visitor=visitor->suivant;

    }
}

