SortedArray
!MIT Licenselicense-imagelicense !Build Statustravis-imagetravis-url !NPM versionnpm-version-imagenpm-urlThis package implements a SortedArray type, which is an array whose contents are always sorted. It supports all standard ES6 Array methods and it provides additional methods relating to keeping elements in a sorted order. It fully supports indexing, enumeration, and a length property.
The package is licensed according to the permissive zlib/libpng license.
Note that the SortedArray type uses the native
Array.sort
method for some functionality, meaning that sort stability
will depend on the platform.
If Array.sort
is stable, however, then all SortedArray sort
and insertion operations will also be stable.const sortedArray = new SortedArray(["alice", "carl", "bob"]);
sortedArray[1]; // "bob"
sortedArray.length; // 3
sortedArray.insert("beatrice"); // ["alice", "beatrice", "bob", "carl"]
sortedArray.indexOf("bob"); // 2 (uses binary search)
sortedArray.pop(); // "carl"
sortedArray.slice(0, 2); // SortedArray(["alice", "beatrice"])
Installation
You can add SortedArray to your JavaScript project by using a package manager to install thesorted-array-type
package. For example:npm install --save sorted-array-type
Import the SortedArray type into your project with
require
or an ES6 import.const SortedArray = require("sorted-array-type");
import SortedArray from "sorted-array-type";
Documentation
You can create a SortedArray object using the constructor or using theof
and from
class methods.The constructor and the
from
static method accept an optional
comparator function.
If no comparator was given, the created SortedArray uses
native JavaScript <
and >
comparisons to sort elements
in ascending order.These functions also accept an optional value equality function. A value equality function should return a truthy value when its two arguments represent identical values, and a falsey value otherwise. This function
valuesEqual(arrayElement, value)
determines, for example,
whether array.indexOf(value)
should return the index of arrayElement
.
When no value equality function is provided, a
SameValueZero
implementation is used by default.When an existing SortedArray is passed to the SortedArray constructor, if the call to the constructor did not specify either the comparator or the value equality function, then the corresponding functions belonging to the input SortedArray will be copied for the new array.
array = new SortedArray(); // []
array = new SortedArray([3, 1, 2]); // [1, 2, 3]
array = new SortedArray([3, 1, 2], (a, b) => b - a); // [3, 2, 1]
array = SortedArray.of(1, 3, 2); // [1, 2, 3]
array = SortedArray.from([1, 3, 2]); // [1, 2, 3]
array = SortedArray.from([1, 3, 2], (a, b) => b - a); // [3, 2, 1]
array = SortedArray.from([1, 3, "2"], // [1, "2", 3]
(a, b) => +a - +b, (a, b) => a == b
);
There are also
ofSorted
and fromSorted
class methods for constructing
a SortedArray. They assume that their input is already sorted.
Passing values to these methods that are not correctly sorted will
cause the SortedArray to behave incorrectly, so use them with care!array = SortedArray.ofSorted(1, 2, 3); // [1, 2, 3]
array = SortedArray.fromSorted([1, 2, 3]); // [1, 2, 3]
array = SortedArray.fromSorted([3, 2, 1], (a, b) => b - a); // [3, 2, 1]
array = SortedArray.fromSorted([1, "2", 3], // [1, "2", 3]
(a, b) => +a - +b, (a, b) => a == b
);
SortedArrays have a
length
property and can be indexed and enumerated
just like normal Arrays.sortedArray = new SortedArray([4, 2, 3, 1]); // [1, 2, 3, 4]
sortedArray[0] // 1
sortedArray.length // 4
for(let element of sortedArray){} // 1, 2, 3, 4
SortedArrays have
insert
and remove
methods. They should be used
to add and remove elements.
You should not normally push
to a SortedArray, and you should
consider using remove
to be better practice than using indexOf
and slice
, though both options will work.The
remove
method returns true
when the value was found in the array
and removed from it and false
otherwise.
The method is complemented by the removeLast
and removeAll
methods.
Where remove
removes the first equal value, removeLast
removes the
last equal value.
removeAll
removes all equal values and returns them in a new SortedArray.There is also an
insertSorted
method, which can be used to efficiently
insert the contents of another iterable which is already sorted according
to the same comparison function.
Passing iterables to the insertSorted
method that are not correctly sorted
will cause the SortedArray to behave incorrectly, so use it with care!The
getEqualValues
method returns all elements in the array equal to
an input, according to its value equality function. (SameValueZero by default.)
Where comparator(a, b) === 0
does not necessarily imply valuesEqual(a, b)
,
it is important to use this method instead of, for example,
slicing from indexOf(value)
to lastIndexOf(value)
.sortedArray = new SortedArray();
sortedArray.insert(1); // Insert 1. Returns the new length of the array.
sortedArray.insertSorted([1, 2, 3, 4]); // Insert already-sorted values.
sortedArray.remove(1); // Remove 1. True if the value was in the array.
sortedArray.removeLast(1); // Remove the last 1. True if successful.
sortedArray.removeAll(2); // Remove all 2. Returns a SortedArray.
sortedArray.getEqualValues(3); // Get a SortedArray of values equal to 3.
SortedArrays support all of the standard ES6 Array methods and properties. They are summarized briefly here, and you should refer to more detailed documentation for more complete information about these methods.
- ! means a method should be used with caution. (Read more below.)
- % means a method is usually faster with a SortedArray than a normal Array.
All methods not marked with a ! can be used safely; they should never invalidate a SortedArray's guarantee of correct ordering, no matter how they are used or what inputs they are given. This includes the
sort
and reverse
methods, which cause later
operations to use the same new ordering.Methods like
indexOf
or remove
which involve comparisons for finding
an exact element in the array all use
SameValueZero
for comparisons by default.
A different value equality function can be passed as an argument to the
SortedArray
constructor or to the from
and fromSorted
static methods.sortedArray.concat(); // Returns a new, concatenated Array.
sortedArray.copyWithin(); // Copies elements. [!]
sortedArray.entries(); // Returns an iterator of [index, value] pairs.
sortedArray.every(); // True when every element satisfies the predicate.
sortedArray.fill(); // Fill the array with values. [!]
sortedArray.filter(); // Returns a new, filtered SortedArray.
sortedArray.find(); // Get the first matching element.
sortedArray.findIndex(); // Get the index of the first matching element.
sortedArray.flat(); // Returns a flattened Array.
sortedArray.flatMap(); // Returns a flattened mapped Array.
sortedArray.forEach(); // Invokes for every element in the array.
sortedArray.includes(); // True when a value is in the array. [%]
sortedArray.indexOf(); // First index of value, or -1 if not present. [%]
sortedArray.join(); // Join elements to produce a string.
sortedArray.keys(); // Returns an iterator of indexes in the array.
sortedArray.lastIndexOf(); // Last index of value; -1 if not present. [%]
sortedArray.map(); // Map elements in the array to produce a new Array.
sortedArray.pop(); // Remove and return the last element in the array.
sortedArray.push(); // Append a new element to the end of the array. [!]
sortedArray.reduce(); // Reduce the array.
sortedArray.reduceRight(); // Reduce the array, backwards.
sortedArray.reverse(); // Reverse and permanently invert sort order.
sortedArray.shift(); // Remove and return the first element in the array.
sortedArray.slice(); // Get a slice as another SortedArray.
sortedArray.some(); // True if any element matches a predicate.
sortedArray.sort(); // Re-sort and update the array with a new comparator.
sortedArray.splice(); // Remove and/or insert elements in the array. [!]
sortedArray.toLocaleString(); // Get a localized string representation.
sortedArray.toString(); // Get a string representation of the array.
sortedArray.unshift(); // Prepend value to the start of the array. [!]
sortedArray.values(); // Returns an iterator of values in the array.
Also of interest are the
firstInsertionIndexOf
and lastInsertionIndexOf
methods. These return the first index and the last index, respectively,
where a value can be found or should be inserted into the array.sortedArray.firstInsertionIndexOf(x);
sortedArray.lastInsertionIndexOf(x);
Some operations, if used carelessly, can cause the SortedArray's contents to no longer be in sorted order. DON'T DO THIS! Invalidating the SortedArray's assumption that its contents are always in a sorted order will cause incorrect behavior. Use these tools with care!
// USE WITH CAUTION!
sortedArray[0] = x;
sortedArray.length = x;
sortedArray.push(x);
sortedArray.unshift(x);
sortedArray.splice(0, 0, x);
sortedArray.fill(x, 0, 1);
sortedArray.copyWithin(0, 1, 2);