Commit | Line | Data |
---|---|---|
f8d5d8fd JB |
1 | /** |
2 | * Default buffer size. | |
3 | */ | |
4 | export const defaultQueueSize = 2048 | |
5 | ||
6 | /** | |
7 | * Priority queue node. | |
8 | * | |
9 | * @typeParam T - Type of priority queue node data. | |
10 | * @internal | |
11 | */ | |
12 | export interface PriorityQueueNode<T> { | |
13 | data: T | |
14 | priority: number | |
15 | } | |
16 | ||
17 | export class FixedPriorityQueue<T> { | |
18 | private start!: number | |
19 | private readonly nodeArray: Array<PriorityQueueNode<T>> | |
20 | public size!: number | |
21 | public maxSize!: number | |
22 | ||
23 | constructor (size: number = defaultQueueSize) { | |
24 | this.checkSize(size) | |
25 | this.nodeArray = new Array<PriorityQueueNode<T>>(size) | |
26 | this.clear() | |
27 | } | |
28 | ||
29 | public empty (): boolean { | |
30 | return this.size === 0 | |
31 | } | |
32 | ||
33 | public full (): boolean { | |
34 | return this.size === this.nodeArray.length | |
35 | } | |
36 | ||
37 | public enqueue (data: T, priority?: number): number { | |
38 | if (this.full()) { | |
39 | throw new Error('Priority queue is full') | |
40 | } | |
41 | priority = priority ?? 0 | |
42 | let inserted = false | |
43 | for (let index = this.start; index < this.nodeArray.length; index++) { | |
44 | if (this.nodeArray[index]?.priority > priority) { | |
45 | this.nodeArray.splice(index, 0, { data, priority }) | |
46 | inserted = true | |
47 | break | |
48 | } | |
49 | } | |
50 | if (!inserted) { | |
51 | let index = this.start + this.size | |
52 | if (index >= this.nodeArray.length) { | |
53 | index -= this.nodeArray.length | |
54 | } | |
55 | this.nodeArray[index] = { data, priority } | |
56 | } | |
57 | return this.incrementSize() | |
58 | } | |
59 | ||
60 | public dequeue (): T | undefined { | |
61 | if (this.empty()) { | |
62 | return undefined | |
63 | } | |
64 | const index = this.start | |
65 | --this.size | |
66 | ++this.start | |
67 | if (this.start === this.nodeArray.length) { | |
68 | this.start = 0 | |
69 | } | |
70 | return this.nodeArray[index].data | |
71 | } | |
72 | ||
73 | /** | |
74 | * Clears the fixed priority queue. | |
75 | */ | |
76 | public clear (): void { | |
77 | this.start = 0 | |
78 | this.size = 0 | |
79 | this.maxSize = 0 | |
80 | } | |
81 | ||
82 | /** | |
83 | * Returns an iterator for the fixed priority queue. | |
84 | * | |
85 | * @returns An iterator for the fixed priority queue. | |
86 | * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols | |
87 | */ | |
88 | [Symbol.iterator] (): Iterator<T> { | |
89 | let i = this.start | |
90 | return { | |
91 | next: () => { | |
92 | if (i >= this.size) { | |
93 | return { | |
94 | value: undefined, | |
95 | done: true | |
96 | } | |
97 | } | |
98 | const value = this.nodeArray[i].data | |
99 | i++ | |
100 | return { | |
101 | value, | |
102 | done: false | |
103 | } | |
104 | } | |
105 | } | |
106 | } | |
107 | ||
108 | /** | |
109 | * Increments the size of the fixed priority queue. | |
110 | * | |
111 | * @returns The new size of the fixed priority queue. | |
112 | */ | |
113 | private incrementSize (): number { | |
114 | ++this.size | |
115 | if (this.size > this.maxSize) { | |
116 | this.maxSize = this.size | |
117 | } | |
118 | return this.size | |
119 | } | |
120 | ||
121 | private checkSize (size: number): void { | |
122 | if (!Number.isSafeInteger(size)) { | |
123 | throw new TypeError( | |
124 | `Invalid fixed priority queue size: ${size} is not an integer` | |
125 | ) | |
126 | } | |
127 | if (size < 0) { | |
128 | throw new RangeError(`Invalid fixed priority queue size: ${size} < 0`) | |
129 | } | |
130 | } | |
131 | } |