From 017f9985e0b58b0d38e5fbf92038a6bdc984f200 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Thu, 20 Jun 2024 13:17:48 +0200 Subject: [PATCH] fix: fix priority queue dequeue() from the last prioritized bucket MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- CHANGELOG.md | 4 ++++ src/priority-queue.ts | 23 ++++++++++++++++------- tests/priority-queue.test.mjs | 16 +++++++++++++--- 3 files changed, 33 insertions(+), 10 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 3f1fd28f..43cdc02a 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -7,6 +7,10 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ## [Unreleased] +### Fixed + +- Fix priority queue dequeue() from the last prioritized bucket. + ## [4.0.14] - 2024-06-12 ### Changed diff --git a/src/priority-queue.ts b/src/priority-queue.ts index 18478afe..2a266d28 100644 --- a/src/priority-queue.ts +++ b/src/priority-queue.ts @@ -128,29 +128,38 @@ export class PriorityQueue { } ++currentBucket tail = tail.next - tailChanged = true } + tailChanged = tail !== this.tail } // eslint-disable-next-line @typescript-eslint/no-non-null-assertion const data = tail!.dequeue() // eslint-disable-next-line @typescript-eslint/no-non-null-assertion - if (tail!.empty() && tail!.next != null) { - if (!tailChanged) { + if (tail!.empty()) { + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + if (!tailChanged && tail!.next != null) { // eslint-disable-next-line @typescript-eslint/no-non-null-assertion this.tail = tail!.next - } else { + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + delete tail!.next + } else if (tailChanged) { let node: PriorityQueueNode | undefined = this.tail while (node != null) { - if (node.next === tail) { + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + if (node.next === tail && tail!.next != null) { // eslint-disable-next-line @typescript-eslint/no-non-null-assertion node.next = tail!.next + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + delete tail!.next + break + // eslint-disable-next-line @typescript-eslint/no-non-null-assertion + } else if (node.next === tail && tail!.next == null) { + delete node.next + this.head = node break } node = node.next } } - // eslint-disable-next-line @typescript-eslint/no-non-null-assertion - delete tail!.next } return data } diff --git a/tests/priority-queue.test.mjs b/tests/priority-queue.test.mjs index 839b6057..80f580d1 100644 --- a/tests/priority-queue.test.mjs +++ b/tests/priority-queue.test.mjs @@ -137,6 +137,7 @@ describe('Priority queue test suite', () => { { data: 2, priority: 0 }, ]) expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head) + expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(3, -1) expect(priorityQueue.buckets).toBe(2) expect(priorityQueue.size).toBe(4) @@ -152,6 +153,7 @@ describe('Priority queue test suite', () => { { data: 2, priority: 0 }, ]) expect(priorityQueue.tail.next).toStrictEqual(priorityQueue.head) + expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(1, 1) expect(priorityQueue.buckets).toBe(2) expect(priorityQueue.size).toBe(5) @@ -165,11 +167,13 @@ describe('Priority queue test suite', () => { { 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 }, ]) + expect(priorityQueue.tail.next.next).toStrictEqual(priorityQueue.head) + expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head) + expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head) rtSize = priorityQueue.enqueue(3, -2) expect(priorityQueue.buckets).toBe(3) expect(priorityQueue.size).toBe(6) @@ -184,11 +188,13 @@ describe('Priority queue test suite', () => { { 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 }, ]) + expect(priorityQueue.tail.next.next).toStrictEqual(priorityQueue.head) + expect(priorityQueue.tail.next).not.toStrictEqual(priorityQueue.head) + expect(priorityQueue.tail).not.toStrictEqual(priorityQueue.head) }) it('Verify default bucket size dequeue() behavior', () => { @@ -201,6 +207,7 @@ describe('Priority queue test suite', () => { expect(priorityQueue.maxSize).toBe(3) expect(priorityQueue.tail.empty()).toBe(false) expect(priorityQueue.tail.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) let rtItem = priorityQueue.dequeue() expect(priorityQueue.buckets).toBe(0) expect(priorityQueue.size).toBe(2) @@ -208,6 +215,7 @@ describe('Priority queue test suite', () => { expect(rtItem).toBe(2) expect(priorityQueue.tail.empty()).toBe(false) expect(priorityQueue.tail.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) rtItem = priorityQueue.dequeue() expect(priorityQueue.buckets).toBe(0) expect(priorityQueue.size).toBe(1) @@ -215,6 +223,7 @@ describe('Priority queue test suite', () => { expect(rtItem).toBe(1) expect(priorityQueue.tail.empty()).toBe(false) expect(priorityQueue.tail.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) rtItem = priorityQueue.dequeue() expect(priorityQueue.buckets).toBe(0) expect(priorityQueue.size).toBe(0) @@ -222,6 +231,7 @@ describe('Priority queue test suite', () => { expect(rtItem).toBe(3) expect(priorityQueue.tail.empty()).toBe(true) expect(priorityQueue.tail.next).toBe(undefined) + expect(priorityQueue.tail).toStrictEqual(priorityQueue.head) }) it('Verify bucketSize=2 dequeue() behavior', () => { @@ -271,7 +281,7 @@ describe('Priority queue test suite', () => { expect(priorityQueue.maxSize).toBe(6) expect(rtItem).toBe(1) expect(priorityQueue.tail.empty()).toBe(false) - expect(priorityQueue.tail.next).toBeInstanceOf(FixedPriorityQueue) + expect(priorityQueue.tail.next).toBe(undefined) rtItem = priorityQueue.dequeue() expect(priorityQueue.buckets).toBe(0) expect(priorityQueue.size).toBe(0) -- 2.34.1