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