@tsdotnet/queue - npm Package Compare versions

Comparing version 1.1.5 to 1.2.0

dist-esm/Queue.js

@@ -1,80 +0,97 @@
-/*!
+/*
  * @author electricessence / https://github.com/electricessence/
- * Licensing: MIT
+ * @license MIT
+ * Based Upon: http://referencesource.microsoft.com/#System/CompMod/system/collections/generic/queue.cs
  */
-import ArgumentNullException from '@tsdotnet/exceptions/dist/ArgumentNullException';
-import InvalidOperationException from '@tsdotnet/exceptions/dist/InvalidOperationException';
-import IterableCollectionBase from '@tsdotnet/collection-base/dist/IterableCollectionBase';
-export default class Queue extends IterableCollectionBase {
+/* eslint-disable @typescript-eslint/no-this-alias */
+import QueueBase from './QueueBase';
+const MINIMUM_GROW = 4;
+const DEFAULT_CAPACITY = 4;
+const SHRINK_THRESHOLD = 42;
+export default class Queue extends QueueBase {
     constructor(initialEntries) {
         super();
-        this._root = {};
-        this._count = 0;
-        if (initialEntries)
-            this.enqueueMultiple(initialEntries);
+        this._head = 0; // First valid element in the queue
+        this._tail = 0; // Last valid element in the queue
+        this._size = 0; // Number of elements.
+        if (!initialEntries)
+            this._array = new Array(DEFAULT_CAPACITY);
+        else {
+            this._array = initialEntries.slice();
+            this._tail = this._size = this._array.length;
+        }
     }
-    /**
-     * The number of items currently in the queue.
-     * @returns {number}
-     */
-    get count() {
-        return this._count;
+    getCount() {
+        return this._size;
     }
-    /**
-     * Returns true if the queue is empty.
-     * @return {boolean}
-     */
-    get isEmpty() {
-        return this._count === 0;
+    clear() {
+        const _ = this, size = _._size;
+        _._array.length = 0;
+        _._head = 0;
+        _._tail = 0;
+        _._size = 0;
+        _.incrementVersion();
+        return size;
     }
     /**
-     * Returns the number of items currently in the queue.
-     * @returns {number}
+     * Dequeues entries into an array.
      */
-    getCount() {
-        return this._count;
+    dump(max = Infinity) {
+        const _ = this;
+        const result = new Array(Math.min(max, _._size));
+        if (isFinite(max)) {
+            if (max !== 0) {
+                let i = 0;
+                while (max-- && _._size)
+                    result[i++] = _._dequeueInternal();
+            }
+        }
+        else {
+            while (_._size)
+                result.push(_._dequeueInternal());
+        }
+        _.incrementVersion();
+        return result;
     }
-    /**
-     * Adds an item to the end of the queue.
-     * @param value
-     * @returns {this}
-     */
-    enqueue(value) {
-        this._enqueueInternal(value);
-        this.incrementVersion();
-        return this;
-    }
-    /**
-     * Adds items to the end of the queue.
-     * @param {Iterable} values
-     * @returns {this}
-     */
-    enqueueMultiple(values) {
-        if (!values)
+    setCapacity(capacity) {
+        if (isNaN(capacity))
             return this;
-        for (const v of values) {
-            this._enqueueInternal(v);
+        if (capacity < 0)
+            capacity = 0;
+        const _ = this;
+        const array = _._array, len = array.length;
+        if (capacity == len)
+            return this;
+        const head = _._head, tail = _._tail, size = _._size;
+        if (!size) {
+            array.length = capacity;
+            this._head = 0;
+            this._tail = 0;
+            return this;
         }
-        this.incrementVersion();
+        // Special case where we can simply extend or shrink the length of the array.
+        if (head < tail && capacity >= tail) {
+            array.length = capacity;
+            return this;
+        }
+        // We create a new array because modifying an existing one could be slow.
+        const newArray = new Array(capacity);
+        let i, n = 0;
+        if (head < tail) {
+            for (i = head; i < tail; i++)
+                newArray[n++] = array[i];
+        }
+        else {
+            for (i = head; i < len; i++)
+                newArray[n++] = array[i];
+            for (i = 0; i < tail; i++)
+                newArray[n++] = array[i];
+        }
+        this._array = newArray;
+        _._head = 0;
+        _._tail = (size == capacity) ? 0 : size;
+        _.incrementVersion();
         return this;
     }
     /**
-     * Adds items to the end of the queue.
-     * @param values
-     * @returns {this}
-     */
-    enqueueThese(...values) {
-        return this.enqueueMultiple(values);
-    }
-    dequeue(throwIfEmpty = false) {
-        const n = this._root.next;
-        if (this._dequeueInternal(n)) {
-            this.incrementVersion();
-            return n.value;
-        }
-        if (throwIfEmpty)
-            throw new InvalidOperationException('Cannot dequeue an empty queue.');
-        return undefined;
-    }
-    /**
      * Checks to see if the queue has entries an pulls an entry from the head of the queue and passes it to the out handler.
@@ -85,119 +102,61 @@ * @param out The 'out' handler that receives the value if it exists.
     tryDequeue(out) {
-        if (!out)
-            throw new ArgumentNullException('out');
-        const n = this._root.next;
-        if (!this._dequeueInternal(n))
-            return false;
-        this.incrementVersion();
-        out(n.value);
-        return true;
-    }
-    peek(throwIfEmpty = false) {
-        const n = this._root.next;
-        if (n)
-            return n.value;
-        if (throwIfEmpty)
-            throw new InvalidOperationException('Cannot call peek on an empty queue.');
-        return undefined;
-    }
-    /**
-     * Dequeues entries into an array.
-     */
-    dump(max = Infinity) {
-        if (!this.count)
-            return [];
-        const result = [];
-        const root = this._root;
-        if (isFinite(max)) {
-            while (0 <= --max) {
-                const n = root.next;
-                if (!this._dequeueInternal(n))
-                    break;
-                result.push(n.value);
-            }
+        const _ = this;
+        if (super.tryDequeue(out)) {
+            if (_._size < _._array.length / 2)
+                _.trimExcess(SHRINK_THRESHOLD);
+            _.incrementVersion();
+            return true;
         }
-        else {
-            let n = root.next;
-            while (this._dequeueInternal(n)) {
-                result.push(n.value);
-                n = root.next;
-            }
-        }
-        this.incrementVersion();
-        return result;
+        return false;
     }
     /**
-     * Produces an iterable that dequeues items when iterated.  Stops when empty.
-     * @return {Iterable}
+     * Trims excess items in the underlying array.
+     * @param {number} threshold
      */
-    consumer() {
-        // eslint-disable-next-line @typescript-eslint/no-this-alias
-        const _ = this, root = this._root;
-        return {
-            *[Symbol.iterator]() {
-                while (true) {
-                    const n = root.next;
-                    if (!_._dequeueInternal(n))
-                        break;
-                    _.incrementVersion();
-                    yield n.value;
-                }
-            }
-        };
+    trimExcess(threshold) {
+        const _ = this;
+        const size = _._size;
+        if (size < Math.floor(_._array.length * 0.9) && (!threshold && threshold !== 0 || isNaN(threshold) || threshold < size))
+            _.setCapacity(size);
     }
-    /**
-     * Clears the list.
-     */
-    clear() {
-        const count = this._count;
-        this._root.next = undefined;
-        this._tail = undefined;
-        this._count = 0;
-        return count;
+    _enqueueInternal(item) {
+        const _ = this;
+        const size = _._size;
+        let len = _._array.length;
+        if (size === len) {
+            let newCapacity = len * 2;
+            if (newCapacity < len + MINIMUM_GROW)
+                newCapacity = len + MINIMUM_GROW;
+            _.setCapacity(newCapacity);
+            len = _._array.length;
+        }
+        const tail = _._tail % len;
+        _._array[tail] = item;
+        _._tail = (tail + 1) % len;
+        _._size = size + 1;
     }
-    /**
-     * Clears the list.
-     */
-    dispose() {
-        this.clear();
+    _dequeueInternal() {
+        if (!this._size)
+            return undefined;
+        const array = this._array, head = this._head;
+        const removed = array[head];
+        array[head] = undefined; // protect the data.
+        this._head = (head + 1) % array.length;
+        this._size--;
+        return removed;
     }
-    /**
-     * Clears the list.
-     */
-    recycle() {
-        this.clear();
+    _peekInternal() {
+        const _ = this;
+        return _._size ? _._array[_._head] : undefined;
     }
     *_getIterator() {
-        let current, next = this._root.next;
-        while (next) {
-            current = next;
-            next = current.next;
-            yield current.value;
-        }
+        const _ = this, size = _._size;
+        for (let i = 0; i < size; i++)
+            yield _._getElement(i);
     }
-    _enqueueInternal(value) {
-        const newTail = { value: value };
-        const tail = this._tail;
-        if (tail)
-            tail.next = newTail;
-        else
-            this._root.next = newTail;
-        this._tail = newTail;
-        this._count++;
+    _getElement(index) {
+        const _ = this, a = _._array;
+        return _._size ? a[(_._head + index) % a.length] : undefined;
     }
-    _dequeueInternal(n) {
-        if (!n)
-            return false;
-        this._root.next = n.next;
-        if (n.next)
-            n.next = undefined;
-        else
-            this._tail = undefined;
-        const count = this._count;
-        if (!count)
-            throw new Error('Dequeuing empty collection.');
-        this._count = count - 1;
-        return true;
-    }
 }
 //# sourceMappingURL=Queue.js.map

dist/Queue.d.ts

@@ -1,64 +0,16 @@
-/*!
- * @author electricessence / https://github.com/electricessence/
- * Licensing: MIT
- */
-import IterableCollectionBase from '@tsdotnet/collection-base/dist/IterableCollectionBase';
-export default class Queue<T> extends IterableCollectionBase<T> {
-    private _root;
-    private _tail?;
-    constructor(initialEntries?: Iterable<T> | null);
-    private _count;
-    /**
-     * The number of items currently in the queue.
-     * @returns {number}
-     */
-    get count(): number;
-    /**
-     * Returns true if the queue is empty.
-     * @return {boolean}
-     */
-    get isEmpty(): boolean;
-    /**
-     * Returns the number of items currently in the queue.
-     * @returns {number}
-     */
+import QueueBase from './QueueBase';
+export default class Queue<T> extends QueueBase<T> {
+    protected _array: T[];
+    protected _head: number;
+    protected _tail: number;
+    protected _size: number;
+    constructor(initialEntries?: T[]);
     getCount(): number;
+    clear(): number;
     /**
-     * Adds an item to the end of the queue.
-     * @param value
-     * @returns {this}
+     * Dequeues entries into an array.
      */
-    enqueue(value: T): this;
+    dump(max?: number): T[];
+    setCapacity(capacity: number): this;
     /**
-     * Adds items to the end of the queue.
-     * @param {Iterable} values
-     * @returns {this}
-     */
-    enqueueMultiple(values: Iterable<T>): this;
-    /**
-     * Adds items to the end of the queue.
-     * @param values
-     * @returns {this}
-     */
-    enqueueThese(...values: T[]): this;
-    /**
-     * Pulls an entry from the head of the queue and returns it.
-     * Returns undefined if the queue is already empty.
-     */
-    dequeue(): T | undefined;
-    /**
-     * Pulls an entry from the head of the queue and returns it.
-     * Returns undefined if the queue is already empty and throwIfEmpty is false.
-     * Throws an InvalidOperationException if the queue is already empty and throwIfEmpty is true.
-     * @param throwIfEmpty
-     */
-    dequeue(throwIfEmpty: true): T | never;
-    /**
-     * Pulls an entry from the head of the queue and returns it.
-     * Returns undefined if the queue is already empty and throwIfEmpty is false.
-     * Throws an InvalidOperationException if the queue is already empty and throwIfEmpty is true.
-     * @param throwIfEmpty
-     */
-    dequeue(throwIfEmpty: boolean): T | undefined | never;
-    /**
      * Checks to see if the queue has entries an pulls an entry from the head of the queue and passes it to the out handler.
@@ -68,46 +20,13 @@ * @param out The 'out' handler that receives the value if it exists.
      */
-    tryDequeue(out: (dequeued: T) => void): boolean;
+    tryDequeue(out: (value: T) => void): boolean;
     /**
-     * Returns the entry at the head of the queue.
-     * Returns undefined if the queue is already empty.
+     * Trims excess items in the underlying array.
+     * @param {number} threshold
      */
-    peek(): T | undefined;
-    /**
-     * Returns the entry at the head of the queue.
-     * Returns undefined if the queue is already empty and throwIfEmpty is false.
-     * Throws an InvalidOperationException if the queue is already empty and throwIfEmpty is true.
-     * @param throwIfEmpty
-     */
-    peek(throwIfEmpty: true): T | never;
-    /**
-     * Returns the entry at the head of the queue.
-     * Returns undefined if the queue is already empty and throwIfEmpty is false.
-     * Throws an InvalidOperationException if the queue is already empty and throwIfEmpty is true.
-     * @param throwIfEmpty
-     */
-    peek(throwIfEmpty: boolean): T | undefined | never;
-    /**
-     * Dequeues entries into an array.
-     */
-    dump(max?: number): T[];
-    /**
-     * Produces an iterable that dequeues items when iterated.  Stops when empty.
-     * @return {Iterable}
-     */
-    consumer(): Iterable<T>;
-    /**
-     * Clears the list.
-     */
-    clear(): number;
-    /**
-     * Clears the list.
-     */
-    dispose(): void;
-    /**
-     * Clears the list.
-     */
-    recycle(): void;
+    trimExcess(threshold?: number): void;
+    protected _enqueueInternal(item: T): void;
+    protected _dequeueInternal(): T | undefined;
+    protected _peekInternal(): T | undefined;
     protected _getIterator(): Iterator<T>;
-    private _enqueueInternal;
-    private _dequeueInternal;
+    private _getElement;
 }

dist/Queue.js

 "use strict";
-/*!
+/*
  * @author electricessence / https://github.com/electricessence/
- * Licensing: MIT
+ * @license MIT
+ * Based Upon: http://referencesource.microsoft.com/#System/CompMod/system/collections/generic/queue.cs
  */
 Object.defineProperty(exports, "__esModule", { value: true });
 const tslib_1 = require("tslib");
-const ArgumentNullException_1 = tslib_1.__importDefault(require("@tsdotnet/exceptions/dist/ArgumentNullException"));
-const InvalidOperationException_1 = tslib_1.__importDefault(require("@tsdotnet/exceptions/dist/InvalidOperationException"));
-const IterableCollectionBase_1 = tslib_1.__importDefault(require("@tsdotnet/collection-base/dist/IterableCollectionBase"));
-class Queue extends IterableCollectionBase_1.default {
+/* eslint-disable @typescript-eslint/no-this-alias */
+const QueueBase_1 = tslib_1.__importDefault(require("./QueueBase"));
+const MINIMUM_GROW = 4;
+const DEFAULT_CAPACITY = 4;
+const SHRINK_THRESHOLD = 42;
+class Queue extends QueueBase_1.default {
     constructor(initialEntries) {
         super();
-        this._root = {};
-        this._count = 0;
-        if (initialEntries)
-            this.enqueueMultiple(initialEntries);
+        this._head = 0; // First valid element in the queue
+        this._tail = 0; // Last valid element in the queue
+        this._size = 0; // Number of elements.
+        if (!initialEntries)
+            this._array = new Array(DEFAULT_CAPACITY);
+        else {
+            this._array = initialEntries.slice();
+            this._tail = this._size = this._array.length;
+        }
     }
-    /**
-     * The number of items currently in the queue.
-     * @returns {number}
-     */
-    get count() {
-        return this._count;
+    getCount() {
+        return this._size;
     }
-    /**
-     * Returns true if the queue is empty.
-     * @return {boolean}
-     */
-    get isEmpty() {
-        return this._count === 0;
+    clear() {
+        const _ = this, size = _._size;
+        _._array.length = 0;
+        _._head = 0;
+        _._tail = 0;
+        _._size = 0;
+        _.incrementVersion();
+        return size;
     }
     /**
-     * Returns the number of items currently in the queue.
-     * @returns {number}
+     * Dequeues entries into an array.
      */
-    getCount() {
-        return this._count;
+    dump(max = Infinity) {
+        const _ = this;
+        const result = new Array(Math.min(max, _._size));
+        if (isFinite(max)) {
+            if (max !== 0) {
+                let i = 0;
+                while (max-- && _._size)
+                    result[i++] = _._dequeueInternal();
+            }
+        }
+        else {
+            while (_._size)
+                result.push(_._dequeueInternal());
+        }
+        _.incrementVersion();
+        return result;
     }
-    /**
-     * Adds an item to the end of the queue.
-     * @param value
-     * @returns {this}
-     */
-    enqueue(value) {
-        this._enqueueInternal(value);
-        this.incrementVersion();
-        return this;
-    }
-    /**
-     * Adds items to the end of the queue.
-     * @param {Iterable} values
-     * @returns {this}
-     */
-    enqueueMultiple(values) {
-        if (!values)
+    setCapacity(capacity) {
+        if (isNaN(capacity))
             return this;
-        for (const v of values) {
-            this._enqueueInternal(v);
+        if (capacity < 0)
+            capacity = 0;
+        const _ = this;
+        const array = _._array, len = array.length;
+        if (capacity == len)
+            return this;
+        const head = _._head, tail = _._tail, size = _._size;
+        if (!size) {
+            array.length = capacity;
+            this._head = 0;
+            this._tail = 0;
+            return this;
         }
-        this.incrementVersion();
+        // Special case where we can simply extend or shrink the length of the array.
+        if (head < tail && capacity >= tail) {
+            array.length = capacity;
+            return this;
+        }
+        // We create a new array because modifying an existing one could be slow.
+        const newArray = new Array(capacity);
+        let i, n = 0;
+        if (head < tail) {
+            for (i = head; i < tail; i++)
+                newArray[n++] = array[i];
+        }
+        else {
+            for (i = head; i < len; i++)
+                newArray[n++] = array[i];
+            for (i = 0; i < tail; i++)
+                newArray[n++] = array[i];
+        }
+        this._array = newArray;
+        _._head = 0;
+        _._tail = (size == capacity) ? 0 : size;
+        _.incrementVersion();
         return this;
     }
     /**
-     * Adds items to the end of the queue.
-     * @param values
-     * @returns {this}
-     */
-    enqueueThese(...values) {
-        return this.enqueueMultiple(values);
-    }
-    dequeue(throwIfEmpty = false) {
-        const n = this._root.next;
-        if (this._dequeueInternal(n)) {
-            this.incrementVersion();
-            return n.value;
-        }
-        if (throwIfEmpty)
-            throw new InvalidOperationException_1.default('Cannot dequeue an empty queue.');
-        return undefined;
-    }
-    /**
      * Checks to see if the queue has entries an pulls an entry from the head of the queue and passes it to the out handler.
@@ -88,120 +105,62 @@ * @param out The 'out' handler that receives the value if it exists.
     tryDequeue(out) {
-        if (!out)
-            throw new ArgumentNullException_1.default('out');
-        const n = this._root.next;
-        if (!this._dequeueInternal(n))
-            return false;
-        this.incrementVersion();
-        out(n.value);
-        return true;
-    }
-    peek(throwIfEmpty = false) {
-        const n = this._root.next;
-        if (n)
-            return n.value;
-        if (throwIfEmpty)
-            throw new InvalidOperationException_1.default('Cannot call peek on an empty queue.');
-        return undefined;
-    }
-    /**
-     * Dequeues entries into an array.
-     */
-    dump(max = Infinity) {
-        if (!this.count)
-            return [];
-        const result = [];
-        const root = this._root;
-        if (isFinite(max)) {
-            while (0 <= --max) {
-                const n = root.next;
-                if (!this._dequeueInternal(n))
-                    break;
-                result.push(n.value);
-            }
+        const _ = this;
+        if (super.tryDequeue(out)) {
+            if (_._size < _._array.length / 2)
+                _.trimExcess(SHRINK_THRESHOLD);
+            _.incrementVersion();
+            return true;
         }
-        else {
-            let n = root.next;
-            while (this._dequeueInternal(n)) {
-                result.push(n.value);
-                n = root.next;
-            }
-        }
-        this.incrementVersion();
-        return result;
+        return false;
     }
     /**
-     * Produces an iterable that dequeues items when iterated.  Stops when empty.
-     * @return {Iterable}
+     * Trims excess items in the underlying array.
+     * @param {number} threshold
      */
-    consumer() {
-        // eslint-disable-next-line @typescript-eslint/no-this-alias
-        const _ = this, root = this._root;
-        return {
-            *[Symbol.iterator]() {
-                while (true) {
-                    const n = root.next;
-                    if (!_._dequeueInternal(n))
-                        break;
-                    _.incrementVersion();
-                    yield n.value;
-                }
-            }
-        };
+    trimExcess(threshold) {
+        const _ = this;
+        const size = _._size;
+        if (size < Math.floor(_._array.length * 0.9) && (!threshold && threshold !== 0 || isNaN(threshold) || threshold < size))
+            _.setCapacity(size);
     }
-    /**
-     * Clears the list.
-     */
-    clear() {
-        const count = this._count;
-        this._root.next = undefined;
-        this._tail = undefined;
-        this._count = 0;
-        return count;
+    _enqueueInternal(item) {
+        const _ = this;
+        const size = _._size;
+        let len = _._array.length;
+        if (size === len) {
+            let newCapacity = len * 2;
+            if (newCapacity < len + MINIMUM_GROW)
+                newCapacity = len + MINIMUM_GROW;
+            _.setCapacity(newCapacity);
+            len = _._array.length;
+        }
+        const tail = _._tail % len;
+        _._array[tail] = item;
+        _._tail = (tail + 1) % len;
+        _._size = size + 1;
     }
-    /**
-     * Clears the list.
-     */
-    dispose() {
-        this.clear();
+    _dequeueInternal() {
+        if (!this._size)
+            return undefined;
+        const array = this._array, head = this._head;
+        const removed = array[head];
+        array[head] = undefined; // protect the data.
+        this._head = (head + 1) % array.length;
+        this._size--;
+        return removed;
     }
-    /**
-     * Clears the list.
-     */
-    recycle() {
-        this.clear();
+    _peekInternal() {
+        const _ = this;
+        return _._size ? _._array[_._head] : undefined;
     }
     *_getIterator() {
-        let current, next = this._root.next;
-        while (next) {
-            current = next;
-            next = current.next;
-            yield current.value;
-        }
+        const _ = this, size = _._size;
+        for (let i = 0; i < size; i++)
+            yield _._getElement(i);
     }
-    _enqueueInternal(value) {
-        const newTail = { value: value };
-        const tail = this._tail;
-        if (tail)
-            tail.next = newTail;
-        else
-            this._root.next = newTail;
-        this._tail = newTail;
-        this._count++;
+    _getElement(index) {
+        const _ = this, a = _._array;
+        return _._size ? a[(_._head + index) % a.length] : undefined;
     }
-    _dequeueInternal(n) {
-        if (!n)
-            return false;
-        this._root.next = n.next;
-        if (n.next)
-            n.next = undefined;
-        else
-            this._tail = undefined;
-        const count = this._count;
-        if (!count)
-            throw new Error('Dequeuing empty collection.');
-        this._count = count - 1;
-        return true;
-    }
 }
 exports.default = Queue;
 //# sourceMappingURL=Queue.js.map

package.json

 {
   "name": "@tsdotnet/queue",
-  "version": "1.1.5",
-  "description": "",
+  "version": "1.2.0",
+  "description": "A simple and fast FIFO collection for enqueuing and dequeuing items.",
   "author": "electricessence",
@@ -6,0 +6,0 @@ "license": "MIT",

README.md

@@ -8,6 +8,6 @@ # ![alt text](https://avatars1.githubusercontent.com/u/64487547?s=30 "tsdotnet") tsdotnet / queue
 
+A simple and fast FIFO collection for enqueuing and dequeuing items.
 
-
 ## Docs
 
-[tsdotnet.github.io/queue](https://tsdotnet.github.io/queue/)
+[tsdotnet.github.io/queue](https://tsdotnet.github.io/queue/classes/_queue_.queue.html)

New alerts

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

53068

increased by97.25%

Number of package files

18

increased by125%

Lines of code

959

increased by85.14%

Worsened metrics

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes