X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=tests%2Fpriority-queue.test.mjs;h=f3da873405855449119dba52df325992a84f39a0;hb=e3b078a1a4aa8865f48cf968644ad7ff0594a1ef;hp=0c39e7461b2c6c4ef5cb1fa4e8ac4614e682932e;hpb=bd8b441c7140491657341a2971940ae7fc35222a;p=poolifier.git

diff --git a/tests/priority-queue.test.mjs b/tests/priority-queue.test.mjs
index 0c39e746..f3da8734 100644
--- a/tests/priority-queue.test.mjs
+++ b/tests/priority-queue.test.mjs
@@ -1,17 +1,42 @@
 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', () => {
+describe('Priority queue test suite', () => {
+  it('Verify constructor() behavior', () => {
+    expect(() => new PriorityQueue('')).toThrow(
+      new TypeError('bucketSize must be an integer')
+    )
+    expect(() => new PriorityQueue(-1)).toThrow(
+      new RangeError('bucketSize must be greater than or equal to 1')
+    )
+    expect(() => new PriorityQueue(0)).toThrow(
+      new RangeError('bucketSize must be greater than or equal to 1')
+    )
+    let priorityQueue = new PriorityQueue()
+    expect(priorityQueue.bucketSize).toBe(Infinity)
+    expect(priorityQueue.buckets).toBe(1)
+    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.buckets).toBe(0)
+    expect(priorityQueue.size).toBe(0)
+    expect(priorityQueue.maxSize).toBe(0)
+    expect(priorityQueue.nodeArray).toStrictEqual([])
+  })
+
+  it('Verify default bucketSize enqueue() behavior', () => {
     const priorityQueue = new PriorityQueue()
     let rtSize = priorityQueue.enqueue(1)
+    expect(priorityQueue.buckets).toBe(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.buckets).toBe(1)
     expect(priorityQueue.size).toBe(2)
     expect(priorityQueue.maxSize).toBe(2)
     expect(rtSize).toBe(priorityQueue.size)
@@ -20,6 +45,7 @@ describe.skip('Priority queue test suite', () => {
       { data: 2, priority: 0 }
     ])
     rtSize = priorityQueue.enqueue(3)
+    expect(priorityQueue.buckets).toBe(1)
     expect(priorityQueue.size).toBe(3)
     expect(priorityQueue.maxSize).toBe(3)
     expect(rtSize).toBe(priorityQueue.size)
@@ -29,6 +55,7 @@ describe.skip('Priority queue test suite', () => {
       { data: 3, priority: 0 }
     ])
     rtSize = priorityQueue.enqueue(3, -1)
+    expect(priorityQueue.buckets).toBe(1)
     expect(priorityQueue.size).toBe(4)
     expect(priorityQueue.maxSize).toBe(4)
     expect(rtSize).toBe(priorityQueue.size)
@@ -39,6 +66,7 @@ describe.skip('Priority queue test suite', () => {
       { data: 3, priority: 0 }
     ])
     rtSize = priorityQueue.enqueue(1, 1)
+    expect(priorityQueue.buckets).toBe(1)
     expect(priorityQueue.size).toBe(5)
     expect(priorityQueue.maxSize).toBe(5)
     expect(rtSize).toBe(priorityQueue.size)
@@ -51,12 +79,81 @@ describe.skip('Priority queue test suite', () => {
     ])
   })
 
-  it('Verify dequeue() behavior', () => {
+  it('Verify bucketSize=2 enqueue() behavior', () => {
+    const priorityQueue = new PriorityQueue(2)
+    let rtSize = priorityQueue.enqueue(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 }])
+    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([
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 }
+    ])
+    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 },
+      { data: 3, priority: 0 }
+    ])
+    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 },
+      { data: 3, priority: -1 },
+      { data: 3, priority: 0 }
+    ])
+    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([
+      { data: 1, priority: 0 },
+      { data: 2, priority: 0 },
+      { data: 3, priority: -1 },
+      { data: 3, priority: 0 },
+      { data: 1, priority: 1 }
+    ])
+    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 },
+      { data: 3, priority: -2 },
+      { data: 1, priority: 1 }
+    ])
+  })
+
+  it('Verify default bucketSize dequeue() behavior', () => {
     const priorityQueue = new PriorityQueue()
     priorityQueue.enqueue(1)
     priorityQueue.enqueue(2, -1)
     priorityQueue.enqueue(3)
+    expect(priorityQueue.buckets).toBe(1)
+    expect(priorityQueue.size).toBe(3)
+    expect(priorityQueue.maxSize).toBe(3)
     let rtItem = priorityQueue.dequeue()
+    expect(priorityQueue.buckets).toBe(1)
     expect(priorityQueue.size).toBe(2)
     expect(priorityQueue.maxSize).toBe(3)
     expect(rtItem).toBe(2)
@@ -65,17 +162,86 @@ describe.skip('Priority queue test suite', () => {
       { data: 3, priority: 0 }
     ])
     rtItem = priorityQueue.dequeue()
+    expect(priorityQueue.buckets).toBe(1)
     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.buckets).toBe(1)
     expect(priorityQueue.size).toBe(0)
     expect(priorityQueue.maxSize).toBe(3)
     expect(rtItem).toBe(3)
     expect(priorityQueue.nodeArray).toStrictEqual([])
   })
 
+  it('Verify bucketSize=2 dequeue() behavior', () => {
+    const priorityQueue = new PriorityQueue(2)
+    priorityQueue.enqueue(1)
+    priorityQueue.enqueue(2)
+    priorityQueue.enqueue(3)
+    priorityQueue.enqueue(3, -1)
+    priorityQueue.enqueue(1, 1)
+    priorityQueue.enqueue(3, -2)
+    expect(priorityQueue.buckets).toBe(3)
+    expect(priorityQueue.size).toBe(6)
+    expect(priorityQueue.maxSize).toBe(6)
+    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 }
+    ])
+    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 }
+    ])
+    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 }
+    ])
+    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 }
+    ])
+    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 }])
+    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)
@@ -96,11 +262,24 @@ describe.skip('Priority queue test suite', () => {
     expect(priorityQueue.size).toBe(3)
   })
 
+  it('Verify iterator behavior', () => {
+    const priorityQueue = new PriorityQueue()
+    priorityQueue.enqueue(1)
+    priorityQueue.enqueue(2)
+    priorityQueue.enqueue(3)
+    let i = 1
+    for (const value of priorityQueue) {
+      expect(value).toBe(i)
+      ++i
+    }
+  })
+
   it('Verify clear() behavior', () => {
     const priorityQueue = new PriorityQueue()
     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([
@@ -109,6 +288,7 @@ describe.skip('Priority queue test suite', () => {
       { data: 3, priority: 0 }
     ])
     priorityQueue.clear()
+    expect(priorityQueue.buckets).toBe(1)
     expect(priorityQueue.size).toBe(0)
     expect(priorityQueue.maxSize).toBe(0)
     expect(priorityQueue.nodeArray).toStrictEqual([])