test: add priority queue test suite

Signed-off-by: Jérôme Benoit <jerome.benoit@piment-noir.org>

diff --git a/src/circular-array.ts b/src/circular-array.ts
index 511b699c8827a2a214efe63e2fce9dfabfcee73a..2347327927d96f46063bb3f17d8e9060173a722c 100644 (file)
--- a/src/circular-array.ts
+++ b/src/circular-array.ts
@@ -1,6 +1,6 @@
 // Copyright Jerome Benoit. 2021-2024. All Rights Reserved.
 
-export const DEFAULT_CIRCULAR_ARRAY_SIZE = 1024
+export const DEFAULT_CIRCULAR_ARRAY_SIZE = 385
 
 /**
  * Array with a maximum length and shifting items when full.

diff --git a/src/index.ts b/src/index.ts
index a4482d58bb34e880291dede0cbe6e7d86b36e820..1d778513d8030595decb29b6aae67bbcddf5122d 100644 (file)
--- a/src/index.ts
+++ b/src/index.ts
@@ -50,6 +50,7 @@ export type {
   WorkerUsage
 } from './pools/worker.js'
 export { WorkerTypes } from './pools/worker.js'
+export type { PriorityQueue } from './priority-queue.js'
 export type {
   MessageValue,
   PromiseResponseWrapper,

diff --git a/src/priority-queue.ts b/src/priority-queue.ts
index 55a97169f757beb0f53c51843d6a8a87f6392612..168e6c3455ca9fe82a864ad93fb61e3e894397a5 100644 (file)
--- a/src/priority-queue.ts
+++ b/src/priority-queue.ts
@@ -7,20 +7,28 @@ interface PriorityQueueNode<T> {
 }
 
 /**
- * Priority queue.
+ * k-priority queue.
  *
  * @typeParam T - Type of priority queue data.
  * @internal
  */
 export class PriorityQueue<T> {
   private nodeArray!: Array<PriorityQueueNode<T>>
+  /** Prioritized bucket size. */
+  private readonly k: number
   /** The size of the priority queue. */
   public size!: number
   /** The maximum size of the priority queue. */
   public maxSize!: number
 
-  public constructor () {
+  /**
+   * Constructs a k-priority queue.
+   *
+   * @param k - Prioritized bucket size.
+   */
+  public constructor (k = Infinity) {
     this.clear()
+    this.k = k
   }
 
   /**

diff --git a/tests/priority-queue.test.mjs b/tests/priority-queue.test.mjs
new file mode 100644 (file)
index 0000000..0c39e74
--- /dev/null
+++ b/tests/priority-queue.test.mjs
@@ -0,0 +1,116 @@
+import { expect } from 'expect'
+
+// eslint-disable-next-line n/no-missing-import, import/no-unresolved
+import { PriorityQueue } from '../lib/priority-queue.cjs'
+
+describe.skip('Priority queue test suite', () => {
+  it('Verify enqueue() behavior', () => {
+    const priorityQueue = new PriorityQueue()
+    let rtSize = priorityQueue.enqueue(1)
+    expect(priorityQueue.size).toBe(1)
+    expect(priorityQueue.maxSize).toBe(1)
+    expect(rtSize).toBe(priorityQueue.size)
+    expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }])
+    rtSize = priorityQueue.enqueue(2)
+    expect(priorityQueue.size).toBe(2)
+    expect(priorityQueue.maxSize).toBe(2)
+    expect(rtSize).toBe(priorityQueue.size)
+    expect(priorityQueue.nodeArray).toStrictEqual([
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 }
+    ])
+    rtSize = priorityQueue.enqueue(3)
+    expect(priorityQueue.size).toBe(3)
+    expect(priorityQueue.maxSize).toBe(3)
+    expect(rtSize).toBe(priorityQueue.size)
+    expect(priorityQueue.nodeArray).toStrictEqual([
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 },
+      { data: 3, priority: 0 }
+    ])
+    rtSize = priorityQueue.enqueue(3, -1)
+    expect(priorityQueue.size).toBe(4)
+    expect(priorityQueue.maxSize).toBe(4)
+    expect(rtSize).toBe(priorityQueue.size)
+    expect(priorityQueue.nodeArray).toStrictEqual([
+      { data: 3, priority: -1 },
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 },
+      { data: 3, priority: 0 }
+    ])
+    rtSize = priorityQueue.enqueue(1, 1)
+    expect(priorityQueue.size).toBe(5)
+    expect(priorityQueue.maxSize).toBe(5)
+    expect(rtSize).toBe(priorityQueue.size)
+    expect(priorityQueue.nodeArray).toStrictEqual([
+      { data: 3, priority: -1 },
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 },
+      { data: 3, priority: 0 },
+      { data: 1, priority: 1 }
+    ])
+  })
+
+  it('Verify dequeue() behavior', () => {
+    const priorityQueue = new PriorityQueue()
+    priorityQueue.enqueue(1)
+    priorityQueue.enqueue(2, -1)
+    priorityQueue.enqueue(3)
+    let rtItem = priorityQueue.dequeue()
+    expect(priorityQueue.size).toBe(2)
+    expect(priorityQueue.maxSize).toBe(3)
+    expect(rtItem).toBe(2)
+    expect(priorityQueue.nodeArray).toStrictEqual([
+      { data: 1, priority: 0 },
+      { data: 3, priority: 0 }
+    ])
+    rtItem = priorityQueue.dequeue()
+    expect(priorityQueue.size).toBe(1)
+    expect(priorityQueue.maxSize).toBe(3)
+    expect(rtItem).toBe(1)
+    expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: 0 }])
+    rtItem = priorityQueue.dequeue()
+    expect(priorityQueue.size).toBe(0)
+    expect(priorityQueue.maxSize).toBe(3)
+    expect(rtItem).toBe(3)
+    expect(priorityQueue.nodeArray).toStrictEqual([])
+  })
+
+  it('Verify peekFirst() behavior', () => {
+    const priorityQueue = new PriorityQueue()
+    priorityQueue.enqueue(1)
+    priorityQueue.enqueue(2)
+    priorityQueue.enqueue(3)
+    expect(priorityQueue.size).toBe(3)
+    expect(priorityQueue.peekFirst()).toBe(1)
+    expect(priorityQueue.size).toBe(3)
+  })
+
+  it('Verify peekLast() behavior', () => {
+    const priorityQueue = new PriorityQueue()
+    priorityQueue.enqueue(1)
+    priorityQueue.enqueue(2)
+    priorityQueue.enqueue(3)
+    expect(priorityQueue.size).toBe(3)
+    expect(priorityQueue.peekLast()).toBe(3)
+    expect(priorityQueue.size).toBe(3)
+  })
+
+  it('Verify clear() behavior', () => {
+    const priorityQueue = new PriorityQueue()
+    priorityQueue.enqueue(1)
+    priorityQueue.enqueue(2)
+    priorityQueue.enqueue(3)
+    expect(priorityQueue.size).toBe(3)
+    expect(priorityQueue.maxSize).toBe(3)
+    expect(priorityQueue.nodeArray).toStrictEqual([
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 },
+      { data: 3, priority: 0 }
+    ])
+    priorityQueue.clear()
+    expect(priorityQueue.size).toBe(0)
+    expect(priorityQueue.maxSize).toBe(0)
+    expect(priorityQueue.nodeArray).toStrictEqual([])
+  })
+})