Tampão circular em javascript
-
21-09-2019 - |
Pergunta
Alguém já implementou um tampão circular em JavaScript? Como você faria isso sem ter dicas?
Solução
Strange Co-incidência, acabei de escrever um hoje cedo! Não sei exatamente seus requisitos, mas isso pode ser útil.
Apresenta uma interface como uma variedade de comprimentos ilimitados, mas esquece itens antigos:
// 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= {};
Outras dicas
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;
}
};
};
ATUALIZAÇÃO: Caso você preencha apenas o buffer com números, aqui estão alguns plugins de um liner:
min : function(){return Math.min.apply(Math, buffer);},
sum : function(){return buffer.reduce(function(a, b){ return a + b; }, 0);},
Como muitos outros, gostei Solução de Noiv, mas eu queria uma API um pouco mais agradável:
var createRingBuffer = function(length){
/* https://stackoverflow.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];
}
}
};
};
Melhorias sobre o original:
get
Suporta argumento padrão (retorna o último item empurrado para o buffer)get
suporta indexação negativa (contagens da direita)prev
move o buffer de volta um e retorna o que está lá (como estourar sem deletar)next
UNIDAS Anterior (move o buffer para a frente e o devolve)
Eu usei isso para armazenar um histórico de comando que eu poderia passar em um aplicativo usando seu prev
e next
Métodos, que retornam bem indefinidos quando não têm para onde ir.
Esta é uma modela rápida do código que você poderia usar (provavelmente não está funcionando e tem bugs, mas mostra como isso pode ser feito):
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 seria como:
var queue = new CircularQueue(10); // a circular queue with 10 items
queue.push(10);
queue.push(20);
alert(queue.pop());
alert(queue.pop());
É claro que você pode implementá -lo usando a matriz também com uma classe que usaria uma matriz internamente e manteria um valor do índice atual de itens e movendo -o.
Eu uso pessoalmente a implementação de Trevor Norris que você pode encontrar aqui:https://github.com/trevnorris/cbuffer
E estou muito feliz com isso :-)
Curto e grosso:
// 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);
Resultado:
98
99
Length: 2
Eu não conseguia fazer o código de Robert Koritnik funcionar, então editei para o seguinte 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
Eu realmente gosto de como O NOIV11 resolveu isso E para minha necessidade, adicionei uma propriedade extra 'buffer' que retorna o 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);
Em vez de implementar a fila circular com JavaScript, podemos usar algumas funções embutidas da matriz para obter a implementação da fila circular.
Exemplo: suponha que precisamos implementar a fila circular para o comprimento 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);
Resultado:
circular [4, 3, 2, 1
Se você tentar adicionar outro elemento a esta matriz, por exemplo:
addElementToQueue(5);
Resultado:
circular [5, 4, 3, 2
Uma abordagem seria usar uma lista vinculada como outras sugeriram. Outra técnica seria usar uma matriz simples como o buffer e acompanhar as posições de leitura e gravação por meio dessa matriz.
Eu acho que você deve ser capaz de fazer isso apenas usando objetos. Algo assim:
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;
Agora você apenas armazenaria o valor na propriedade Value de cada link.
Obrigado noiv pelo seu simples e eficiente solução. Eu também precisava ser capaz de acessar o buffer como Pers, mas eu queria obter os itens na ordem em que foram adicionados. Então, aqui está o que eu acabei com:
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;
}
Aqui está a suíte de teste:
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"]);
});
Auto -plugue sem vergonha:
Se você está procurando um buffer node.js rotativo, escrevi um que pode ser encontrado aqui: http://npmjs.org/packages/pivot-buffer
Falta documentação atualmente, mas RotatingBuffer#push
Permite anexar um buffer ao buffer atual, girando os dados anteriores se o novo comprimento for maior que o comprimento especificado no construtor.
É muito fácil se você agora o que Array.prototype.length é:
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;
}