Class SortedArray<T, C>

SortedArray is a sorted mutable collection.

SortedArray values are maintained in sorted order.

SortedArray values must have a total ordering. The total ordering of values must not change while they are stored in the SortedArray.

Methods for adding values:

Methods for removing values:

Methods for looking up values:

Methods for iterating values:

Miscellaneous methods and properties:

Type Parameters

  • T extends C

    The element type.

  • C = T

    Part of the element that the comparator function sees.

Hierarchy

  • AbstractSortedArray<T, C>
    • SortedArray

Constructors

constructor

Properties

DEFAULT_LOAD_FACTOR

Accessors

length

Methods

_iter [iterator] add at bisectLeft bisectRight clear clone concat count delete deleteAt deleteSlice entries find forEach includes indexOf irange islice keys pop reversed shift slice toJSON toString update values

Constructors

constructor

  • new SortedArray<T, C = T>(
        iterable?: Iterable<T, any, any>,
        options?: SortedArrayConstructorOptions<C>,
    ): SortedArray<T, C>

    Initialize a sorted container instance.

    Optional iterable argument provides an initial iterable of values to initialize the sorted container.

    Type Parameters

    • T
    • C = T

    Parameters

    • Optionaliterable: Iterable<T, any, any>

      Initial values (optional).

    • Optionaloptions: SortedArrayConstructorOptions<C>

      An object that specifies characteristics about the sorted container.

    Returns SortedArray<T, C>

Properties

StaticDEFAULT_LOAD_FACTOR

DEFAULT_LOAD_FACTOR: number = 1000

The default load factor. Override it with option loadFactor at construction time.

Accessors

length

Methods

_iter

  • _iter(): IteratorObject<T, undefined, unknown>

    Return an iterator over the sorted container.

    Iterating a sorted container while adding or deleting elements may throw an error or silently fail to iterate over all elements.

    Returns IteratorObject<T, undefined, unknown>

[iterator]

add

  • add(value: T): void

    Add value to SortedArray.

    Parameters

    • value: T

      Value to add to SortedArray.

    Returns void

    Example

    const sl = new SortedArray();
    sl.add(3);
    sl.add(1);
    sl.add(2);
    sl // SortedArray [1, 2, 3]

at

  • at(index: number): undefined | T

    Lookup value at index in sorted container.

    If index is out of range, returns undefined.

    Parameters

    • index: number

      The zero-based index of the desired code unit. A negative index will count back from the last item.

    Returns undefined | T

    The item located at the specified index, or undefined if index out of range.

    Example

    const sl = new SortedList('abcde');
    sl.at(1) // 'b'
    sl.at(-1) // 'e'
    sl.at(7) // undefined

bisectLeft

  • bisectLeft(value: C): number

    Return an index to insert value in the sorted container.

    If the value is already present, the insertion point will be before (to the left of) any existing values.

    Parameters

    • value: C

      Value to find the insertion point of.

    Returns number

    Insertion index of value in the sorted container.

    Example

    const sl = new SortedArray([10, 11, 12, 13, 14]);
    sl.bisectLeft(12) // 2

bisectRight

  • bisectRight(value: C): number

    Return an index to insert value in the sorted container.

    Similar to bisectLeft, but if value is already present, the insertion point will be after (to the right of) any existing values.

    Parameters

    • value: C

      Value to find the insertion point of.

    Returns number

    Insertion index of value in the sorted container.

    Example

    const sl = new SortedArray([10, 11, 12, 13, 14]);
    sl.bisectRight(12) // 3

clear

  • clear(): void

    Remove all values from sorted container.

    Returns void

clone

  • clone(): this

    Return a shallow copy of the sorted container.

    Returns this

    A new sorted container.

concat

  • concat(other: Iterable<T>): SortedArray<T>

    Return new SortedArray containing all values in both sequences.

    Values in other do not need to be in sorted order.

    Parameters

    • other: Iterable<T>

      Other iterable.

    Returns SortedArray<T>

    New SortedArray.

    Example

    const sl1 = new SortedArray('bat');
    const sl2 = new SortedArray('cat');
    sl1.concat(sl2) // SortedArray ['a', 'a', 'b', 'c', 't', 't']

