Introduction sur les types abstraits de données avec Vegas

Marc Alcaraz

Ce tutoriel se veut une introduction aux types abstraits de données ou ADT (Abstract data type) avec le framework Vegas. ♪

- Titre : Introduction sur les types abstraits de données avec Vegas

- Auteur : Marc Alcaraz

- Parution : 21 août 2007

- Licence : Copyright ® 2006-2007 Marc Alcaraz. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Généralités

- II. Les interfaces du package vegas.data.

- Bag

- BidiMap

- Boundable, BoundedCollection, BoundedMap, BoundedQueue…

- Collection

- Dictionnary

- Iterator

- Entry

- Enumeration

- List

- Map

- MultiMap

- Queue

- Set

- SortedBag

- SortedMap

- Stack

- III. Conclusion

I - Généralités

Un point important dans VEGAS comme dans beaucoup de frameworks repose sur les structures de données ou Abstract Data Types (ADT).

Les données dans une application (même toute petite) peuvent être gérées efficacement quand elles sont regroupées pour former ce que l'on appelle généralement une collection.

En ActionScript par exemple et de façon générale dans tous les langages basés sur les normes ECMAScript 262, la classe Array permet de gérer les structures de données. Sa simplicité d'utilisation est vraiment agréable, mais au niveau architecture cette classe trouve rapidement ses limites. Une instance de type Array propose finalement une simple liste indexée numériquement. D'un autre côté si l'on souhaite retrouver une structure de donnée indexée un peu différemment, il est possible d'utiliser la classe Object avec sa notation entre crochets, il devient alors possible de créer une collection d'objets indexés via un identifiant de type « chaîne de caractère » (String).

Voici des exemples très simples de structures de données avec les types natifs Actionscript.

var liste:Array = [
"element1",
"element2",
"element3"
] ;

trace( liste[1] ) ; // element2

var classes = {
classe_A : [ "marc", "eliane", "georges", "louise" ] ,
classe_B : [ "laurence", "sandrine", "christian", "jean-pierre" ]
}

trace( classes["classe_A"][1] ) ; // eliane

Il est clair que l'on peut récupérer des données et les stocker avec ce genre de structure. Malgré tout, dans la pratique un développeur digne de ce nom se retrouve rapidement face à certains concepts ou problèmes qui vont le pousser à utiliser d'autres outils bien plus performants.

Créer des modèles en se basant sur des structures de données externes contenues dans une base de données ou un fichier de configuration Eden ou XML, gérer un historique, gérer un diaporama d'images… Dans chacune de mes applications, les Collections deviennent indispensables. C'est pour cela que pratiquement tout mon framework utilise à un moment ou à un autre le package vegas.data.

Vous trouverez toutes les classes principales concernant les ADT dans le package vegas.data. Pour chaque version de VEGAS vous retrouvez ce package dans le répertoire /trunk/src/vegas/data du SVN du projet.

De façon générale, le mot Collection est souvent utilisé pour résumer en un mot l'ensemble des structures de données. Même si, finalement, le terme ADT reste bien plus approprié étant donné que l'utilisation des Collections revient finalement à utiliser une toute petite partie d'un framework d'ADT.

Pour mettre en place mes ADT, je me suis énormément inspiré du framework des Collections de l'API JAVA™2 Platform Standard ED.5.0, mais aussi de l'extension apache Jakarta Commons Collections basée elle aussi sur ce que l'on peut trouver dans le framework JAVA. Il est certain que je suis loin d'avoir couvert à moi tout seul toutes les structures de données que proposent ces API, mais je pense que le contenu du package vegas.data vous permettra de gérer la plupart des problèmes que l'on peut rencontrer dans une application ActionScript. Il est certain que la version la plus avancée de mon package vegas.data se trouve dans la version AS2 de VEGAS. Mais les frameworks SSAS et AS3 ne sont pas en reste et je pense que très prochainement j'aurai fini l'ensemble de tous les tests unitaires de ces packages et que je pourrai enfin passer le framework en version finale !

Revenons au sujet principal de cet article. Pour simplifier les ADT sont des objets qui permettent de regrouper ou lister d'autres objets et d'y accéder selon la situation sous certaines conditions :

- possibilité de gérer des doublons ou non ;

- possibilité de gérer un ordre de tri ;

- gestion et manipulation des données et propriétés ;

- parcourir facilement les structures de données ;

- etc.

