This package is an extension of popular collections library Immutable.js. It provides additional immutable collections SortedMap and SortedSet that maintain their entries sorted by a comparator. The current implementation is using a classic B-tree memory structure.
Additionally, this package provides partial sort (returning the n smallest elements)
and incremental sort
operations implemented using Floyd-Rivest variant of selection algorithm.
The current version [email protected] is an extension of [email protected].
npm install immutable-sortedSee more details on SortedSet page.
SortedSet is a type of Set that keeps its values sorted by a comparator. The current implementation is using a classic B-Tree memory structure with O(N) space requirements and O(log N) get, add, and delete operations.
Example:
> const { SortedSet } = require('immutable-sorted');
> const set1=SortedSet(['orange', 'apple', 'banana']);
SortedSet { "apple", "banana", "orange" }
> const set2=set1.add('mango');
SortedSet { "apple", "banana", "mango", "orange" }
> const set3=set2.delete('banana');
SortedSet { "apple", "mango", "orange" }Using a custom comparator:
> const reverseCmp=(a,b)=>(a>b?-1:a<b?1:0);
> const set4=SortedSet(set1, reverseCmp);
SortedSet { "orange", "banana", "apple" }
> const set5=set4.add('mango');
SortedSet { "orange", "mango", "banana", "apple" }
> const set6=set5.delete('banana');
SortedSet { "orange", "mango", "apple" }Set values, like Map keys, may be of any type. Equality is determined by comparator returning 0 value. In case of a custom comparator the equality may be redefined to have a different meaning than Immutable.is.
Searching SortedSet
Many real applications require ability to efficiently search in a sorted dataset. The method:
from(value, backwards) returns a sequence that represents a subset of a sorted set starting with value up to the last element in the set.
If the optional parameter backwards is set to true, the returned sequence will list the entries backwards, starting with value down to the first element in the set.
Example:
const { SortedSet } = require('immutable-sorted');
const abc = SortedSet(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]);
> abc.from("R");
Seq { "R", "S", "T", "U", "V", "W", "X", "Y", "Z" }
> abc.from("R", true);
Seq { "R", "Q", "P", "O", "N", "M", "L", "K", "J", "I", "H", "G", "F", "E", "D", "C", "B", "A" }The method from() can be efficiently combined with take() to retrieve the desired number of values or with takeWhile() to retrieve a specific range:
> abc.from("R").take(5);
Seq { "R", "S", "T", "U", "V" }
> abc.from("R").takeWhile(s => s < "W");
Seq { "R", "S", "T", "U", "V" }
> abc.from("R", true).take(5);
Seq { "R", "Q", "P", "O", "N" }
> abc.from("R", true).takeWhile(s => s > "K");
Seq { "R", "Q", "P", "O", "N", "M", "L" }Working with objects
Many real use cases will be about storing the whole objects in SortedSet. That will usually be meaningful only when custom comparator is defined.
Let's consider the following example with city objects:
> const { SortedSet, Seq, fromJS } = require('immutable-sorted');
// Have an array of city objects
> const cities=[
{state: 'MA', city: 'Boston'},
{city: 'Miami', state: 'FL'},
{city: 'Seattle', state: 'WA'},
{city: 'Phoenix', state: 'AZ'}];
// Make a seq that converts cities from JS into immutable objects
> const citiesSeq=Seq(cities).map((v)=>fromJS(v));
// Create a default SortedSet
> const set1=SortedSet(citiesSeq);
SortedSet {
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Seattle", "state": "WA" },
Map { "state": "MA", "city": "Boston" } }When relying on defaultComparator, like in example above, the objects get sorted by their string representations from toString() method. This is usually not what the application designers want. In our case it makes more sense to sort by the city name, than the whole string representation.
Let's create a custom comparator:
// Define a general comparator
> const cmp=(a,b)=>(a>b?1:(a<b?-1:0));
// Define a comparator of city names
> let citiesCmp=(a,b)=>cmp(a.get('city'), b.get('city'));
// Create a SortedSet with custom comparator
> const set2=SortedSet(citiesSeq, citiesCmp);
SortedSet {
Map { "state": "MA", "city": "Boston" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Seattle", "state": "WA" } }The custom comparator that we have created seems to work as expected. Now let's add into the collection another city of Phoenix, this time from state Illinois.
> const set3=set2.add(fromJS({city: 'Phoenix', state: 'IL'}));
SortedSet {
Map { "state": "MA", "city": "Boston" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "IL" },
Map { "city": "Seattle", "state": "WA" } }The Phoenix, AZ had been replaced with Phoenix, IL. This is because of the way the custom comparator is defined. It determines equality by comparing city names only, therefore Phoenix, AZ and Phoenix, IL are equal according to this comparator. Let's try to extend the comparator to compare the city name first and if they match then determine the result by comparing the state.
// Define more complex custom comparator
> citiesCmp=(a,b)=>cmp(a.get('city'), b.get('city'))||cmp(a.get('state'), b.get('state'));
// Create a new SortedSet with new custom comparator
> const set4=SortedSet(set2, citiesCmp);
SortedSet {
Map { "state": "MA", "city": "Boston" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Seattle", "state": "WA" } }
// set4 looks the same as set2, now let's add the conflicting Phoenix, IL to set4
> const set5=set4.add(fromJS({city: 'Phoenix', state: 'IL'}));
SortedSet {
Map { "state": "MA", "city": "Boston" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Phoenix", "state": "IL" },
Map { "city": "Seattle", "state": "WA" } }The custom comparator behaves as expected. Now let's swap the order of commands in the comparator and sort by state first and by city name second.
> const stateCitiesCmp=(a,b)=>cmp(a.get('state'), b.get('state'))||cmp(a.get('city'), b.get('city'));
> const set6=SortedSet(set5, stateCitiesCmp);
SortedSet {
Map { "city": "Phoenix", "state": "AZ" },
Map { "city": "Miami", "state": "FL" },
Map { "city": "Phoenix", "state": "IL" },
Map { "state": "MA", "city": "Boston" },
Map { "city": "Seattle", "state": "WA" } }See more details on SortedMap page.
SortedMap is a type of Map that keeps its entries (their keys) sorted by a comparator. The current implementation is using a classic B-Tree memory structure with O(N) space requirements and O(log N) get, set, and delete operations.
Example:
const { SortedMap } = require('immutable-sorted');
> const map1=SortedMap([['orange','orange'], ['apple','red'], ['banana','yellow']]);
SortedMap { "apple": "red", "banana": "yellow", "orange": "orange" }
> const map2=map1.set('mango', 'yellow/orange');
SortedMap { "apple": "red", "banana": "yellow", "mango": "yellow/orange", "orange": "orange" }
> const map3=map2.delete('banana');
SortedMap { "apple": "red", "mango": "yellow/orange", "orange": "orange" }Using a custom comparator:
> const reverseCmp=(a,b)=>(a>b?-1:(a<b?1:0));
> const map4=SortedMap(map1, reverseCmp);
SortedMap { "orange": "orange", "banana": "yellow", "apple": "red" }
> const map5=map4.set('mango', 'yellow/orange');
SortedMap { "orange": "orange", "mango": "yellow/orange", "banana": "yellow", "apple": "red" }
> const map6=map5.delete('banana');
SortedMap { "orange": "orange", "mango": "yellow/orange", "apple": "red" }When iterating a SortedMap, the order of entries is guaranteed to be the same as the sorted order of keys determined by a comparator.
Map keys and values may be of any type. Equality of keys is determined by comparator returning 0 value. In case of a custom comparator the equality may be redefined to have a different meaning than Immutable.is.
Searching SortedMap
Many real applications require ability to efficiently search in a sorted data structure. The method:
from(key, backwards)returns a sequence that represents a portion of this sorted map starting with a specific key up to the last entry in the sorted map.
If the optional parameter backwards is set to true, the returned sequence will list the entries backwards, starting with key down to the first entry in the sorted map.
Example:
> const abc = SortedMap([["A", "a"], ["B", "b"], ["C", "c"], ["D", "d"], ["E", "e"], ["F", "f"], ["G", "g"], ["H", "h"], ["I", "i"], ["J", "j"], ["K", "k"], ["L", "l"], ["M", "m"], ["N", "n"], ["O", "o"], ["P", "p"], ["Q", "q"], ["R", "r"], ["S", "s"], ["T", "t"], ["U", "u"], ["V", "v"], ["W", "w"], ["X", "x"], ["Y", "y"], ["Z", "z"]]);
> abc.from("R");
Seq { "R": "r", "S": "s", "T": "t", "U": "u", "V": "v", "W": "w", "X": "x", "Y": "y", "Z": "z" }
> abc.from("R", true);
Seq { "R": "r", "Q": "q", "P": "p", "O": "o", "N": "n", "M": "m", "L": "l", "K": "k", "J": "j", "I": "i", "H": "h", "G": "g", "F": "f", "E": "e", "D": "d", "C": "c", "B": "b", "A": "a" }The method from() can be efficiently combined with take() to retrieve the desired number of values or with takeWhile() to retrieve a specific range:
> abc.from("R").take(5);
Seq { "R": "r", "S": "s", "T": "t", "U": "u", "V": "v" }
> abc.from("R").takeWhile((v, k) => k < "W");
Seq { "R": "r", "S": "s", "T": "t", "U": "u", "V": "v" }
> abc.from("R", true).take(5);
Seq { "R": "r", "Q": "q", "P": "p", "O": "o", "N": "n" }
> abc.from("R", true).takeWhile((v, k) => k > "K");
Seq { "R": "r", "Q": "q", "P": "p", "O": "o", "N": "n", "M": "m", "L": "l" }Working with objects
Many real use cases will be about storing the whole objects in SortedMap. That will usually be meaningful only when custom comparator is defined.
Let's consider the following example with city objects as keys and their co-ordinates as values:
> const { SortedMap, Seq, fromJS } = require('immutable-sorted');
// Have an array of city objects
> const cities=[
[{state: 'MA', city: 'Boston'}, ['42°21′N','71°04′W']],
[{city: 'Miami', state: 'FL'},['25°47′N','80°13′W']],
[{city: 'Seattle', state: 'WA'},['47°37′N','122°20′W']],
[{city: 'Phoenix', state: 'AZ'},['33°27′N','112°04′W']]];
// Make a seq that converts cities and their co-ordinates from JS into immutable objects
> const citiesSeq=Seq.Keyed(cities).mapKeys((v)=>fromJS(v)).map((v)=>fromJS(v));
Seq {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ] }
// Create a default SortedMap
> const map1=SortedMap(citiesSeq);
SortedMap {
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ],
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ] }When relying on defaultComparator, like in example above, the objects get sorted by their string representations from toString() method. This is usually not what the application designers want. In our case it makes more sense to sort by the city name, than the whole string representation.
Let's create a custom comparator:
// Define a general simple comparator
> const cmp=(a,b)=>(a>b?1:(a<b?-1:0));
// Define a comparator of city names
> let citiesCmp=(a,b)=>cmp(a.get('city'), b.get('city'));
// Create a SortedSet with custom comparator
> const map2=SortedMap(citiesSeq, citiesCmp);
SortedMap {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }The custom comparator that we have created seems to work as expected. Now let's add into the collection another city of Phoenix, this time from state Illinois.
> const map3=map2.set(fromJS({city: 'Phoenix', state: 'IL'}), fromJS(['41°36′N','87°37′W']));
SortedMap {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "IL" }: List [ "41°36′N", "87°37′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }The Phoenix, AZ had been replaced with Phoenix, IL. This is because of the way the custom comparator is defined. It determines equality by comparing city names only, therefore Phoenix, AZ and Phoenix, IL are equal according to this comparator. Let's try to extend the comparator to compare the city name first and if they match then determine the result by comparing the state.
// Define more complex custom comparator
> citiesCmp=(a,b)=>cmp(a.get('city'), b.get('city'))||cmp(a.get('state'), b.get('state'));
// Create a new SortedMap with new custom comparator
> const map4=SortedMap(map2, citiesCmp);
SortedMap {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }
// map4 looks the same as map2, now let's add the conflicting Phoenix, IL to map4
> const map5=map4.set(fromJS({city: 'Phoenix', state: 'IL'}), fromJS(['41°36′N','87°37′W']));
SortedMap {
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Phoenix", "state": "IL" }: List [ "41°36′N", "87°37′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }The custom comparator behaves as expected. Now let's swap the order of commands in the comparator and sort by state first and by city name second.
> const stateCitiesCmp=(a,b)=>cmp(a.get('state'), b.get('state'))||cmp(a.get('city'), b.get('city'));
> const map6=SortedMap(map5, stateCitiesCmp);
SortedMap {
Map { "city": "Phoenix", "state": "AZ" }: List [ "33°27′N", "112°04′W" ],
Map { "city": "Miami", "state": "FL" }: List [ "25°47′N", "80°13′W" ],
Map { "city": "Phoenix", "state": "IL" }: List [ "41°36′N", "87°37′W" ],
Map { "state": "MA", "city": "Boston" }: List [ "42°21′N", "71°04′W" ],
Map { "city": "Seattle", "state": "WA" }: List [ "47°37′N", "122°20′W" ] }Any collection (including sequences) provides partialSort() and partialSortBy()
functions for efficiently finding and sorting the n smallest elements in a collection using
Floyd-Rivest select algorithm.
Example:
> const { Seq } = require('immutable-sorted');
> const seq1=Seq(['orange', 'apple', 'banana']);
> seq1.partialSort(2)
Seq [ "apple", "banana" ]Any collection (including sequences) also provides incSort() and incSortBy() functions optimized to provide first entries of the result set faster than regular sort(). This function is expected to be used with iterators or sequence operations retrieving limited number of result entries.
Example:
> const { Seq } = require('immutable-sorted');
> const seq1=Seq(['orange', 'apple', 'banana']);
> seq1.incSort().take(2)
Seq [ "apple", "banana" ]MIT License
Modified work Copyright (c) 2017-2018, Applitopia, Inc.
Original work Copyright (c) 2014-present, Facebook, Inc.