count

  • count(value: T): number

    Return number of occurrences of value in the SortedArray.

    Parameters

    • value: T

      Value to count in SortedArray.

    Returns number

    Count.

    Example

    const sl = new SortedArray([1, 2, 2, 3, 3, 3, 4, 4, 4, 4]);
    sl.count(3) // 3

delete

  • delete(value: C): boolean

    Remove one value from sorted container if it is a member.

    If value is not a member, do nothing.

    Parameters

    • value: C

      Value to discard from SortedArray.

    Returns boolean

    Returns true if an element in the SortedArray existed and has been removed, or false if the element does not exist.

    Example

    const sl = new SortedArray([1, 2, 3, 4, 5])
    sl.delete(5)
    sl.delete(0)
    Array.from(sl) // [1, 2, 3, 4]

deleteAt

  • deleteAt(index: number): undefined | T

    Remove and return value at index in sorted container.

    If the sorted container is empty or index is out of range, undefined is returned and the sorted container is not modified.

    Negative indices count back from the last item.

    Parameters

    • index: number

      Index of value. Negative integers count back from the last item in the array.

    Returns undefined | T

    The removed value or undefined.

    Example

    const sl = new SortedArray('abcde');
    sl.deleteAt(-1) // 'e'
    sl.deleteAt(2) // 'c'
    sl // SortedArray ['a', 'b', 'd']

deleteSlice

  • deleteSlice(start?: number, end?: number): void

    Removes elements from sorted container by index.

    Parameters

    • start: number = 0

      The zero-based location in the array from which to start removing elements. Negative integers count back from the last item in the array.

    • end: number = ...

      The zero-based location in the array at which to stop removing elements. Negative integers count back from the last item in the array. Elements up to but not including end are removed.

    Returns void

    Example

    const sl = new SortedArray('abcde');
    sl.deleteSlice(0, 2);
    sl // SortedArray ['c', 'd', 'e']

entries

  • entries(): ArrayIterator<[number, T]>

    Returns an iterable of index-value pairs of elements in the SortedArray.

    Returns ArrayIterator<[number, T]>

find

  • find(value: C): undefined | T

    Return the first element in the sorted container that is equal to the provided value. If it is not found, undefined is returned.

    With the default comparator and primitive elements, this method does not tell anything beyond whether the value exists in the sorted container. However, it can turn out to be useful with a custom comparator.

    Parameters

    • value: C

      The value to find.

    Returns undefined | T

    Example

    const sl = new SortedArray(
      [
        { id: 1, value: 'one' },
        { id: 2, value: 'two' },
        { id: 3, value: 'three' },
      ],
      { comparator: (a, b) => a.id - b.id }
    );
    sl.find({ id: 2 }) // { id: 2, value: 'two' }

forEach

  • forEach(fn: (value: T, index: number, array: this) => void, thisArg?: any): void

    Executes a callback function once for each element in a SortedArray.

    Parameters

    • fn: (value: T, index: number, array: this) => void

      The function to execute.

    • OptionalthisArg: any

      An object to which the this keyword can refer in the callback function. If thisArg is omitted, undefined is used.

    Returns void

includes

  • includes(value: C): boolean

    Return true if value is an element of the SortedArray.

    Parameters

    • value: C

      Search for value in SortedArray.

    Returns boolean

    True if value in SortedArray.

    Example

    const sl = new SortedArray([1, 2, 3, 4, 5]);
    sl.includes(3) // true

indexOf

  • indexOf(value: C, start?: number, end?: number): number

    Return first index of value in the sorted container, or -1 if value is not present.

    Index must be between start and end for the value to be considered present. Negative indices count back from the last item.

    Parameters

    • value: C

      Value in sorted container.

    • start: number = 0

      The array index at which to start the search. If omitted, defaults to 0.

    • end: number = ...

      The array index at which to end the search. If omitted, defaults to the end of the sorted container.

    Returns number

    The index of the first occurrence of value in the sorted container, or -1 if it is not present.

    Example

    const sl = new SortedArray('abcde');
    sl.indexOf('d') // 3
    sl.indexOf('z') // -1

