Discussion :

[Rahan2000]

Bonjour a tous,

Je créé un paquettage de liste chainée qui utilise en interne un type Noeud privé.

On déclare donc un type Noeud et un type access à un Noeud (ptr_Noeud), pour pouvoir gérer des Noeuds suivants, précédents, etc...

Très classique jusqu'ici.

Je veux créer une fonction qui compare TOUTE une liste chainée et pas seulement deux Noeuds. Elle renverra VRAI si tous les noeuds sont identiques (même valeur).

On peut surcharger la fonction "=" qui prend comme paramètres deux ptr_Noeuds qui sont des listes (éventuellement NULL).

FUNCTION "=" (ptr_A, ptr_B : ptr_Noeud) RETURN Boolean IS ...

Et on appelle la fonction dans le programme principal :

IF ListeA = ListeB THEN ...

Quand j'écris la fonction "=" sur les types ptr_Noeud, j'ai besoin de savoir dès le début si les pointeurs sont nuls.

Pour cela je fais : IF ptr_A = NULL THEN ...

Et là j'ai un problème car comme j'ai surchargé la fonction "=", le test de comparaison me faire rentrer en récursivité dans ma propre fonction "=" surchargée...

Je cherche donc un moyen pour comparer ces références (pointeurs) sans utiliser la fonction "=" que j'ai réécrite.

Faut-il convertir ptr_A et Null en adresse ? Comment faire ?
Existe--il un moyen de forcer l'utilisation de "=" avant la surcharge ?

Comment faire (je veux conserver la fonction "=" surchargée) ?

Merci pour votre aide.

Rahan2000fr [@] free.fr

[Emile8]

La difficulté rencontrée pointe le fait que au delà des apparences, liste et noeud (mais on pourrait aussi bien dire : arbre binaire et noeud où ça apparaît plus clairement) ne sont pas de même nature et correspondent bien à des concepts différents. Cette différence conduit tout naturellement à définir un premier type pour la liste (pointeur vers un noeud) et un autre type pour les noeuds (information, pointeur (anonyme en ada 2005) vers un autre noeud ...). Les fonctions telles que l'égalité sont maintenant à définir pour chacun des types et le compilateur ne se trompera pas dans leur appel.

Sinon il y a peut-être une autre solution qui serait d'arriver à associer à des packages différents les deux fonctions égalités et à les préfixer par ces noms lors de leurs appels. (Je n'ai pas poussé plus loin la réflexion qu'il faudrait sans doute consolider)

[Rahan2000]

Si j'ai bien compris, on aurait :

- Un type Noeud
- Un type ptr_Noeud is access Noeud, pour gérer les suivants, droite, gauche, etc...
- Un autre type Liste is access Noeud pour gérer une liste/arbre complet.

Pour comparer des listes complètes, on surcharge "=" sur des Listes mais comment serait écrit par exemple le début de la fonction qui teste si une des listes est vide ? Je ne peux pas écrire "IF ListeA = NULL THEN" car réentrence...

FUNCTION "=" (ListeA, ListeB : Liste) RETURN Boolean IS

... ?

Il faudrait peut-être esssayer de "caster" le type Liste en type ptr_Noeud pour faire la comparaison (car le "=" sur ptr_Noeud n'est pas surchargé, lui) ?

IF ptr_Noeud'(ListeA) = null THEN ? (je ne connais pas la syntaxe...)


Merci.

[Rahan2000]

Voilà, pour faire avancer le pb j'ai écrit ça et ça semble passer.

Il faut bien déclarer des types différents, qui auront des opérateurs différents.

Le "all" dans la déclaration "access" permet d'avoir des pointeurs génériques et est obligatoire ici.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
type T_Cellule;
type T_Ptr_Cellule is access all T_Cellule;
type T_Liste is access all T_Cellule;

et donc on peut en suite surcharger pour comparer deux listes complètes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
function "=" (ListeA, ListeB : T_Liste) return Boolean is
 
  -- Variables de parcours
  T_Ptr_Cellule : ptrTmpA := T_Ptr_Cellule (ListeA);
  T_Ptr_Cellule : ptrTmpB := T_Ptr_Cellule (ListeB);
 
  --------------------------------------
  Begin
 
    -- On compare membre à membre les deux listes
    while ((ptrTmpA /= null) and (ptrTmpB) /= null))
    ...

