Commit | Line | Data |
---|---|---|
097dea68 | 1 | import { defaultQueueSize, type FixedQueueNode, type IFixedQueue } from './utility-types.js' |
f8d5d8fd | 2 | |
eadb37e2 JB |
3 | /** |
4 | * Fixed priority queue. | |
eadb37e2 JB |
5 | * @typeParam T - Type of fixed priority queue data. |
6 | * @internal | |
7 | */ | |
097dea68 | 8 | export class FixedPriorityQueue<T> implements IFixedQueue<T> { |
f8d5d8fd | 9 | private start!: number |
097dea68 | 10 | /** @inheritdoc */ |
9df282a0 | 11 | public readonly capacity: number |
097dea68 | 12 | /** @inheritdoc */ |
f8d5d8fd | 13 | public size!: number |
097dea68 JB |
14 | /** @inheritdoc */ |
15 | public nodeArray: FixedQueueNode<T>[] | |
f8d5d8fd | 16 | |
9df282a0 JB |
17 | /** |
18 | * Constructs a fixed priority queue. | |
9df282a0 JB |
19 | * @param size - Fixed priority queue size. @defaultValue defaultQueueSize |
20 | * @returns FixedPriorityQueue. | |
21 | */ | |
097dea68 | 22 | constructor (size: number = defaultQueueSize) { |
f8d5d8fd | 23 | this.checkSize(size) |
9df282a0 | 24 | this.capacity = size |
097dea68 | 25 | this.nodeArray = new Array<FixedQueueNode<T>>(this.capacity) |
f8d5d8fd JB |
26 | this.clear() |
27 | } | |
28 | ||
097dea68 | 29 | /** @inheritdoc */ |
f8d5d8fd JB |
30 | public empty (): boolean { |
31 | return this.size === 0 | |
32 | } | |
33 | ||
097dea68 | 34 | /** @inheritdoc */ |
f8d5d8fd | 35 | public full (): boolean { |
9df282a0 | 36 | return this.size === this.capacity |
f8d5d8fd JB |
37 | } |
38 | ||
097dea68 | 39 | /** @inheritdoc */ |
f8d5d8fd JB |
40 | public enqueue (data: T, priority?: number): number { |
41 | if (this.full()) { | |
42 | throw new Error('Priority queue is full') | |
43 | } | |
44 | priority = priority ?? 0 | |
45 | let inserted = false | |
097dea68 JB |
46 | let index = this.start |
47 | for (let i = 0; i < this.size; i++) { | |
48 | if (this.nodeArray[index].priority > priority) { | |
49 | this.nodeArray.splice(index, 0, { data, priority }) | |
50 | this.nodeArray.length = this.capacity | |
51 | inserted = true | |
52 | break | |
53 | } | |
54 | ++index | |
55 | if (index === this.capacity) { | |
56 | index = 0 | |
3451940f | 57 | } |
f8d5d8fd JB |
58 | } |
59 | if (!inserted) { | |
60 | let index = this.start + this.size | |
9df282a0 JB |
61 | if (index >= this.capacity) { |
62 | index -= this.capacity | |
f8d5d8fd JB |
63 | } |
64 | this.nodeArray[index] = { data, priority } | |
65 | } | |
10b1b252 | 66 | return ++this.size |
f8d5d8fd JB |
67 | } |
68 | ||
097dea68 | 69 | /** @inheritdoc */ |
1d98bad2 JB |
70 | public get (index: number): T | undefined { |
71 | if (this.empty() || index >= this.size) { | |
72 | return undefined | |
73 | } | |
74 | index += this.start | |
75 | if (index >= this.capacity) { | |
76 | index -= this.capacity | |
77 | } | |
78 | return this.nodeArray[index].data | |
79 | } | |
80 | ||
097dea68 | 81 | /** @inheritdoc */ |
f8d5d8fd JB |
82 | public dequeue (): T | undefined { |
83 | if (this.empty()) { | |
84 | return undefined | |
85 | } | |
86 | const index = this.start | |
87 | --this.size | |
88 | ++this.start | |
9df282a0 | 89 | if (this.start === this.capacity) { |
f8d5d8fd JB |
90 | this.start = 0 |
91 | } | |
92 | return this.nodeArray[index].data | |
93 | } | |
94 | ||
097dea68 | 95 | /** @inheritdoc */ |
f8d5d8fd JB |
96 | public clear (): void { |
97 | this.start = 0 | |
98 | this.size = 0 | |
f8d5d8fd JB |
99 | } |
100 | ||
097dea68 | 101 | /** @inheritdoc */ |
9df282a0 | 102 | public [Symbol.iterator] (): Iterator<T> { |
3451940f JB |
103 | let index = this.start |
104 | let i = 0 | |
f8d5d8fd JB |
105 | return { |
106 | next: () => { | |
107 | if (i >= this.size) { | |
108 | return { | |
109 | value: undefined, | |
3a502712 | 110 | done: true, |
f8d5d8fd JB |
111 | } |
112 | } | |
3451940f | 113 | const value = this.nodeArray[index].data |
02c769d0 JB |
114 | ++index |
115 | ++i | |
9df282a0 | 116 | if (index === this.capacity) { |
3451940f JB |
117 | index = 0 |
118 | } | |
f8d5d8fd JB |
119 | return { |
120 | value, | |
3a502712 | 121 | done: false, |
f8d5d8fd | 122 | } |
3a502712 | 123 | }, |
f8d5d8fd JB |
124 | } |
125 | } | |
126 | ||
e75373e6 | 127 | /** |
097dea68 | 128 | * Checks the fixed queue size. |
fcfc3353 | 129 | * @param size - Queue size. |
e75373e6 | 130 | */ |
f8d5d8fd JB |
131 | private checkSize (size: number): void { |
132 | if (!Number.isSafeInteger(size)) { | |
133 | throw new TypeError( | |
6e5d7052 | 134 | `Invalid fixed priority queue size: '${size.toString()}' is not an integer` |
f8d5d8fd JB |
135 | ) |
136 | } | |
137 | if (size < 0) { | |
6e5d7052 JB |
138 | throw new RangeError( |
139 | `Invalid fixed priority queue size: ${size.toString()} < 0` | |
140 | ) | |
f8d5d8fd JB |
141 | } |
142 | } | |
143 | } |