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