Discussion :

[BaygonV]

Bonjour, ce fil fait suite à un précédent fil intitulé Héritage, template, généralisation et particularisation. Comment s'organiser proprement ? et concerne peu ou prou la même thématique au travers d'un exemple (cf titre).

Dans ce premier post, je pose quelques définitions afin qu'on essaie de parler le même langage.

Un graphe (type Graph) est une collection de noeuds (type Node).
Un noeud est la composition d'une Valeur(type Val) et d'une collection de liens vers d'autres noeuds.
Un lien (type Link) pointe vers un noeud et peu comporter un drapeau (type Flag).

Un graphe doit pouvoir être parcouru :
- via les liens, en largeur (type BFiterator) , en profondeur (type DFiterator).
- transversalement (type Titerator).
- autrement...

J'aimerais organiser le choses de manière à ce que ce type Graph offre facilement la possibilité de faire a peu près tout ce qu'on peut imaginer faire sur un graphe.

N.B. : Je n'attends (surtout) pas que vous me donniez une réponse toute cuite, je cherche à élaborer une méthode. J'attends des critiques, des objections, et des conseils méthodiques.

[BaygonV]

Bon, tout d'abord, il faut distinguer les types paramètres des types a implémenter.

Les types paramètres : Val et Flag.
Tous les autres sont à implémenter.

Dans l'idéal, le type Node ne dépend que de Val et le type Link que de Flag.
Toujours dans l'idéal, ces considérations devraient êtres transparentes pour le Graph, seulement les Itérateurs devraient s'en soucier.

Organisation 1
Si je reste sur ce point de vue il me semble logique d'avoir quelque chose comme ca (je ne mets que des 'déclarations').

Code :

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

1
2
3
4
5
6
7
8
 
class Node_ ;
class Link_ ;
template<class Val> class Node : public Node_ { Val val; collection_de(Link_*);}
template <> class Node<void> : public Node_ {collection_de(Link*_);}
template<class Flag> class Link : public Link_{ Flag flag ; Node_* pointedNode; }
template<> class Link<void> : public Link_ {Node_* pointedNode;}
class Graph{collection_de(Node_*)};

Ca m'a l'air d'être l'organisation la plus 'générale' mais j'ai plusieurs problèmes avec ça (certainement liés à ma connaissance partielle du langage) :
P1) Le graphe aura certainement besoin d'accès aux valeurs et au flags mais par contre n'aura accès qu'à l'interface de Node_ et Link_ qui elles n'ont pas accès au flags et valeurs...
P2) 'Beaucoup' d'héritage mais si cette question ne porte que sur un problème de performance, disons que je suis prêt à passer l'éponge.

[BaygonV]

Tentative de résolution de P1

Se résoudre à ce que Graph ne soit pas si indépendant que ca de Flag et Val.

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
 
template<Val> struct Node_ {
typedef Val::valtype valtype;
virtual valtype getValue() const = 0;
}; //+ Des tas de spécialisations eurk
 
template<Flag> struct Link_ {
typedef Flag::flagtype flagtype;
virtual flagtype getFlag() const = 0;
}; //+ Re Eurk
 
template<class Val, class Flag> class Node : public Node_<Val>  { 
Val val; collection_de(Link_<Flag>*); 
public :
valtype getValue() const; };
/* Mega Re Eurk 
/* template <class Flag> class Node<void> : public Node_ {collection_de(Link_<Flag>*);} */
 
/* Traitement du même genre pour l'ex class Link */
template<class Val, class Flag> class Graph{collection_de(Node_<Val,Flag>*)};

Maintenant la dépendance est trop forte... tout a l'heure l'utilisateur pouvait mettre n'importe quels types Val et Flag dans un même graphe mais le graphe ne pouvait avoir accès ni aux valeurs ni aux flags.
Maintenant le graphe a accès aux valeurs et aux flags mais l'utilisateur ne peut mettre à la fois qu'un seul type Val et Flag.

Je vais relire Présentation des classes de Traits et de Politiques en C++ et voir si je trouve mieux.

[BaygonV]

Ok, j crois que j'ai un truc.... je montre juste pour Node parce que c'est déjà assez tordu comme ca (a mon gout).

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
 
template<class T> struct typeinfo { // Fournit des types
typedef T type;
const static T TypicVal = T(); 
}; //+ spécialisations
 
template<class T> struct virtualget   { // *Fournit une fonction virtuelle à Node_ pour le type T.
protected :
virtual typeinfo<T>::type getVal(const typeinfo<T>::type&) {return typeinfo::TypicVal;} //histoire que la fonction ne soit pas pure, 
};                                                                                            //le mieux serait peut etre que cette fonction provoque une erreur a l'execution...
                                                                                              // le parametre de getVal est 'fictif', seulement utile pour la sélection de la surcharge. 
 
 
