fix: fix task dequeuing from the last bucket

[poolifier.git] / tests / priority-queue.test.mjs

diff --git a/tests/priority-queue.test.mjs b/tests/priority-queue.test.mjs
index 00ecb33f9d3595840e7b203bd28e6432d8ab4797..bcd3cf0a169e0a9b0ca1f806f3328a2d3d719131 100644 (file)
--- a/tests/priority-queue.test.mjs
+++ b/tests/priority-queue.test.mjs
@@ -1,6 +1,7 @@
 import { expect } from 'expect'
 
-import { PriorityQueue } from '../lib/priority-queue.cjs'
+import { FixedPriorityQueue } from '../lib/fixed-priority-queue.cjs'
+import { defaultBucketSize, PriorityQueue } from '../lib/priority-queue.cjs'
 
 describe('Priority queue test suite', () => {
   it('Verify constructor() behavior', () => {
@@ -14,69 +15,90 @@ describe('Priority queue test suite', () => {
       new RangeError('bucketSize must be greater than or equal to 1')
     )
     let priorityQueue = new PriorityQueue()
-    expect(priorityQueue.bucketSize).toBe(Number.POSITIVE_INFINITY)
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.bucketSize).toBe(defaultBucketSize)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(0)
     expect(priorityQueue.maxSize).toBe(0)
-    expect(priorityQueue.nodeArray).toStrictEqual([])
-    priorityQueue = new PriorityQueue(2)
-    expect(priorityQueue.bucketSize).toBe(2)
+    expect(priorityQueue.head).toBeInstanceOf(FixedPriorityQueue)
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.head.capacity).toBe(defaultBucketSize)
+    expect(priorityQueue.tail).toBeInstanceOf(FixedPriorityQueue)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
+    const bucketSize = 2
+    priorityQueue = new PriorityQueue(bucketSize)
+    expect(priorityQueue.bucketSize).toBe(bucketSize)
     expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(0)
     expect(priorityQueue.maxSize).toBe(0)
-    expect(priorityQueue.nodeArray).toStrictEqual([])
+    expect(priorityQueue.head).toBeInstanceOf(FixedPriorityQueue)
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.head.capacity).toBe(bucketSize)
+    expect(priorityQueue.tail).toBeInstanceOf(FixedPriorityQueue)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
   })
 
