Tampon circulaire en JavaScript

var createRingBuffer = function(length){

  var pointer = 0, buffer = []; 

  return {
    get  : function(key){return buffer[key];},
    push : function(item){
      buffer[pointer] = item;
      pointer = (length + pointer +1) % length;
    }
  };
};

Mise à jour: dans le cas où vous remplissez le tampon avec uniquement des chiffres, en voici quelques-un liner plugins:

min  : function(){return Math.min.apply(Math, buffer);},
sum  : function(){return buffer.reduce(function(a, b){ return a + b; }, 0);},

C'est un moyen rapide maquette du code que vous pourriez utiliser (il n'est probablement pas de travail et a des bugs, mais il montre la façon dont il pourrait être fait):

var CircularQueueItem = function(value, next, back) {
    this.next = next;
    this.value = value;
    this.back = back;
    return this;
};

var CircularQueue = function(queueLength){
    ///<summary>Creates a circular queue of specified length</summary>
    ///<param name="queueLength" type="int">Length of the circular queue</type>
    this._current = new CircularQueueItem(undefined, undefined, undefined);
    var item = this._current;
    for(var i = 0; i < queueLength - 1; i++)
    {
        item.next = new CircularQueueItem(undefined, undefined, item);
        item = item.next;
    }
    item.next = this._current;
    this._current.back = item;
}

CircularQueue.prototype.push = function(value){
    ///<summary>Pushes a value/object into the circular queue</summary>
    ///<param name="value">Any value/object that should be stored into the queue</param>
    this._current.value = value;
    this._current = this._current.next;
};

CircularQueue.prototype.pop = function(){
    ///<summary>Gets the last pushed value/object from the circular queue</summary>
    ///<returns>Returns the last pushed value/object from the circular queue</returns>
    this._current = this._current.back;
    return this._current.value;
};

l'aide de cet objet serait comme:

var queue = new CircularQueue(10); //a circular queue with 10 items
queue.push(10);
queue.push(20);
alert(queue.pop());
alert(queue.pop());

Vous pouvez bien sûr mettre en œuvre à l'aide du tableau ainsi avec une classe qui permettrait d'utiliser à l'interne d'un tableau et de garder une valeur de l'index de l'élément et le déplacement de celui-là.

Court et doux:

//IMPLEMENTATION
function CircularArray(maxLength) {
  this.maxLength = maxLength;
}

CircularArray.prototype = Object.create(Array.prototype);

CircularArray.prototype.push = function(element) {
  Array.prototype.push.call(this, element);
  while (this.length > this.maxLength) {
    this.shift();
  }
}

//USAGE
var ca = new CircularArray(2);
var i;

for (i = 0; i < 100; i++) {
  ca.push(i);
}

console.log(ca[0]);
console.log(ca[1]);
console.log("Length: " + ca.length);

De sortie:

98
99
Length: 2

J'aime vraiment comment noiv11 résolu ce et pour mon besoin, j'ai ajouté un supplément de propriété "tampon" qui renvoie la mémoire tampon:

var createRingBuffer = function(length){

  var pointer = 0, buffer = []; 

  return {
    get  : function(key){return buffer[key];},
    push : function(item){
      buffer[pointer] = item;
      pointer = (length + pointer +1) % length;
    },
    buffer : buffer
  };
};

//sample use
var rbuffer = createRingBuffer(3);
rbuffer.push('a');
rbuffer.push('b');
rbuffer.push('c');
alert(rbuffer.buffer.toString());
rbuffer.push('d');
alert(rbuffer.buffer.toString());
var el = rbuffer.get(0);
alert(el);

Une approche serait d'utiliser une liste chaînée comme d'autres l'ont suggéré. Une autre technique est d'utiliser un simple tableau en mémoire tampon et de garder une trace de la lire et d'écrire des positions via des indices dans ce tableau.

Grâce noiv pour votre simple et efficace solution. J'ai aussi besoin d'être en mesure d'accéder à la mémoire tampon comme PerS ne, mais je voulais obtenir les éléments dans l'ordre où ils ont été ajoutés. Voici donc ce que j'ai:

