@santi100/bisect-lib - npm Package Compare versions

Comparing version 0.0.2 to 0.0.3

cjs/index.d.ts

@@ -0,9 +1,52 @@
+type Comparator<T = unknown> = (a: T, b: T) => number;
 /**
- * Searches for `target` through `array` with a recursive binary-search algorithm (better for sorted arrays).
- * @param array The array to look through. It's highly recommended to sort it before passing it to this function, in order to make it faster.
+ * @since 0.0.3
+ */
+interface BisectOptions<C = unknown> {
+    /**
+     * Inclusive optional starting index. Defaults to 0.
+     */
+    start?: number;
+    /**
+   * Inclusive optional ending index. Defaults to the length of the array..
+   */
+    end?: number;
+    /**
+     * Optional epsilon for floating-point comparisons. Defaults to `Number.EPSILON`.
+     */
+    epsilon?: number;
+    /**
+     * Optional order. Defaults to 'ascending'.
+     */
+    order?: 'ascending' | 'descending';
+    /**
+     * Optional custom comparator. Is compatible with {@link Array.prototype.sort}.
+     */
+    comparator?: Comparator<C>;
+}
+/**
+ * Searches for `target` through `array` with an iterative binary-search algorithm (designed for sorted arrays).
+ * **Tests show it doesn't work correctly for unsorted arrays, so you shouldn't pass them to this function:
+ * ```javascript
+ * bisectLib.bisect([5, 7, 3], 3) // Outputs -1 (not present)
+ * ```
+ * It's not a bug, it's just how binary search algorithms work.
+ * @param array The array to look through.
  * @param target The item to look for.
+ * @param opts Optional object of options. See {@link BisectOptions}.
  * @returns The index of the first ocurrence of `target`, or -1 if it's not present.
  */
-declare function bisect<T = unknown>(array: T[], target: T): number;
+declare function bisect<T extends C, C = T>(array: T[], target: T, opts?: BisectOptions<C>): number;
+/**
+ * Searches for `target` through `array` with an iterative binary-search algorithm
+ (designed for sorted arrays) and returns an array of indices. See {@link bisect} for details.
+ *
+ * @since 0.0.3
+ * @param array The array to look through.
+ * @param target The item to look for.
+ * @param opts Optional object of options. See {@link BisectOptions}.
+ * @returns An array of indices whose values match `target`, or an empty array if it's not present.
+ */
+declare function bisectMultiple<T extends C, C = unknown>(array: T[], target: T, opts?: BisectOptions<C>): number[];
 export default bisect;
-export { bisect };
+export { bisect, bisectMultiple };

cjs/index.js

 "use strict";
 exports.__esModule = true;
-exports.bisect = void 0;
+exports.bisectMultiple = exports.bisect = void 0;
 /**
- * Searches for `target` through `array` with a recursive binary-search algorithm (better for sorted arrays).
- * @param array The array to look through. It's highly recommended to sort it before passing it to this function, in order to make it faster.
+ * Searches for `target` through `array` with an iterative binary-search algorithm (designed for sorted arrays).
+ * **Tests show it doesn't work correctly for unsorted arrays, so you shouldn't pass them to this function:
+ * ```javascript
+ * bisectLib.bisect([5, 7, 3], 3) // Outputs -1 (not present)
+ * ```
+ * It's not a bug, it's just how binary search algorithms work.
+ * @param array The array to look through.
  * @param target The item to look for.
+ * @param opts Optional object of options. See {@link BisectOptions}.
  * @returns The index of the first ocurrence of `target`, or -1 if it's not present.
  */
