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