-  it('Verify default bucketSize enqueue() behavior', () => {
+  it('Verify default bucket size enqueue() behavior', () => {
     const priorityQueue = new PriorityQueue()
     let rtSize = priorityQueue.enqueue(1)
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(1)
     expect(priorityQueue.maxSize).toBe(1)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }])
+    expect(priorityQueue.head.nodeArray).toMatchObject([
+      { data: 1, priority: 0 }
+    ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
     rtSize = priorityQueue.enqueue(2)
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(2)
     expect(priorityQueue.maxSize).toBe(2)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([
+    expect(priorityQueue.head.nodeArray).toMatchObject([
       { data: 1, priority: 0 },
       { data: 2, priority: 0 }
     ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
     rtSize = priorityQueue.enqueue(3)
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(3)
     expect(priorityQueue.maxSize).toBe(3)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([
+    expect(priorityQueue.head.nodeArray).toMatchObject([
       { data: 1, priority: 0 },
       { data: 2, priority: 0 },
       { data: 3, priority: 0 }
     ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
     rtSize = priorityQueue.enqueue(3, -1)
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(4)
     expect(priorityQueue.maxSize).toBe(4)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([
+    expect(priorityQueue.head.nodeArray).toMatchObject([
       { data: 3, priority: -1 },
       { data: 1, priority: 0 },
       { data: 2, priority: 0 },
       { data: 3, priority: 0 }
     ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
     rtSize = priorityQueue.enqueue(1, 1)
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(5)
     expect(priorityQueue.maxSize).toBe(5)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([
+    expect(priorityQueue.head.nodeArray).toMatchObject([
       { data: 3, priority: -1 },
       { data: 1, priority: 0 },
       { data: 2, priority: 0 },
       { data: 3, priority: 0 },
       { data: 1, priority: 1 }
     ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
   })
 
   it('Verify bucketSize=2 enqueue() behavior', () => {
@@ -86,93 +108,121 @@ describe('Priority queue test suite', () => {
     expect(priorityQueue.size).toBe(1)
     expect(priorityQueue.maxSize).toBe(1)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([{ data: 1, priority: 0 }])
+    expect(priorityQueue.head.nodeArray).toMatchObject([
+      { data: 1, priority: 0 }
+    ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
     rtSize = priorityQueue.enqueue(2)
     expect(priorityQueue.buckets).toBe(1)
     expect(priorityQueue.size).toBe(2)
     expect(priorityQueue.maxSize).toBe(2)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([
+    expect(priorityQueue.head.nodeArray).toMatchObject([
       { data: 1, priority: 0 },
       { data: 2, priority: 0 }
     ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
     rtSize = priorityQueue.enqueue(3)
     expect(priorityQueue.buckets).toBe(1)
     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 },
+    expect(priorityQueue.head.nodeArray).toMatchObject([
       { data: 3, priority: 0 }
     ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail.nodeArray).toMatchObject([
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 }
+    ])
+    expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
     rtSize = priorityQueue.enqueue(3, -1)
     expect(priorityQueue.buckets).toBe(2)
     expect(priorityQueue.size).toBe(4)
     expect(priorityQueue.maxSize).toBe(4)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([
-      { data: 1, priority: 0 },
-      { data: 2, priority: 0 },
+    expect(priorityQueue.head.nodeArray).toMatchObject([
       { data: 3, priority: -1 },
       { data: 3, priority: 0 }
     ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail.nodeArray).toMatchObject([
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 }
+    ])
+    expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head)
     rtSize = priorityQueue.enqueue(1, 1)
     expect(priorityQueue.buckets).toBe(2)
     expect(priorityQueue.size).toBe(5)
     expect(priorityQueue.maxSize).toBe(5)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([
+    expect(priorityQueue.head.nodeArray).toMatchObject([
+      { data: 1, priority: 1 }
+    ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail.nodeArray).toMatchObject([
       { data: 1, priority: 0 },
-      { data: 2, priority: 0 },
+      { data: 2, priority: 0 }
+    ])
+    expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
+    expect(priorityQueue.tail.next.nodeArray).toMatchObject([
       { data: 3, priority: -1 },
-      { data: 3, priority: 0 },
-      { data: 1, priority: 1 }
+      { data: 3, priority: 0 }
     ])
     rtSize = priorityQueue.enqueue(3, -2)
     expect(priorityQueue.buckets).toBe(3)
     expect(priorityQueue.size).toBe(6)
     expect(priorityQueue.maxSize).toBe(6)
     expect(rtSize).toBe(priorityQueue.size)
-    expect(priorityQueue.nodeArray).toStrictEqual([
-      { data: 1, priority: 0 },
-      { data: 2, priority: 0 },
-      { data: 3, priority: -1 },
-      { data: 3, priority: 0 },
+    expect(priorityQueue.head.nodeArray).toMatchObject([
       { data: 3, priority: -2 },
       { data: 1, priority: 1 }
     ])
+    expect(priorityQueue.head.next).toBe(undefined)
+    expect(priorityQueue.tail.nodeArray).toMatchObject([
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 }
+    ])
+    expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head)
+    expect(priorityQueue.tail.next.nodeArray).toMatchObject([
+      { data: 3, priority: -1 },
+      { data: 3, priority: 0 }
+    ])
   })
 
-  it('Verify default bucketSize dequeue() behavior', () => {
+  it('Verify default bucket size dequeue() behavior', () => {
     const priorityQueue = new PriorityQueue()
     priorityQueue.enqueue(1)
     priorityQueue.enqueue(2, -1)
     priorityQueue.enqueue(3)
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(3)
     expect(priorityQueue.maxSize).toBe(3)
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail.next).toBe(undefined)
     let rtItem = priorityQueue.dequeue()
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     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 }
-    ])
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail.next).toBe(undefined)
     rtItem = priorityQueue.dequeue()
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(1)
     expect(priorityQueue.maxSize).toBe(3)
     expect(rtItem).toBe(1)
-    expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: 0 }])
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail.next).toBe(undefined)
     rtItem = priorityQueue.dequeue()
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(0)
     expect(priorityQueue.maxSize).toBe(3)
     expect(rtItem).toBe(3)
-    expect(priorityQueue.nodeArray).toStrictEqual([])
+    expect(priorityQueue.tail.empty()).toBe(true)
+    expect(priorityQueue.tail.next).toBe(undefined)
   })
 
   it('Verify bucketSize=2 dequeue() behavior', () => {
@@ -186,84 +236,54 @@ describe('Priority queue test suite', () => {
     expect(priorityQueue.buckets).toBe(3)
     expect(priorityQueue.size).toBe(6)
     expect(priorityQueue.maxSize).toBe(6)
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
     let rtItem = priorityQueue.dequeue(3)
     expect(priorityQueue.buckets).toBe(2)
     expect(priorityQueue.size).toBe(5)
     expect(priorityQueue.maxSize).toBe(6)
     expect(rtItem).toBe(3)
-    expect(priorityQueue.nodeArray).toStrictEqual([
-      { data: 1, priority: 0 },
-      { data: 2, priority: 0 },
-      { data: 3, priority: -1 },
-      { data: 3, priority: 0 },
-      { data: 1, priority: 1 }
-    ])
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
     rtItem = priorityQueue.dequeue()
     expect(priorityQueue.buckets).toBe(2)
     expect(priorityQueue.size).toBe(4)
     expect(priorityQueue.maxSize).toBe(6)
     expect(rtItem).toBe(1)
-    expect(priorityQueue.nodeArray).toStrictEqual([
-      { data: 2, priority: 0 },
-      { data: 3, priority: -1 },
-      { data: 3, priority: 0 },
-      { data: 1, priority: 1 }
-    ])
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
     rtItem = priorityQueue.dequeue(2)
     expect(priorityQueue.buckets).toBe(1)
     expect(priorityQueue.size).toBe(3)
     expect(priorityQueue.maxSize).toBe(6)
     expect(rtItem).toBe(3)
-    expect(priorityQueue.nodeArray).toStrictEqual([
-      { data: 2, priority: 0 },
-      { data: 3, priority: -1 },
-      { data: 1, priority: 1 }
-    ])
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
     rtItem = priorityQueue.dequeue(2)
     expect(priorityQueue.buckets).toBe(1)
     expect(priorityQueue.size).toBe(2)
     expect(priorityQueue.maxSize).toBe(6)
-    expect(rtItem).toBe(1)
-    expect(priorityQueue.nodeArray).toStrictEqual([
-      { data: 2, priority: 0 },
-      { data: 3, priority: -1 }
-    ])
+    expect(rtItem).toBe(3)
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
     rtItem = priorityQueue.dequeue(2)
     expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(1)
     expect(priorityQueue.maxSize).toBe(6)
-    expect(rtItem).toBe(2)
-    expect(priorityQueue.nodeArray).toStrictEqual([{ data: 3, priority: -1 }])
+    expect(rtItem).toBe(1)
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue)
     rtItem = priorityQueue.dequeue()
     expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(0)
     expect(priorityQueue.maxSize).toBe(6)
-    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)
+    expect(rtItem).toBe(2)
+    expect(priorityQueue.tail.empty()).toBe(true)
+    expect(priorityQueue.tail.next).toBe(undefined)
   })
 
   it('Verify iterator behavior', () => {
-    const priorityQueue = new PriorityQueue()
+    const priorityQueue = new PriorityQueue(2)
     priorityQueue.enqueue(1)
     priorityQueue.enqueue(2)
     priorityQueue.enqueue(3)
@@ -275,22 +295,21 @@ describe('Priority queue test suite', () => {
   })
 
   it('Verify clear() behavior', () => {
-    const priorityQueue = new PriorityQueue()
+    const priorityQueue = new PriorityQueue(2)
     priorityQueue.enqueue(1)
     priorityQueue.enqueue(2)
     priorityQueue.enqueue(3)
     expect(priorityQueue.buckets).toBe(1)
     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 }
-    ])
+    expect(priorityQueue.head.empty()).toBe(false)
+    expect(priorityQueue.tail.empty()).toBe(false)
+    expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head)
     priorityQueue.clear()
-    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.buckets).toBe(0)
     expect(priorityQueue.size).toBe(0)
     expect(priorityQueue.maxSize).toBe(0)
-    expect(priorityQueue.nodeArray).toStrictEqual([])
+    expect(priorityQueue.head.empty()).toBe(true)
+    expect(priorityQueue.tail).toStrictEqual(priorityQueue.head)
   })
 })