ed9-corrige

ED 9--corrigé

Les paquetages

Enoncé

Une file de priorité (FP) est une séquence d'élements munis d'une priorité. L'insertion d'un nouvel élément dans une FP ne tient pas compte de l'ordre de priorité. En revanche, lors d'une extraction, c'est toujours l'élément de plus haute priorité qui est retiré. Si plusieurs éléments possèdent la même plus haute priorité, seul un élément est extrait.

On définit un Type Abstrait de Données (TAD) pour les FPs :

type FP Domaine de valeurs : ensemble des FPs
Opérations taille : FP -> N inserer : Element*FP -> FP extraire : FP -> Element vide : -> FP racine : FP -> Element Sémantique inserer : on insère un élément en queue de la séquence extraire : (soit X, l'entier extrait, quel que soit Y appartenant à FP, X>=Y)

Les élements que l'on veut insérer et extraire d'une FP sont des articles caractérisés par deux champs :
le sigle d'un aéroport (chaine de 3 caractères) et sa priorité (un entier naturel). Les opérations réalisables sur ces éléments sont :

Domaine de valeurs : Element
Utilise : Chaine (de 3 caractères)
Opérations :
get : Chaine *Naturel -> Element
put : Element -> vide
itemPriorite : Element -> Naturel
itemChaine : Element -> Chaine

On donne la spécification Ada de ce TAD :

--PAQUETAGE ITEMFP (spécification)

package itemfp is
type Chaine3 is new string(1..3);
type Element is private;

function itemValeur(e:Element) return Chaine3;
function itemPriorite(e:Element) return natural;
procedure put(e:in Element);
function get(c:Chaine3;p:natural) return Element;
private
type Element is
record
valeur:Chaine3;
priorite:natural;
end record;
end itemfp;

A titre indicatif, voici son implantation. Sa connaissance n'est pas nécessaire pour la suite de l'exercice.

-- PAQUETAGE ITEMFP (body)

with text_io;use text_io;
package body itemfp is
package natural_io is new integer_io(natural);

function get(c: in Chaine3;p:in natural) return Element is
e:Element;
begin
e.valeur:=c;
e.priorite:=p;
return e;
end get;

function itemValeur(e:Element) return Chaine3 is
begin
return e.valeur;
end itemValeur;

function itemPriorite(e:Element) return natural is
begin
return e.priorite;
end itemPriorite;

procedure put(e:in Element)is
begin
put("(");
put(e.valeur,width=>3);
put(",");
natural_io.put(e.priorite,width=>2);
put(") ");
end put;
end itemfp;
-------------------------------------------
-------------------------------------------

Chaque élément, quelle que soit sa priorité est rangé dans le tableau à la première place libre, repérée par un indice. Lors de l'extraction, une place du tableau est libérée et les éléments suivants sont décalés vers la gauche afin de combler la place vacante. On suppose le tableau suffisamment grand pour satisfaire toute insertion .
Question 4 : Définir le type FP. Ne pas oublier que l'indice d'insertion ainsi que le nombre d'éléments font partie des données caractérisant une FP. On suppose aussi que MAX est la constante représentant la dimension du tableau.
Question 4 : spécification du paquetage prioritequeueliste qui implante l'interface du TAD précédent
Question 5 : spécification du corps du paquetage prioritequeueliste qui implante le TAD précédent

with itemfp;use itemfp;
package FPtab is
type FP is private;
function taille(X:FP) return natural;
procedure inserer(E:in Element;X:in out FP);
procedure extraire(X:in out FP;E:out Element);

private
MAX:constant positive:=8;
type TablePriorite is array(Positive range<>) of Element;
type FP is
record
   nbElements:natural:=0;
   indiceCourant:positive:=1;
   table:TablePriorite(1..MAX);
end record;
end FPtab;

with itemfp;use itemfp;
with text_io;
package body fptab is
function taille(X:FP) return natural is
begin
return X.table'last-X.table'first+1;
end taille;

procedure inserer(E:in Element;X:in out FP) is
begin
X.nbElements:=X.nbElements+1;
X.table(X.indiceCourant):=E;
X.indiceCourant:=X.indiceCourant+1;
end inserer;

procedure extraire(X:in out FP;E:out Element)is
FPvide:exception;
begin
if X.nbElements=0
then
   raise FPvide;
else
   -- recherche de l'indice de l'element
   -- de plus haute priorite
   -- et de l'element maximum
   declare
    positionDeL_ElementMax:natural:=1;
    elementMax:Element:=X.table(X.table'first);
   begin
    for i in X.table'first+1..X.indiceCourant-1 loop
     if X.table(i)>elementMax
     then
      elementMax:=X.table(i);
      positionDeL_ElementMax:=i;
     end if;
    end loop;
   -- E contient l'element de plus haute priorite
    E:=elementMax;
   -- decalage des elements situes a la droite du plus grand
    for i in positionDeL_ElementMax+1..X.indiceCourant-1 loop
     X.table(i-1):=X.table(i);
    end loop;
   -- mises ajour des donnees de la FP
    X.indiceCourant:=X.indiceCourant-1;
    X.nbElements:=X.nbElements-1;
   end;
end if;
exception
when FPvide=>text_io.put_line("la FP est vide");
end extraire;
end fptab;

----------------------------------------------------------
----------------------------------------------------------

Implantation du type FP sous la forme d'une liste chainée

--PAQUETAGE FPListe(spécification)
--implantation des FPs avec des listes chainées

with itemfp;
package FPListe is

type FP is private;
function taille(c:FP) return natural;
function inserer(e: in itemfp.Element;c: in FP) return FP;
procedure extraire(e: out itemfp.Element;c: in out FP);
private

type Maillon;
type ListeD_Element is access Maillon;
type Maillon is
record
   item:itemfp.Element;
   suivant:ListeD_Element;
end record;
type FP is
record
   tete: ListeD_Element;
end record;
end prioritequeueliste;

-- PAQUETAGE FPListe (body)

with itemfp;
with Ada.Text_io;use Ada.Text_io;
package body FPListe is

function vide return FP is
p:FP:=(tete=>NULL);
begin
return p;
end vide;

function taille(c:FP) return Natural is
total:natural:=0;
curseur:ListeD_Element:=c.tete;
begin
loop
exit when curseur.suivant=NULL;
total:=total+1;
curseur:=curseur.suivant;
end loop;
return total+1;
end taille;

function insererDansL_Ordre(e:in itemfp.Element;l:in ListeD_Element)
           return ListeD_Element is
begin
if (l=NULL) or else (itemfp.itemPriorite(e)>=itemfp.itemPriorite(l.item))
then
   return (new Maillon'(e,l));
else
   return new Maillon'(l.item,insererDansL_Ordre(e,l.suivant));
end if;
end insererDansL_Ordre;

function inserer(e: in itemfp.Element;c: in FP)return FP is
begin
c.tete:=insererDansL_Ordre(e,c.tete);
return c;
end inserer;

procedure extraire(e: out itemfp.Element;c: in out FP) is
FPvide:exception;
begin
if c.tete=NULL
then
   raise PQvide;
else
   e:=c.tete.item;
   c.tete:=c.tete.suivant;
end if;
exception
when FPvide=>put_line("la FP est vide");
end extraire;

function racine(c:in FP) return itemfp.Element is
begin
return c.tete.item;
end racine;
end FPListe;
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------

Implantation d'un client du type FP

--Programme de test des paquetages précédents
--Il réalise un tri en utilisant les FP.
--Les éléments du tableauà trier sont insérés
--dans une FP puis extraits et rangés dans l'ordre
--d'extraction dans le tableau d'origine

with Ada.Text_io;use Ada.Text_io;
with FPliste; use FPliste;
--si on veut utiliser l'implantation avec des tableaux
--il suffit d'importer le paquetage correspondant
-- with FPTab; use FPTab;
with itemfp;
procedure testprioritequeue is
dimension:constant natural:=5;
type tabElement is array(1..dimension) of itemfp.Element;
e1,e2,e3,e4,e5:itemfp.Element;
uneTable:tabElement;

procedure triFP(T:in out tabElement) is
uneFP:FP:=vide;
elt:itemfp.Element;
begin
for i in T'range loop
   uneFP:=inserer(T(i),uneFP);
end loop;
for i in reverse T'rangeloop
   extraire(elt,uneFP);
   T(i):=elt;
end loop;
end triFP;

begin
e1:=itemfp.get("ORY",7);
e2:=itemfp.get("FRA",9);
e3:=itemfp.get("GLA",3);
e4:=itemfp.get("NWY",5);
e5:=itemfp.get("PHI",23);
uneTable:=(e1,e2,e3,e4,e5);
triFP(uneTable);
for i in uneTable'rangeloop
itemfp.put(uneTable(i));
new_line;
end loop;
end testprioritequeue;

-------------------------------------------------------
-------------------------------------------------------

Autre implantation possible

--PAQUETAGE FPTab(spécification)
--implantation des FPs avec des tableaux dimensionnés dynamiquement
with itemfp;
package FPTab is
type FP is private;
function taille(c:FP) return natural;
function inserer(e: in itemfp.Element;c:in FP) return FP;
procedure extraire(e: out itemfp.Element;c: in out FP);

private
dimension:natural:=5;
type TableD_Elements is array(positive range <>) of itemfp.Element;
type FP is
record
nbElements:natural:=0;
table:TableD_Elements(1..dimension);
end record;
end FPTab;

--PAQUETAGE FPTab(body)
with itemfp;
with text_io;use text_io;
package body prioritequeuetab is

function vide return FP is
t:FP;
begin
t.nbElements:=0;
return t;
end vide;

function taille(c:FP) return natural is
begin
return c.table'last-c.table'first+1;
end taille;

function inserer(e:in itemfp.Element;c:in FP) return FP is
begin

   if c.nbElements=dimension
   then
    declare
     temp:PQ;

    begin
     dimension:=dimension+5;
     for i in 1..c.nbElements loop
      temp.table(i):=c.table(i);
      temp.nbElements:=temp.nbElements+1;
     end loop;
     temp.table(temp.nbElements+1):=e;
       return temp;
    end;
   else
    declare
     temp:FP;
    begin
     temp.table(c.nbElements+1):=e;
     temp.nbElements:=c.nbElements+1;
     return temp;
    end;
   end if;
end inserer;

procedure extraire(e: out itemfp.Element;c: in out FP) is
FPvide:exception;
begin
if c.nbElements=0
then
   raise FPvide;
else
   declare
    positionDeL_ElementMax:natural:=1;
    elementMax:itemfp.Element:=c.table(c.table'first);
   begin
    for i in c.table'first..c.nbElements loop
     if itemfp.itemPriorite(c.table(i))>itemfp.itemPriorite(elementMax)
     then
      elementMax:=c.table(i);
      positionDeL_ElementMax:=i;
     end if;
    end loop;
    e:=c.table(positionDeL_ElementMax);
    for i in positionDeL_ElementMax+1..c.nbElements loop
     c.table(i-1):=c.table(i);
    end loop;
    c.nbElements:=c.nbElements-1;
   end;
end if;
exception
when FPvide=>put_line("la FP est vide");
end extraire;

function racine(c:in FP) return itemfp.Element is
begin
return c.table(c.table'first);
end racine;
end FPTab;