I. Généralités▲
Les structures de données de type Queue ou Stack FIFO (First In First Out) sont utilisées dans une application pour traiter des données en les stockant dans une file d'attente. Le principe d'une Queue est simple en s'assurant que la première donnée insérée dans la collection sera la première à en sortir. Il est possible avec ce type d'objets de créer des outils simples, mais efficaces dans des domaines variés : buffer de chargement de données, séquenceur d'animation, massive loader pour gérer le chargement des images d'une galerie, etc.
Les Queues s'opposent par leur nature aux Stack ou Stack LIFO (Last In First Out) qui, à l'inverse des Queues, permettent de stocker des données, mais en s'assurant que la dernière donnée insérée dans la collection sera la première retirée de celle-ci. Cette structure de donnée permet, elle encore, la mise en place d'algorithmes ou de certains design patterns très utiles comme la création d'un historique ou d'un pattern Memento.
II. Implémentation dans VEGAS▲
Regardons de plus près l'interface de type Queue.
import vegas.core.ISerializable;
import vegas.data.iterator.Iterator;
/**
* A collection designed for holding elements prior to processing. Besides basic Collection
* operations, queues provide additional insertion, extraction, and inspection operations.
* Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner.
* Whatever the ordering used, the head of the queue is that element which
* would be removed by a call to remove() or poll().
* @author eKameleon
*/
interface vegas.data.Queue extends ISerializable
{
/**
* Removes all of the elements from this queue (optional operation).
*/
function clear():Void ;
/**
* Returns the shallow copy of this queue.
*/
function clone() ;
/**
* Retrieves and removes the head of this queue.
*/
function dequeue():Boolean ;
/**
* Retrieves, but does not remove, the head of this queue.
*/
function element() ;
/**
* Inserts the specified element into this queue, if possible.
*/
function enqueue(o):Boolean ;
/**
* Returns {@code true} if this queue contains no elements.
* @return {@code true} if this queue is empty else {@code false}.
*/
function isEmpty():Boolean ;
/**
* Returns the iterator of this queue.
*/
function iterator():Iterator ;
/**
* Retrieves, but does not remove, the head of this queue, returning null if this queue is empty.
*/
function peek() ;
/**
* Retrieves and removes the head of this queue.
*/
function poll() ;
/**
* Returns the number of elements in this queue.
*/
function size():Number ;
/**
* Returns an array containing all of the elements in this collection.
*/
function toArray():Array ;
/**
* Returns the string representation of this instance.
* @return the string representation of this instance
*/
function toString():String ;
}Comme vous pouvez le voir, cette interface possède des méthodes simples permettant d'ajouter des éléments à la fin de la Queue, de récupérer ou de faire sortir la valeur du premier élément dans la file d'attente.
- dequeue() : supprime le premier élément de la structure de donnée et renvoie true si l'opération réussie.
- element() : renvoie le premier élément de la file d'attente, mais ne le supprime pas.
- enqueue() : cette méthode permet d'ajouter un nouvel élément à la fin de la file d'attente.
- peek() : identique ou presque à la méthode element(), cette méthode renvoie la valeur du premier élément dans la Queue sans la supprimer. Sa seule différence c'est que cette méthode renvoie null si la Queue est vide.
- poll() : supprime le premier élément en attente dans la file et renvoie sa valeur.
Comme dans toutes les classes de type Collection, vous pouvez remarquer également les méthodes :
- clear() : efface l'intégralité du contenu de la collection.
- clone() : permet de renvoyer une shallow copy de l'objet.
- isEmpty() : permet de définir si la structure de donnée est vide ou non ?
- iterator() : renvoie un Iterator qui permet d'énumérer facilement le contenu de la file d'attente.
- size() : renvoie la taille de la collection
- toArray() : renvoie représentation simplifiée de la structure de donnée avec un simple Array.
- toSource() : renvoie la chaine de caractère au format EDEN de la Queue. Cette méthode est utilisée pour sérialiser la Queue.
- toString() : renvoie la chaine de caractère correspondant à la Collection.
Maintenant, regardons l'interface de type Stack.
import vegas.core.ISerializable;
import vegas.data.iterator.Iterator;
/**
* A collection designed for holding elements prior to processing.
* Stacks typically, but do not necessarily, order elements in a LIFO (last-in-first-out) manner.
* @author eKameleon
*/
interface vegas.data.Stack extends ISerializable
{
/**
* Removes all of the elements from this stack (optional operation).
*/
function clear():Void ;
/**
* Returns the shallow copy of this stack.
*/
function clone() ;
/**
* Returns {@code true} if this stack contains no elements.
* @return {@code true} if this stack is empty else {@code false}.
*/
function isEmpty():Boolean ;
/**
* Returns the iterator of this stack.
*/
function iterator():Iterator ;
/**
* Returns the lastly pushed value without removing it.
* @throws the lastly pushed value.
*/
function peek() ;
/**
* Removes and returns the lastly pushed value.
* @return the lastly pushed value
*/
function pop() ;
/**
* Pushes the passed-in value to this stack.
*/
function push(o):Void ;
/**
* Search a value in the stack.
* @return the index position of a value in the stack.
*/
function search(o):Number ;
/**
* Returns the number of pushed values.
* @return the number of pushed values.
*/
function size():Number ;
/**
* Returns the array representation of this stack.
* @return the array representation of this stack
*/
function toArray():Array ;
/**
* Returns the string representation of this stack.
* @return the string representation of this stack.
*/
function toString():String ;
}Regardons de plus près les méthodes importantes de cette interface :
- peek() : renvoie la valeur du dernier élément stocké dans la pile sans supprimer cette valeur.
- pop() : supprime le dernier élément inséré dans la pile et renvoie sa valeur.
- push() : permet d'ajouter un nouvel élément à la fin de la pile.
- search() : permet de renvoyer l'index d'un objet se trouvant dans la pile (en principe les collections utilisent la méthode indexOf() pour gérer cette fonctionnalité, j'ai tout de même conservé ce nom de méthode pour rester compatible avec les outils JAVA).
Nous retrouvons, comme dans l'interface de type Queue, les méthodes size(), isEmpty(), toArray()…
Je vais ajouter à ces deux interfaces, l'interface BoundedQueue qui impose à une queue un nombre limité d'éléments. Nous verrons l'utilisation de cette interface dans la classe CircularQueue.
/**
* Defines a queue that is bounded in size. The size of the queue can vary,
* but it can never exceed a preset maximum number of elements. This interface
* allows the querying of details associated with the maximum number of elements.
* @author eKameleon
*/
interface vegas.data.BoundedQueue extends Queue
{
/**
* Returns {@code true} if the object is full.
*/
function isFull():Boolean ;
/**
* Returns the max number of occurrences in the given queue.
*/
function maxSize():Number ;
}Cette interface est très simple en imposant la mise en place des deux méthodes isFull() et maxSize().
III. Classes de type Queue▲
III-A. LinearQueue▲
La plus simple implémentation de l'interface Queue dans VEGAS reste la classe LinearQueue qui se contente d'implémenter simplement les méthodes définies par l'interface. Je ne vais pas entrer dans les détails du code contenu dans cette classe et à mon avis un simple exemple suffira à vous donner une bonne idée de son utilisation.
import vegas.data.iterator.Iterator ;
import vegas.data.queue.LinearQueue ;
var q:LinearQueue = new LinearQueue(["item0", "item1"]) ;
trace ("queue size : " + q.size()) ; // 2
trace ("enqueue item2 : " + q.enqueue ("item2")) ; // true
trace ("enqueue item3 : " + q.enqueue ("item3")) ; // true
trace ("enqueue item4 : " + q.enqueue ("item4")) ; // true
trace ("------- element") ;
trace ("element : " + q.element()) ; // element : item0
trace ("peek : " + q.peek()) ; // peek : item0
trace ("------- dequeue") ;
trace ("dequeue : " + q.dequeue()) ; // dequeue : true
trace ("------- iterator") ;
var i:Iterator = q.iterator() ;
while (i.hasNext())
{
trace (i.next()) ;
}
trace ("------- queue size") ;
trace (q.size() + " >> " + q) ; // 4 >> {item1,item2,item3,item4}
trace ("------- queue EDEN") ;
trace ("queue.toSource : " + q.toSource()) ;
// queue.toSource : new vegas.data.queue.LinearQueue(["item1","item2","item3","item4"])Rien de bien compliqué dans cet exemple. À noter l'utilisation de la méthode iterator() avec les méthodes next() et hasNext() de l'iterator, je ne rentre pas dans les détails de cette utilisation du pattern Iterator, car je compte écrire un tutoriel complet à ce propos. Malgré tout cela si vous avez des questions sur le sujet n'hésitez pas à me le dire dans vos commentaires, j'essaierai de vous répondre en attendant l'article sur le sujet.
III-B. CircularQueue▲
Cette classe est un peu différente par sa structure interne des autres Collections du package vegas.data. Je me suis inspiré de l'algorithme des files circulaires que l'on peut retrouver dans de nombreux livres d'Algorithmique. Pour ma part, je me suis basé sur les exercices et démonstrations contenues dans le très bon « Exercices et Problèmes d'Algorithmique » chez Dunod (à noter pour ceux que cela intéresse que j'ai illustré ce livre il y a quelques années;) ).
Le principe de cette classe est double, car il permet de limiter le nombre d'éléments dans la file d'attente, mais il permet également de gérer le contenu de la file en utilisant un algorithme non linéaire permettant l'accès très rapide aux données.
Voici un exemple d'utilisation simple de cette classe :
import vegas.data.iterator.Iterator ;
import vegas.data.queue.CircularQueue ;
var q:CircularQueue = new CircularQueue(5) ;
trace ("maxSize : " + q.maxSize()) ;
trace ("enqueue item1 : " + q.enqueue ("item1")) ;
trace ("enqueue item2 : " + q.enqueue ("item2")) ;
trace ("enqueue item3 : " + q.enqueue ("item3")) ;
trace ("enqueue item4 : " + q.enqueue ("item4")) ;
trace ("enqueue item5 : " + q.enqueue ("item5")) ;
trace ("enqueue item6 : " + q.enqueue ("item6")) ;
trace ("element : " + q.element()) ;
trace ("dequeue : " + q.dequeue()) ;
trace ("element : " + q.element()) ;
trace ("size : " + q.size()) ;
trace ("isFull : " + q.isFull()) ;
trace ("array : " + q.toArray()) ;
trace("") ;
trace ("queue : " + q) ;
trace("") ;
trace ("dequeue : " + q.dequeue()) ;
trace ("enqueue item6 : " + q.enqueue("item6")) ;
trace ("enqueue item7 : " + q.enqueue("item7")) ;
trace ("peek : " + q.peek()) ;
trace ("size : " + q.size()) ;
trace ("isFull : " + q.isFull()) ;
trace("") ;
trace ("q : " + q) ;
trace ("------- clone") ;
var clone:CircularQueue = q.clone() ;
trace ("dequeue clone : " + clone.dequeue()) ;
trace ("enqueue clone item8 : " + clone.enqueue("item8")) ;
trace ("original queue : " + q) ;
trace ("clone queue : " + clone) ;
trace ("clone iterator :") ;
var i:Iterator = clone.iterator() ;
while (i.hasNext())
{
trace ("\t+ " + i.next()) ;
}
trace("clone.toSource : " + clone.toSource()) ;III-C. PriorityQueue▲
Cette classe implémente l'interface Queue, mais également l'interface IComparator. Ainsi cette classe permet de créer des files d'attente avec une notion de « priorité » ce qui permet à chaque insertion dans la queue de trier tous les éléments contenus à l'intérieur pour forcer la sortie des éléments (par la tête de la file) selon un ordre défini par l'utilisateur.
Ainsi si l'on souhaite modifier l'ordre naturel d'insertion des données dans une Queue, la classe PriorityQueue sera indispensable.
Pour changer l'ordre des éléments dans la file d'attente, la classe PriorityQueue utilise une instance qui implémente l'interface vegas.core.IComparator de VEGAS.
/**
* A comparison function, which imposes a total ordering on some collection of objects.
* @author eKameleon
*/
interface vegas.core.IComparator
{
/**
* Compares its two arguments for order.
* @param o1 the first object to compare.
* @param o2 the second object to compare.
* @return <p>
* <li>-1 if o1 is "lower" than (less than, before, etc.) o2 ;</li>
* <li> 1 if o1 is "higher" than (greater than, after, etc.) o2 ;</li>
* <li> 0 if o1 and o2 are equal.</li>
* </p>
*/
function compare(o1, o2):Number ;
}Cette interface permet de comparer des objets de même type entre eux et renvoie une valeur numérique positive(1), négative(-1) ou nulle(0) selon l'ordre des deux éléments.
Il est possible à tout moment de créer vos propres IComparator, mais j'ai tout de même avancé un peu votre travail avec le package vegas.util.comparators de VEGAS qui contient quelques IComparator bien pratique : BooleanComparator, ComparableComparator, DateComparator, NullComparator, etc.
Regardons maintenant un exemple pour illustrer l'utilisation de la classe PriorityQueue avec l'utilisation d'un IComparator de type StringComparator :
import vegas.data.iterator.Iterator ;
import vegas.data.queue.PriorityQueue ;
import vegas.util.comparators.StringComparator ;
var q:PriorityQueue = new PriorityQueue(null, ["item0", "item1"]) ;
trace ("queue size : " + q.size()) ;
trace ("enqueue item4 : " + q.enqueue ("item4")) ;
trace ("enqueue item3 : " + q.enqueue ("item2")) ;
trace ("enqueue item2 : " + q.enqueue ("item3")) ;
trace ("enqueue item2 : " + q.enqueue ("item1")) ;
trace("> " + q) ; // > {item0,item1,item4,item2,item3,item1}
q.setComparator( new StringComparator() ) ;
trace("> " + q) ; // > {item0,item1,item1,item2,item3,item4}
trace ("------- element") ;
trace ("queue element : " + q.element()) ;
trace ("queue peek : " + q.peek()) ;
trace ("------- dequeue") ;
trace ("queue dequeue : " + q.dequeue()) ;
trace ("------- iterator") ;
trace ("queue size : " + q.size() + " : " + q) ;
trace ("queue toSource : " + q.toSource()) ;Voici maintenant un second exemple très simple pour illustrer une queue avec un tri par date avec un IComparator de type DateComparator :
import vegas.data.iterator.Iterator ;
import vegas.data.queue.PriorityQueue ;
import vegas.core.IComparator ;
import vegas.util.comparators.ReverseComparator ;
import vegas.util.comparators.DateComparator ;
var comp:IComparator = new DateComparator() ;
var q:PriorityQueue = new PriorityQueue() ;
q.enqueue( new Date(2006, 11, 25) ) ;
q.enqueue( new Date(2004, 2, 10) ) ;
q.enqueue( new Date(2005, 5, 5) ) ;
q.enqueue( new Date(2005, 1, 23) ) ;
trace(q) ;
trace("---") ;
q.setComparator( comp ) ;
trace(q) ;III-D. TypedQueue▲
Cette classe permet d'encapsuler une instance de type Queue et de s'assurer que tous les éléments dans cette queue auront le même type. Cette classe utilise une instance de type Queue et implémente l'interface ITypeable qui permet de valider la nature des éléments de la file d'attente via les méthodes validate() et supports() définies dans l'interface vegas.core.ITypeable.
Regardons un exemple d'utilisation pour nous faire une idée de son utilisation :
import vegas.data.queue.LinearQueue ;
import vegas.data.queue.TypedQueue ;
import vegas.data.iterator.Iterator ;
var tq:TypedQueue = new TypedQueue(String, new LinearQueue()) ;
trace("----o enqueue") ;
trace ("enqueue item1 : " + tq.enqueue("item1")) ;
trace ("enqueue item2 : " + tq.enqueue("item2")) ;
trace ("tq size : " + tq.size() + " : " + tq) ;
trace ("tq toSource : " + tq.toSource()) ;
trace("----o supports") ;
trace ("supports a string : " + tq.supports("hello")) ;
trace ("supports a number : " + tq.supports(150)) ;
trace ("---o setType") ;
tq.setType(Number) ; // clear the queue when the type change
trace (tq) ; // [TypeMismatchError] {} validate('value' : true) is mismatch.
trace ("---o Validate") ;
trace ("enqueue true : " + tq.enqueue(true)) ;Une exception de type TypeMismatchError est notifiée quand l'utilisateur essaie d'insérer dans la file d'attente un objet avec un type non valide. Je pense qu'il n'y a rien de vraiment compliqué ici encore et avec un peu de pratique je pense que vous maitriserez rapidement cette classe.
Remarque : Dans VEGAS, il existe la classe LinkedList qui implémenter elle aussi l'interface Queue. Mais cette classe appartient au package vegas.data.list. Je vous parlerai de cette classe dans un autre article consacré à ce package.
IV. Classe de type Stack▲
IV-A. SimpleStack▲
La classe SimpleStack est la classe de base pour utiliser une collection de type stack LIFO. Je ne vais pas m'attarder sur l'utilisation de cette classe, car les méthodes de cette classe sont très simples d'utilisation :
import vegas.data.iterator.Iterator ;
import vegas.data.Stack ;
import vegas.data.stack.SimpleStack ;
var s:Stack = new SimpleStack() ;
s.push("item1") ;
s.push("item2") ;
s.push("item3") ;
trace ("stack.toSource : " + s.toSource()) ;
// stack.toSource : new vegas.data.stack.SimpleStack(["item1","item2","item3"])
trace ("stack peek : " + s.peek()) ;
// stack peek : item3
trace ("toString : " + s) ;
// toString : {item3,item2,item1}
trace ("stack pop : " + s.pop()) ;
// stack pop : item3
trace ("toString : " + s) ;
// toString : {item2,item1}
trace ("--- stack iterator") ;
var i:Iterator = s.iterator() ;
while (i.hasNext())
{
trace (i.next()) ;
}IV-B. TypedStack▲
La classe TypedStack fonctionne de la même manière que la classe TypedQueue décrite dans le chapitre précédent. Elle se base sur une Stack encapsulée dans une instance de type TypedStack.
import vegas.data.Stack ;
import vegas.data.stack.SimpleStack ;
import vegas.data.stack.TypedStack ;
var s:Stack = new SimpleStack() ;
s.push("item1") ;
s.push("item2") ;
s.push("item3") ;
var ts:Stack = new TypedStack(String, s) ;
ts.push("item4") ;
trace ("stack >> " + ts.size() + " : " + ts) ;
ts.push(2) ; [TypeMismatchError] {item4,item3,item2,item1} validate('value' : 2) is mismatch.V. Conclusion▲
Voici donc la fin de ce petit article de présentation des stacks FIFO et stacks LIFO dans VEGAS. J'espère vous donner avec cet article et ceux qui vont suivre une bonne idée du contenu de mes packages. Si vous avez des questions précises sur le sujet ou que certaines notions vous semblent un peu floues, n'hésitez pas à me le dire. À suivre des articles sur les ADT de type Collections, les List et Set, mais aussi sur les Map et les Iterator.