Namespace SortedSet

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.

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

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

Copy

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

When iterating a SortedSet, the entries will be (value, value) pairs. Iteration order of a SortedSet is determined by a comparator.

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.

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