repositories
/
poolifier.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
fix: fix task dequeuing from the last bucket
[poolifier.git]
/
src
/
fixed-priority-queue.ts
diff --git
a/src/fixed-priority-queue.ts
b/src/fixed-priority-queue.ts
index 78ba2aff39d0b9604b990b85627847c986b75ad5..2424b652033d42ee2dad7538a09b64621b60a4ae 100644
(file)
--- a/
src/fixed-priority-queue.ts
+++ b/
src/fixed-priority-queue.ts
@@
-9,7
+9,7
@@
export const defaultQueueSize = 2048
* @typeParam T - Type of priority queue node data.
* @internal
*/
* @typeParam T - Type of priority queue node data.
* @internal
*/
-
export
interface PriorityQueueNode<T> {
+interface PriorityQueueNode<T> {
data: T
priority: number
}
data: T
priority: number
}
@@
-23,29
+23,53
@@
export interface PriorityQueueNode<T> {
export class FixedPriorityQueue<T> {
private start!: number
private readonly nodeArray: Array<PriorityQueueNode<T>>
export class FixedPriorityQueue<T> {
private start!: number
private readonly nodeArray: Array<PriorityQueueNode<T>>
+ public readonly capacity: number
public size!: number
public maxSize!: number
public size!: number
public maxSize!: number
+ /**
+ * Constructs a fixed priority queue.
+ *
+ * @param size - Fixed priority queue size. @defaultValue defaultQueueSize
+ * @returns FixedPriorityQueue.
+ */
constructor (size: number = defaultQueueSize) {
this.checkSize(size)
constructor (size: number = defaultQueueSize) {
this.checkSize(size)
- this.nodeArray = new Array<PriorityQueueNode<T>>(size)
+ this.capacity = size
+ this.nodeArray = new Array<PriorityQueueNode<T>>(this.capacity)
this.clear()
}
this.clear()
}
+ /**
+ * Checks if the fixed priority queue is empty.
+ *
+ * @returns `true` if the fixed priority queue is empty, `false` otherwise.
+ */
public empty (): boolean {
return this.size === 0
}
public empty (): boolean {
return this.size === 0
}
+ /**
+ * Checks if the fixed priority queue is full.
+ *
+ * @returns `true` if the fixed priority queue is full, `false` otherwise.
+ */
public full (): boolean {
public full (): boolean {
- return this.size === this.
nodeArray.length
+ return this.size === this.
capacity
}
}
+ /**
+ * Enqueue data into the fixed priority queue.
+ *
+ * @param data - Data to enqueue.
+ * @param priority - Priority of the data. Lower values have higher priority.
+ * @returns The new size of the priority queue.
+ */
public enqueue (data: T, priority?: number): number {
if (this.full()) {
throw new Error('Priority queue is full')
}
priority = priority ?? 0
public enqueue (data: T, priority?: number): number {
if (this.full()) {
throw new Error('Priority queue is full')
}
priority = priority ?? 0
- const nodeArrayLength = this.nodeArray.length
let index = this.start
let inserted = false
for (let i = 0; i < this.size; i++) {
let index = this.start
let inserted = false
for (let i = 0; i < this.size; i++) {
@@
-55,22
+79,27
@@
export class FixedPriorityQueue<T> {
break
}
++index
break
}
++index
- if (index ===
nodeArrayLength
) {
+ if (index ===
this.capacity
) {
index = 0
}
}
index = 0
}
}
- this.nodeArray.length !==
nodeArrayLength
&&
- (this.nodeArray.length =
nodeArrayLength
)
+ this.nodeArray.length !==
this.capacity
&&
+ (this.nodeArray.length =
this.capacity
)
if (!inserted) {
let index = this.start + this.size
if (!inserted) {
let index = this.start + this.size
- if (index >=
nodeArrayLength
) {
- index -=
nodeArrayLength
+ if (index >=
this.capacity
) {
+ index -=
this.capacity
}
this.nodeArray[index] = { data, priority }
}
return this.incrementSize()
}
}
this.nodeArray[index] = { data, priority }
}
return this.incrementSize()
}
+ /**
+ * Dequeue data from the fixed priority queue.
+ *
+ * @returns The dequeued data or `undefined` if the priority queue is empty.
+ */
public dequeue (): T | undefined {
if (this.empty()) {
return undefined
public dequeue (): T | undefined {
if (this.empty()) {
return undefined
@@
-78,7
+107,7
@@
export class FixedPriorityQueue<T> {
const index = this.start
--this.size
++this.start
const index = this.start
--this.size
++this.start
- if (this.start === this.
nodeArray.length
) {
+ if (this.start === this.
capacity
) {
this.start = 0
}
return this.nodeArray[index].data
this.start = 0
}
return this.nodeArray[index].data
@@
-99,7
+128,7
@@
export class FixedPriorityQueue<T> {
* @returns An iterator for the fixed priority queue.
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
*/
* @returns An iterator for the fixed priority queue.
* @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
*/
- [Symbol.iterator] (): Iterator<T> {
+
public
[Symbol.iterator] (): Iterator<T> {
let index = this.start
let i = 0
return {
let index = this.start
let i = 0
return {
@@
-113,7
+142,7
@@
export class FixedPriorityQueue<T> {
const value = this.nodeArray[index].data
++index
++i
const value = this.nodeArray[index].data
++index
++i
- if (index === this.
nodeArray.length
) {
+ if (index === this.
capacity
) {
index = 0
}
return {
index = 0
}
return {
@@
-137,6
+166,11
@@
export class FixedPriorityQueue<T> {
return this.size
}
return this.size
}
+ /**
+ * Checks the size.
+ *
+ * @param size - The size to check.
+ */
private checkSize (size: number): void {
if (!Number.isSafeInteger(size)) {
throw new TypeError(
private checkSize (size: number): void {
if (!Number.isSafeInteger(size)) {
throw new TypeError(