init

马宇豪

2024-07-16 f591c27b57e2418c9495bc02ae8cfff84d35bc18

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;