X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;ds=sidebyside;f=tests%2Fpriority-queue.test.mjs;h=bcd3cf0a169e0a9b0ca1f806f3328a2d3d719131;hb=e75373e6b8ed2882c1b8dd7eedc8ca9217582121;hp=f3da873405855449119dba52df325992a84f39a0;hpb=2107bc577c9620f6140183691f8038e71304489b;p=poolifier.git diff --git a/tests/priority-queue.test.mjs b/tests/priority-queue.test.mjs index f3da8734..bcd3cf0a 100644 --- 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(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) }) })