packageDocumentation module import { OrderedComparator } from "./Compare" ; public export type CloneFunction < T > = ( value : T ) => T ; param value returns public export function shallowClone < T > ( value ) { return value ; } param value param list param compare returns public export function lowerBound < T , U = T > ( value , list , compare ) { return lowerBoundOfEquivalent ( list , ( element ) => compare ( value , element ) ) ; } function lowerBoundOfEquivalent < T > ( list , criterion ) { let low = 0 ; let high = list . length ; while ( low < high ) { const mid = Math . floor ( ( low + high ) / 2 ) ; const comp = criterion ( list [ mid ] ) ; if ( 0 === comp ) return { index : mid , equal : true } ; else if ( comp < 0 ) high = mid ; else low = mid + 1 ; } return { index : low , equal : false } ; } public export enum DuplicatePolicy { note Allow , /** Duplicate values are forbidden - when attempting to insert a value equivalent to one already present, the already-present value is retained. */ Retain , /** Duplicate values are forbidden - when attempting to insert a value equivalent to one already present, the already-present value is replaced by the new value.
     * This can be useful when the value type carries additional data that is not evaluated by the comparison function.
     */ Replace } see public export class ReadonlySortedArray < T > implements Iterable < T > { protected _array : T [ ] = [ ] ; protected readonly _compare : OrderedComparator < T > ; protected readonly _clone : CloneFunction < T > ; protected readonly _duplicatePolicy : DuplicatePolicy ; param compare param duplicatePolicy param clone protected constructor ( compare , duplicatePolicy = false , clone = shallowClone ) { this . _compare = compare ; this . _clone = clone ; if ( typeof duplicatePolicy === "boolean" ) duplicatePolicy = duplicatePolicy ? DuplicatePolicy . Allow : DuplicatePolicy . Retain ; this . _duplicatePolicy = duplicatePolicy ; } /** The number of elements in the array */ public get length ( ) : number { return this . _array . length ; } /** Returns true if the array contains no elements. */ public get isEmpty ( ) : boolean { return 0 === this . length ; } /** Returns an iterator over the contents of the array in sorted order, suitable for use in `for-of` loops. */ public [ Symbol . iterator ] ( ) { return this . _array [ Symbol . iterator ] ( ) ; } param value returns public indexOf ( value ) { const bound = this . lowerBound ( value ) ; return bound . equal ? bound . index : - 1 ; } param value returns public contains ( value ) { return - 1 !== this . indexOf ( value ) ; } param value returns public findEqual ( value ) { const index = this . indexOf ( value ) ; return - 1 !== index ? this . _array [ index ] : undefined ; } param criterion returns see public public findEquivalent ( criterion ) { const index = this . indexOfEquivalent ( criterion ) ; return - 1 !== index ? this . _array [ index ] : undefined ; } param criterion returns public public indexOfEquivalent ( criterion ) { const bound = lowerBoundOfEquivalent ( this . _array , ( elem ) => 0 - criterion ( elem ) ) ; return bound . equal ? bound . index : - 1 ; } param index returns public get ( index ) { return index < this . length ? this . _array [ index ] : undefined ; } param func public forEach ( func ) { for ( let i = 0 ; i < this . length ; i ++ ) func ( this . _array [ i ] ) ; } param value returns protected lowerBound ( value ) { return lowerBound ( value , this . _array , this . _compare ) ; } /** Clears the contents of the sorted array. */ protected _clear ( ) { this . _array . length = 0 ; } returns protected _extractArray ( ) { const result = this . _array ; this . _array = [ ] ; return result ; } param value param onInsert returns protected _insert ( value , onInsert ? ) { const bound = this . lowerBound ( value ) ; if ( bound . equal ) { switch ( this . _duplicatePolicy ) { case DuplicatePolicy . Retain : return bound . index ; case DuplicatePolicy . Replace : this . _array [ bound . index ] = this . _clone ( value ) ; if ( onInsert ) onInsert ( value ) ; return bound . index ; } } this . _array . splice ( bound . index , 0 , this . _clone ( value ) ) ; if ( undefined !== onInsert ) onInsert ( value ) ; return bound . index ; } param value returns protected _remove ( value ) { const bound = this . lowerBound ( value ) ; if ( bound . equal ) { this . _array . splice ( bound . index , 1 ) ; return bound . index ; } else { return - 1 ; } } } public export class SortedArray < T > extends ReadonlySortedArray < T > { param compare param duplicatePolicy param clone public constructor ( compare , duplicatePolicy = false , clone = shallowClone ) { super ( compare , duplicatePolicy , clone ) ; } /** Clears the contents of the sorted array. */ public clear ( ) { this . _clear ( ) ; } returns public extractArray ( ) { return this . _extractArray ( ) ; } param value param onInsert returns public insert ( value , onInsert ? ) { return this . _insert ( value , onInsert ) ; } param value returns public remove ( value ) { return this . _remove ( value ) ; } }