Ordino

A class extending built-in Array to efficiently handle sorted data.

Installation

npm i ordino -S 

Usage

Import the class:

const SortedArray = require('ordino');

To create a SortedArray from unsorted array-like objects or items use SortedArray.from and SortedArray.of respectively:

SortedArray.from(unsorted);
//=> SortedArray [ 2, 3, 4, 5, 9 ]
SortedArray.of(8, 5, 6);
//=> SortedArray [ 5, 6, 8 ]

new SortedArray behaves the same way as new Array and should be used with already sorted elements:

new SortedArray(...first);
//=> SortedArray [ 1, 2, 3, 4, 8 ];
new SortedArray(2,3,4);
//=> SortedArray [ 2, 3, 4 ];

A custom comparison function can be specified on the array instance to be use for sorting:

sortedArray.compare = (a, b) => (a > b ? -1 : a < b ? 1 : 0);
sortedArray.sort();
//=> [ 9, 5, 4, 3, 2 ]

SortedArray supports all methods of Array. The methods that change the contents of an array do so while preserving the sorted order:

sortedArray.push(1);
//=> SortedArray [ 1, 2, 3, 4, 5, 9 ]
sortedArray.unshift(8);
//=> SortedArray [ 1, 2, 3, 4, 5, 8, 9 ]
sortedArray.splice(0, 2, 6);
//=> SortedArray [ 3, 4, 5, 6, 8, 9 ]

indexOf and includes use binary search that increasingly outperforms the built-in methods as the size of the array grows.

In addition to the Array instance methods, SortedArray provides isSorted method to check is the array is sorted, and range method to get elements of the array whose values are between the specified range:

sortedArray.range(3, 5);
// => [ 3, 4, 5 ]
sortedArray.range(undefined, 4);
// => [ 2, 3, 4 ]
sortedArray.range(4);
// => [ 4, 5, 8 ]

uniquify can be used to remove duplicating elements from the array:

const a = SortedArray.from([ 1, 1, 2, 2, 3, 4 ]);
a.uniquify();
//=> SortedArray [ 1, 2, 3, 4 ]

SortedArray also provides a set of functions to perform common set operations and find statistics of any sorted array-like objects without converting them to SortedArrays:

const SortedArray = require('ordino');

const first = [1, 2, 3, 4, 8];
const second = [2, 4, 6, 7, 9];
const inversedFirst = [8, 4, 3, 2, 1];
const inversedSecond = [9, 7, 6, 4, 2];
const customComparator = (a, b) => (a > b ? -1 : a < b ? 1 : 0);

// the intersection of sorted arrays:
SortedArray.getIntersection(first, second);
//=> [ 2, 4 ]

// intersection using a custom comparator:
SortedArray.getIntersection(inversedFirst, inversedSecond, customComparator);
//=> [ 4, 2 ]

// intersection score of sorted arrays:
SortedArray.getIntersectionScore(first, second);
//=> 2

// difference of sorted arrays:
SortedArray.getDifference(first, second);
//=> [ 1, 3, 8 ]

// difference score of sorted arrays:
SortedArray.getDifferenceScore(first, second);
//=> 3

// symmetric difference of sorted arrays:
SortedArray.getDifference(first, second, true);
//=> [ 1, 3, 6, 7, 8, 9 ]

// difference using a custom comparator:
SortedArray.getDifference(inversedFirst, inversedSecond, false, customComparator);
//=> [ 8, 3, 1 ]

// union of sorted arrays:
SortedArray.getUnion(first, second);
//=> [ 1, 2, 2, 3, 4, 4, 6, 7, 8, 9 ]

// union of sorted arrays without duplicates:
SortedArray.getUnion(first, second, true);
//=> [ 1, 2, 3, 4, 6, 7, 8, 9 ]

// union using a custom comparator:
SortedArray.getUnion(inversedFirst, inversedSecond, true, customComparator);
//=> [ 9, 8, 7, 6, 4, 3, 2, 1 ]

// index of an item in a sorted array:
SortedArray.getIndex(first, 4);
//=> 3
SortedArray.getIndex(inversedFirst, 2, customComparator)
//=> 3

// rank of an item in a sorted array:
SortedArray.getRank(second, 5);
//=> 2
SortedArray.getRank(inversedSecond, 5, customComparator)
//=> 3

