yasorted-array
    Preparing search index...

    Class SortedArray<T>

    SortedArray is a generic class that maintains a sorted array of items.

    Type Parameters

    • T

    Implements

    Indexable

    • [index: number]: T

      Allows array-like indexing.

    Index

    Constructors

    • Creates a new SortedArray.

      Type Parameters

      • T

      Parameters

      • comparator: (a: T, b: T) => number

        Function to compare two items. Should return a negative number if a < b, zero if a === b, or a positive number if a > b. Comparisons are assumed to be consistent.

      Returns SortedArray<T>

    Accessors

    • get length(): number

      Gets the number of items in the array.

      Returns number

    Methods

    • Returns an iterator for the array.

      Returns Iterator<T>

    • Adds a new value to the sorted array.

      Complexity: O(log(n)) for binary search + O(n) for insertion

      Parameters

      • value: T

        The value to add.

      Returns number

      The index at which the value was inserted.

    • 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.

      Parameters

      • ...values: T[]

        The values to add.

      Returns number[]

      Array of indices, in ascending order, where the values were inserted.

    • Clears the array, removing all elements.

      Complexity: O(1)

      Returns void

    • 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.

      Parameters

      • predicate: (value: T, index: number, obj: readonly T[]) => boolean

        The function used to test each element.

      Returns ISortedArray<T>

      A new ISortedArray containing the elements that match the predicate.

    • Finds the first index of an element that matches using the specified predicate.

      Complexity: O(n) for search

      Parameters

      • predicate: (value: T, index: number, obj: readonly T[]) => boolean

        The function to test each element.

      Returns number

      The index of the first matching element, which will be -1 if not found.

    • Finds all indices of elements that match using the specified predicate.

      Complexity: O(n) for search

      Parameters

      • predicate: (value: T, index: number, obj: readonly T[]) => boolean

        The function to test each element.

      Returns number[]

      The indices of the matching elements, in ascending order, which will be empty if no matches are found.

    • Finds the last index of an element that matches using the specified predicate.

      Complexity: O(n) for search

      Parameters

      • predicate: (value: T, index: number, obj: readonly T[]) => boolean

        The function to test each element.

      Returns number

      The index of the last matching element, which will be -1 if not found.

    • Finds the index of the first element that matches the provided value.

      Complexity: O(log(n))

      Parameters

      • value: T

        The value to find.

      Returns number

      The index of the first matching element, or -1 if not found.

    • Gets the item at the specified index.

      Complexity: O(1)

      Parameters

      • index: number

        The index to access.

      Returns T

      The item at the specified index.

    • Finds the index of the last element that matches the provided value.

      Complexity: O(log(n))

      Parameters

      • value: T

        The value to find.

      Returns number

      The index of the last matching element, or -1 if not found.

    • Removes all elements that match the provided value.

      Complexity: O(log(n)) for search + O(n) for removal

      Parameters

      • value: T

        The value to remove.

      Returns number[]

      Array of former indices of the removed elements (in reverse order).

    • Removes the element at the specified index.

      Complexity: O(n) for removal

      Parameters

      • index: number

        The index of the element to remove.

      Returns number

      The index of the removed element, or -1 if invalid (non-integer) or out of bounds.

    • Removes the elements at the specified indices.

      Complexity: O(n) for rebuilding the array

      Parameters

      • ...indices: number[]

        The indices of the elements to remove.

      Returns number[]

      Array of former indices of the removed elements (in reverse order).

    • Removes the first element that matches the provided value.

      Complexity: O(log(n)) for search + O(n) for removal

      Parameters

      • value: T

        The value to remove.

      Returns number

      The former index of the removed element, or -1 if not found.

    • Removes the last element that matches the provided value.

      Complexity: O(log(n)) for search + O(n) for removal

      Parameters

      • value: T

        The value to remove.

      Returns number

      The former index of the removed element, or -1 if not found.

    • 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.

      Parameters

      • ...values: T[]

        The values to remove.

      Returns number[]

      Array of indices, in descending order, of the items that were removed.