build(deps-dev): apply updates
[poolifier.git] / src / fixed-priority-queue.ts
... / ...
CommitLineData
1/**
2 * Default buffer size.
3 */
4export const defaultQueueSize = 2048
5
6/**
7 * Fixed priority queue node.
8 * @typeParam T - Type of priority queue node data.
9 * @internal
10 */
11export interface FixedPriorityQueueNode<T> {
12 data: T
13 priority: number
14}
15
16/**
17 * Fixed priority queue.
18 * @typeParam T - Type of fixed priority queue data.
19 * @internal
20 */
21export class FixedPriorityQueue<T> {
22 private start!: number
23 private readonly nodeArray: FixedPriorityQueueNode<T>[]
24 /** The fixed priority queue capacity. */
25 public readonly capacity: number
26 /** The fixed priority queue size. */
27 public size!: number
28 /** Whether to enable priority. */
29 public enablePriority: boolean
30
31 /**
32 * Constructs a fixed priority queue.
33 * @param size - Fixed priority queue size. @defaultValue defaultQueueSize
34 * @param enablePriority - Whether to enable priority. @defaultValue false
35 * @returns FixedPriorityQueue.
36 */
37 constructor (size: number = defaultQueueSize, enablePriority = false) {
38 this.checkSize(size)
39 this.capacity = size
40 this.enablePriority = enablePriority
41 this.nodeArray = new Array<FixedPriorityQueueNode<T>>(this.capacity)
42 this.clear()
43 }
44
45 /**
46 * Checks if the fixed priority queue is empty.
47 * @returns `true` if the fixed priority queue is empty, `false` otherwise.
48 */
49 public empty (): boolean {
50 return this.size === 0
51 }
52
53 /**
54 * Checks if the fixed priority queue is full.
55 * @returns `true` if the fixed priority queue is full, `false` otherwise.
56 */
57 public full (): boolean {
58 return this.size === this.capacity
59 }
60
61 /**
62 * Enqueue data into the fixed priority queue.
63 * @param data - Data to enqueue.
64 * @param priority - Priority of the data. Lower values have higher priority.
65 * @returns The new size of the priority queue.
66 * @throws If the fixed priority queue is full.
67 */
68 public enqueue (data: T, priority?: number): number {
69 if (this.full()) {
70 throw new Error('Priority queue is full')
71 }
72 priority = priority ?? 0
73 let inserted = false
74 if (this.enablePriority) {
75 let index = this.start
76 for (let i = 0; i < this.size; i++) {
77 if (this.nodeArray[index].priority > priority) {
78 this.nodeArray.splice(index, 0, { data, priority })
79 this.nodeArray.length = this.capacity
80 inserted = true
81 break
82 }
83 ++index
84 if (index === this.capacity) {
85 index = 0
86 }
87 }
88 }
89 if (!inserted) {
90 let index = this.start + this.size
91 if (index >= this.capacity) {
92 index -= this.capacity
93 }
94 this.nodeArray[index] = { data, priority }
95 }
96 return ++this.size
97 }
98
99 /**
100 * Gets data from the fixed priority queue.
101 * @param index - The index of the data to get.
102 * @returns The data at the index or `undefined` if the fixed priority queue is empty or the index is out of bounds.
103 */
104 public get (index: number): T | undefined {
105 if (this.empty() || index >= this.size) {
106 return undefined
107 }
108 index += this.start
109 if (index >= this.capacity) {
110 index -= this.capacity
111 }
112 return this.nodeArray[index].data
113 }
114
115 /**
116 * Dequeue data from the fixed priority queue.
117 * @returns The dequeued data or `undefined` if the priority queue is empty.
118 */
119 public dequeue (): T | undefined {
120 if (this.empty()) {
121 return undefined
122 }
123 const index = this.start
124 --this.size
125 ++this.start
126 if (this.start === this.capacity) {
127 this.start = 0
128 }
129 return this.nodeArray[index].data
130 }
131
132 /**
133 * Clears the fixed priority queue.
134 */
135 public clear (): void {
136 this.start = 0
137 this.size = 0
138 }
139
140 /**
141 * Returns an iterator for the fixed priority queue.
142 * @returns An iterator for the fixed priority queue.
143 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
144 */
145 public [Symbol.iterator] (): Iterator<T> {
146 let index = this.start
147 let i = 0
148 return {
149 next: () => {
150 if (i >= this.size) {
151 return {
152 value: undefined,
153 done: true,
154 }
155 }
156 const value = this.nodeArray[index].data
157 ++index
158 ++i
159 if (index === this.capacity) {
160 index = 0
161 }
162 return {
163 value,
164 done: false,
165 }
166 },
167 }
168 }
169
170 /**
171 * Checks the queue size.
172 * @param size - Queue size.
173 */
174 private checkSize (size: number): void {
175 if (!Number.isSafeInteger(size)) {
176 throw new TypeError(
177 `Invalid fixed priority queue size: '${size.toString()}' is not an integer`
178 )
179 }
180 if (size < 0) {
181 throw new RangeError(
182 `Invalid fixed priority queue size: ${size.toString()} < 0`
183 )
184 }
185 }
186}