-function bisect(array, target) {
-    function __(start, end) {
-        if (start === void 0) { start = 0; }
-        if (end === void 0) { end = array.length; }
-        if (start > end)
-            return -1;
-        var middle = Math.floor((start + end) / 2);
-        if (array[middle] === target)
+function bisect(array, target, opts) {
+    if (!Array.isArray(array)) {
+        throw new TypeError("\"array\" must be an Array. Received \"".concat(String(array), "\"."));
+    }
+    var _a = opts || {}, comparator = _a.comparator, // Satisfies idea #1, see `ideas.md`
+    _b = _a.order, // Satisfies idea #1, see `ideas.md`
+    order = _b === void 0 ? 'ascending' : _b, // Satisfies idea #3, see `ideas.md`
+    _c = _a.epsilon, // Satisfies idea #3, see `ideas.md`
+    epsilon = _c === void 0 ? Number.EPSILON || 0 : _c, // Satisfies idea #5, see `ideas.md` 
+    _d = _a.start, // Satisfies idea #5, see `ideas.md` 
+    start = _d === void 0 ? 0 : _d, // Satisfies idea #4, see `ideas.md`
+    _e = _a.end // Satisfies idea #4, see `ideas.md`
+    , // Satisfies idea #4, see `ideas.md`
+    end = _e === void 0 ? array.length : _e // Satisfies idea #4, see `ideas.md`
+    ;
+    var left = start;
+    var right = end - 1;
+    while (left <= right) {
+        var middle = Math.floor((left + right) / 2);
+        if (typeof array[middle] === 'number' &&
+            Math.abs(array[middle] - target) <= epsilon) {
             return middle;
-        if (array[middle] > target)
-            return __(start, middle - 1);
-        return __(middle + 1, end);
+        }
+        else if (array[middle] === target) {
+            return middle;
+        }
+        else if (comparator) {
+            var cmp = comparator(target, array[middle]);
+            if ((order === 'ascending' && cmp < 0) || (order === 'descending' && cmp > 0)) {
+                right = middle - 1;
+            }
+            else {
+                left = middle + 1;
+            }
+        }
+        else if (array[middle] > target) {
+            right = middle - 1;
+        }
+        else {
+            left = middle + 1;
+        }
     }
-    return __();
+    return -1;
 }
 exports.bisect = bisect;
+/**
+ * Searches for `target` through `array` with an iterative binary-search algorithm
+ (designed for sorted arrays) and returns an array of indices. See {@link bisect} for details.
+ *
+ * @since 0.0.3
+ * @param array The array to look through.
+ * @param target The item to look for.
+ * @param opts Optional object of options. See {@link BisectOptions}.
+ * @returns An array of indices whose values match `target`, or an empty array if it's not present.
+ */
+function bisectMultiple(array, target, opts) {
+    if (opts === void 0) { opts = {}; }
+    var firstIndex = bisect(array, target, opts);
+    var indices = firstIndex === -1 ? [] : [firstIndex];
+    var i = firstIndex + 1;
+    while (array[i] === target && i < array.length) {
+        indices.push(i);
+        i++;
+    }
+    return indices;
+}
+exports.bisectMultiple = bisectMultiple;
 exports["default"] = bisect;

CODE_OF_CONDUCT.md

@@ -58,4 +58,5 @@ # Code of Conduct
 Instances of abusive, harassing, or otherwise unacceptable behavior may be
-reported by contacting me at [[e-mail]](mailto:[e-mail]). All complaints will be reviewed and investigated and will result in a response that
+reported by contacting me at <[e-mail]>.
+All complaints will be reviewed and investigated and will result in a response that
 is deemed necessary and appropriate to the circumstances. I will maintain confidentiality with regard to the reporter of an incident.
 Further details of specific enforcement policies may be posted separately.

index.d.ts

@@ -0,9 +1,52 @@
+type Comparator<T = unknown> = (a: T, b: T) => number;
 /**
- * Searches for `target` through `array` with a recursive binary-search algorithm (better for sorted arrays).
- * @param array The array to look through. It's highly recommended to sort it before passing it to this function, in order to make it faster.
+ * @since 0.0.3
+ */
+interface BisectOptions<C = unknown> {
+    /**
+     * Inclusive optional starting index. Defaults to 0.
+     */
+    start?: number;
+    /**
+   * Inclusive optional ending index. Defaults to the length of the array..
+   */
+    end?: number;
+    /**
+     * Optional epsilon for floating-point comparisons. Defaults to `Number.EPSILON`.
+     */
+    epsilon?: number;
+    /**
+     * Optional order. Defaults to 'ascending'.
+     */
+    order?: 'ascending' | 'descending';
+    /**
+     * Optional custom comparator. Is compatible with {@link Array.prototype.sort}.
+     */
+    comparator?: Comparator<C>;
+}
+/**
+ * Searches for `target` through `array` with an iterative binary-search algorithm (designed for sorted arrays).
+ * **Tests show it doesn't work correctly for unsorted arrays, so you shouldn't pass them to this function:
+ * ```javascript
+ * bisectLib.bisect([5, 7, 3], 3) // Outputs -1 (not present)
+ * ```
+ * It's not a bug, it's just how binary search algorithms work.
+ * @param array The array to look through.
  * @param target The item to look for.
+ * @param opts Optional object of options. See {@link BisectOptions}.
  * @returns The index of the first ocurrence of `target`, or -1 if it's not present.
  */
-declare function bisect<T = unknown>(array: T[], target: T): number;
+declare function bisect<T extends C, C = T>(array: T[], target: T, opts?: BisectOptions<C>): number;
+/**
+ * Searches for `target` through `array` with an iterative binary-search algorithm
+ (designed for sorted arrays) and returns an array of indices. See {@link bisect} for details.
+ *
+ * @since 0.0.3
+ * @param array The array to look through.
+ * @param target The item to look for.
+ * @param opts Optional object of options. See {@link BisectOptions}.
+ * @returns An array of indices whose values match `target`, or an empty array if it's not present.
+ */
+declare function bisectMultiple<T extends C, C = unknown>(array: T[], target: T, opts?: BisectOptions<C>): number[];
 export default bisect;
-export { bisect };
+export { bisect, bisectMultiple };

package.json

@@ -9,3 +9,3 @@ {
   ],
-  "version": "0.0.2",
+  "version": "0.0.3",
   "main": "index.js",
@@ -22,6 +22,7 @@ "author": "santi100a <[e-mail]>",
     "test": "jest",
+    "test:coverage": "jest --coverage",
     "dev": "tsc -w",
-    "test:watch": "jest --watchAll"
+    "test:watch": "jest --watchAll --coverage"
   },
   "type": "module"
 }

