yasorted-array

An efficient sorted array.

Provided as:

• CommonJS
• ES Module

Usage Examples

// Basics
const numbers = new SortedArray<number>((a,b) => b - a);
console.log(numbers.add(3)); // 0
console.log(numbers.add(1)); // 1
console.log(numbers.add(2)); // 1
console.log(numbers.firstIndexOf(1)); // 2
console.log(numbers.firstIndexOf(2)); // 1
console.log(numbers.firstIndexOf(3)); // 0
console.log(numbers.firstIndexOf(4)); // -1

for (const element of numbers) {
  console.log(element)
} // 3, 2, 1

numbers.removeFirst(2); // 1
numbers.clear();

// Add Multiple
console.log(numbers.addMultiple(3, 1, 2)); // [0, 1, 2]
console.log(numbers.firstIndexOf(1)); // 2
console.log(numbers.firstIndexOf(2)); // 1
console.log(numbers.firstIndexOf(3)); // 0
console.log(Array.from(numbers)); // [3, 2, 1]

console.log(numbers.addMultiple(0, 0.5, 1.5, 2.5, 3.5)); // [0, 2, 4, 6, 7]
console.log(Array.from(numbers)); // [3.5, 3, 2.5, 2, 1.5, 1, 0.5, 0]

// Remove Multiple
console.log(numbers.removeMultiple(0, 2)); // [7, 3]
console.log(Array.from(numbers)); // [3.5, 3, 2.5, 1.5, 1, 0.5]

Interface

The SortedArray class implements the ISortedArray interface, which is as follows.

export interface ISortedArray<T> extends Iterable<T> {
  /** Gets the number of items in the array. */
  readonly length: number;

  /**
   * Adds a new value to the sorted array.
   *
   * Complexity: O(log(n)) for binary search + O(n) for insertion
   *
   * @param value - The value to add.
   * @returns The index at which the value was inserted.
   */
  add(value: T): number;

  /**
   * Adds multiple values to the sorted array.
   *
   * Complexity: O(M * log(n)) for finding insertion points + O(n) for rebuilding the array, where M is the number of items to add.
   *
   * @param values - The values to add.
   * @returns Array of indices, in ascending order, where the values were inserted.
   */
  addMultiple(...values: T[]): number[];

  /**
   * Finds the index of the first element that matches the provided value.
   *
   * Complexity: O(log(n))
   *
   * @param value - The value to find.
   * @returns The index of the first matching element, or `-1` if not found.
   */
  firstIndexOf(value: T): number;

  /**
   * Finds the index of the last element that matches the provided value.
   *
   * Complexity: O(log(n))
   *
   * @param value - The value to find.
   * @returns The index of the last matching element, or `-1` if not found.
   */
  lastIndexOf(value: T): number;

  /**
   * Removes the element at the specified index.
   *
   * Complexity: O(n) for removal
   *
   * @param value - The value to remove.
   * @returns The index of the removed element, or `-1` if invalid (non-integer) or out of bounds.
   */
  removeAtIndex(index: number): number;

  /**
   * Removes the elements at the specified indices.
   *
   * Complexity: O(n) for rebuilding the array
   *
   * @param indices - The indices of the elements to remove.
   * @returns Array of former indices of the removed elements (in reverse order).
   */
  removeAtIndices(...indices: number[]): number[];
  
  /**
   * Removes the first element that matches the provided value.
   *
   * Complexity: O(log(n)) for search + O(n) for removal
   *
   * @param value - The value to remove.
   * @returns The former index of the removed element, or `-1` if not found.
   */
  removeFirst(value: T): number;

  /**
   * Removes the last element that matches the provided value.
   *
   * Complexity: O(log(n)) for search + O(n) for removal
   *
   * @param value - The value to remove.
   * @returns The former index of the removed element, or `-1` if not found.
   */
  removeLast(value: T): number;

  /**
   * Removes all elements that match the provided value.
   *
   * Complexity: O(log(n)) for search + O(n) for removal
   *
   * @param value - The value to remove.
   * @returns Array of former indices of the removed elements (in reverse order).
   */
  removeAll(value: T): number[];

  /**
   * Removes multiple values from the sorted array.
   *
   * If specified values are duplicated in the array, all occurrences are removed.
   *
   * Complexity: O(M * log(n)) for finding values + O(n) for rebuilding the array, where M is the number of items to remove.
   *
   * @param values - The values to remove.
   * @returns Array of indices, in descending order, of the items that were removed.
   */
  removeMultiple(...values: T[]): number[];

  /**
   * Clears the array, removing all elements.
   *
   * Complexity: O(1)
   */
  clear(): void;

  /**
   * Gets the item at the specified index.
   *
   * Complexity: O(1)
   *
   * @param index - The index to access.
   * @returns The item at the specified index.
   */
  get(index: number): T;

  /**
   * Creates a new `ISortedArray` by filtering the elements of this array using the specified predicate.
   *
   * Complexity: O(n) for filtering.  No sort comparison are performed since it's assumed all elements will be in the same relative order.
   *
   * @param predicate - The function used to test each element.
   * @returns A new `ISortedArray` containing the elements that match the predicate.
   */
  filter(predicate: (value: T, index: number, obj: Readonly<T[]>) => boolean): ISortedArray<T>;

  /**
   * Finds the first index of an element that matches using the specified predicate.
   *
   * Complexity: O(n) for search
   *
   * @param predicate - The function to test each element.
   * @returns The index of the first matching element, which will be `-1` if not found.
   */
  findIndex(predicate: (value: T, index: number, obj: Readonly<T[]>) => boolean): number;

  /**
   * Finds the last index of an element that matches using the specified predicate.
   *
   * Complexity: O(n) for search
   *
   * @param predicate - The function to test each element.
   * @returns The index of the last matching element, which will be `-1` if not found.
   */
  findLastIndex(predicate: (value: T, index: number, obj: Readonly<T[]>) => boolean): number;

  /**
   * Finds all indices of elements that match using the specified predicate.
   *
   * Complexity: O(n) for search
   *
   * @param predicate - The function to test each element.
   * @returns The indices of the matching elements, in ascending order, which will be empty if no matches are found.
   */
  findIndices(predicate: (value: T, index: number, obj: Readonly<T[]>) => boolean): number[];
}

API Docs

Thanks

Thanks for checking it out. Feel free to create issues or otherwise provide feedback.

Be sure to check out our other TypeScript OSS projects as well.