Arbre : Feuilles et Noeuds de structure différente.

Version imprimable

Bonjour!

Je rencontre un problème et je viens vous voir en espérant trouver de l'aide !
Je dispose d'une assez grande structure d'arbres que j'ai déclaré comme suit :
Code:

1 2 3 4 5 6 7 8 9 10 11 type Node; type Tree is access Node; package List_Fils is new Ada.Containers.Doubly_Linked_Lists(Tree); use List_Fils; type Node is record Char : Character; Num : Integer; Fils : List_Fils.List; end record;
L'idée est de programmer un dictionnaire : à chaque chemin (de la racine jusqu'à une feuille) est associé une liste de mots.
Je dois donc avoir des listes chainées de String à la toute fin de mon arbre (après les feuilles). Autrement dit, une fois arrivé à une feuille, celle-ci doit pointer sur une Liste de String.

Je comptais donc déclarer un type Feuille comme ça :
Code:

1 2 3 4 5 6 7 8 package List_Words is new Ada.Containers.Doubly_Linked_Lists(unbounded_string); use List_Words; type Feuille is record Char : Character; Num : Integer; Words : List_Words.List; end record;
Mon problème c'est que l'avant-dernier niveau de mon arbre (celui juste avant les feuilles) ne peut pas pointer sur une structure différente que celle de Node !
Et la surcharge de type n'existe pas (à ma connaissance) en Ada....

J'ai bien pensé à ajouter une Liste de String dans ma structure Node. Mais sachant que l'arbre est très grand, et que seules les feuilles en auront besoin, je trouve cette solution pas très élégante.

Je dois bien vous avouer que mon imagination s'arrête là. Auriez-vous l'idée d'un stratagème pour contourner mon problème ?

Merci beaucoup !

02/04/2016, 20h50
localghost

Bonjour Realloc,
Si tu peux reprendre la question à la définition de ce qu'est un dictionnaire pour toi ? S'il te plait !
02/04/2016, 21h25
Realloc

Yep, bien sûr.

L’arbre contient 27 niveaux. Au niveau du noeud racine, aucune lettre
n’est définie. Nous notons par M une constante définissant le nombre max-
imal d’apparition d’une même lettre dans un mot
Le noeud racine possède jusqu’à M + 1 noeuds fils. Le premier d’entre eux va mener vers l’ensemble
des mots ne possédant aucune fois la lettre ’a’. Le second d’entre eux mène
vers l’ensemble des mots contenant exactement une fois la lettre ’a’, et ainsi
de suite. Chacun de ces sommets possède à son tour jusqu’à M + 1 noeuds
fils, qui concernent cette fois-ci la lettre ’b’.
En partant de la racine, et au bout de 26 arètes traversées, on arrive
sur un noeud feuille qui contient tous les mots contenant exactement pour
chaque lettre un nombre de lettres correspondant aux différents noeuds du
chemin.

Pour créer l'arbre, on lit un dictionnaire et on parcourt les noeuds de façon récursive (en créeant ceux qui n'y sont pas).

J'ai pas trop pigé en fait.
Je tente quand même une approche de réponse en te proposant un type paramétré pour les noeud pourvant être soit des pères soit des feuille.

Code:

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
38
39
40
41
42
43
44
45
46
 
with Ada.Strings.Unbounded;
use Ada.Strings.Unbounded;
with Ada.Containers.Doubly_Linked_Lists;
generic
   M : Positive;
package Lexic is
 
   package Unbounded_String_Lists is new Ada.Containers.Doubly_Linked_Lists(Unbounded_String);
 
   type Tree_Type is limited private;
 
   procedure Initialize
     (T    : out Tree_Type);
 
   procedure Construct
     (T    : in out Tree_Type;
      From : in string);
 
private    
 
   use Unbounded_String_Lists;
 
   type Node_Type(Is_Terminal : Boolean);
   type Node_Access is access Node_Type;
   type Node_Set_Type is array (Positive range 1..M+1) of Node_Access;
   type Node_Type(Is_Terminal : Boolean) is
      record
 
         case Is_Terminal is
            when False =>
               Char    : Character := Ascii.Nul;       
               Nb_Occ  : Natural := 0;
               Childs  : Node_Set_Type;
            when True =>
               L       : List;
         end case;
      end record;
 
   type Tree_Type is
      record
         Depth   : Natural := 0;
         Root    : Node_Access;
      end record;
 
end Lexic;

03/04/2016, 20h44
Realloc

Bonjour localghost,

Je viens à l'instant de tester, et ça fonctionne parfaitement ! Merci beaucoup, c'est exactement ce que je voulais faire.
J'avais fait mes recherches autour de la surcharge de type en Ada et je n'avais rien trouvé. Mais au final les types paramétrés sont un peu pareil. C'était une facette du langage que je n'avais pas du tout vu !

Merci beaucoup ! :')

Passe une bonne soirée !
04/04/2016, 12h06
localghost

Bonjour Realloc.

Contant que ça te convienne.

A propos de cette arbre, j'ai moi même implémenté le dictionnaire ou lexique en question et j'aimerais avoir ton avis.
Je posterai les sources dès que j'aurais ton accord, que tu aura implémenté toi même le programme.
04/04/2016, 20h48
Realloc

Bonjour localghost,

Pas de soucis, j'ai fini mon implém', j'attends tes sources.

Bon, alors sans prétention parce que je ne suis pas certain d'avoir piger le truc.
Un procedure initialize, une procédure construc pour lire le fichier et construire le lexique avec une procédure Add pour ajouter un mot, et une procédure Print pour afficher l'arbre.
Add utilise une fonction nommée Number_Of_Occurence pour compter le nombre d'occurence d'un caractère dans un mot.

Specification :

