Commit | Line | Data |
---|---|---|
bcfb06ce JB |
1 | /** |
2 | * @internal | |
3 | */ | |
4 | interface PriorityQueueNode<T> { | |
5 | data: T | |
6 | priority: number | |
7 | } | |
8 | ||
9 | /** | |
10 | * Priority queue. | |
11 | * | |
12 | * @typeParam T - Type of priority queue data. | |
13 | * @internal | |
14 | */ | |
15 | export class PriorityQueue<T> { | |
16 | private nodeArray!: Array<PriorityQueueNode<T>> | |
17 | /** The size of the priority queue. */ | |
18 | public size!: number | |
19 | /** The maximum size of the priority queue. */ | |
20 | public maxSize!: number | |
21 | ||
22 | public constructor () { | |
23 | this.clear() | |
24 | } | |
25 | ||
26 | /** | |
27 | * Enqueue data into the priority queue. | |
28 | * | |
29 | * @param data - Data to enqueue. | |
30 | * @param priority - Priority of the data. Lower values have higher priority. | |
31 | * @returns The new size of the priority queue. | |
32 | */ | |
33 | public enqueue (data: T, priority?: number): number { | |
34 | priority = priority ?? 0 | |
35 | let inserted = false | |
36 | for (const [index, node] of this.nodeArray.entries()) { | |
37 | if (node.priority > priority) { | |
38 | this.nodeArray.splice(index, 0, { data, priority }) | |
39 | inserted = true | |
40 | break | |
41 | } | |
42 | } | |
43 | if (!inserted) { | |
44 | this.nodeArray.push({ data, priority }) | |
45 | } | |
46 | return this.incrementSize() | |
47 | } | |
48 | ||
49 | /** | |
50 | * Dequeue data from the priority queue. | |
51 | * | |
52 | * @returns The dequeued data or `undefined` if the priority queue is empty. | |
53 | */ | |
54 | public dequeue (): T | undefined { | |
55 | if (this.size > 0) { | |
56 | --this.size | |
57 | } | |
58 | return this.nodeArray.shift()?.data | |
59 | } | |
60 | ||
61 | /** | |
62 | * Peeks at the first data. | |
63 | * @returns The first data or `undefined` if the priority queue is empty. | |
64 | */ | |
65 | public peekFirst (): T | undefined { | |
66 | return this.nodeArray[0]?.data | |
67 | } | |
68 | ||
69 | /** | |
70 | * Peeks at the last data. | |
71 | * @returns The last data or `undefined` if the priority queue is empty. | |
72 | */ | |
73 | public peekLast (): T | undefined { | |
74 | return this.nodeArray[this.nodeArray.length - 1]?.data | |
75 | } | |
76 | ||
77 | /** | |
78 | * Clears the priority queue. | |
79 | */ | |
80 | public clear (): void { | |
81 | this.nodeArray = [] | |
82 | this.size = 0 | |
83 | this.maxSize = 0 | |
84 | } | |
85 | ||
86 | /** | |
87 | * Increments the size of the deque. | |
88 | * | |
89 | * @returns The new size of the deque. | |
90 | */ | |
91 | private incrementSize (): number { | |
92 | ++this.size | |
93 | if (this.size > this.maxSize) { | |
94 | this.maxSize = this.size | |
95 | } | |
96 | return this.size | |
97 | } | |
98 | } |