Créer une liste circulaire FIFO associative en Javascript

Dans le cadre du développement d'un système de cache en Javascript, j'ai rencontré le besoin de disposer d'une structure de données associative organisée selon le modèle de la liste circulaire. Ce concept n'est si je ne m'abuse qu'un cas particulier de la file FIFO (queue), une structure déjà implémentée nativement dans le langage via les méthodes push et pop d'un simple objet Array au même titre d'ailleurs que la pile LIFO (stack) l'est via shift et unshift. Cependant, ces pratiques impliquent une gestion séquentielle de la collection, c'est à dire qu'il n'est possible d'accéder à un élément que via son index numérique et non via une clef associative.

J'ai donc créé une classe très rudimentaire qui fourni les fonctionnalités essentielles d'une file FIFO associative de taille fixe.

/**
 * GQueue
 * Fixed size FIFO queue class providing associative access. Can also be used as a Circular Buffer.
 * @author  Geoffray Warnants <http://www.geoffray.be>
 * @version 1.0.20100921
 */

/**
 * Creates an empty queue
 * @param {int} maxlength
 * @param {Boolean} circular If true, the queue as will be defined as a "Circular Buffer".
 * @constructor
 */
function GQueue(size,circular){
    this.data = {};
    this.circular = Boolean(circular);
    if (isNaN(this.maxlength=parseInt(size))) {
        this.maxlength=0;
    }
    this.length = 0;
}
GQueue.prototype = {
    /**
     * Adds new element to the end of the queue
     * @param {String}  k   Key
     * @param {Object}  v   Value
     * @return {int}    The new length, or -1 if the queue is full
     */
    push: function(k,v){
        if (this.circular) {
            this.data[k]=v;
            if (++this.length > this.maxlength) {
                this.pop();
            }
            return this.length;
        } else if (this.length < this.maxlength) {
            this.data[k]=v;
            return this.length++;
        } else {
            return -1;
        }
    },
    /**
     * Removes the last element of the queue
     * @return {Object}    The removed element, or null if none.
     */
    pop: function(){
        for (var i in this.data) {
            var value = this.data[i];
            delete this.data[i];
            this.length--;
            return value;
        }
        return null;
    },
    /**
     * Checks if a key exists in the queue.
     * @param {String}  k   Searched key
     * @return {Boolean}
     */
    has: function(k){
        return typeof(this.data[k])!="undefined";
    },
    /**
     * Searches an element for a given key
     * @param {String} k  Searched key
     * @return {Object}    The found element, or null if none.
     */
    find: function(k){
        return (typeof(this.data[k])!="undefined") ? this.data[k] : null;
    }
}

Comme le montre le constructeur, le second argument permet de définir si la structure doit se comporter comme une file FIFO classique, ce qui est le cas par défaut ou comme une file circulaire. La différence se constate dans le cas où l'on tente d'empiler un nouvel élément dans une file pleine : la file classique retournera une erreur tandis que la file circulaire permettra l'insertion tout en dépilant le plus ancien élément.

// créé une file FIFO circulaire de 3 éléments
var q = new GQueue(3,true);
for (var i=0; i<5; i++) {
    q.push("key"+i, "val"+i);
}

// accès associatif aux éléments via la clef
console.log(q.has("key1")); // affiche false
console.log(q.has("key2")); // affiche true
console.log(q.find("key3")); // affiche "val3"

Téléchargements

gqueue-1.3.js (27/04/2012)

<<< Retour

27/04/2012 07:21Posté par Geoffray

Salut, merci pour ta contribution, je viens de mettre à jour la dernière version.

PS: Le code est maintenant dispo sur Github

26/04/2012 01:12Posté par OuT

Bonjour,

Je viens de remarquer un bug assez important dans la réécriture que je t'avais proposée et que tu as implémentée dans la v1.2.

Je n'en reviens pas d'avoir mis tant de temps avant de le remarquer !

Dans la fonction push, il faut rajouter un length++, comme suit :

else if (this.circular) {
this.pop();
this.length++;
}

Toutes mes excuses pour ce désagrément...

à plus,
OuT

15/11/2010 07:18Posté par Geoffray

Salut OuT,
Un grand merci pour ta contribution et tes remarques qui s'avèrent très pertinentes. Comme tu peux le voir, j'ai mis la classe à jour en suivant ta proposition. Merci à toi !

11/11/2010 05:17Posté par OuT

Bonjour, je me suis amusé à écrire la function push() différemment :

push: function (k, v) {
if (typeof this.data[k] === "undefined") {
if (this.length < this.maxlength) {
this.length += 1;
} else if (this.circular) {
this.pop();
} else {
return -1;
}
}
this.data[k] = v;
return this.length;
},

Je vois deux avantages avec cette forme, lorsqu'on est en mode "circular" :
- en cas de pop(), celui-ci est effectué avant d'ajouter la donnée, ce qui évite un dépassement du tampon, pour ainsi dire
- une fois la longueur max atteinte, la valeur de length cesse d'être incrémentée (ta technique continue d'incrémenter length à l'infini)

à plus

Créer une liste circulaire FIFO associative en Javascript

Téléchargements

Vos commentaires

Réagir à cet article