diff options
Diffstat (limited to 'node_modules/denque')
| -rw-r--r-- | node_modules/denque/CHANGELOG.md | 22 | ||||
| -rw-r--r-- | node_modules/denque/LICENSE | 201 | ||||
| -rw-r--r-- | node_modules/denque/README.md | 77 | ||||
| -rw-r--r-- | node_modules/denque/index.d.ts | 47 | ||||
| -rw-r--r-- | node_modules/denque/index.js | 443 | ||||
| -rw-r--r-- | node_modules/denque/package.json | 55 |
6 files changed, 845 insertions, 0 deletions
diff --git a/node_modules/denque/CHANGELOG.md b/node_modules/denque/CHANGELOG.md new file mode 100644 index 0000000..0577ebc --- /dev/null +++ b/node_modules/denque/CHANGELOG.md @@ -0,0 +1,22 @@ +## 2.0.1 + + - fix(types): incorrect return type on `size()` + +## 2.0.0 + + - fix!: `push` & `unshift` now accept `undefined` values to match behaviour of `Array` (fixes #25) (#35) + - This is only a **BREAKING** change if you are currently expecting `push(undefined)` and `unshift(undefined)` to do + nothing - the new behaviour now correctly adds undefined values to the queue. + - **Note**: behaviour of `push()` & `unshift()` (no arguments) remains unchanged (nothing gets added to the queue). + - **Note**: If you need to differentiate between `undefined` values in the queue and the return value of `pop()` then + check the queue `.length` before popping. + - fix: incorrect methods in types definition file + +## 1.5.1 + + - perf: minor performance tweak when growing queue size (#29) + +## 1.5.0 + + - feat: adds capacity option for circular buffers (#27) + diff --git a/node_modules/denque/LICENSE b/node_modules/denque/LICENSE new file mode 100644 index 0000000..c9cde92 --- /dev/null +++ b/node_modules/denque/LICENSE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright 2018-present Invertase Limited + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. diff --git a/node_modules/denque/README.md b/node_modules/denque/README.md new file mode 100644 index 0000000..3c645d3 --- /dev/null +++ b/node_modules/denque/README.md @@ -0,0 +1,77 @@ +<p align="center"> + <h1 align="center">Denque</h1> +</p> + +<p align="center"> + <a href="https://www.npmjs.com/package/denque"><img src="https://img.shields.io/npm/dm/denque.svg?style=flat-square" alt="NPM downloads"></a> + <a href="https://www.npmjs.com/package/denque"><img src="https://img.shields.io/npm/v/denque.svg?style=flat-square" alt="NPM version"></a> + <a href="https://github.com/invertase/denque/actions/workflows/testing.yam"><img src="https://github.com/invertase/denque/actions/workflows/testing.yaml/badge.svg" alt="Tests status"></a> + <a href="https://codecov.io/gh/invertase/denque"><img src="https://codecov.io/gh/invertase/denque/branch/master/graph/badge.svg?token=rn91iI4bSe" alt="Coverage"></a> + <a href="/LICENSE"><img src="https://img.shields.io/npm/l/denque.svg?style=flat-square" alt="License"></a> + <a href="https://twitter.com/invertaseio"><img src="https://img.shields.io/twitter/follow/invertaseio.svg?style=social&label=Follow" alt="Follow on Twitter"></a> +</p> + +Denque is a well tested, extremely fast and lightweight [double-ended queue](http://en.wikipedia.org/wiki/Double-ended_queue) +implementation with zero dependencies and includes TypeScript types. + +Double-ended queues can also be used as a: + +- [Stack](http://en.wikipedia.org/wiki/Stack_\(abstract_data_type\)) +- [Queue](http://en.wikipedia.org/wiki/Queue_\(data_structure\)) + +This implementation is currently the fastest available, even faster than `double-ended-queue`, see the [benchmarks](https://docs.page/invertase/denque/benchmarks). + +Every queue operation is done at a constant `O(1)` - including random access from `.peekAt(index)`. + +**Works on all node versions >= v0.10** + +## Quick Start + +Install the package: + +```bash +npm install denque +``` + +Create and consume a queue: + +```js +const Denque = require("denque"); + +const denque = new Denque([1,2,3,4]); +denque.shift(); // 1 +denque.pop(); // 4 +``` + + +See the [API reference documentation](https://docs.page/invertase/denque/api) for more examples. + +--- + +## Who's using it? + +- [Kafka Node.js client](https://www.npmjs.com/package/kafka-node) +- [MariaDB Node.js client](https://www.npmjs.com/package/mariadb) +- [MongoDB Node.js client](https://www.npmjs.com/package/mongodb) +- [MySQL Node.js client](https://www.npmjs.com/package/mysql2) +- [Redis Node.js clients](https://www.npmjs.com/package/redis) + +... and [many more](https://www.npmjs.com/browse/depended/denque). + + +--- + +## License + +- See [LICENSE](/LICENSE) + +--- + +<p align="center"> + <a href="https://invertase.io/?utm_source=readme&utm_medium=footer&utm_campaign=denque"> + <img width="75px" src="https://static.invertase.io/assets/invertase/invertase-rounded-avatar.png"> + </a> + <p align="center"> + Built and maintained by <a href="https://invertase.io/?utm_source=readme&utm_medium=footer&utm_campaign=denque">Invertase</a>. + </p> +</p> diff --git a/node_modules/denque/index.d.ts b/node_modules/denque/index.d.ts new file mode 100644 index 0000000..e125dd4 --- /dev/null +++ b/node_modules/denque/index.d.ts @@ -0,0 +1,47 @@ +declare class Denque<T = any> { + length: number; + + constructor(); + + constructor(array: T[]); + + constructor(array: T[], options: IDenqueOptions); + + push(item: T): number; + + unshift(item: T): number; + + pop(): T | undefined; + + shift(): T | undefined; + + peekBack(): T | undefined; + + peekFront(): T | undefined; + + peekAt(index: number): T | undefined; + + get(index: number): T | undefined; + + remove(index: number, count: number): T[]; + + removeOne(index: number): T | undefined; + + splice(index: number, count: number, ...item: T[]): T[] | undefined; + + isEmpty(): boolean; + + clear(): void; + + size(): number; + + toString(): string; + + toArray(): T[]; +} + +interface IDenqueOptions { + capacity?: number +} + +export = Denque; diff --git a/node_modules/denque/index.js b/node_modules/denque/index.js new file mode 100644 index 0000000..0e03764 --- /dev/null +++ b/node_modules/denque/index.js @@ -0,0 +1,443 @@ +'use strict'; + +/** + * Custom implementation of a double ended queue. + */ +function Denque(array, options) { + var options = options || {}; + + this._head = 0; + this._tail = 0; + this._capacity = options.capacity; + this._capacityMask = 0x3; + this._list = new Array(4); + if (Array.isArray(array)) { + this._fromArray(array); + } +} + +/** + * -------------- + * PUBLIC API + * ------------- + */ + +/** + * Returns the item at the specified index from the list. + * 0 is the first element, 1 is the second, and so on... + * Elements at negative values are that many from the end: -1 is one before the end + * (the last element), -2 is two before the end (one before last), etc. + * @param index + * @returns {*} + */ +Denque.prototype.peekAt = function peekAt(index) { + var i = index; + // expect a number or return undefined + if ((i !== (i | 0))) { + return void 0; + } + var len = this.size(); + if (i >= len || i < -len) return undefined; + if (i < 0) i += len; + i = (this._head + i) & this._capacityMask; + return this._list[i]; +}; + +/** + * Alias for peekAt() + * @param i + * @returns {*} + */ +Denque.prototype.get = function get(i) { + return this.peekAt(i); +}; + +/** + * Returns the first item in the list without removing it. + * @returns {*} + */ +Denque.prototype.peek = function peek() { + if (this._head === this._tail) return undefined; + return this._list[this._head]; +}; + +/** + * Alias for peek() + * @returns {*} + */ +Denque.prototype.peekFront = function peekFront() { + return this.peek(); +}; + +/** + * Returns the item that is at the back of the queue without removing it. + * Uses peekAt(-1) + */ +Denque.prototype.peekBack = function peekBack() { + return this.peekAt(-1); +}; + +/** + * Returns the current length of the queue + * @return {Number} + */ +Object.defineProperty(Denque.prototype, 'length', { + get: function length() { + return this.size(); + } +}); + +/** + * Return the number of items on the list, or 0 if empty. + * @returns {number} + */ +Denque.prototype.size = function size() { + if (this._head === this._tail) return 0; + if (this._head < this._tail) return this._tail - this._head; + else return this._capacityMask + 1 - (this._head - this._tail); +}; + +/** + * Add an item at the beginning of the list. + * @param item + */ +Denque.prototype.unshift = function unshift(item) { + if (arguments.length === 0) return this.size(); + var len = this._list.length; + this._head = (this._head - 1 + len) & this._capacityMask; + this._list[this._head] = item; + if (this._tail === this._head) this._growArray(); + if (this._capacity && this.size() > this._capacity) this.pop(); + if (this._head < this._tail) return this._tail - this._head; + else return this._capacityMask + 1 - (this._head - this._tail); +}; + +/** + * Remove and return the first item on the list, + * Returns undefined if the list is empty. + * @returns {*} + */ +Denque.prototype.shift = function shift() { + var head = this._head; + if (head === this._tail) return undefined; + var item = this._list[head]; + this._list[head] = undefined; + this._head = (head + 1) & this._capacityMask; + if (head < 2 && this._tail > 10000 && this._tail <= this._list.length >>> 2) this._shrinkArray(); + return item; +}; + +/** + * Add an item to the bottom of the list. + * @param item + */ +Denque.prototype.push = function push(item) { + if (arguments.length === 0) return this.size(); + var tail = this._tail; + this._list[tail] = item; + this._tail = (tail + 1) & this._capacityMask; + if (this._tail === this._head) { + this._growArray(); + } + if (this._capacity && this.size() > this._capacity) { + this.shift(); + } + if (this._head < this._tail) return this._tail - this._head; + else return this._capacityMask + 1 - (this._head - this._tail); +}; + +/** + * Remove and return the last item on the list. + * Returns undefined if the list is empty. + * @returns {*} + */ +Denque.prototype.pop = function pop() { + var tail = this._tail; + if (tail === this._head) return undefined; + var len = this._list.length; + this._tail = (tail - 1 + len) & this._capacityMask; + var item = this._list[this._tail]; + this._list[this._tail] = undefined; + if (this._head < 2 && tail > 10000 && tail <= len >>> 2) this._shrinkArray(); + return item; +}; + +/** + * Remove and return the item at the specified index from the list. + * Returns undefined if the list is empty. + * @param index + * @returns {*} + */ +Denque.prototype.removeOne = function removeOne(index) { + var i = index; + // expect a number or return undefined + if ((i !== (i | 0))) { + return void 0; + } + if (this._head === this._tail) return void 0; + var size = this.size(); + var len = this._list.length; + if (i >= size || i < -size) return void 0; + if (i < 0) i += size; + i = (this._head + i) & this._capacityMask; + var item = this._list[i]; + var k; + if (index < size / 2) { + for (k = index; k > 0; k--) { + this._list[i] = this._list[i = (i - 1 + len) & this._capacityMask]; + } + this._list[i] = void 0; + this._head = (this._head + 1 + len) & this._capacityMask; + } else { + for (k = size - 1 - index; k > 0; k--) { + this._list[i] = this._list[i = (i + 1 + len) & this._capacityMask]; + } + this._list[i] = void 0; + this._tail = (this._tail - 1 + len) & this._capacityMask; + } + return item; +}; + +/** + * Remove number of items from the specified index from the list. + * Returns array of removed items. + * Returns undefined if the list is empty. + * @param index + * @param count + * @returns {array} + */ +Denque.prototype.remove = function remove(index, count) { + var i = index; + var removed; + var del_count = count; + // expect a number or return undefined + if ((i !== (i | 0))) { + return void 0; + } + if (this._head === this._tail) return void 0; + var size = this.size(); + var len = this._list.length; + if (i >= size || i < -size || count < 1) return void 0; + if (i < 0) i += size; + if (count === 1 || !count) { + removed = new Array(1); + removed[0] = this.removeOne(i); + return removed; + } + if (i === 0 && i + count >= size) { + removed = this.toArray(); + this.clear(); + return removed; + } + if (i + count > size) count = size - i; + var k; + removed = new Array(count); + for (k = 0; k < count; k++) { + removed[k] = this._list[(this._head + i + k) & this._capacityMask]; + } + i = (this._head + i) & this._capacityMask; + if (index + count === size) { + this._tail = (this._tail - count + len) & this._capacityMask; + for (k = count; k > 0; k--) { + this._list[i = (i + 1 + len) & this._capacityMask] = void 0; + } + return removed; + } + if (index === 0) { + this._head = (this._head + count + len) & this._capacityMask; + for (k = count - 1; k > 0; k--) { + this._list[i = (i + 1 + len) & this._capacityMask] = void 0; + } + return removed; + } + if (i < size / 2) { + this._head = (this._head + index + count + len) & this._capacityMask; + for (k = index; k > 0; k--) { + this.unshift(this._list[i = (i - 1 + len) & this._capacityMask]); + } + i = (this._head - 1 + len) & this._capacityMask; + while (del_count > 0) { + this._list[i = (i - 1 + len) & this._capacityMask] = void 0; + del_count--; + } + if (index < 0) this._tail = i; + } else { + this._tail = i; + i = (i + count + len) & this._capacityMask; + for (k = size - (count + index); k > 0; k--) { + this.push(this._list[i++]); + } + i = this._tail; + while (del_count > 0) { + this._list[i = (i + 1 + len) & this._capacityMask] = void 0; + del_count--; + } + } + if (this._head < 2 && this._tail > 10000 && this._tail <= len >>> 2) this._shrinkArray(); + return removed; +}; + +/** + * Native splice implementation. + * Remove number of items from the specified index from the list and/or add new elements. + * Returns array of removed items or empty array if count == 0. + * Returns undefined if the list is empty. + * + * @param index + * @param count + * @param {...*} [elements] + * @returns {array} + */ +Denque.prototype.splice = function splice(index, count) { + var i = index; + // expect a number or return undefined + if ((i !== (i | 0))) { + return void 0; + } + var size = this.size(); + if (i < 0) i += size; + if (i > size) return void 0; + if (arguments.length > 2) { + var k; + var temp; + var removed; + var arg_len = arguments.length; + var len = this._list.length; + var arguments_index = 2; + if (!size || i < size / 2) { + temp = new Array(i); + for (k = 0; k < i; k++) { + temp[k] = this._list[(this._head + k) & this._capacityMask]; + } + if (count === 0) { + removed = []; + if (i > 0) { + this._head = (this._head + i + len) & this._capacityMask; + } + } else { + removed = this.remove(i, count); + this._head = (this._head + i + len) & this._capacityMask; + } + while (arg_len > arguments_index) { + this.unshift(arguments[--arg_len]); + } + for (k = i; k > 0; k--) { + this.unshift(temp[k - 1]); + } + } else { + temp = new Array(size - (i + count)); + var leng = temp.length; + for (k = 0; k < leng; k++) { + temp[k] = this._list[(this._head + i + count + k) & this._capacityMask]; + } + if (count === 0) { + removed = []; + if (i != size) { + this._tail = (this._head + i + len) & this._capacityMask; + } + } else { + removed = this.remove(i, count); + this._tail = (this._tail - leng + len) & this._capacityMask; + } + while (arguments_index < arg_len) { + this.push(arguments[arguments_index++]); + } + for (k = 0; k < leng; k++) { + this.push(temp[k]); + } + } + return removed; + } else { + return this.remove(i, count); + } +}; + +/** + * Soft clear - does not reset capacity. + */ +Denque.prototype.clear = function clear() { + this._head = 0; + this._tail = 0; +}; + +/** + * Returns true or false whether the list is empty. + * @returns {boolean} + */ +Denque.prototype.isEmpty = function isEmpty() { + return this._head === this._tail; +}; + +/** + * Returns an array of all queue items. + * @returns {Array} + */ +Denque.prototype.toArray = function toArray() { + return this._copyArray(false); +}; + +/** + * ------------- + * INTERNALS + * ------------- + */ + +/** + * Fills the queue with items from an array + * For use in the constructor + * @param array + * @private + */ +Denque.prototype._fromArray = function _fromArray(array) { + for (var i = 0; i < array.length; i++) this.push(array[i]); +}; + +/** + * + * @param fullCopy + * @returns {Array} + * @private + */ +Denque.prototype._copyArray = function _copyArray(fullCopy) { + var newArray = []; + var list = this._list; + var len = list.length; + var i; + if (fullCopy || this._head > this._tail) { + for (i = this._head; i < len; i++) newArray.push(list[i]); + for (i = 0; i < this._tail; i++) newArray.push(list[i]); + } else { + for (i = this._head; i < this._tail; i++) newArray.push(list[i]); + } + return newArray; +}; + +/** + * Grows the internal list array. + * @private + */ +Denque.prototype._growArray = function _growArray() { + if (this._head) { + // copy existing data, head to end, then beginning to tail. + this._list = this._copyArray(true); + this._head = 0; + } + + // head is at 0 and array is now full, safe to extend + this._tail = this._list.length; + + this._list.length <<= 1; + this._capacityMask = (this._capacityMask << 1) | 1; +}; + +/** + * Shrinks the internal list array. + * @private + */ +Denque.prototype._shrinkArray = function _shrinkArray() { + this._list.length >>>= 1; + this._capacityMask >>>= 1; +}; + + +module.exports = Denque; diff --git a/node_modules/denque/package.json b/node_modules/denque/package.json new file mode 100644 index 0000000..f1a0fcc --- /dev/null +++ b/node_modules/denque/package.json @@ -0,0 +1,55 @@ +{ + "name": "denque", + "version": "2.0.1", + "description": "The fastest javascript implementation of a double-ended queue. Used by the official Redis, MongoDB, MariaDB & MySQL libraries for Node.js and many other libraries. Maintains compatability with deque.", + "main": "index.js", + "engines": { + "node": ">=0.10" + }, + "keywords": [ + "data-structure", + "data-structures", + "queue", + "double", + "end", + "ended", + "deque", + "denque", + "double-ended-queue" + ], + "scripts": { + "test": "istanbul cover --report lcov _mocha && npm run typescript", + "coveralls": "cat ./coverage/lcov.info | coveralls", + "typescript": "tsc --project ./test/type/tsconfig.json", + "benchmark_thousand": "node benchmark/thousand", + "benchmark_2mil": "node benchmark/two_million", + "benchmark_splice": "node benchmark/splice", + "benchmark_remove": "node benchmark/remove", + "benchmark_removeOne": "node benchmark/removeOne" + }, + "repository": { + "type": "git", + "url": "git+https://github.com/invertase/denque.git" + }, + "license": "Apache-2.0", + "author": { + "name": "Invertase", + "email": "oss@invertase.io", + "url": "http://github.com/invertase/" + }, + "contributors": [ + "Mike Diarmid (Salakar) <mike@invertase.io>" + ], + "bugs": { + "url": "https://github.com/invertase/denque/issues" + }, + "homepage": "https://docs.page/invertase/denque", + "devDependencies": { + "benchmark": "^2.1.4", + "codecov": "^3.8.3", + "double-ended-queue": "^2.1.0-0", + "istanbul": "^0.4.5", + "mocha": "^3.5.3", + "typescript": "^3.4.1" + } +} |