ordino v1.2.0

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 ]

If the instance property unique of an array is set to true, the array will behave as a set and avoid duplicating elements:

const a = new SortedArray();
a.unique = true;
a.push(1);
//=> 1
a.push(2);
//=> 2
a.push(1);
//=> 2
a
//=> SortedArray [ 1, 2 ]

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,227 ops/sec ±1.13% (86 runs sampled)
   sorted x 8,626 ops/sec ±0.95% (89 runs sampled)
 Fastest is ordino

Concat:
   ordino x 145,565 ops/sec ±0.68% (89 runs sampled)
   sorted x 6,722 ops/sec ±1.05% (87 runs sampled)
   native x 4,184 ops/sec ±0.81% (88 runs sampled)
 Fastest is ordino

Find Index:
   ordino x 9,407,508 ops/sec ±1.76% (86 runs sampled)
   sorted x 4,000,189 ops/sec ±0.72% (89 runs sampled)
   native x 2,089,131 ops/sec ±1.04% (88 runs sampled)
 Fastest is ordino

Push One:
   ordino x 28,129 ops/sec ±0.82% (85 runs sampled)
   sorted x 348,519 ops/sec ±0.96% (89 runs sampled)
 Fastest is sorted

Push Many:
   ordino x 12,784 ops/sec ±0.71% (89 runs sampled)
   sorted x 6,718 ops/sec ±1.04% (89 runs sampled)
 Fastest is ordino

Range:
   ordino x 255,454 ops/sec ±0.70% (89 runs sampled)
   sorted x 1,417,667 ops/sec ±0.89% (89 runs sampled)
 Fastest is sorted

Splice:
   ordino x 2,885 ops/sec ±2.49% (72 runs sampled)
   sorted x 5,487 ops/sec ±3.18% (75 runs sampled)
 Fastest is sorted

Get Intersection
   ordino x 319,265 ops/sec ±0.70% (90 runs sampled)
   sorted-intersect x 299,447 ops/sec ±1.11% (88 runs sampled)
   intersect x 14,649 ops/sec ±0.67% (91 runs sampled)
   lodash.intersection x 19,327 ops/sec ±8.54% (90 runs sampled)
   just-intersect x 23,920 ops/sec ±0.96% (89 runs sampled)
 Fastest is ordino

Get Intersection Score
   ordino x 345,188 ops/sec ±0.73% (87 runs sampled)
   sorted-intersect x 300,694 ops/sec ±0.74% (91 runs sampled)
   intersect x 14,457 ops/sec ±0.89% (90 runs sampled)
   lodash.intersection x 20,312 ops/sec ±0.92% (89 runs sampled)
   just-intersect x 23,887 ops/sec ±0.80% (89 runs sampled)
 Fastest is ordino

Get Difference
   ordino x 217,084 ops/sec ±0.77% (90 runs sampled)
   difference x 15,645 ops/sec ±1.26% (90 runs sampled)
   lodash.difference x 31,550 ops/sec ±1.39% (89 runs sampled)
   arr-diff x 14,435 ops/sec ±0.89% (91 runs sampled)
   array-differ x 14,700 ops/sec ±1.19% (88 runs sampled)
 Fastest is ordino

Get Difference Score
   ordino x 332,046 ops/sec ±0.93% (90 runs sampled)
   difference x 15,605 ops/sec ±0.67% (90 runs sampled)
   lodash.difference x 31,657 ops/sec ±1.24% (88 runs sampled)
   arr-diff x 14,246 ops/sec ±0.94% (89 runs sampled)
   array-differ x 14,807 ops/sec ±0.76% (91 runs sampled)
 Fastest is ordino

License

MIT © Maga D. Zandaqo