README.md

@@ -20,2 +20,8 @@ # Santi's Bisect Library
 
-- `function bisect<T = unknown>(array: T[], target: T): number;` Searches for `target` through `array` with a recursive binary-search algorithm (suited for sorted arrays). Returns the index of the first ocurrence of `target`, or -1 if it's not present.
+- `function bisect<T = unknown>(array: T[], target: T): number;` Searches for `target` through `array` with a recursive binary-search algorithm (designed for sorted arrays). Returns the index of the first ocurrence of `target`, or -1 if it's not present.
+
+**Tests show it doesn't work correctly for unsorted arrays, so you shouldn't pass them to this function:**
+```javascript
+bisectLib.bisect([5, 7, 3], 3) // Outputs -1 (not present)
+```
+**Also, keep in mind this library doesn't do deep equality for now. You can file an issue if you want this feature.**

src/index.ts

@@ -0,19 +1,109 @@
+type Comparator<T = unknown> = (a: T, b: T) => number;
+
 /**
- * Searches for `target` through `array` with a recursive binary-search algorithm (better for sorted arrays). 
- * @param array The array to look through. It's highly recommended to sort it before passing it to this function, in order to make it faster.
+ * @since 0.0.3
+ */
+interface BisectOptions<C = unknown> {
+  /**
+   * Inclusive optional starting index. Defaults to 0.
+   */
+    start?: number;
+    /**
+   * Inclusive optional ending index. Defaults to the length of the array..
+   */
+    end?: number;
+    /**
+     * Optional epsilon for floating-point comparisons. Defaults to `Number.EPSILON`.
+     */
+    epsilon?: number;
+    /**
+     * Optional order. Defaults to 'ascending'.
+     */
+    order?: 'ascending' | 'descending';
+    /**
+     * Optional custom comparator. Is compatible with {@link Array.prototype.sort}.
+     */
+    comparator?: Comparator<C>;
+}  
+
+/**
+ * Searches for `target` through `array` with an iterative binary-search algorithm (designed for sorted arrays). 
+ * **Tests show it doesn't work correctly for unsorted arrays, so you shouldn't pass them to this function:
+ * ```javascript
+ * bisectLib.bisect([5, 7, 3], 3) // Outputs -1 (not present)
+ * ```
+ * It's not a bug, it's just how binary search algorithms work.
+ * @param array The array to look through. 
  * @param target The item to look for.
+ * @param opts Optional object of options. See {@link BisectOptions}. 
  * @returns The index of the first ocurrence of `target`, or -1 if it's not present.
  */ 
