-- Notion de File
--
-- Une file est une suite :
--   - dont les informations sont souvent representees de facon contigues
--     en memoire (par le biais de tableaux)
--   - dont la taille est souvent fixe (utilisation des tableaux)
--
-- La notion de pile est souvent utilisee en programmation pour gerer
-- des objets en attente d'un traitement (file d'impression, evenements X11)
--
-- Une pile est definie par :
--    - un ensemble d'elements d'un type donne
--    - un indicateur du debut de la file (cas des tableaux) 
--    - un indicateur de la fin de la file (cas des tableaux)
--
-- Proprietes
--
--    - dans une file, on n'ajoute qu'au debut (queue)
--    - on ne supprime qu'en fin (tete)
--    - on ne lit en general que la valeur de l'elt de fin de file
--    - on ne supprime en general qu'en fin de file
--
-- On dit que l'on a une gestion FIFO des files, contre une
-- gestion LIFO des piles.
-----------------------------------------------------------
with Text_IO ; use Text_IO ; -- pour les entrees/sorties

procedure file is

  type ELT is new INTEGER ;
  MAX : CONSTANT INTEGER := 100 ;
  type TYP_TAB is array (INTEGER range <>) of ELT ;
  type FILE is
     record 
        taille : INTEGER:=MAX ;
	debut : INTEGER ;
	fin : INTEGER ;
	f : TYP_TAB(0..MAX) ;
     end record ;
  package ELT_Io is new Integer_IO (ELT); use ELT_Io;
  package Int_Io is new Integer_IO (INTEGER); use Int_Io;

  -- cre une file
  function creation return FILE is
     f1 : FILE ;
     i : INTEGER ;
  begin
      -- initialisation facultative
      for i in 0..MAX loop
	 f1.f(i) := 0 ;
      end loop ;
      f1.debut := 0 ; 
      f1.fin := 0 ; 
      return(f1) ;
  end creation ;

  -- retourne V si la file est vide et F sinon
  function file_vide(f1 : in FILE) return BOOLEAN is
  begin
     if (f1.debut=f1.fin) then return(TRUE) ;
     else return(FALSE) ;
     end if ;
  end file_vide ;

  -- retourne V si la file est pleine et F sinon
  function file_pleine(f1 : in FILE) return BOOLEAN is
  begin
     if (f1.debut-1)=f1.fin OR (f1.debut=0 AND f1.fin=f1.taille)
     then return(TRUE) ;
     else return(FALSE) ;
     end if ;
  end file_pleine ;

  -- ajoute en debut
  procedure ajout(f1 : IN OUT FILE ; e : IN ELT) is
  begin
     if not file_pleine(f1) then
	f1.f(f1.debut) := e ;
	f1.debut := f1.debut - 1 ;
	if (f1.debut<0) then f1.debut := f1.taille ;
	end if ;
     else
	put("Erreur, depassement de capacite") ; new_line ;
     end if ;
  end ajout ;

  -- supprime en fin
  procedure retrait(f1 : IN OUT FILE) is
  begin
     if not file_vide(f1) then
	f1.f(f1.fin) := 0 ; -- pas absolument necessaire
	f1.fin := f1.fin - 1 ;
	if (f1.fin<0) then f1.fin := f1.taille ;
	end if ;
     else
	put("Erreur, plus d'elements dans la file") ; new_line ;
     end if ;
  end retrait ;

  -- valeur du sommet de file
  function valeur (f1 : in FILE) return ELT is
  begin
     return(f1.f(f1.fin)) ;
  end valeur ;

-- programme principal
i : integer ;
e : ELT := 0 ;
ma_file : FILE ;
begin
   new_line ;

   ma_file := creation ;
   for i in 1..10 loop
        put(i) ; new_line ;
        ajout(ma_file, e) ;
   end loop ;
   for i in 1..10 loop
        put(valeur(ma_file)) ;
        put(i) ; new_line ;    
        retrait(ma_file) ;
   end loop ;
   new_line ;
end file ;

-- Exercices
--
-- 1) Recrire ce programme de facon a faire tourner la file dans l'autre
--    sens.
--
-- 2) Recrire ce programme en utilisation une allocation dynamique des
-- cellules de la file