template<int n, class T, class ...Args> struct typerval : public typerval<n-1,Args...> {}; //structure vide tant que le parametre int n'est pas nul
template<class T, class ...Args> struct typerval<0, T, Args...> : public typeinfo<T> {typedef typeinfo<T>::type valuetype;} // Quand le parametre int est nul, on place un typedef sur le n-ieme type
 
template<class... Args> class Node_; // pré déclaration de Node_
template<> class Node_<> {}; // cas de zéro paramètres
template<class T, class ... Args> class Node_ : public virtualget<T>, Node_<Args...> {}; //Dote Node_ d'une fonction virtuelle non pure (voir *) pour chaque type possible.  
 
template class Node<int n, class... Args); // pré déclaration de Node
template<> class Node<int n> : public Node_<> {} // Cas d'aucun type.
template<int n,  class T, class ... Args> class Node : public Node_<T, Args...>, typerval<n,T, Args...> {private : valuetype val; protected : valuetype getval() const {return getValue(val);}}; //

L'idée étant que graph maintienne une collection de Node_<Type0,Type1,Type2>* dont chaque Node<0, Type0, Type1, Type2>, Node<1,Type0,Type1,Type2>, Node<2,Type0,Type1,Type2> dérive avec sa propre surcharge valide de getVal.
Je dois dire que la simple idée de rajouter les flags me donne envie de pleurer

[BaygonV]

Puisqu'il est question de méthode, j'ai l'impression de m'en éloigner avec les deux posts précédents...
Peut-être qu'après avoir séparé les types paramètres et les types à implémenter vaut-il mieux se demander à qui appartient quoi ?
Il semble évident que si l'on parle des objets, un graphe possède des noeuds qui eux même ont des liens.

Mais lorsqu'on parle des types ?
Quels types possèdent quels autres ?
Qu'est ce que çà peut bien signifier d'ailleurs ?

En terme de code, la relation de possession à l'air de s'exprimer assez clairement...
un type possède tous ses membres statiques.

Code :

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

1
2
3
4
5
6
 
class A {                         // Le type A : 
static int unEntierA = 0;  //          - possède la variable unEntierA
int unEntierB;                  //          - ne possède pas unEntierB, propriété d'un objet de type A.
class B{};                       //          - possède le type B 
};

La question précédente reste entière... si vous avez des idées sur comment déterminer qu'un certain type doit (ou pas) appartenir à un autre, je suis plus que preneur.

[Iradrille]

Organisation 1
Si je reste sur ce point de vue il me semble logique d'avoir quelque chose comme ca (je ne mets que des 'déclarations').

Code :

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

1
2
3
4
5
6
7
8
 
class Node_ ;
class Link_ ;
template<class Val> class Node : public Node_ { Val val; collection_de(Link_*);}
template <> class Node<void> : public Node_ {collection_de(Link*_);}
template<class Flag> class Link : public Link_{ Flag flag ; Node_* pointedNode; }
template<> class Link<void> : public Link_ {Node_* pointedNode;}
class Graph{collection_de(Node_*)};

P2) 'Beaucoup' d'héritage mais si cette question ne porte que sur un problème de performance, disons que je suis prêt à passer l'éponge.

Ce n'est pas vraiment une question de performance, à quoi sert l'héritage ici ? (cf mon post précédent sur ton ancien thread).
Peux-tu le justifier ?

Code :

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

1
2
3
4
 
virtual typeinfo<T>::type getVal(const typeinfo<T>::type&) {return typeinfo::TypicVal;} //histoire que la fonction ne soit pas pure, 
};                                                                                            //le mieux serait peut etre que cette fonction provoque une erreur a l'execution...
                                                                                              // le parametre de getVal est 'fictif', seulement utile pour la sélection de la surcharge.

Pour avoir une fonction virtuelle non pure, mais sans réelle implémentation, tu peux faire

Code :

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

1
2
virtual typeinfo<T>::type getVal(const typeinfo<T>::type&) const { throw 1; } // ou n'importe quel type d'exception,
// attention à la cont-correctness aussi, un getter se doit d'être const

Mais si la méthode n'a pas d'implémentation, alors elle doit etre virtuelle pure.

edit : oui, je n'aime pas l'héritage, et je m'assure que ce soit la meilleure solution avant de l'utiliser à chaque fois.

[BaygonV]

Oui, il me semble que je peux justifier l'héritage :
Comme tu le dis dans ta réponse :

L'héritage serait utile seulement si tu as besoin d'avoir un graphe avec des noeuds différents dans le même graphe.

Or ici oui, je veux pouvoir mettre des noeuds de types différents (ou pas) dans mon graphe.
J'ai dans l'idée que cette classe Graph puisse être utilisée pour construire... un AST par exemple ? Il me semble que dans ce cas là on peut bien s'attendre à ce qu'il y ait des objets de plusieurs types dans le graphe mais effectivement tous les types que l'on peut introduire dans le graphe sont connus a la compilation.