-function bisect<T = unknown>(array: T[], target: T): number {
-    function __<U>(start: number = 0, end: number = array.length): number {
-        if (start > end) return -1;
-        const middle = Math.floor((start + end) / 2);
+function bisect<T extends C, C = T>(
+  array: T[],
+  target: T,
+  opts?: BisectOptions<C>
+): number {
+  if (!Array.isArray(array)) {
+    throw new TypeError(`"array" must be an Array. Received "${String(array)}".`);
+  }
 
-        if (array[middle] === target) return middle;
-        if (array[middle] > target) return __<U>(start, middle - 1);
-        return __<U>(middle + 1, end);
+  const { 
+    comparator, // Satisfies idea #1, see `ideas.md`
+    order = 'ascending', // Satisfies idea #3, see `ideas.md`
+    epsilon = Number.EPSILON || 0, // Satisfies idea #5, see `ideas.md` 
+    start = 0, // Satisfies idea #4, see `ideas.md`
+    end = array.length // Satisfies idea #4, see `ideas.md`
+  } = opts || {};
+  let left = start;
+  let right = end - 1;
+
+  while (left <= right) {
+    const middle = Math.floor((left + right) / 2);
+    if (
+      typeof array[middle] === 'number' && 
+      Math.abs(array[middle] as number - (target as number)) <= epsilon) {
+      return middle;
+    } else if (array[middle] === target) {
+      return middle;
+    } else if (comparator) {
+      const cmp = comparator(target, array[middle]);
+      if ((order === 'ascending' && cmp < 0) || (order === 'descending' && cmp > 0)) {
+        right = middle - 1;
+      } else {
+        left = middle + 1;
+      }
+    } else if (array[middle] > target) {
+      right = middle - 1;
+    } else {
+      left = middle + 1;
     }
-    return __();
+  }
+
+  return -1;
 }
+
+/**
+ * Searches for `target` through `array` with an iterative binary-search algorithm 
+ (designed for sorted arrays) and returns an array of indices. See {@link bisect} for details.
+ * 
+ * @since 0.0.3
+ * @param array The array to look through. 
+ * @param target The item to look for.
+ * @param opts Optional object of options. See {@link BisectOptions}. 
+ * @returns An array of indices whose values match `target`, or an empty array if it's not present.
+ */
+ function bisectMultiple<T extends C, C = unknown>(
+  array: T[], target: T, opts: BisectOptions<C> = {}
+): number[] {
+  const firstIndex = bisect(array, target, opts);
+  const indices: number[] = firstIndex === -1 ? [] : [firstIndex];
+  let i = firstIndex + 1;
+  while (array[i] === target && i < array.length) {
+    indices.push(i);
+    i++;
+  }
+  return indices;
+}
+
 export default bisect;
-export { bisect }; 
+export { bisect, bisectMultiple }; 

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

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

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

21670

increased by96.96%

Number of package files

17

increased by13.33%

Lines of code

329

increased by311.25%

Number of lines in readme file

26

increased by30%

Worsened metrics

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes