sorted-array

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.

Compatibility

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.

Usage

Installation

npm i @itrocks/sorted-array

Examples

Sorting by Item Value

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.

Sorting by Object Property Value

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.

Sorting with a Custom Comparison Function

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.

When does It Sort?

Sorting occurs on each call to insert() or push().

When does It NOT Sort?

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.

Example

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.

API

Classes

These classes extend the standard JavaScript Array class to provide continuous sorting and fast search capabilities:

SortedArray

This array continuously sorts by item value.

Refer to the Common API for additional enhancements over the standard JavaScript Array class.

SortedArrayBy

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.

SortedArrayBy() constructor

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 and arrayLength parameters function the same as in the standard JavaScript Array constructor.

SortedArrayCompareFn

An array of elements of any type, sorted continuously using a custom comparison function.

Additional property and methods: refer to the Common API.

SortedArrayCompareFn() constructor

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 and arrayLength parameters function the same as in the standard JavaScript Array constructor.

Common API

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:

distinct

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()

insert(element)

Inserts an element into the array in sorted order.

Equivalent to push() with a single argument, but optimized for single-element insertion.

isSorted()

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.

Example

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']