[Caml-list] Trees revised in Baire

[Caml-list] Trees revised in Baire

[Diego Olivier Fernandez Pons]

    Bonjour,

-- an english abstract follows --

Les implémentations des ensembles et dictionnaires en Baire ont été
révisées.

Vous y trouverez désormais des versions polymorphes, objet et
fonctorielle de chaque structure de données (arbres et dictionnaires)
dans les principas schémas d'équilibrage (AVL, pondéré, bicolore).

Le code est commenté en français, anglais, espagnol et n'interfère
plus avec la librairie standard. Des fonctions de compatibilité ont
été mises en place afin de pouvoir utiliser le code Caml déjà écrit
sans changement.

Vous pourrez trouver tout cela dans le(s) fichier(s)
RevisedTrees.tar.* sur la page de téléchargement de Baire.

Par ailleurs, on m'a signalé qu'un certain nombre d'idées développées
dans les implémentations précédentes n'étaient pas très claires (la
spécialisation des arbres cartésiens pour obtenir les différents
schémas d'équilibrage, le passage global -> local, les questions de
coloriage, etc.) et que l'on ne comprenait pas très bien les apports
de Baire dans le domaine.

J'ai donc écrit un historique : il examine les idées antérieures sur
lesquelles s'appuie Baire, montre ensuite comment les combiner pour
obtenir une vision d'ensemble simple et homogène, montre enfin comment
à partir de là on peut apporter des réponses ou élements d'explication
à plusieurs problèmes soulevés par la diversité des méthodes
d'équilibrages inventées jusqu'à présent. Aucune connaissance avancée
n'est nécessaire et les notions de bases sont rapidement rappelées et
illustrées de schémas.

Vous trouverez cet historique dans la section "Documentation" du site
de Baire.

Je signale au passage que la librairie a déménagé (la Bosse a déjà été
mise à jour) et que le nouvel hébergeur nous dispense de toute
publicité et dispose d'un bien meilleur temps de transfert.

        Diego Olivier


English abstact

Trees implementation in Baire has been revised. You will find now
complete implementation of sets and maps in several balancing schemes
(AVL, red and black, weight balanced). The code is in english,
commented in french, english and spanich.

You will find all this in the download page of Baire (and there is now
a partial translation of Baire main page in english)

For those who also read french, there is a document explaining more in
detail the Baire theoretical foundations. You will find it in the
"documentation" part of the Baire site. Anyway, you will find some
explanations in english in the source code.

The Baire site has moved. The Caml Hump has already corrected his link
so you may saftly follow it.

        Diego Olivier







-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners