UNPKG

2.2 kBJavaScriptView Raw
1/*
2 MIT License http://www.opensource.org/licenses/mit-license.php
3 Author Tobias Koppers @sokra
4*/
5
6"use strict";
7
8/**
9 * @template T
10 */
11class ArrayQueue {
12 /**
13 * @param {Iterable<T>=} items The initial elements.
14 */
15 constructor(items) {
16 /** @private @type {T[]} */
17 this._list = items ? Array.from(items) : [];
18 /** @private @type {T[]} */
19 this._listReversed = [];
20 }
21
22 /**
23 * Returns the number of elements in this queue.
24 * @returns {number} The number of elements in this queue.
25 */
26 get length() {
27 return this._list.length + this._listReversed.length;
28 }
29
30 /**
31 * Empties the queue.
32 */
33 clear() {
34 this._list.length = 0;
35 this._listReversed.length = 0;
36 }
37
38 /**
39 * Appends the specified element to this queue.
40 * @param {T} item The element to add.
41 * @returns {void}
42 */
43 enqueue(item) {
44 this._list.push(item);
45 }
46
47 /**
48 * Retrieves and removes the head of this queue.
49 * @returns {T | undefined} The head of the queue of `undefined` if this queue is empty.
50 */
51 dequeue() {
52 if (this._listReversed.length === 0) {
53 if (this._list.length === 0) return undefined;
54 if (this._list.length === 1) return this._list.pop();
55 if (this._list.length < 16) return this._list.shift();
56 const temp = this._listReversed;
57 this._listReversed = this._list;
58 this._listReversed.reverse();
59 this._list = temp;
60 }
61 return this._listReversed.pop();
62 }
63
64 /**
65 * Finds and removes an item
66 * @param {T} item the item
67 * @returns {void}
68 */
69 delete(item) {
70 const i = this._list.indexOf(item);
71 if (i >= 0) {
72 this._list.splice(i, 1);
73 } else {
74 const i = this._listReversed.indexOf(item);
75 if (i >= 0) this._listReversed.splice(i, 1);
76 }
77 }
78
79 [Symbol.iterator]() {
80 let i = -1;
81 let reversed = false;
82 return {
83 next: () => {
84 if (!reversed) {
85 i++;
86 if (i < this._list.length) {
87 return {
88 done: false,
89 value: this._list[i]
90 };
91 }
92 reversed = true;
93 i = this._listReversed.length;
94 }
95 i--;
96 if (i < 0) {
97 return {
98 done: true,
99 value: undefined
100 };
101 }
102 return {
103 done: false,
104 value: this._listReversed[i]
105 };
106 }
107 };
108 }
109}
110
111module.exports = ArrayQueue;