Facebook LinkedIn SourceForge Twitter RSS LastFM
logologo

Créer une liste circulaire FIFO associative en Javascript

Geoffray Warnants|23/09/2010|8 commentaires

Dans le cadre du dveloppement d'un systme de cache en Javascript, j'ai rencontr le besoin de disposer d'une structure de donnes associative organise selon le modle de la liste circulaire. Ce concept n'est si je ne m'abuse qu'un cas particulier de la file FIFO (queue), une structure dj implmente nativement dans le langage via les mthodes push et pop d'un simple objet Array au mme titre d'ailleurs que la pile LIFO (stack) l'est via shift et unshift. Cependant, ces pratiques impliquent une gestion squentielle de la collection, c'est dire qu'il n'est possible d'accder un lment que via son index numrique et non via une clef associative.

J'ai donc cr une classe trs rudimentaire qui fourni les fonctionnalits 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 dfinir si la structure doit se comporter comme une file FIFO classique, ce qui est le cas par dfaut ou comme une file circulaire. La diffrence se constate dans le cas o l'on tente d'empiler un nouvel lment dans une file pleine : la file classique retournera une erreur tandis que la file circulaire permettra l'insertion tout en dpilant le plus ancien lment.

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

// accs associatif aux lments via la clef
console.log(q.has("key1")); // affiche false
console.log(q.has("key2")); // affiche true
console.log(q.find("key3")); // affiche "val3"

Tlchargements

<<< Retour

Vos commentaires

8 commentaires posts

Alex
17/03/2021 17:30Post par Alex
Hi, I think your web site might be having internet browser
compatibility problems. Whenever I look at your website in Safari, it
looks fine however, if opening in IE, it has some overlapping
issues. I merely wanted to provide you with a quick
heads up! Apart from that, wonderful site!
F?lice Robin
23/12/2020 08:30Post par F?lice Robin
Maintenant que j?ai connais un peu le principe de fonctionnement de ce FIFO en JavaScript, je veux essayer de construire une. En fait, j?ai utilis? plusieurs fois JavaScript, mais je n?ai jamais trouv? un autre algorithme comme cela. Merci
Oliva Lefevre
07/12/2020 15:20Post par Oliva Lefevre
Je suis tombé par hasard sur votre article. Et malgré le fait qu?il soit un peu vieux, je trouve que votre publication va aider beaucoup de personnes. Perso, je ne connais rein en ce langage que vous avez publié.
Thaïs Mulot
16/10/2020 10:39Post par Thaïs Mulot
Je croyais qu?une FIFO est une FIFO et ce n?est pas une liste circulaire. Il y a, certes, un soi, disons FIFO circulaire, mais encore faudra-t-il savoir si c?est réellement une FIFO. Bref, je suis perdu en lisant votre article.
Geoffray
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
OuT
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
Geoffray
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 !
OuT
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

Ragir cet article

*


(Ne sera pas publie, servira uniquement afficher votre gravatar)


(Lien en dur et dofollow)

zend framework