@mathigon/core - npm Package Compare versions

Comparing version 1.1.2 to 1.1.3

dist/arrays.d.ts

@@ -57,2 +57,17 @@ /** Creates an array of size `n`, containing `value` at every entry. */
 }
+export declare enum BinarySearchType {
+    first = 0,
+    firstGreater = 1
+}
+export declare type BinarySearchArray<T> = Array<{
+    item: T;
+    val: number;
+}>;
+/**
+ * Performs binary search on `array`, finding elements with value `value` based
+ * on the `type` criteria. The array is assumed to be sorted (small to large)
+ * in oder of the value returned by the `getValue()` method.
+ */
+export declare function binarySearch<T>(array: BinarySearchArray<T>, value: number, type: BinarySearchType): number;
+export declare function binaryIndexOf<T>(array: BinarySearchArray<T>, item: T, value: number): number;
 export {};

dist/index.cjs.js

@@ -23,2 +23,3 @@ "use strict";
 __export(src_exports, {
+  BinarySearchType: () => BinarySearchType,
   Cache: () => Cache,
@@ -30,2 +31,4 @@ Color: () => Color,
   autoCorrect: () => autoCorrect,
+  binaryIndexOf: () => binaryIndexOf,
+  binarySearch: () => binarySearch,
   cache: () => cache,
@@ -317,2 +320,42 @@ chunk: () => chunk,
 };
+var BinarySearchType = /* @__PURE__ */ ((BinarySearchType2) => {
+  BinarySearchType2[BinarySearchType2["first"] = 0] = "first";
+  BinarySearchType2[BinarySearchType2["firstGreater"] = 1] = "firstGreater";
+  return BinarySearchType2;
+})(BinarySearchType || {});
+function binarySearch(array, value, type) {
+  let low = 0;
+  let high = array.length - 1;
+  let ans = -1;
+  while (low <= high) {
+    const mid = Math.floor((low + high) / 2);
+    const midVal = array[mid].val;
+    if (midVal < value) {
+      low = mid + 1;
+    } else if (midVal > value) {
+      if (type === 1 /* firstGreater */)
+        ans = mid;
+      high = mid - 1;
+    } else {
+      if (type === 0 /* first */) {
+        ans = mid;
+        high = mid - 1;
+      } else if (type === 1 /* firstGreater */) {
+        low = mid + 1;
+      }
+    }
+  }
+  return ans;
+}
+function binaryIndexOf(array, item, value) {
+  let i = binarySearch(array, value, 0 /* first */);
+  if (i < 0)
+    return -1;
+  while (array[i].val === value) {
+    if (array[i].item === item)
+      return i;
+    i += 1;
+  }
+  return -1;
+}
 
@@ -319,0 +362,0 @@ // src/strings.ts

dist/index.esm.js

@@ -244,2 +244,42 @@ // src/utilities.ts
 };
+var BinarySearchType = /* @__PURE__ */ ((BinarySearchType2) => {
+  BinarySearchType2[BinarySearchType2["first"] = 0] = "first";
+  BinarySearchType2[BinarySearchType2["firstGreater"] = 1] = "firstGreater";
+  return BinarySearchType2;
+})(BinarySearchType || {});
+function binarySearch(array, value, type) {
+  let low = 0;
+  let high = array.length - 1;
+  let ans = -1;
+  while (low <= high) {
+    const mid = Math.floor((low + high) / 2);
+    const midVal = array[mid].val;
+    if (midVal < value) {
+      low = mid + 1;
+    } else if (midVal > value) {
+      if (type === 1 /* firstGreater */)
+        ans = mid;
+      high = mid - 1;
+    } else {
+      if (type === 0 /* first */) {
+        ans = mid;
+        high = mid - 1;
+      } else if (type === 1 /* firstGreater */) {
+        low = mid + 1;
+      }
+    }
+  }
+  return ans;
+}
+function binaryIndexOf(array, item, value) {
+  let i = binarySearch(array, value, 0 /* first */);
+  if (i < 0)
+    return -1;
+  while (array[i].val === value) {
+    if (array[i].item === item)
+      return i;
+    i += 1;
+  }
+  return -1;
+}
 
