feat: ✨ implement sorted array class

paveda · paveda · commit e469e09bd9fe · 2021-12-11T14:07:44.000+03:00
diff --git a/src/SortedArray.ts b/src/SortedArray.ts
@@ -1,23 +1,21 @@
 import type { Index, Size, CompareFunction } from './types';
-import { binarySearch } from './binarySearch';
 import { bubbleSort } from './bubbleSort';
+import { binarySearch } from "./binarySearch";
 
 /**
  *
  */
-export class SortedArray<T> {
-    private array: T[] = [];
+export class SortedArray<T = number> {
+    private readonly array: T[] = [];
+    private readonly compare: CompareFunction<T>;
 
     /**
      *
      * @param array -
      * @param compareFunction -
      */
-    constructor(array: T[], compareFunction?: CompareFunction<T>) {
-        if (compareFunction) {
-            this.compare = compareFunction;
-        }
-
+    constructor(array: T[], compareFunction: CompareFunction<T>) {
+        this.compare = compareFunction;
         this.array = bubbleSort(array, this.compare);
     }
 
@@ -27,45 +25,194 @@ export class SortedArray<T> {
      * @param unique -
      */
     insert(element: T, unique = true): Index {
-        let pos = binarySearch(this.array, element, this.compare, true);
+        let high = this.array.length - 1;
+        let low = 0;
+        let pos = -1;
+        let index = 0;
+        let ordering = 0;
+
+        while (high >= low) {
+            index = (high + low) / 2 >>> 0;
+            ordering = this.compare(this.array[index], element);
+            if (ordering < 0) {
+                low  = index + 1;
+            } else if (ordering > 0) {
+                high = index - 1;
+            } else {
+                pos = index;
+                break;
+            }
+        }
+
+        if (pos === -1) {
+            pos = high;
+        }
 
         pos++;
 
-        let high = this.array.length - 1;
+        high = this.array.length-1;
         while ((pos < high) && (this.compare(element, this.array[pos]) === 0)){
             pos++;
         }
 
-        let mid = this.array.length;
+        index = this.array.length;
         this.array.push(element);
-        while (mid > pos) {
-            this.array[mid] = this.array[--mid];
+        while (index > pos) {
+            this.array[index] = this.array[--index];
         }
 
         this.array[pos] = element;
 
         return pos;
     }
-    delete(element: T, all = true): Index {}
 
-    set(index: Index, element: T): T {}
-    get(index: Index): T {}
+    /**
+     *
+     * @param element -
+     * @param all -
+     */
+    delete(element: T, all = true): Index {
+        const index = binarySearch(this.array, element, this.compare);
 
-    search(element: T): Index {}
-    has(element: T): boolean {}
+        if (index === -1) {
+            return index;
+        }
 
-    slice(from: Index, to = this.array.length): SortedArray<T> {}
-    splice(from: Index, to = this.array.length): SortedArray<T> {}
-    concat(array: T[] | SortedArray<T>): SortedArray<T>{}
-    merge(array: T[] | SortedArray<T>): Size {}
+        this.array.splice(index, 1);
 
-    peek(index: Index): T {}
-    first(): T {}
-    last(): T {}
+        return index;
+    }
 
-    join(separator: string): string {}
+    /**
+     *
+     * @param index -
+     */
+    get(index: Index): T {
+        return this.array[index];
+    }
 
-    toArray(): T[] {}
+    /**
+     *
+     * @param element -
+     */
+    search(element: T): Index {
+        const index = binarySearch(this.array, element, this.compare);
 
-    private compare(a: T, b: T): number {}
+        return index;
+    }
+
+    /**
+     *
+     * @param element -
+     */
+    has(element: T): boolean {
+        const index = binarySearch(this.array, element, this.compare);
+
+        return (index !== -1);
+    }
+
+    /**
+     *
+     * @param from -
+     * @param to -
+     */
+    slice(from: Index, to = this.array.length): SortedArray<T> {
+        const slice = this.array.slice(from, to);
+        const sortedArray = new SortedArray<T>(slice, this.compare);
+
+        return sortedArray;
+    }
+
+    /**
+     *
+     * @param from -
+     * @param to -
+     */
+    splice(from: Index, to = this.array.length): SortedArray<T> {
+        const splice = this.array.splice(from, to);
+        const sortedArray = new SortedArray<T>(splice, this.compare);
+
+        return sortedArray;
+    }
+
+    /**
+     *
+     * @param array -
+     */
+    concat(array: T[] | SortedArray<T>): SortedArray<T>{
+        const one = array instanceof SortedArray ? array.toArray() : array;
+        const two = this.array.slice(0);
+        const tree = one.concat(two);
+        const sortedArray = new SortedArray<T>(tree, this.compare);
+
+        return sortedArray;
+    }
+
+    /**
+     *
+     * @param array -
+     */
+    merge(array: T[] | SortedArray<T>): Size {
+        for (const element of array) {
+            this.insert(element);
+        }
+
+        return this.array.length;
+    }
+
+    /**
+     *
+     */
+    first(): T | undefined {
+        return this.array.at(0);
+    }
+
+    /**
+     *
+     */
+    last(): T | undefined {
+        return this.array.at(-1);
+    }
+
+    /**
+     *
+     * @param separator
+     */
+    join(separator: string): string {
+        return this.array.join(separator);
+    }
+
+    /**
+     *
+     */
+    toArray(): T[] {
+        return this.array.slice(0);
+    }
+
+    get length() {
+        return this.array.length;
+    }
+
+    [Symbol.iterator]() {
+        let i = 0;
+        const array = this.array;
+
+        return {
+            next() {
+                if (i < array.length - 1) {
+                    i = i + 1;
+
+                    return {
+                        value: array[i],
+                        done: false
+                    }
+                }
+
+                return {
+                    value: array[i],
+                    done: true
+                }
+            }
+        }
+    }
 }
diff --git a/src/binarySearch.ts b/src/binarySearch.ts
@@ -10,10 +10,12 @@ export function binarySearch<T>(
     let high = array.length - 1;
     let low = 0;
     let pos = -1;
+    let mid = 0;
+    let ordering = 0;
 
     while (high >= low) {
-        const mid = (high + low) / 2 >>> 0;
-        const ordering = compare(array[mid], element);
+        mid = (high + low) / 2 >>> 0;
+        ordering = compare(array[mid], element);
         if (ordering < 0) {
             low  = mid + 1;
         } else if (ordering > 0) {
diff --git a/src/bubbleSort.ts b/src/bubbleSort.ts
@@ -1,5 +1,13 @@
 import type { CompareFunction } from './types';
 
+/**
+ * Bubble sort.
+ *
+ * @param array -
+ * @param compare -
+ *
+ * @returns - new sorted array.
+ */
 export function bubbleSort<T>(array: T[], compare: CompareFunction<T>): T[] {
     const sorted = array.slice(0);
     let len = sorted.length ;
diff --git a/src/compareNumbers.ts b/src/compareNumbers.ts
@@ -1,4 +1,6 @@
-export function compareNumbers(a: number, b: number): number {
+import { CompareFunction } from "./types";
+
+export const compareNumbers: CompareFunction<number> = (a, b) => {
     if (a < b) {
         return -1;
     } else if (a > b) {