Code:

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
38
39
40
41
42
43
44
45
46
47
48
 
with Ada.Strings.Unbounded;
use Ada.Strings.Unbounded;
with Ada.Containers.Doubly_Linked_Lists;
generic
   M : Positive;
package Lexic is
 
   package Unbounded_String_Lists is new Ada.Containers.Doubly_Linked_Lists(Unbounded_String);
 
   type Tree_Type is limited private;
 
   procedure Initialize
     (T    : out Tree_Type);
 
   procedure Construct
     (T    : in out Tree_Type;
      From : in string);
 
   procedure Print
     (T    : in Tree_Type);
 
   Specification_Error : exception;
 
private    
 
   use Unbounded_String_Lists;
 
   type Node_Type(Is_Terminal : Boolean);
   type Node_Access is access Node_Type;
   type Node_Set_Type is array (Positive range 1..M+1) of Node_Access;
   type Node_Type(Is_Terminal : Boolean) is
      record
 
         case Is_Terminal is
            when False =>              
               Childs  : Node_Set_Type;
            when True =>
               L       : List;
         end case;
      end record;
 
   type Tree_Type is
      record
         Root    : Node_Access;
      end record;
 
end Lexic;

Implementation

Code:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
with Ada.Text_Io;
use Ada.Text_Io;
with Ada.Characters.Handling;
use Ada.Characters.Handling;
package body Lexic is
 
   procedure Initialize
     (T    : out Tree_Type) is
   begin
      T.Root := new Node_Type(False);
   end Initialize;
 
 
   function Number_Of_Occurence
     (Char : in Character;
      Word : in Unbounded_String) return Natural is
 
      Sum : Natural := 0;
 
      Item : constant String := To_String(Word);
 
   begin
      for Char_Id in Item'Range loop
         if To_Basic(Item(Char_Id)) = Char then
            Sum := Sum + 1;
         end if;
      end loop;
      return Sum;
   end Number_Of_Occurence;
 
 procedure Print
     (T    : in Tree_Type) is
 
 
      procedure Node_Print(N : in Node_Access) is
         Current_Node : Node_Access := N;
      begin
         if Current_Node /= null and then
           not Current_Node.Is_Terminal then
            for Occ_Id in reverse 1..M+1 loop
               Node_Print(Current_Node.Childs(Occ_Id));        
            end loop;
         end if;
         if Current_Node /= null and then
           Current_Node.Is_Terminal then            
            if not Is_Empty(Current_Node.L) then
               declare
                  Curs : Cursor := First(Current_Node.L);
               begin
 
                  for Word_Id in 1..Length(Current_Node.L) loop
                     declare
                        Word : Unbounded_String := Element(Curs);
                     begin                         
                        Put_Line(To_String(Word));                         
                        Curs := Next(curs);
                        end;
                     end loop;
               end;
            end if;
         end if;
      end Node_Print;
 
 
     Current_Node : Node_Access := T.Root;
   begin
 
      if Current_Node = null then
         raise Specification_Error;
      end if;      
      Node_Print(Current_Node);
   end Print;
 
   procedure Add
     (Word  : in Unbounded_String;
      Where : in out Tree_Type) is
 
 
      Current_Node : Node_Access := Where.Root;
      Nb_Occ : Natural := 0;
   begin
 
      for Char in Character'Val(97) .. Character'Val(122) loop
 
         Nb_Occ := Number_Of_Occurence(Char, Word);
 
         begin
 
            if Nb_Occ > M then
               raise Specification_Error;
            end if;
            if Current_Node.Is_Terminal then
               raise Program_Error;
            end if;
            if Current_Node.Childs(Nb_Occ+1) = null then
               Current_Node.Childs(Nb_Occ+1) := 
                 new Node_Type ' 
                 (
                  Is_Terminal => False,
                  Childs => (others => null)
                 );
            end if;
            Current_Node := Current_Node.Childs(Nb_Occ+1);       
         end;
      end loop;
      if Current_Node.Childs(Nb_Occ+1) = null then
 
         Current_Node.Childs(Nb_Occ+1) := new Node_Type(True);
      else
         if not Current_Node.Childs(Nb_Occ+1).Is_Terminal then
            raise Program_Error;
         end if;
      end if;
      Append(Current_Node.Childs(Nb_Occ+1).L, Word);
   end Add;
 
   procedure Construct
     (T    : in out Tree_Type;
      From : in String) is
 
      File : File_Type;    
   begin
      Open(File, In_File, From);
      while not End_Of_File(File) loop
         declare
            Word : Unbounded_String := To_Unbounded_String(Get_Line(File));
         begin
            Add(Word => Word, Where => T);
         end;
      end loop;
   end Construct;
end Lexic;

Main file :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
with Lexic;
procedure Main is
 
   package My_Lexic is new Lexic(6);
   Tree : My_Lexic.Tree_Type;
 
begin
 
   My_Lexic.Initialize(T => Tree);
   My_Lexic.Construct(T => Tree, From => "lexique.txt");
   My_Lexic.Print(T => Tree);
end Main;

Set de mot dans le fichier d'exemple "lexique.txt" :

Citation:

a
aventure
bouton
bonbons
ceinture
porte
portail
rupture
silence
silencieux
tentation
tentative
univers
universel
vert
voyelle
wagon
zéro

Resultat de l'affichage :

Citation:

tentative
aventure
tentation
wagon
portail
a
bonbons
bouton
silencieux
silence
ceinture
universel
voyelle
univers
porte
rupture
vert
zéro

Ai-je vu juste ?
Le résultat affiché est-il correct ?

07/04/2016, 09h24
localghost

Bonjour,

Quelqu'un aurait la solution venu d'ailleurs dans ce sujet ?