irange

  • irange(
        minimum?: C,
        maximum?: C,
        includeMinimum?: boolean,
        includeMaximum?: boolean,
        reverse?: boolean,
    ): IteratorObject<T, undefined, unknown>

    Create an iterator of values between minimum and maximum.

    Both minimum and maximum default to undefined which is automatically inclusive of the beginning and end of the sorted container.

    The argument includeMinimum and includeMaximum is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. Both arguments default to true such that the range is inclusive of both minimum and maximum.

    When reverse is true the values are yielded from the iterator in reverse order; reverse defaults to false.

    Iterating a sorted container while adding or deleting elements may throw an error or silently fail to iterate over all elements.

    Parameters

    • Optionalminimum: C

      Minimum value to start iterating.

    • Optionalmaximum: C

      Maximum value to stop iterating.

    • includeMinimum: boolean = true

      Whether the minimum ought to be included in the range.

    • includeMaximum: boolean = true

      Whether the maximum ought to be included in the range.

    • reverse: boolean = false

      Whether to yield values in reverse order.

    Returns IteratorObject<T, undefined, unknown>

    Iterator.

    Example

    const sl = new SortedArray('abcdefghij');
    const it = sl.irange('c', 'f');
    Array.from(it) // ['c', 'd', 'e', 'f']

islice

  • islice(
        start?: number,
        end?: number,
        reverse?: boolean,
    ): IteratorObject<T, undefined, unknown>

    Return an iterator that slices sorted container from start to end.

    The start and end index are treated inclusive and exclusive, respectively.

    A negative index will count back from the last item.

    Both start and end default to undefined which is automatically inclusive of the beginning and end of the sorted container.

    When reverse is true the values are yielded from the iterator in reverse order; reverse defaults to false.

    Iterating a sorted container while adding or deleting elements may throw an error or silently fail to iterate over all elements.

    Parameters

    • start: number = 0

      Start index (inclusive).

    • end: number = ...

      Stop index (exclusive).

    • reverse: boolean = false

      Whether to yield values in reverse order.

    Returns IteratorObject<T, undefined, unknown>

    Iterator.

    Example

    const sl = new SortedArray('abcdefghij');
    const it = sl.islice(2, 6);
    Array.from(it) // ['c', 'd', 'e', 'f']

keys

  • keys(): ArrayIterator<number>

    Returns an iterable of integers ranging from 0 (inclusive) to the length of the SortedArray (exclusive).

    Returns ArrayIterator<number>

pop

  • pop(): undefined | T

    Remove the last element from the sorted container and return it. If the sorted container is empty, undefined is returned and the sorted container is not modified.

    Returns undefined | T

    Popped value or undefined.

    Example

    const sl = new SortedArray('abcde');
    sl.pop() // 'e'
    sl.pop() // 'd'
    sl // SortedArray ['a', 'b', 'c']

reversed

  • reversed(): IteratorObject<T, undefined, unknown>

    Return a reverse iterator over the sorted container.

    Iterating a sorted container while adding or deleting elements may throw an error or silently fail to iterate over all elements.

    Returns IteratorObject<T, undefined, unknown>

shift

  • shift(): undefined | T

    Remove the first element from the sorted container and return it. If the sorted container is empty, undefined is returned and the sorted container is not modified.

    Returns undefined | T

    Shifted value or undefined.

    Example

    const sl = new SortedArray('abcde');
    sl.shift() // 'a'
    sl.shift() // 'b'
    sl // SortedArray ['c', 'd', 'e']

slice

  • slice(start?: number, end?: number): T[]

    Returns a copy of a section of sorted container as an ordinary Array.

    For both start and end, a negative index can be used to indicate an offset from the end of the array.

    Parameters

    • start: number = 0

      The beginning index of the specified portion of the array. If start is undefined, then the slice begins at index 0.

    • end: number = ...

      The end index of the specified portion of the array. This is exclusive of the element at the index end. If end is undefined, then the slice extends to the end of the array.

    Returns T[]

toJSON

  • toJSON(): T[]

    Return sorted container as an ordinary Array.

    Returns T[]

toString

  • toString(): string

    Return a string representation of sorted container.

    Returns string

update

  • update(iterable: Iterable<T>): void

    Update sorted container by adding all values from iterable.

    Parameters

    • iterable: Iterable<T>

      Iterable of values to add.

    Returns void

    Example

    const sl = new SortedArray();
    sl.update([3, 1, 2]);
    sl // SortedArray [1, 2, 3]

values

  • values(): ArrayIterator<T>

    Returns an iterable of values in the SortedArray.

    Returns ArrayIterator<T>

Settings

Member Visibility

On This Page

Constructors
Properties
Accessors
Methods