| /** |
| * Copyright (c) 2014 Petka Antonov |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a copy |
| * of this software and associated documentation files (the "Software"), to deal |
| * in the Software without restriction, including without limitation the rights |
| * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| * copies of the Software, and to permit persons to whom the Software is |
| * furnished to do so, subject to the following conditions:</p> |
| * |
| * The above copyright notice and this permission notice shall be included in |
| * all copies or substantial portions of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
| * THE SOFTWARE. |
| * |
| */ |
| "use strict"; |
| function arrayCopy(src, srcIndex, dst, dstIndex, len) { |
| for (var j = 0; j < len; ++j) { |
| dst[j + dstIndex] = src[j + srcIndex]; |
| } |
| } |
| |
| function pow2AtLeast(n) { |
| n = n >>> 0; |
| n = n - 1; |
| n = n | (n >> 1); |
| n = n | (n >> 2); |
| n = n | (n >> 4); |
| n = n | (n >> 8); |
| n = n | (n >> 16); |
| return n + 1; |
| } |
| |
| function getCapacity(capacity) { |
| if (typeof capacity !== "number") return 16; |
| return pow2AtLeast( |
| Math.min( |
| Math.max(16, capacity), 1073741824) |
| ); |
| } |
| |
| function Queue(capacity) { |
| this._capacity = getCapacity(capacity); |
| this._length = 0; |
| this._front = 0; |
| this._makeCapacity(); |
| } |
| |
| Queue.prototype._willBeOverCapacity = |
| function Queue$_willBeOverCapacity(size) { |
| return this._capacity < size; |
| }; |
| |
| Queue.prototype._pushOne = function Queue$_pushOne(arg) { |
| var length = this.length(); |
| this._checkCapacity(length + 1); |
| var i = (this._front + length) & (this._capacity - 1); |
| this[i] = arg; |
| this._length = length + 1; |
| }; |
| |
| Queue.prototype.push = function Queue$push(fn, receiver, arg) { |
| var length = this.length() + 3; |
| if (this._willBeOverCapacity(length)) { |
| this._pushOne(fn); |
| this._pushOne(receiver); |
| this._pushOne(arg); |
| return; |
| } |
| var j = this._front + length - 3; |
| this._checkCapacity(length); |
| var wrapMask = this._capacity - 1; |
| this[(j + 0) & wrapMask] = fn; |
| this[(j + 1) & wrapMask] = receiver; |
| this[(j + 2) & wrapMask] = arg; |
| this._length = length; |
| }; |
| |
| Queue.prototype.shift = function Queue$shift() { |
| var front = this._front, |
| ret = this[front]; |
| |
| this[front] = void 0; |
| this._front = (front + 1) & (this._capacity - 1); |
| this._length--; |
| return ret; |
| }; |
| |
| Queue.prototype.length = function Queue$length() { |
| return this._length; |
| }; |
| |
| Queue.prototype._makeCapacity = function Queue$_makeCapacity() { |
| var len = this._capacity; |
| for (var i = 0; i < len; ++i) { |
| this[i] = void 0; |
| } |
| }; |
| |
| Queue.prototype._checkCapacity = function Queue$_checkCapacity(size) { |
| if (this._capacity < size) { |
| this._resizeTo(this._capacity << 3); |
| } |
| }; |
| |
| Queue.prototype._resizeTo = function Queue$_resizeTo(capacity) { |
| var oldFront = this._front; |
| var oldCapacity = this._capacity; |
| var oldQueue = new Array(oldCapacity); |
| var length = this.length(); |
| |
| arrayCopy(this, 0, oldQueue, 0, oldCapacity); |
| this._capacity = capacity; |
| this._makeCapacity(); |
| this._front = 0; |
| if (oldFront + length <= oldCapacity) { |
| arrayCopy(oldQueue, oldFront, this, 0, length); |
| } |
| else { var lengthBeforeWrapping = |
| length - ((oldFront + length) & (oldCapacity - 1)); |
| |
| arrayCopy(oldQueue, oldFront, this, 0, lengthBeforeWrapping); |
| arrayCopy(oldQueue, 0, this, lengthBeforeWrapping, |
| length - lengthBeforeWrapping); |
| } |
| }; |
| |
| module.exports = Queue; |