// range
SortedArray.getRange(first, 2, 4);
//=> [ 2, 3, 4 ]
SortedArray.getRange(inversedFirst, 8, 3, customComparator);
//=> [ 8, 4, 3 ]

// an array of unique elements
SortedArray.getUnique([1, 1, 2, 2, 3, 4]);
//=> [ 1, 2, 3, 4 ]

// check whether an array is sorted:
SortedArray.isSorted(first);
//=> true
SortedArray.isSorted(inversedFirst);
//=> false
SortedArray.isSorted(inversedFirst, customComparator);
//=> true

// check whether an array has duplicating elements:
SortedArray.isUnique(first);
//=> true
SortedArray.isUnique([1, 2, 2, 3, 4]);
//=> false
SortedArray.isUnique(inversedFirst, customComparator);
//=> true

Benchmark

> node benchmark.js

Construction:
   ordino x 15,359 ops/sec ±1.06% (89 runs sampled)
   sorted x 8,851 ops/sec ±1.12% (92 runs sampled)
 Fastest is ordino

Concat:
   ordino x 148,013 ops/sec ±0.91% (89 runs sampled)
   sorted x 6,908 ops/sec ±1.08% (89 runs sampled)
   native x 5,122 ops/sec ±0.87% (88 runs sampled)
 Fastest is ordino

Find Index:
   ordino x 8,011,612 ops/sec ±1.02% (89 runs sampled)
   sorted x 4,224,509 ops/sec ±0.70% (90 runs sampled)
   native x 2,163,293 ops/sec ±0.90% (92 runs sampled)
 Fastest is ordino

Push One:
   ordino x 28,707 ops/sec ±1.01% (92 runs sampled)
   sorted x 358,144 ops/sec ±1.04% (93 runs sampled)
 Fastest is sorted

Push Many:
   ordino x 12,850 ops/sec ±1.12% (90 runs sampled)
   sorted x 7,005 ops/sec ±0.72% (91 runs sampled)
 Fastest is ordino

Range:
   ordino x 208,975 ops/sec ±1.05% (90 runs sampled)
   sorted x 1,463,587 ops/sec ±0.76% (89 runs sampled)
 Fastest is sorted

Splice:
   ordino x 3,099 ops/sec ±2.48% (76 runs sampled)
   sorted x 5,234 ops/sec ±4.04% (71 runs sampled)
 Fastest is sorted

Get Intersection
   ordino x 327,559 ops/sec ±0.71% (90 runs sampled)
   sorted-intersect x 256,896 ops/sec ±0.94% (88 runs sampled)
   intersect x 15,203 ops/sec ±0.73% (90 runs sampled)
   lodash.intersection x 18,765 ops/sec ±10.39% (92 runs sampled)
   just-intersect x 25,073 ops/sec ±0.70% (93 runs sampled)
 Fastest is ordino

Get Intersection Score
   ordino x 359,711 ops/sec ±0.61% (91 runs sampled)
   sorted-intersect x 254,582 ops/sec ±0.99% (90 runs sampled)
   intersect x 15,326 ops/sec ±0.67% (90 runs sampled)
   lodash.intersection x 19,768 ops/sec ±1.33% (91 runs sampled)
   just-intersect x 24,983 ops/sec ±0.75% (91 runs sampled)
 Fastest is ordino

Get Difference
   ordino x 222,286 ops/sec ±1.22% (87 runs sampled)
   difference x 17,019 ops/sec ±0.65% (92 runs sampled)
   lodash.difference x 32,700 ops/sec ±1.19% (89 runs sampled)
   arr-diff x 15,293 ops/sec ±0.53% (92 runs sampled)
   array-differ x 15,233 ops/sec ±1.13% (90 runs sampled)
 Fastest is ordino

Get Difference Score
   ordino x 346,135 ops/sec ±0.73% (91 runs sampled)
   difference x 16,887 ops/sec ±1.27% (90 runs sampled)
   lodash.difference x 32,837 ops/sec ±1.00% (89 runs sampled)
   arr-diff x 15,209 ops/sec ±0.64% (91 runs sampled)
   array-differ x 14,985 ops/sec ±1.86% (88 runs sampled)
 Fastest is ordino

License

MIT © Maga D. Zandaqo