ReadonlySortedArray<T> Class

A read-only view of an array of some type T sorted according to some user-supplied criterion. Duplicate elements may be present, though sub-types may enforce uniqueness of elements. In the absence of duplicates, a ReadonlySortedArray can behave like a Set where T is an object and equality is determined by some criterion other than object identity.

Because the array is always sorted, querying for the presence of an element is performed using binary search, which is more efficient than a linear search for reasonably large arrays.

The comparison function must meet the following criteria, given 'lhs' and 'rhs' of type T:

  • If lhs is equal to rhs, returns 0
  • If lhs is less than rhs, returns a negative value
  • If lhs is greater than rhs, returns a positive value
  • If compare(lhs, rhs) returns 0, then compare(rhs, lhs) must also return 0
  • If compare(lhs, rhs) returns a negative value, then compare(rhs, lhs) must return a positive value, and vice versa.

Note that the array is read-only only from the perspective of its public interface. Mutation methods are defined for internal use by sub-types.

@see SortedArray for a general-purpose mutable sorted array.

Extended by

Implements

  • Iterable<T>

Methods

Name Description
constructor<T>(compare: OrderedComparator<T>, duplicatePolicy: boolean | DuplicatePolicyfalse, clone: CloneFunction<T>shallowClone): ReadonlySortedArray<T> Protected Construct a new ReadonlySortedArray.  
[iterator](): Iterator<T, any, undefined> Returns an iterator over the contents of the array in sorted order, suitable for use in for-of loops.  
_clear(): void Protected Clears the contents of the sorted array.  
_extractArray(): T[] Protected Extracts the sorted array as a T[] and empties the contents of this ReadonlySortedArray.  
_insert(value: T, onInsert?: (value: T) => any): number Protected Attempts to insert a new value into the array at a position determined by the ordering.  
_remove(value: T): number Protected Removes the first occurrence of a value comparing equal to the specified value from the array.  
contains(value: T): boolean Returns true if this array contains at least one value comparing equal to the specified value.  
findEqual(value: T): undefined | T Looks up an element comparing equal to the specified value using binary search.  
findEquivalent(criterion: (element: T) => number): undefined | T Find an element that compares as equivalent based on some criterion.  
forEach(func: (value: T) => void): void Apply a function to each element in the array, in sorted order.  
get(index: number): undefined | T Looks up an element by its index in the array.  
indexOf(value: T): number Looks up the index of an element comparing equal to the specified value using binary search.  
indexOfEquivalent(criterion: (element: T) => number): number Find the index of an element that compares as equivalent based on some criterion.  
lowerBound(value: T): { equal: boolean, index: number } Protected Computes the position at which the specified value should be inserted to maintain sorted order.  
slice(start?: number, end?: number): ReadonlySortedArray<T> The equivalent of Array.slice.  

Properties

Name Type Description
_array Protected T[]    
_clone Protected Readonly CloneFunction<T>    
_compare Protected Readonly OrderedComparator<T>    
_duplicatePolicy Protected Readonly DuplicatePolicy    
isEmpty Accessor ReadOnly boolean Returns true if the array contains no elements.  
length Accessor ReadOnly number The number of elements in the array  

Defined in

Last Updated: 25 May, 2024