Arborescence et arbres binaires

Version imprimable

07/07/2007, 15h40
Grégory PLANCHAT

Arborescence et arbres binaires

Bonjour,

Je cherche à gérer dynamiquement mes menus sous Win32 grâce à un arbre binaire, mais je n'arrive pas à trouver quoi que ce soit qui me permettrait d'éviter de tout recoder (je veux aussi rester indépendant des HMENU jusqu'au bout).

Après une petite recherche, je n'ai pas pu trouver quoi que ce soit qui s'en rapproche, ni dans la STL, ni chez Boost et les codes que j'ai pu trouver sont soit trop complexes pour ce que je veux en faire, soit trop mal codées ou documentés pour pouvoir en faire quoi que ce soit. J'ai bien trouvé des sources pour gérer des arborescences de fichiers que je pourrais adapter, mais tout le monde cherche à utiliser du n-aire, alors que j'en veux pas :?

Es-ce que quelqu'un aurait une idée?
07/07/2007, 15h44
Médinoc

Euh...
Comment veux-tu générer dynamiquement un menu sous Win32 sans HMENU ? 8O

Tu veux générer des menus qui ne sont pas des menus Win32 ?
07/07/2007, 15h58
Grégory PLANCHAT

non, je les génère au dernier moment avec l'opérateur de cast vers HMENU
07/07/2007, 17h31
Médinoc

Un cast en HMENU ?
Dès qu'il est question de cast en un type quelquonque de handle, ça veut dire un truc crade, non-documenté, du genre qui donne des sueurs froides à des types comme Raymond Chen par la faute du programmeur.

Soit tu utilises les vraies fonctions de Windows pour générer un menu, soit tu fais des menus non-Windows. Mais pas de cast.

non, je crée une couche d'abstraction sous la forme d'un wrapper C++, les opérateurs de cast ne sont appelés que par l'interface elle-même, en utilisant une class de ce type :

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
template<class _Traits>
class wrapper
{
public:
    typedef unsigned long size_type;
 
    wrapper(){}
    wrapper(_Traits pal) : _handle(pal) {}
    wrapper(wrapper &pal) : _handle(pal._handle) {}
 
    wrapper &operator= (wrapper &pal) {_handle = pal._handle; return *this;}
    wrapper &operator= (_Traits pal) {_handle = pal; return *this;}
    operator _Traits() {return _handle;}
    _Traits * operator &() {return &_handle;}
    _Traits * operator-> () {return &_handle;}
    _Traits  &operator* () {return _handle;}
    bool operator! () {return !_handle;}
    bool operator!= (wrapper &pal) {return _handle != pal._handle;}
    bool operator== (wrapper &pal) {return _handle == pal._handle;}
 
    static const size_type size() {return sizeof(_Traits);}
 
protected:
    _Traits _handle;
};

l'opérateur de cast fait office d'accesseur/compilateur, rien de plus. par exemple avec une implémentation pour win32, j'ai quelquechose du genre :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#ifdef _WIN32
typedef wrapper<HMENU> menu_handler;
#else
...
#endif
 
class menu : public menu_handler
{
...
};
 
window &window::set_menu(menu &m)
{
    if(!SetMenu(_handle, m))
        throw "Doh!";
 
    return *this;
}

mais ca m'arrangerait une petite réponse à la question initiale ;)

07/07/2007, 18h20
Médinoc

Premièrement, je pense que ton template manque pas mal de const.

Ensuite, si je comprends bien, tu cherches une bibliothèque ou des exemples de code sur les arbres binaires ?
Et des fonctions qui prcourent ce genre d'arbre pour faire les AppendMenu() et CreateMenu() qui vont bien...

Pourquoi spécialement binaires, les arbres ? J'ai du mal à comprendre ta conception...
07/07/2007, 18h35
Grégory PLANCHAT
Citation:

Envoyé par Médinoc

Premièrement, je pense que ton template manque pas mal de const.

c'est possible, je code un "prototype" de la lib pour l'instant pour voir comment je pouvais implémenter la version finale, j'ai codé la classe en fonction de mes besoins sur le moment

Citation:

Envoyé par Médinoc

Ensuite, si je comprends bien, tu cherches une bibliothèque ou des exemples de code sur les arbres binaires ?

oui, je cherche une lib qui puisse me faire ca simplement

Citation:

Envoyé par Médinoc

Et des fonctions qui prcourent ce genre d'arbre pour faire les AppendMenu() et CreateMenu() qui vont bien...

ca, je saurais m'en occupper, rien de bien dur

Citation:

Envoyé par Médinoc

Pourquoi spécialement binaires, les arbres ? J'ai du mal à comprendre ta conception...

parcequ'on arrive à gérer une arborescence aussi simplement (peut-être même plus simplement) qu'avec un arbre n-aire tout en utilisant moins de mémoire et de temps CPU

par exemple avec ce type de noeuds :
Code:

1 2 3 4 5 6 7 8 9 template<class _Traits> struct node { _Traits data; node * brother; node * child; }
je place d'un côté le pointeur vers un élément du même niveau dans mon arborescence (node::brother) et de l'autre le pointeur vers le premier fils (node::child), c'est en quelque sorte l'utilisation d'un arbre binaire comme une liste chainée, mais capable de gérer une arborescence complète :)
07/07/2007, 18h49
Médinoc

Et qu'est-ce qui te dit que les bibliothèques d'arbres N-aires que tu trouves sur le web ne sont pas déjà implémentées de cette façon ?

Tu dois penser en premier à ce que tu veux (des menus, qui sont une arborescence N-aire) avant de t'intéresser aux détails d'implémentation (arbres binaires fils-gauche-frère-droit).
Quant au coup de la mémoire et du temps CPU...

Citation:

Envoyé par C. A. R. Hoare & Donald Knuth

Premature optimization is the root of all evil

Tu optimiseras l'implémentation si tu vois que c'est vraiment ça qui prend du temps (et quand je dis "voir", c'est en vérifiant avec un profiler)...
07/07/2007, 19h48
Grégory PLANCHAT

Citation:

Envoyé par Médinoc

Et qu'est-ce qui te dit que les bibliothèques d'arbres N-aires que tu trouves sur le web ne sont pas déjà implémentées de cette façon ?

je n'ai évidemment pas parcouru tout le web, mais les quelques implémentations de gestion de menus (exploitables) que j'ai trouvées utilisaient des arbres avec des noeuds contenant un std::list vers leurs fils, des classes MFC (ou quelquechose qui y ressemble) ou bien directement l'API win32 :?

Citation:

Envoyé par Médinoc

Tu dois penser en premier à ce que tu veux (des menus, qui sont une arborescence N-aire) avant de t'intéresser aux détails d'implémentation (arbres binaires fils-gauche-frère-droit).
Quant au coup de la mémoire et du temps CPU...

Tu optimiseras l'implémentation si tu vois que c'est vraiment ça qui prend du temps (et quand je dis "voir", c'est en vérifiant avec un profiler)...

Je suis bien d'accord, mais je cherche une source existante qui se rapproche le plus possible de ce que je veux faire. tout ce que j'ai trouvé pour l'instant, c'est des arbres appliqués au stockage ordonné ou au spanning tree. j'ai bien trouvé une source qui se rapproche de ce que je veux faire, mais il y a des MFC de partout...
09/07/2007, 10h44
Grégory PLANCHAT

Finalement je vais utiliser Qt, il y a tout ce que je voulais, à l'exception de DirectX