whatwg - Buffer circular en JavaScript

whatwg español

Question

¿Alguien ha implementado un búfer circular en JavaScript? ¿Cómo harías eso sin tener punteros?

Answer 1

Como muchos otros, me gustó la solución de noiv , pero quería una API algo más agradable:

var createRingBuffer = function(length){
  /* https://.com/a/4774081 */
  var pointer = 0, buffer = []; 

  return {
    get  : function(key){
        if (key < 0){
            return buffer[pointer+key];
        } else if (key === false){
            return buffer[pointer - 1];
        } else{
            return buffer[key];
        }
    },
    push : function(item){
      buffer[pointer] = item;
      pointer = (pointer + 1) % length;
      return item;
    },
    prev : function(){
        var tmp_pointer = (pointer - 1) % length;
        if (buffer[tmp_pointer]){
            pointer = tmp_pointer;
            return buffer[pointer];
        }
    },
    next : function(){
        if (buffer[pointer]){
            pointer = (pointer + 1) % length;
            return buffer[pointer];
        }
    }
  };
};

Mejoras sobre el original:

• get soporte argumento predeterminado (devuelve el último elemento insertado en el búfer)
• get supports indexación negativa (cuenta desde la derecha)
• prev mueve el búfer a uno y devuelve lo que está allí (como hacer estallar sin eliminar)
• next deshace prev (mueve el buffer hacia adelante y lo devuelve)

Utilicé esto para almacenar un historial de comandos que luego podría hojear en una aplicación usando sus métodos prev y next , que muy bien devuelven indefinido cuando no tienen a dónde ir.

Answer 2

Corto y dulce:

// 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);

Salida:

98
99
Length: 2

Answer 3

Creo que deberías poder hacer esto solo usando objetos. Algo como esto:

var link = function(next, value) {
    this.next = next;
    this.value = value;
};

var last = new link();
var second = link(last);
var first = link(second);
last.next = first;

Ahora solo almacenarías el valor en la propiedad de valor de cada enlace.

Answer 4

En lugar de implementar una cola circular con JavaScript, podemos usar algunas funciones incorporadas de la matriz para lograr la implementación de la cola circular.

ejemplo: supongamos que necesitamos implementar la cola circular para la longitud 4.

var circular = new Array();
var maxLength = 4;
var addElementToQueue = function(element){
    if(circular.length == maxLength){
        circular.pop();
    }
    circular.unshift(element);
};
addElementToQueue(1);
addElementToQueue(2);
addElementToQueue(3);
addElementToQueue(4);

Salida:

circular [4, 3, 2, 1]

Si intenta agregar otro elemento a esta matriz, por ejemplo:

addElementToQueue(5);

Salida:

circular [5, 4, 3, 2]

Answer 5

Enchufe sin vergüenza:

Si está buscando un buffer rotativo node.js, escribí uno que se puede encontrar aquí: http://npmjs.org/packages/pivot-buffer

La documentación falta actualmente, pero RotatingBuffer#push permite agregar un búfer al búfer en uso, rotando los datos previos si la longitud nueva es mayor que la longitud especificada en el constructor.

Answer 6

Esta es una maqueta rápida del código que podría usar (probablemente no funciona y tiene errores, pero muestra la forma en que se podría hacer):

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;
};

usar este objeto sería como:

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

Por supuesto, podrías implementarlo usando una matriz con una clase que usaría internamente una matriz y mantendría un valor del índice de elemento actual y movería esa.

Answer 7

Extraña coincidencia, ¡acabo de escribir uno el día de hoy! No sé cuáles son exactamente tus requisitos, pero esto podría ser útil.

Presenta una interfaz como una matriz de longitud ilimitada, pero ''olvida'' elementos antiguos:

// Circular buffer storage. Externally-apparent ''length'' increases indefinitely
// while any items with indexes below length-n will be forgotten (undefined
// will be returned if you try to get them, trying to set is an exception).
// n represents the initial length of the array, not a maximum
function CircularBuffer(n) {
    this._array= new Array(n);
    this.length= 0;
}
CircularBuffer.prototype.toString= function() {
    return ''[object CircularBuffer(''+this._array.length+'') length ''+this.length+'']'';
};
CircularBuffer.prototype.get= function(i) {
    if (i<0 || i<this.length-this._array.length)
        return undefined;
    return this._array[i%this._array.length];
};
CircularBuffer.prototype.set= function(i, v) {
    if (i<0 || i<this.length-this._array.length)
        throw CircularBuffer.IndexError;
    while (i>this.length) {
        this._array[this.length%this._array.length]= undefined;
        this.length++;
    }
    this._array[i%this._array.length]= v;
    if (i==this.length)
        this.length++;
};
CircularBuffer.IndexError= {};

Answer 8

Gracias noiv por su solution simple y eficiente. También necesitaba poder acceder al buffer como lo hizo PerS , pero quería obtener los elementos en el orden en que fueron agregados. Así que aquí es a lo que terminé:

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;
}

Aquí está el conjunto de pruebas:

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"]);
});

Answer 9

Me gustó mucho cómo noiv11 resolvió esto y para mi necesidad agregué una propiedad adicional ''buffer'' que devuelve el buffer:

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);

Answer 10

No pude hacer funcionar el código de Robert Koritnik, así que lo edité a lo siguiente, lo que parece funcionar:

    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;

        this.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;
        };
        this.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;
        };
        return this;
    }

Usar:

    var queue = new CircularQueue(3); // a circular queue with 3 items
    queue.push("a");
    queue.push("b");
    queue.push("c");
    queue.push("d");
    alert(queue.pop()); // d
    alert(queue.pop()); // c
    alert(queue.pop()); // b
    alert(queue.pop()); // d
    alert(queue.pop()); // c

Answer 11

Un enfoque sería usar una lista vinculada como otros han sugerido. Otra técnica sería usar una matriz simple como buffer y hacer un seguimiento de las posiciones de lectura y escritura a través de índices en esa matriz.

Answer 12

Utilizo personalmente la implementación de Trevor Norris que puede encontrar aquí: https://github.com/trevnorris/cbuffer

y estoy bastante contento con eso :-)

Answer 13

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;
    }
  };
};

Actualización: en caso de que llene el búfer solo con números, aquí hay algunos plugins de liner:

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