function buffer(capacity) {
    if (!(capacity > 0)) {
        throw new Error();
    }

    var pointer = 0, buffer = [];

    var publicObj = {
        get: function (key) {
            if (key === undefined) {
                //return all items in the order they were added
                if (pointer == 0 || buffer.length < capacity) {
                    //the buffer as it is now is in order
                    return buffer;
                }
                //split and join the two parts so the result is in order
                return buffer.slice(pointer).concat(buffer.slice(0, pointer));
            }
            return buffer[key];
        },
        push: function (item) {
            buffer[pointer] = item;
            pointer = (capacity + pointer + 1) % capacity;
            //update public length field
            publicObj.length = buffer.length;
        },
        capacity: capacity,
        length: 0
    };

    return publicObj;
}

Voici la suite de tests:

QUnit.module("buffer");
QUnit.test("constructor", function () {
QUnit.expect(4);
QUnit.equal(buffer(1).capacity, 1, "minimum length of 1 is allowed");
QUnit.equal(buffer(10).capacity, 10);
QUnit.throws(
function () {
buffer(-1);
},
Error,
"must throuw exception on negative length"
);
QUnit.throws(
function () {
buffer(0);
},
Error,
"must throw exception on zero length"
);
});
QUnit.test("push", function () {
QUnit.expect(5);
var b = buffer(5);
QUnit.equal(b.length, 0);
b.push("1");
QUnit.equal(b.length, 1);
b.push("2");
b.push("3");
b.push("4");
b.push("5");
QUnit.equal(b.length, 5);
b.push("6");
QUnit.equal(b.length, 5);
b.push("7");
b.push("8");
QUnit.equal(b.length, 5);
});
QUnit.test("get(key)", function () {
QUnit.expect(8);
var b = buffer(3);
QUnit.equal(b.get(0), undefined);
b.push("a");
QUnit.equal(b.get(0), "a");
b.push("b");
QUnit.equal(b.get(1), "b");
b.push("c");
QUnit.equal(b.get(2), "c");
b.push("d");
QUnit.equal(b.get(0), "d");
b = buffer(1);
b.push("1");
QUnit.equal(b.get(0), "1");
b.push("2");
QUnit.equal(b.get(0), "2");
QUnit.equal(b.length, 1);
});
QUnit.test("get()", function () {
QUnit.expect(7);
var b = buffer(3);
QUnit.deepEqual(b.get(), []);
b.push("a");
QUnit.deepEqual(b.get(), ["a"]);
b.push("b");
QUnit.deepEqual(b.get(), ["a", "b"]);
b.push("c");
QUnit.deepEqual(b.get(), ["a", "b", "c"]);
b.push("d");
QUnit.deepEqual(b.get(), ["b", "c", "d"]);
b.push("e");
QUnit.deepEqual(b.get(), ["c", "d", "e"]);
b.push("f");
QUnit.deepEqual(b.get(), ["d", "e", "f"]);
});

Il est très facile si vous maintenant ce que Tableau.le prototype.longueur est:

function CircularBuffer(size) {
Array.call(this,size); //superclass
this.length = 0; //current index
this.size = size; //buffer size
};
CircularBuffer.prototype = Object.create(Array.prototype);
CircularBuffer.prototype.constructor = CircularBuffer;
CircularBuffer.prototype.constructor.name = "CircularBuffer";
CircularBuffer.prototype.push = function push(elem){
Array.prototype.push.call(this,elem);
if (this.length >= this.size) this.length = 0;
return this.length;
}
CircularBuffer.prototype.pop = function pop(){
var r = this[this.length];
if (this.length <= 0) this.length = this.size;  
this.length--;
return r;
}

Je préfère des approches plus simples. Ce doit être un trois-liner, de l'OMI.

Quelque chose comme

const makeRing = sz                   => ({ sz, buf: new Array(size) }),
at       = ({sz, buf}, pos)     => buf[pos % sz],
set      = ({sz, buf}, pos, to) => buf[pos % sz] = to;

Alors vous pouvez simplement

const ring = makeRing(10);
ring.buf.fill(1);
set(ring, 35, 'TWO!');
console.log(ring.buf);
console.log(at(ring, 65));