Array subclasses that remain continuously sorted on insert() or push() calls, featuring optimized includes() and indexOf().
This design makes inserting or pushing elements slower but accelerates searches, without the overhead of using a Map or a Set.
Sorting can be based on:
- the item's value,
- a specific property of an object item,
- a custom comparison function.
Isomorphic, load-anywhere, and typescript typed:
- Written in Typescript; the types declaration files are included in this package,
- Can be required or imported in any CommonJS or ES6 script running in node.js or your browser.
npm i @itrocks/sorted-array
import { SortedArray } from '@itrocks/sorted-array'
const array = new SortedArray(4, 10, 12)
array.push(7)
//> [4, 7, 10, 12]
See SortedArray for more information.
import { SortedArrayBy } from '@itrocks/sorted-array'
const array = new SortedArrayBy('name',
{ age: 10, name: 'Paul' },
{ age: 4, name: 'Robert' },
{ age: 12, name: 'William' }
)
array.push({ age: 7, name: 'Philip' })
/*> [
{ age: 10, name: 'Paul' },
{ age: 7, name: 'Philip' },
{ age: 4, name: 'Robert' },
{ age: 12, name: 'William' }
] */
See SortedArrayBy for more information.
import { SortedArrayCompareFn } from '@itrocks/sorted-array'
const array = new SortedArrayCompareFn((a, b) => (a.open + a.close) - (b.open + b.close),
{ open: 0, close: 4 },
{ open: 3, close: 47 },
{ open: 4, close: 80 }
)
array.push({ open: 2, close: 50 })
/*>[
{ open: 0, close: 4 },
{ open: 3, close: 47 },
{ open: 2, close: 50 },
{ open: 4, close: 80 }
] */
See SortedArrayCompareFn for more information.
Sorting occurs on each call to insert() or push().
If elements are passed as arguments to the constructor, they are expected to be pre-sorted and won’t be sorted again. This allows for faster storage and retrieval of pre-sorted arrays.
If you're unsure whether your source data is sorted, you can call sort() to apply sorting.
import { SortedArray } from '@itrocks/sorted-array'
const array = new SortedArray('Rupert', 'Mary', 'Francesca')
//> ['Rupert', 'Mary', 'Francesca']
array.sort()
//> ['Francesca', 'Mary', 'Rupert']
Both SortedArrayBy and SortedArrayCompareFn behave similarly.
These classes extend the standard JavaScript Array class to provide continuous sorting and fast search capabilities:
This array continuously sorts by item value.
Refer to the Common API for additional enhancements over the standard JavaScript Array class.
An array of objects continuously sorted by a specific property value, or an array of arrays continuously sorted by a value at a specified index.
Additional property and methods: refer to the Common API.
new SortedArrayBy(compareBy)
new SortedArrayBy(compareBy, element1)
new SortedArrayBy(compareBy, element1, element2)
new SortedArrayBy(compareBy, element1, /* ..., */ elementN)
new SortedArrayBy(compareBy, arrayLength)
-
If
compareBy
is a number, it specifies the index of each inner array's element that will be used for comparison. Example:new SortedArrayBy(1, ['a', 'c', 'b'], ['r', 'd', 'a'])
The array will be continuously sorted by the 2nd element of the array (index 1), comparing
'c'
and'd'
in this example. -
If
compareBy
is a number or a string, it specifies the property name by which object elements will be compared. Example:new SortedArrayBy('name', { age: 30, name: 'Henry', age: 20, name: 'Johana' })
The array will be continuously sorted by the value of the
name
property in each object element. -
The
elements
andarrayLength
parameters function the same as in the standard JavaScript Array constructor.
An array of elements of any type, sorted continuously using a custom comparison function.
Additional property and methods: refer to the Common API.
new SortedArrayCompareFn(compareFn)
new SortedArrayCompareFn(compareFn, element1)
new SortedArrayCompareFn(compareFn, element1, element2)
new SortedArrayCompareFn(compareFn, element1, /* ..., */ elementN)
new SortedArrayCompareFn(compareFn, arrayLength)
-
The
compareFn
parameter must be provided as a comparison function, which will be used by the standard sort() method if no specific comparaison function is passed as an argument. -
The
elements
andarrayLength
parameters function the same as in the standard JavaScript Array constructor.
All standard methods and properties from the parent Array class apply.
Notable behaviour changes:
- push() will insert elements in sorted order rather than appending them at the end.
-
includes()
and indexOf()
are optimized for a continously sorted array. They may not work as expected if:
- elements passed to the constructor are unsorted,
- a custom comparison function is used with sort().
Additional property and methods include:
The distinct
property of a SortedArray
instance determine whether to ignore duplicates during insertion
with insert()
or push().
Defaults to false
. Set to true
to prevent duplicate entries.
insert(element)
Inserts an element into the array in sorted order.
Equivalent to push() with a single argument, but optimized for single-element insertion.
Scan the entire array to verify if it is sorted according to the SortedArray algorithm.
Returns true
if the array is sorted.
After calling
sort()
without arguments, isSorted()
will always return true
.
This checks the array's order before sorting:
import { SortedArray } from '@itrocks/sorted-array'
const array = new SortedArray('Rupert', 'Mary', 'Francesca')
//> ['Rupert', 'Mary', 'Francesca']
if (!array.isSorted())
array.sort()
//> ['Francesca', 'Mary', 'Rupert']