Ces conditions sont la plupart du temps décrites dans plusieurs Interfaces qui permettent de choisir facilement les règles que l'utilisateur voudra utiliser selon ses besoins.

II - Les interfaces du package vegas.data.

Pour le moment, les interfaces mises en place dans le package vegas.data sont assez nombreuses, je vais essayer de vous les décrire rapidement…

Bag

Définit une collection qui peut contenir plusieurs fois le même objet et qui permet de compter le nombre de fois où cet objet apparaît dans la Collection.

BidiMap

Définit une Map qui permet l'accès aux données aussi bien dans le sens clé/valeur que valeur/clé. Cette collection ne permet pas de retrouver plusieurs fois la même clé ou la même valeur. Je n'ai pas encore implémenté cette interface dans le framework, mais je compte très bientôt établir les classes concrètes de cette interface.

Boundable, BoundedCollection, BoundedMap, BoundedQueue…

Définit toutes les interfaces qui permettent de limiter la taille des Collections. Une classe « Boundable » doit respecter le contrat d'implémentation de l'interface avec les méthodes isFull() et maxSize().

Collection

Interface de base permettant d'implémenter des collections simples et fonctionnelles.

Dictionnary

J'utilise très peu en SSAS et AS2 cette interface qui ressemble beaucoup à l'implémentation des Maps. Cette interface se base sur l'interface Dictionnary (dépréciée) du framework JAVA et reste dans la library vegas.data pour des raisons de compatibilité avec certains de mes vieux travaux.

Iterator

Cette interface se trouve dans le package vegas.data.iterator.

Interface qui permet d'implémenter le pattern du même nom. Un Iterator permet d'énumération les données contenues dans les collections. Un iterator apporte un outil simple pour parcourir les objets sans savoir à l'avance leur taille ou la stratégie à utiliser pour les parcourir. Il suffit d'utiliser en priorité les méthodes next() et hasNext() de cette interface pour énumérer l'objet.

Entry

Cette interface définit une entrée (clé/valeur) dans un objet de type Map.

Enumeration

Cette classe permet de créer des outils servant à énumérer des objets ou des collections. Je vous avoue que j'utilise très peu cette interface, car je préfère l'utilisation de l'interface Iterator qui réalise en gros la même opération … histoire de goût ?

List

Interface servant à collecter des objets en autorisant la gestion des doublons et un accès direct à un élément de la collection. Les listes sont les versions évoluées des Collections de base du framework. A noter la classe LinkedList qui implémente cette interface et qui reste un outil très puissant au sein de VEGAS.

Map

Interface implémentée par les Collections qui associent une clé à une valeur. Les clés sont uniques et de n'importe quel type. Il est possible de retrouver plusieurs fois la même valeur pour des clés différentes et les valeurs sont également de n'importe quel type.

MultiMap

Cette interface permet de respecter la notion de type clé/valeurs (au pluriel). C'est-à-dire que pour une clé unique il existe dans la Map plusieurs valeurs.

Queue

Définit une queue de type « premier entré/premier sorti » ou en anglais stack FIFO (First In First Out). J'utilise énormément cette structure de donnée pour créer des séquenceurs.

Set

Cette interface définit une Collection ne contenant aucun doublon. Il est donc très pratique d'utiliser ces collections pour s'assurer de l'unicité d'un objet dans une application.

SortedBag

Cette interface permet d'implémenter des Bag triables.

SortedMap

Cette interface permet d'implémenter des Map qui garantissent un tri des clés suivant un ordre naturel ou personnalisé.

Stack

Définit une pile de type « dernier entré/premier sorti » ou en anglais stack LIFO (Last In First Out). Cette structure de donnée peut être très pratique pour implémenter par exemple un historique et un pattern Memento.

III - Conclusion

Voici donc le résumé de toutes les interfaces implémentées par les classes que j'essaierai de vous illustrer dans les prochains tutoriels dédiés au package vegas.data.

Je recherche une ou des personnes motivées maîtrisant l'anglais qui pourraient m'aider à traduire bénévolement les tutoriels de VEGAS en anglais… Je fais ce que je peux au niveau de la documentation de VEGAS pour rester dans la langue de Shakespeare, mais pour ce qui est de mes tutoriels cela devient très vite très compliqué pour moi. Bien entendu vu que VEGAS est un projet open source, je ne peux valider pour m'aider que les candidatures de traducteurs très motivés !