Spique - A Spiral Double-Ended Queue

Spique is a deque implemented as a doubly-linked list of circular buffers. This structure allows for both high performance and unlimited dynamic growth of the queue. All operations are O(1) (constant time).

Spique does not require an initial or maximum size (although you can define a maximum if you wish), and will both grow and shrink dynamically as items are added and removed.

Spique is available via npm:

npm install spique

API

var Spique = require('spique');
var s = new Spique(size = 0, ringSize = 1024);

size sets the maximum number of items which may be stored in the queue at any given time. Attempting to store more items than this will return an error. If size is zero, then there is no maximum, and the queue may continue to grow as long as there is available memory. By default, size is unlimited.

ringSize sets the number of items stored in each ring. This defaults to 1024, which is normally fine for most purposes. Dynamic resizing is done in chunks of ringSize items (i.e. one buffer at a time).

Both size and ringSize are optional.

Spique can also be used as an iterator - this pattern will call dequeue() until the queue is empty.

for(myValue of s) {
  doSomething(myValue);
}

.enqueue(value, isSource = false, applyTransforms = true)

s.enqueue(myValue);
s.enqueue([1,2,3,4,5], true)

Append a value to the tail of the queue. If a max queue size has been set, and the queue is full, then this method will throw an error.

If isSource is true, then value will be treated as an iterator. All items returned by the iterator will be added to the queue as space allows. If the queue is full, the iterator will be called again once there is space available.

If isSource is true and value is an asynchronous iterator, then Spique will wait for each yielded promise to resolve before adding it to the queue, and before requesting another value from the iterator.

If isSource is true and value is another Spique instance, then in addition to being added as an iterator, it will also be watched for new data. If value is closed, then the queue into which it is feeding will also close once there is no more data available.

.dequeue()

var myValue = s.dequeue();

Return the value at the head of the queue, and remove it from the queue. If the queue is empty, this method will throw an error.

.enqueueHead(value, isSource = false, applyTransforms = true)

s.unshift(myValue...);

Identical to .enqueue(), except that items are prepended to the head of the queue instead of being appended to the tail.

.dequeueTail()

var myValue = s.pop();

Identical to dequeue(), except that itemd are removed from the tail of the queue, rather than from the head.

.peek()

var myValue = s.peek();

Return the value at the head of the queue. The value is not removed. If the queue is empty, then this method will throw an error.

.peekTail()

var myValue = s.peekTail();

Return the value at the end of the queue. The value is not removed. If the queue is empty, then this method will throw an error.

.transform(transformFn)

s.transform(n => n * n);
s.transform(function*(n) {
    while (n > 0) {
        yield n--;
    }
});
s.transform((n, reject) => {
    if (n < 1) {
        reject();
    }
    return n * n;
});

Apply the provided transform function to all items as they are inserted into the queue. More than one transform function can be registered - if this is the case, they are run in order from oldest to newest, and the final output from the transform pipeline is what eventually gets inserted.

If transformFn is a generator function, then every result it yields will be processed individually by the remainder of the transform pipeline and inserted as a separate value.

The second argument to transformFn is a reject callback. If this is called, then the value is silently dropped, and will not be enqueued or processed further.

.close()

s.on("close", queue => {
  // there are no items remaining and the queue is now closed
});
s.close(); // close immediately

Mark the queue as closed. A closed queue will never emit a free event, and will emit a close event once the queue is completely empty and all pending items have been processed.

Please note that items cannot be inserted into a closed queue. However if the queue is being fed from a source, then this will continue until the source is empty. It's also possible to continue inserting into a queue that has been marked closed, but has not yet been emptied.

Properties

.length

The number of items currently stored in the queue.

.size

The maximum capacity of the queue - if unlimited, this will be zero.

.free

The number of available slots remaining in the queue.

.closed

Whether the queue is closed. If the queue has been marked closed, but still contains items, then this will return false until the queue is empty.

.ringSize

The size of each circular buffer. The queue will grow / shrink by this many items at a time.

Events

Event handlers will be called immediately upon attachment if the queue is currently in a state where entering that state would have emitted the target event. For example, if the queue contains one or more items, and a listener is attached for the data event, it will be called immediately.

data

The queue has one or more items stored in it.

full

The queue is full.

free

The queue has space available to store more items. Note that even if you receive a free event, if the queue is of a limited size then you should still check that there is space available before inserting, as this event may have multiple listeners, and you might not be the first one to receive it - somebody else might have filled up the queue before you.

empty

The queue is empty. The same caveats as free apply here too.

close

The queue is empty, and the queue is marked as closed.