From 116a8c861a8a7c5b348b848f1409e1b68dd82699 Mon Sep 17 00:00:00 2001
From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= <jerome.benoit@sap.com>
Date: Thu, 15 Jun 2023 22:22:34 +0200
Subject: [PATCH] perf: optimize O(1) queue implementation
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

Signed-off-by: Jérôme Benoit <jerome.benoit@sap.com>
---
 src/queue.ts        | 70 +++++++++++++++++++--------------------------
 tests/queue.test.js | 42 ++++++++++++---------------
 2 files changed, 47 insertions(+), 65 deletions(-)

diff --git a/src/queue.ts b/src/queue.ts
index 86b69051..8b761c8f 100644
--- a/src/queue.ts
+++ b/src/queue.ts
@@ -6,36 +6,18 @@
  * @typeParam T - Type of queue items.
  */
 export class Queue<T> {
-  private items: Record<number, T>
-  private head: number
-  private tail: number
-  private max: number
+  private items: T[]
+  private offset: number
+  public size: number
+  public maxSize: number
 
   public constructor () {
-    this.items = {}
-    this.head = 0
-    this.tail = 0
-    this.max = 0
-  }
-
-  /**
-   * Get the size of the queue.
-   *
-   * @returns The size of the queue.
-   * @readonly
-   */
-  public get size (): number {
-    return this.tail - this.head
-  }
-
-  /**
-   * Get the maximum size of the queue.
-   *
-   * @returns The maximum size of the queue.
-   * @readonly
-   */
-  public get maxSize (): number {
-    return this.max
+    this.items = []
+    /** The size of the queue. */
+    this.size = 0
+    this.offset = 0
+    /** The maximum size of the queue. */
+    this.maxSize = 0
   }
 
   /**
@@ -45,9 +27,11 @@ export class Queue<T> {
    * @returns The new size of the queue.
    */
   public enqueue (item: T): number {
-    this.items[this.tail] = item
-    this.tail++
-    if (this.size > this.max) this.max = this.size
+    this.items.push(item)
+    ++this.size
+    if (this.size > this.maxSize) {
+      this.maxSize = this.size
+    }
     return this.size
   }
 
@@ -57,23 +41,27 @@ export class Queue<T> {
    * @returns The dequeued item or `undefined` if the queue is empty.
    */
   public dequeue (): T | undefined {
-    if (this.size <= 0) return undefined
-    const item = this.items[this.head]
-    // eslint-disable-next-line @typescript-eslint/no-dynamic-delete
-    delete this.items[this.head]
-    this.head++
-    if (this.head === this.tail) {
-      this.head = 0
-      this.tail = 0
+    if (this.size <= 0) {
+      return undefined
     }
+    const item = this.items[this.offset]
+    if (++this.offset * 2 >= this.items.length) {
+      this.items = this.items.slice(this.offset)
+      this.offset = 0
+    }
+    --this.size
     return item
   }
 
   /**
    * Peek at the first item.
+   *
+   * @returns The first item or `undefined` if the queue is empty.
    */
   public peek (): T | undefined {
-    if (this.size <= 0) return undefined
-    return this.items[this.head]
+    if (this.size <= 0) {
+      return undefined
+    }
+    return this.items[this.offset]
   }
 }
diff --git a/tests/queue.test.js b/tests/queue.test.js
index 3a61f43d..3fd51dc8 100644
--- a/tests/queue.test.js
+++ b/tests/queue.test.js
@@ -7,24 +7,21 @@ describe('Queue test suite', () => {
     let rtSize = queue.enqueue(1)
     expect(queue.size).toBe(1)
     expect(rtSize).toBe(queue.size)
-    expect(queue.head).toBe(0)
-    expect(queue.tail).toBe(1)
-    expect(queue.max).toBe(1)
-    expect(queue.items).toStrictEqual({ 0: 1 })
+    expect(queue.offset).toBe(0)
+    expect(queue.maxSize).toBe(1)
+    expect(queue.items).toStrictEqual([1])
     rtSize = queue.enqueue(2)
     expect(queue.size).toBe(2)
     expect(rtSize).toBe(queue.size)
-    expect(queue.head).toBe(0)
-    expect(queue.tail).toBe(2)
-    expect(queue.max).toBe(2)
-    expect(queue.items).toStrictEqual({ 0: 1, 1: 2 })
+    expect(queue.offset).toBe(0)
+    expect(queue.maxSize).toBe(2)
+    expect(queue.items).toStrictEqual([1, 2])
     rtSize = queue.enqueue(3)
     expect(queue.size).toBe(3)
     expect(rtSize).toBe(queue.size)
-    expect(queue.head).toBe(0)
-    expect(queue.tail).toBe(3)
-    expect(queue.max).toBe(3)
-    expect(queue.items).toStrictEqual({ 0: 1, 1: 2, 2: 3 })
+    expect(queue.offset).toBe(0)
+    expect(queue.maxSize).toBe(3)
+    expect(queue.items).toStrictEqual([1, 2, 3])
   })
 
   it('Verify dequeue() behavior', () => {
@@ -35,23 +32,20 @@ describe('Queue test suite', () => {
     let rtItem = queue.dequeue()
     expect(queue.size).toBe(2)
     expect(rtItem).toBe(1)
-    expect(queue.head).toBe(1)
-    expect(queue.tail).toBe(3)
-    expect(queue.max).toBe(3)
-    expect(queue.items).toStrictEqual({ 1: 2, 2: 3 })
+    expect(queue.offset).toBe(1)
+    expect(queue.maxSize).toBe(3)
+    expect(queue.items).toStrictEqual([1, 2, 3])
     rtItem = queue.dequeue()
     expect(queue.size).toBe(1)
     expect(rtItem).toBe(2)
-    expect(queue.head).toBe(2)
-    expect(queue.tail).toBe(3)
-    expect(queue.max).toBe(3)
-    expect(queue.items).toStrictEqual({ 2: 3 })
+    expect(queue.offset).toBe(0)
+    expect(queue.maxSize).toBe(3)
+    expect(queue.items).toStrictEqual([3])
     rtItem = queue.dequeue()
     expect(queue.size).toBe(0)
     expect(rtItem).toBe(3)
-    expect(queue.head).toBe(0)
-    expect(queue.tail).toBe(0)
-    expect(queue.max).toBe(3)
-    expect(queue.items).toStrictEqual({})
+    expect(queue.offset).toBe(0)
+    expect(queue.maxSize).toBe(3)
+    expect(queue.items).toStrictEqual([])
   })
 })
-- 
2.34.1