Latest
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639import type { IndexedCollection } from "./utility-types.ts";
export type Comparator<T> = (a: T, b: T) => -1 | 0 | 1;
/** * Extends Array to handle sorted data. */export class SortedArray<ItemType> extends Array<ItemType> { unique = false;
/** * The default comparator. * * @param a the first value * @param b the second value * @throws RangeError if the comparison is unstable */ static compare<T>(a: T, b: T): -1 | 0 | 1 { if (a > b) return 1; if (a < b) return -1; if (a === b) return 0; throw new RangeError("Unstable comparison."); }
/** * Creates a new SortedArray from a given array-like object. */ static from<T>(iterable: Iterable<T> | ArrayLike<T>): SortedArray<T>;
static from<T, U>( iterable: Iterable<T> | ArrayLike<T>, mapfn?: (v: T, k: number) => U, thisArg?: unknown, ): SortedArray<U> { const result = (mapfn !== undefined ? super.from(iterable, mapfn, thisArg) : super.from(iterable)) as SortedArray<U>; result.sort(); return result; }
/** * Returns the difference of two sorted arrays, * i.e. elements present in the first array but not in the second array. * If `symmetric=true` finds the symmetric difference of two arrays, that is, * the elements that are absent in one or another array. * * @param a the first array * @param b the second array * @param [symmetric=false] whether to get symmetric difference. * @param [comparator] the comparator static used to sort the arrays * @param [container] an array-like object to hold the results * @return the difference of the arrays * @example * * SortedArray.getDifference([1, 2, 3, 4, 8], [2, 4, 6, 7, 9]); * //=> [ 1, 3, 8 ] * * // symmetric difference of sorted arrays: * SortedArray.getDifference(first, second, true); * //=> [ 1, 3, 6, 7, 8, 9 ]
* // difference using a custom comparator: * const customComparator = (a, b) => (a > b ? -1 : a < b ? 1 : 0); * SortedArray.getDifference([8, 4, 3, 2, 1], [9, 7, 6, 4, 2], false, customComparator); * //=> [ 8, 3, 1 ] */ static getDifference<T, U extends IndexedCollection<T>>( a: U, b: U, symmetric = false, comparator: Comparator<T> = this.compare, container: U = ([] as unknown) as U, ): typeof container { let i = 0; let j = 0; while (i < a.length && j < b.length) { const compared = comparator(a[i], b[j]); if (compared > 0) { if (symmetric) container[container.length] = b[j]; j++; } else if (compared < 0) { container[container.length] = a[i]; i++; } else { i++; j++; } } while (i < a.length) { container[container.length] = a[i]; i++; } if (symmetric) { while (j < b.length) { container[container.length] = b[j]; j++; } } return container; }
/** * Returns the amount of differing elements in the first array. * * @param a the first array * @param b the second array * @param [symmetric=false] whether to use symmetric difference * @param [comparator] the comparator static used to sort the arrays * @return the amount of differing elements * @example * * SortedArray.getDifferenceScore([1, 2, 3, 4, 8], [2, 4, 6, 7, 9]); * //=> 3 */ static getDifferenceScore<T, U extends IndexedCollection<T>>( a: U, b: U, symmetric = false, comparator = this.compare, ): number { const score = this.getIntersectionScore(a, b, comparator); return symmetric ? a.length + b.length - 2 * score : a.length - score; }
/** * Uses binary search to find the index of an element inside a sorted array. * * @param arr the array to search * @param target the target value to search for * @param [comparator] a custom comparator * @param [rank=false] whether to return the element's rank if the element isn't found * @param [start] the start position of the search * @param [end] the end position of the search * @return the index of the searched element or it's rank * @example * * SortedArray.getIndex([1, 2, 3, 4, 8], 4); * //=> 3 */ static getIndex<T, U extends IndexedCollection<T>>( arr: U, target: T, comparator: Comparator<T> = this.compare, rank = false, start = 0, end = arr.length - 1, ): number { let left = start; let right = end; let m; while (left <= right) { m = (left + right) >> 1; const compared = comparator(arr[m], target); if (compared < 0) { left = m + 1; } else if (compared > 0) { right = m - 1; } else { return m; } } return rank ? left : -1; }
/** * Returns the intersection of two sorted arrays. * * @param a the first array * @param b the second array * @param [comparator] the comparator static used to sort the arrays * @param [container] an array-like object to hold the results * @return the intersection of the arrays * @example * * SortedArray.getIntersection([1, 2, 3, 4, 8], [2, 4, 6, 7, 9]); * //=> [ 2, 4 ] * * // intersection using a custom comparator: * const customComparator = (a, b) => (a > b ? -1 : a < b ? 1 : 0); * SortedArray.getIntersection([8, 4, 3, 2, 1], [9, 7, 6, 4, 2], customComparator); * //=> [ 4, 2 ] */ static getIntersection<T, U extends IndexedCollection<T>>( a: U, b: U, comparator: Comparator<T> = this.compare, container: U = ([] as unknown) as U, ): U { let i = 0; let j = 0; while (i < a.length && j < b.length) { const compared = comparator(a[i], b[j]); if (compared > 0) { j++; } else if (compared < 0) { i++; } else { container[container.length] = a[i]; i++; j++; } } return container; }
/** * Returns the amount of common elements in two sorted arrays. * * @param a the first array * @param b the second array * @param [comparator] the comparator static used to sort the arrays * @return the amount of different elements * @example * * SortedArray.getIntersection([1, 2, 3, 4, 8], [2, 4, 6, 7, 9]); * //=> 2 */ static getIntersectionScore<T, U extends IndexedCollection<T>>( a: U, b: U, comparator: Comparator<T> = this.compare, ): number { let score = 0; let i = 0; let j = 0; while (i < a.length && j < b.length) { const compared = comparator(a[i], b[j]); if (compared > 0) { j++; } else if (compared < 0) { i++; } else { score++; i++; j++; } } return score; }
/** * Returns a range of elements of a sorted array from the start through the end inclusively. * * @param arr the array * @param [start] the starting item * @param [end] the ending item * @param [comparator] a custom comparator * @param [subarray] return a subarray instead of copying resulting value with slice * @return the range of items * @example * * SortedArray.getRange([1, 2, 3, 4, 8], 2, 4); * //=> [ 2, 3, 4 ] * * const customComparator = (a, b) => (a > b ? -1 : a < b ? 1 : 0); * SortedArray.getRange([8, 4, 3, 2, 1], 8, 3, customComparator); * //=> [ 8, 4, 3 ] */ static getRange<T, U extends IndexedCollection<T>>( arr: U, start?: T, end?: T, comparator?: Comparator<T>, subarray?: boolean, ): U { const startIndex = start === undefined ? 0 : this.getIndex<T, U>(arr, start, comparator, true); const endIndex = end === undefined ? arr.length : this.getIndex(arr, end, comparator, true, startIndex) + 1; return subarray ? (arr as unknown as Int32Array).subarray(startIndex, endIndex) : // deno-lint-ignore no-explicit-any (arr as any).slice(startIndex, endIndex); }
/** * Returns the union of two sorted arrays as a sorted array. * * @param a the first array * @param b the second array * @param [unique=false] whether to avoid duplicating items when merging unique arrays * @param [comparator] the comparator static used to sort the arrays * @param [container] an array-like object to hold the results * @return the union of the arrays * @example * * SortedArray.getUnion([1, 2, 3, 4, 8], [2, 4, 6, 7, 9]); * //=> [ 1, 2, 2, 3, 4, 4, 6, 7, 8, 9 ] * * // union of sorted arrays without duplicates: * SortedArray.getUnion([1, 2, 3, 4, 8], [2, 4, 6, 7, 9], true); * //=> [ 1, 2, 3, 4, 6, 7, 8, 9 ] * * //union using a custom comparator: * SortedArray.getUnion([8, 4, 3, 2, 1], [9, 7, 6, 4, 2], true, customComparator); * //=> [ 9, 8, 7, 6, 4, 3, 2, 1 ] */ static getUnion<T, U extends IndexedCollection<T>>( a: IndexedCollection<T>, b: IndexedCollection<T>, unique = false, comparator: Comparator<T> = this.compare, container: U = ([] as unknown) as U, ): U { let i = 0; let j = 0; while (i < a.length && j < b.length) { const compared = comparator(a[i], b[j]); if (compared > 0) { container[container.length] = b[j]; j++; } else if (compared < 0) { container[container.length] = a[i]; i++; } else { container[container.length] = a[i]; if (!unique) container[container.length] = b[j]; i++; j++; } } while (i < a.length) { container[container.length] = a[i]; i++; } while (j < b.length) { container[container.length] = b[j]; j++; } return container; }
/** * Returns an array of unique elements from a sorted array. * * @param arr the sorted array * @param [comparator] a custom comparator * @param [container] an array-like object to hold the results * @return the sorted array without duplicates * @example * * SortedArray.getUnique([1, 1, 2, 2, 3, 4]); * //=> [ 1, 2, 3, 4 ] */ static getUnique<T, U extends IndexedCollection<T>>( arr: IndexedCollection<T>, comparator: Comparator<T> = this.compare, container: U = ([] as unknown) as U, ): typeof container { container[0] = arr[0]; for (let i = 1; i < arr.length; i++) { if (comparator(arr[i - 1], arr[i]) !== 0) { container[container.length] = arr[i]; } } return container; }
/** * Checks whether an array is sorted according to a provided comparator. * * @param arr the array to check * @param [comparator] a custom comparator * @return whether the array is sorted * * @example * * SortedArray.isSorted([1, 2, 3, 4, 8]); * //=> true */ static isSorted<T, U extends IndexedCollection<T>>( arr: U, comparator: Comparator<T> = this.compare, ): boolean { for (let i = 1; i < arr.length; i++) { if (comparator(arr[i - 1], arr[i]) > 0) return false; } return true; }
/** * Checks whether an array has any duplicating elements. * * @param arr the array to check * @param [comparator] a custom comparator * @return whether the array has duplicating elements * @example * * SortedArray.isUnique([1, 2, 2, 3, 4]); * //=> false */ static isUnique<T, U extends IndexedCollection<T>>( arr: U, comparator: Comparator<T> = this.compare, ) { for (let i = 1; i < arr.length; i++) { if (comparator(arr[i - 1], arr[i]) === 0) return false; } return true; }
/** * Creates a new SortedArray instance with a variable number of arguments, * regardless of number or type of the arguments * * @param elements the elements of which to create the array * @return the new SortedArray */ static of<U>(...elements: Array<U>): SortedArray<U> { const result = (super.of(...elements) as unknown) as SortedArray<U>; result.sort(); return result; }
/** * Returns a merger of the array with one or more provided sorted arrays. * * @param arrays sorted array(s) to merge * @return a new SortedArray */ concat(...arrays: Array<Array<ItemType>>): SortedArray<ItemType> { const constructor = this.constructor as typeof SortedArray; let result = this.slice(0) as SortedArray<ItemType>; // TODO rewrite for (let i = 0; i < arrays.length; i++) { result = constructor.getUnion( result, arrays[i], this.unique, constructor.compare, new constructor<ItemType>() as this, ); } return result; }
/** * Uses binary search to quickly check if the element is the array. * @param element the element to check * @return whether the element is in the array */ includes(element: ItemType): boolean { return !!~this.indexOf(element); }
/** * Looks for the index of a given element in the array or -1 * * @param element the element to look for * @return the element's index in the array or -1 */ indexOf(element: ItemType): number { return (this.constructor as typeof SortedArray).getIndex(this, element); }
/** * Checks if the array is sorted. * * @return whether the array is sorted * @example * * //=> SortedArray [ 2, 3, 4, 5, 9 ]; * SortedArray.isSorted(); * //=> true * SortedArray.reverse(); * SortedArray.isSorted(); * //=> false; */ isSorted(): boolean { return (this.constructor as typeof SortedArray).isSorted(this); }
/** * Checks if the array has duplicating elements. * * @return whether the array has duplicating elements * @example * * //=> SortedArray [ 2, 3, 3, 4, 5, 9 ]; * SortedArray.isUnique(); * //=> false; */ isUnique(): boolean { return (this.constructor as typeof SortedArray).isUnique(this); }
/** * Adds provided elements to the array preserving the sorted order of the array. * * @param elements the elements to add to the array * @return the new length of the array */ push(...elements: Array<ItemType>): number { const { compare } = this.constructor as typeof SortedArray; const m = this.length; if (!m) return super.push(...elements.sort(compare)); const toAdd = this.unique ? elements.filter((el) => !~this.indexOf(el)) : elements; const n = toAdd.length; if (!n) return m; toAdd.sort(compare); for (let i = n - 1; i >= 0; i--) { let j; const last = this[m - 1]; for (j = m - 2; j >= 0 && compare(this[j], toAdd[i]) === 1; j--) { this[j + 1] = this[j]; } if (j !== m - 2 || compare(last, toAdd[i]) === 1) { this[j + 1] = toAdd[i]; toAdd[i] = last; } } return super.push(...toAdd); }
/** * Returns a range of elements of the array that are greater or equal to the provided * starting element and less or equal to the provided ending element. * * @param start the starting element * @param end the ending element * @return the resulting range of elements * @example * * //=> SortedArray [ 2, 3, 4, 5, 9 ]; * SortedArray.range(3, 5); * // => [ 3, 4, 5 ] * SortedArray.range(undefined, 4); * // => [ 2, 3, 4 ] * SortedArray.range(4); * // => [ 4, 5, 8 ] */ range(start?: ItemType, end?: ItemType): SortedArray<ItemType> { const constructor = this.constructor as typeof SortedArray; return constructor.getRange(this, start, end, constructor.compare, false); }
/** * Returns the rank of an element in the array. * * @param element the element to look for * @return the rank in the array * @example * * //=> SortedArray [ 2, 3, 4, 5, 9 ]; * SortedArray.rank(1); * // => 0 * SortedArray.rank(6); * // => 4 */ rank(element: ItemType): number { const constructor = this.constructor as typeof SortedArray; return constructor.getIndex(this, element, constructor.compare, true); }
/** * Implements in-place replacement of the array elements. * * @param arr an array of new elements to use * * @example * * //=> SortedArray [ 2, 3, 4, 5, 9 ]; * sortedArray.set([1, 2, 3]); * //=> SortedArray [ 1, 2, 3 ] */ set(arr: Array<ItemType>): this { this.length = arr.length; for (let i = 0; i < arr.length; i++) { this[i] = arr[i]; } return this; }
/** * Sorts the array with a provided compare function. * * @param compareFunction the function to use for comparison */ sort( compareFunction: Comparator<ItemType> = (this .constructor as typeof SortedArray).compare, ): this { return super.sort(compareFunction); }
/** * Changes the array by removing existing elements and adding new ones. * * @param start the index at which to start changing the array * @param deleteCount the amount of old elements to delete * @param elements the elements to add to the array * @return an array of deleted elements */ splice( start: number, deleteCount: number, ...elements: Array<ItemType> ): SortedArray<ItemType> { const deletedElements = super.splice( start, deleteCount, ) as SortedArray<ItemType>; this.push(...elements); return deletedElements; }
/** * Removes duplicating elements from the array. * * @example * * //=> SortedArray [ 2, 2, 3, 4, 5, 5, 9 ]; * sortedArray.uniquify(); * // => SortedArray [ 2, 3, 4, 5, 9 ] */ uniquify() { const constructor = this.constructor as typeof SortedArray; return this.set( constructor.getUnique(this, constructor.compare, new constructor()), ); }
/** * Adds provided elements to the array preserving the sorted order of the array. * * @param elements the elements to add to the array * @return the new length of the array */ unshift(...elements: Array<ItemType>) { return this.push(...elements); }}