Namespace SortedMap

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.

> const { SortedMap } = require('@oraichain/immutable');

> 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" }
Copy

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" }
Copy

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.

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('@oraichain/immutable');
// 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" ] }
Copy

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 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" ] }
Copy

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" ] }
Copy

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" ] }
Copy

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" ] }
Copy