Discussion :

[stylostylo]

Bonjour,

J'essaie de faire un ensemble de paquets pour manipuler des arbres binaires de recherche ("normal", AVL, rouge-noir). Pour m'entraîner, j'ai voulu faire des arbres avec des données génériques (l'arbre manipule toujours des clés, de type Integer, et chaque noeud contient en plus une donnée de type 'T_Data').

Mes deux types de bases sont un type arbre qui contient des informations sur l'arbre (hauteur, nombre de noeuds) et un pointeur sur la racine, et un type noeud qui est...un noeud avec un père, un fils gauche, un fils droit, une clé et une donnée (de type 'T_Data'). Tout ça dans un même paquet. J'ai fait un arbre binaire de recherche "normal" (?) avec toutes les procédures et fonctions nécessaires, j'ai fais des tests et tout marchait.

Les problèmes sont arrivés au moment où j'ai voulu sortir le type noeud pour en faire un paquet à part: types A_Node et T_Node non définis et insultes en tout genre qui vont avec.

En gros j'ai:
- une classe abstraite pour les arbres et une classe arbre binaire qui en hérite
- une classe abstraite pour les noeuds et une classe noeud binaire qui en hérite.
Les deux classes abstraites sont génériques et ont un type T_Data générique.

arbre (abstrait)

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
 
generic
	type T_Data is private;
	with function  BT_Transform_Data (data: in T_Data) return Integer;
	with procedure Print_Data        (data: in T_Data);
 
package P_Tree is
	type T_Tree is abstract tagged private;
 
[...]
 
private
 
type T_Tree is abstract tagged
	record
		height: Natural;
		nodes : Natural;
	end record;
 
[...]

arbre binaire

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
 
with P_Node;
 
generic
package P_Tree.P_BT is
 
	package Node    is new P_Node (T_Data, BT_Transform_Data, Print_Data);
	package BT_Node is new P_Node.P_BT_Node;
	use BT_Node;
 
	type T_BT is private;
 
[...]
 
private
 
        type T_BT is new P_Tree with
	        record
		        root: A_Node;
	        end record;
 
[...]

noeud (abstrait)

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
 
generic
	type T_Data is private;
	with function  BT_Transform_Data (data: in T_Data) return Integer;
	with procedure Print_Data        (data: in T_Data);
 
package P_Node is
 
	type T_NodeAb is abstract tagged private;
	type A_NodeAb is access all T_NodeAb; 
 
[...]
private
 
type T_NodeAb is abstract tagged 
	record
		data: T_Data;
		key : Integer;
	end record;
[...]

noeud pour arbre binaire

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
 
generic
package P_Node.P_BT_Node is
 
	type T_Node is private;
	type A_Node is access T_Node;
 
[...]
 
private
 
type T_Node is new T_NodeAb with
	record
		father: A_Node;
		ls    : A_Node;
		rs    : A_Node;
	end record;
[...]

L'idée c'est de pouvoir dire "un arbre contient des noeuds", et là je n'arrive pas à utiliser les types T_Node et A_Node. J'ai donc essayé dans mon fichier p_tree-p_bt.ads de faire

Code :

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

1
2
3
package Node    is new P_Node (T_Data, BT_Transform_Data, Print_Data);
package BT_Node is new P_Node.P_BT_Node;
use BT_Node;

mais j'ai droit à un:

Code :

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

1
2
3
 
p_tree-p_bt.ads:22:32: invalid prefix in selected component "P_Node"
p_tree-p_bt.ads:23:13: "BT_Node" is undefined

j'ai essayé de remplacer P_Node.P_BT_Node par Node.P_BT_Node mais le compilateur me dit que P_BT_Node n'existe pas dans Node...et je tourne en rond depuis quelques jours.

La question c'est aussi de savoir s'il est possible de s'assurer que le type générique 'T_Data' utilisé par l'arbre et les noeuds soit le même ?

Est-ce que vouloir sortir mon type noeud est absurde ? Si non, comment est-ce que je pourrais faire pour manipuler des noeuds dans mes arbres (toujours dans une optique de "un arbre contient des noeuds") ?
Et est-ce que les classes abstraites ont du sens ici ? (je dirais que oui, mais peut-être que c'est un point qui attire beaucoup d'ennuis pour pas grand chose ?)

Merci d'avance.

[Blackknight]

Bon, j'ai regardé très rapidement et le premier truc qui me choque, c'est que ton package générique d'arbre binaire ne prend aucun paramètre.
Du coup, comment réussis-tu à instancier les autres génériques ?

[stylostylo]

Bonne question.
Je crois que je vais faire plus simple et revenir dessus plus tard. J'ai du brûlé quelques étapes...
En tout cas merci d'avoir jeté un oeil à tout ça, et désolé pour ce sujet un peu inutile du coup

[Zerte]

Bon, j'ai regardé très rapidement et le premier truc qui me choque, c'est que ton package générique d'arbre binaire ne prend aucun paramètre.
Du coup, comment réussis-tu à instancier les autres génériques ?

Remarque totalement hors-contexte: parfois il y a une utilité à avoir un générique sans paramètre.