- Notifications
You must be signed in to change notification settings - Fork6
This is an extension of Immutable.js that provides sorted collections SortedMap and SortedSet. The current implementation is using highly optimized B-tree memory structure.
License
applitopia/immutable-sorted
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
This package is an extension of popular collections libraryImmutable.js. It provides additional immutable collectionsSortedMap andSortedSet that maintain their entries sorted by a comparator. The current implementation is using a classicB-tree memory structure.
Additionally, this package providespartial sort (returning then smallest elements)andincremental sortoperations implemented usingFloyd-Rivest variant ofselection algorithm.
The current versionimmutable-sorted@0.2.11 is an extension ofimmutable-js@4.0.0-rc.12.
npm install immutable-sorted
See more details onSortedSet 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');>constset1=SortedSet(['orange','apple','banana']);SortedSet{"apple","banana","orange"}>constset2=set1.add('mango');SortedSet{"apple","banana","mango","orange"}>constset3=set2.delete('banana');SortedSet{"apple","mango","orange"}
Using a custom comparator:
>constreverseCmp=(a,b)=>(a>b?-1:a<b?1:0);>constset4=SortedSet(set1,reverseCmp);SortedSet{"orange","banana","apple"}>constset5=set4.add('mango');SortedSet{"orange","mango","banana","apple"}>constset6=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 valueup to the last element in the set.
If the optional parameter backwards is set to true, the returned sequence willlist the entries backwards, starting with value down to the first element in the set.
Example:
const{ SortedSet}=require('immutable-sorted');constabc=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"}
We can also use the numeric index to efficiently iterate through the sorted collections starting from numeric index as if they were arrays. The method:
fromIndex(n,backwards)
is optimized to quickly find the n-th entry inside the b-tree structure by checking the computed sizes of underlying nodes. Even though the algorithm is not as fast as working with native array, it is faster by orders of magnitude than walking through the first n elements in unindexed collection to skip them. The access time is O(log N).
Examples:
>abc.fromIndex(4).take(5);Seq{"E","F","G","H","I"}>abc.fromIndex(4,true).take(5);Seq{"E","D","C","B","A"}
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>constcities=[{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>constcitiesSeq=Seq(cities).map((v)=>fromJS(v));// Create a default SortedSet>constset1=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>constcmp=(a,b)=>(a>b?1:(a<b?-1:0));// Define a comparator of city names>letcitiesCmp=(a,b)=>cmp(a.get('city'),b.get('city'));// Create a SortedSet with custom comparator>constset2=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.
>constset3=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>constset4=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>constset5=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.
>conststateCitiesCmp=(a,b)=>cmp(a.get('state'),b.get('state'))||cmp(a.get('city'),b.get('city'));>constset6=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 onSortedMap 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');>constmap1=SortedMap([['orange','orange'],['apple','red'],['banana','yellow']]);SortedMap{"apple":"red","banana":"yellow","orange":"orange"}>constmap2=map1.set('mango','yellow/orange');SortedMap{"apple":"red","banana":"yellow","mango":"yellow/orange","orange":"orange"}>constmap3=map2.delete('banana');SortedMap{"apple":"red","mango":"yellow/orange","orange":"orange"}
Using a custom comparator:
>constreverseCmp=(a,b)=>(a>b?-1:(a<b?1:0));>constmap4=SortedMap(map1,reverseCmp);SortedMap{"orange":"orange","banana":"yellow","apple":"red"}>constmap5=map4.set('mango','yellow/orange');SortedMap{"orange":"orange","mango":"yellow/orange","banana":"yellow","apple":"red"}>constmap6=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:
>constabc=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>constcities=[[{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>constcitiesSeq=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>constmap1=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>constcmp=(a,b)=>(a>b?1:(a<b?-1:0));// Define a comparator of city names>letcitiesCmp=(a,b)=>cmp(a.get('city'),b.get('city'));// Create a SortedSet with custom comparator>constmap2=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.
>constmap3=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>constmap4=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>constmap5=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.
>conststateCitiesCmp=(a,b)=>cmp(a.get('state'),b.get('state'))||cmp(a.get('city'),b.get('city'));>constmap6=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 then smallest elements in a collection usingFloyd-Rivest select algorithm.
Example:
>const{ Seq}=require('immutable-sorted');>constseq1=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 operationsretrieving limited number of result entries.
Example:
>const{ Seq}=require('immutable-sorted');>constseq1=Seq(['orange','apple','banana']);>seq1.incSort().take(2)Seq["apple","banana"]
MIT License
Modified work Copyright (c) 2017-present, Applitopia, Inc.
Original work Copyright (c) 2014-present, Facebook, Inc.
About
This is an extension of Immutable.js that provides sorted collections SortedMap and SortedSet. The current implementation is using highly optimized B-tree memory structure.
Topics
Resources
License
Code of conduct
Contributing
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Packages0
Uh oh!
There was an error while loading.Please reload this page.