@@ -674,2 +714,3 @@ // src/strings.ts
 export {
+  BinarySearchType,
   Cache,
@@ -681,2 +722,4 @@ Color,
   autoCorrect,
+  binaryIndexOf,
+  binarySearch,
   cache,
@@ -683,0 +726,0 @@ chunk,

package.json

 {
   "name": "@mathigon/core",
-  "version": "1.1.2",
+  "version": "1.1.3",
   "license": "MIT",
@@ -5,0 +5,0 @@ "homepage": "https://mathigon.io/core",

src/arrays.ts

@@ -210,1 +210,55 @@ // =============================================================================
 }
+
+export enum BinarySearchType {
+  first,
+  firstGreater
+}
+
+export type BinarySearchArray<T> = Array<{item: T, val: number}>;
+
+/**
+ * Performs binary search on `array`, finding elements with value `value` based
+ * on the `type` criteria. The array is assumed to be sorted (small to large)
+ * in oder of the value returned by the `getValue()` method.
+ */
+export function binarySearch<T>(array: BinarySearchArray<T>, value: number, type: BinarySearchType) {
+  let low = 0;
+  let high = array.length - 1;
+  let ans = -1;
+
+  while (low <= high) {
+    const mid = Math.floor((low + high) / 2);
+    const midVal = array[mid].val;
+    if (midVal < value) {
+      // If mid < zIndex, all elements in [low, mid] are also less, so we now
+      // search in [mid + 1, high]:
+      low = mid + 1;
+    } else if (midVal > value) {
+      // If mid > zIndex, all elements in [mid + 1, high] are also greater, so
+      // we now search in [low, mid - 1]:
+      if (type === BinarySearchType.firstGreater) ans = mid;
+      high = mid - 1;
+    } else {
+      if (type === BinarySearchType.first) {
+        // If mid is equal to zIndex, we note down the last found index and then
+        // search for more in left side of mid, so we now in [low, mid - 1]:
+        ans = mid;
+        high = mid - 1;
+      } else if (type === BinarySearchType.firstGreater) {
+        low = mid + 1;
+      }
+    }
+  }
+
+  return ans;
+}
+
+export function binaryIndexOf<T>(array: BinarySearchArray<T>, item: T, value: number) {
+  let i = binarySearch(array, value, BinarySearchType.first);
+  if (i < 0) return -1;
+  while (array[i].val === value) {
+    if (array[i].item === item) return i;
+    i += 1;
+  }
+  return -1;
+}

test/arrays-test.ts

@@ -8,3 +8,3 @@ // =============================================================================
 import tape from 'tape';
-import {tabulate2D} from '../src';
+import {binaryIndexOf, binarySearch, BinarySearchType, tabulate2D} from '../src';
 
@@ -16,1 +16,26 @@
 });
+
+tape('binary search', (t) => {
+  const data = [1, 2, 2, 4, 4, 5, 5, 6].map(val => ({item: {}, val}));
+
+  t.equals(binarySearch(data, 0, BinarySearchType.first), -1);
+  t.equals(binarySearch(data, 1, BinarySearchType.first), 0);
+  t.equals(binarySearch(data, 4, BinarySearchType.first), 3);
+  t.equals(binarySearch(data, 6, BinarySearchType.first), 7);
+  t.equals(binarySearch(data, 7, BinarySearchType.first), -1);
+
+  t.equals(binarySearch(data, 0, BinarySearchType.firstGreater), 0);
+  t.equals(binarySearch(data, 1, BinarySearchType.firstGreater), 1);
+  t.equals(binarySearch(data, 4, BinarySearchType.firstGreater), 5);
+  t.equals(binarySearch(data, 6, BinarySearchType.firstGreater), -1);
+  t.equals(binarySearch(data, 7, BinarySearchType.firstGreater), -1);
+
+  t.equals(binaryIndexOf(data, {}, 0), -1);
+  t.equals(binaryIndexOf(data, {}, 2), -1);
+  t.equals(binaryIndexOf(data, data[2].item, data[2].val), 2);
+  t.equals(binaryIndexOf(data, data[3].item, data[3].val), 3);
+  t.equals(binaryIndexOf(data, data[6].item, data[6].val), 6);
+  t.equals(binaryIndexOf(data, data[7].item, data[7].val), 7);
+
+  t.end();
+});

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

180135

increased by6.33%

Lines of code

2776

increased by6.48%

Worsened metrics

Number of downloads

2426

decreased by-38.64%

No dependency changes