Dans la fonction on a remplacé la comparaison sur des "T_Liste" par une comparaison sur des "T_Ptr_Cellule", dont la fonction "=" n'a pas été surchargée avec ce type. ADA compare donc bien les pointeurs maintenant sans réentrance.

Il a fallu initialiser les pointeurs ptrTmpA, ptrTmpB sur la tête de la liste A et B et on a "casté" ou "fait la conversion" du type T_Liste vers le type T_Ptr_Cellule (ce qui se passe bien puisqu'ils pointent vers les mêmes objets, des cellules) :

ptrTmpA = T_Ptr_Cellule(ListeA);

A priori ca marche sous GNAT / AdaCore.

A++

[Emile8]

Voici une implémentation un peu plus générale d'une liste bi-directionelle qui ne demande pas de conversion de type. La liste est tout simplement un record avec un pointeur vers le premier noeud de la liste et un pointeur vers son dernier noeud. Pour implémenter une liste uni-directionnelle il suffit d'omettre le deuxième pointeur.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package liste_demo is
type noeud is record 
 info : integer;
 next : access noeud;
 previous : access noeud;
end record;
 
type liste is record  
   tete : access noeud;
   queue :access noeud;
end record;
 
function "="(lg, Ld : liste) return boolean;
end liste_demo;
 
 
package body liste_demo is
    function "="(lg,ld : liste) return boolean is
        Pg : access noeud := lg.tete;
        Pd : access noeud := ld.tete;
    begin
       while Pg /= null and then Pd /= null loop 
           if Pg.info = Pd.info then
               Pg := Pg.next;
               Pd := Pd.next;
           else
               return false;
           end if;    
       end loop;
 
       if Pg = null and then  Pd = null then
           return true;
       else
           return false;
       end if;
    end;
end liste_demo;

[poincare]

Bonjour,
Il n'est pas nécessaire de réécrire un paquetage de listes chainées.
Cela fait partie intégrante d'Ada dans les bibliothèques Ada.Containers depuis Ada 05.
Dans Gnat/GPS onglet Help > GnatRuntime>Ada 2005> Ada > Containers.
Il y a 2 variantes.
Ada.Containers.Doubly_Linked_Lists
Ada.Containers.Restricted_Doubly_Linked_Lists

En plus, ces paquetages sont prévus pour gérer des accés concurrents ce que
votre construction ne fait pas a priori.
Il suffit d'instancier le paquetage avec le type utilisé.

[Emile8]

Etes-vous sûr que les containers d'Ada 2005 supportent les accès concurrents ? John Barnes dans son papier : "Rationale for Ada 2005: 6a Containers" écrit le contraire :

"Perhaps a remark about using containers from a multitasking program would be helpful. The general rule is given in paragraph 3 of Annex A which says "The implementation shall ensure that each language defined subprogram is reentrant in the sense that concurrent calls on the same subprogram perform as specified, so long as all parameters that could be passed by reference denote nonoverlapping objects." So in other words we have to protect ourselves by using the normal techniques such as protected objects when container operations are invoked concurrently on the same object from multiple tasks even if the operations are only reading from the container."

[poincare]

Vous avez raison.
J'ai été trop rapide dans ma précédente réponse.
C'est à l'utilisateur de gérer les accès concurrents.
Pour en revenir à la question de départ, il y a dans le paquetage prédéfini la fonction de comparaison recherchée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
  function "=" (Left, Right : List) return Boolean is
      L : Node_Access := Left.First;
      R : Node_Access := Right.First;
 
   begin
      if Left'Address = Right'Address then
         return True;
      end if;
 
      if Left.Length /= Right.Length then
         return False;
      end if;
 
      for J in 1 .. Left.Length loop
         if L.Element /= R.Element then
            return False;
         end if;
 
         L := L.Next;
         R := R.Next;
      end loop;
 
      return True;
   end "=";