Quick Start

Import

SortAO has no side effects. You can directly import the container you want from sortao:

import { SortedSet } from "sortao";

Basic Usage

SortAO provides an API that is extremely similar to the native ES6 Set, but always remains ordered. Take Sorted-Set as an example.

import { SortedSet } from "sortao";

const set = new SortedSet<number>();

set.add(50).add(10).add(30);

if (set.has(10)) {
  console.log(set.toArray());  // [10, 30, 50]
  console.log(set.min());      // 10
  console.log(set.max());      // 50
}

CompareFn

You can pass in your own comparison function to control the sorting logic. The sample function in the following code is the default comparison function.

Note: your function must be able to correctly compare the three cases of >, < and ==.

import { SortedSet } from "sortao";

function comp<T>(a: T, b: T) {
  if (a > b) return 1;
  else if (a < b) return -1;
  return 0;
}

const set = new SortedSet<number>(comp);

Ranking and range query

SortAO provides interesting retrieval capabilities. Take Sorted-Multiset as an example.

import { SortedMultiset } from "sortao";

const scores = new SortedMultiset<number>();

scores.add(45)
      .add(60).add(60).add(60) // Multiset allows inserting duplicate values
      .add(75)
      .add(90);

// Count the occurrence of 60
console.log(scores.count(60));  // 3

// Query rank (the number of values strictly less than the query value).
// The rank starts from 0.
console.log([
  scores.rank(10), scores.rank(45),  // 0, 0
  scores.rank(60), scores.rank(61),  // 1, 4
  scores.rank(90), scores.rank(91)   // 5, 6
]);

// Query by ranking. Ranking starts from 0.
console.log(scores.kth(0));     // 45
console.log(scores.kth(1));     // 60
console.log(scores.kth(3));     // 60

Cursor

Regarding cursors, please refer to the Cursor page for detailed documentation.

Functions named in JavaScript style, such as lowerBound and upperBound, will return rankings.
Functions named in C++ style, such as lower_bound, upper_bound, and equal_range, return iterators.

Take Sorted-Multimap as an example.

import { SortedMultimap } from "sortao";

const users = new SortedMultimap<number, string>();

users.add(10, "asahi")
     .add(10, "luna")
     .add(20, "resona");

console.log(users.lowerBound(20));            // 2

const cur = users.lower_bound(20);            // returns a cursor
console.log(cur.index, cur.key, cur.value);   // 2, 20, resona

cur.prev();
console.log(cur.index, cur.key, cur.value);   // 1, 10, luna

cur.prev();
console.log(cur.index, cur.key, cur.value);   // 0, 10, asahi

equal_range

equal_range returns two cursors, indicating a range of left-closed and right-open [start, end).

// Following the previous example
const [start, end] = users.equal_range(10);

console.log(start.index); // 0 (points to the first 10)
console.log(end.index);   // 2 (points to the position after the last 10)

console.log(`contains ${end.index - start.index} elements`); // 2

while (start.index < end.index) { // traverse
  console.log(start.key, start.value);
  start.next();
}

  // Output:
  // 10 "asahi"
  // 10 "luna"

Regarding cursors, please refer to the Cursor page for detailed documentation.

Multi-container behavior

For the same value, the Multi container behaves as a queue (FIFO):

When inserting the same value, the newly inserted element is always placed at the end.
When deleting the same value, the earliest inserted element is always deleted.

import { SortedMultiset } from "sortao";

const some = new SortedMultiset< any >( sorted_by_id_comp );

some.add({ id: 1, s: 114 })
    .add({ id: 1, a: 514 })
    .add({ id: 1, o: "s" })

some.toArray(); // [{ id: 1, s: 114 }, { id: 1, a: 514 }, { id: 1, o: "s" }]

some.deleteOne({ id: 1 }); // Always query by structure (heterogeneous query)

some.toArray(); // [{ id: 1, a: 514 }, { id: 1, o: "s" }]

This also reflects the difference from native collections:

The delete method of the native collection matches based on the reference of the value.
The delete method used by SortAO compares based on the structure of the value.

This is due to the fundamental difference between hash tables based on matching (unordered) and sorting algorithms based on comparison (ordered).

Kernel

Taking Sorted-Map and SplayTree as examples:

import { SortedMap, SplayTree } from "sortao";
import type { MapEntry } from "sortao"; // for Map Container.

// 1. Define a comparison function for keys
const compareFn = (a: number, b: number) => a - b;

// 2. Incoming Kernel Factory
const map = new SortedMap<number, string, SplayTree<MapEntry<number, string>>>(
  compareFn,
  (comp) => new SplayTree(comp)
)

map.set(100, "Splay");
map.set(200, "Tree");

In TypeScript, type annotations can be somewhat cumbersome, but generally speaking:

set < T, Container<T> >
map < K, V, Container< MapEntry<K,V> > >

Traverse

Most containers provided by SortAO implement Internal-Iterable, offering a plethora of traversal methods.

The native for..of iterator generates a large number of temporary objects. It is recommended to use the traversal method provided by SortAO:

import { SortedSet } from "sortao";

const set = new SortedSet<number>();
set.add(10).add(20).add(30).add(40).add(50);

set.forEach((value, index) => {
  if (value > 30) return true; // short-circuit
  console.log(`Rank: ${index}, Value: ${value}`);
});

  // Output:
  // Rank: 0, Value: 10
  // Rank: 1, Value: 20
  // Rank: 2, Value: 30

For Map-like containers:

import { SortedMap } from "sortao";

const map = new SortedMap<number, string>();
map.set(100, "Alice").set(200, "Bob");

map.forEach((value, key, index) => {
  console.log(`Rank: ${index} | ${key} -> ${value}`);
});

  // Output:
  // Rank: 0 | 100 -> Alice
  // Rank: 1 | 200 -> Bob

const entries = map.toArray(); // [[100, "Alice"], [200, "Bob"]]

Difference from ES

In fact, there exists an essential difference between hash tables based on matching (unordered) and sorting algorithms based on comparison (ordered).
The API of SortAO must differ from that of native collections, especially in the following aspects:

Methods such as get and delete

The native get method will return T or undefined
The native delete method returns a boolean value.
The methods such as get and delete of SortAO will return T, [K, V], or undefined.

The design is based on the fact that SortAO is comparison-based (ordered) rather than matching-based (unordered). Consider the following scenario:

const some = new SortedSet< Object >( comp_by_id );

some.add({ id: 1, name: "Alice" });

const one = some.get({ id: 1 });    // { id: 1, name: "Alice" }
const two = some.delete({ id: 1 }); // { id: 1, name: "Alice" }

If we don’t return the original T or [K, V], we may never be able to learn the name in the aforementioned structure.

Such confusion often arises when you use map-like containers:

const some = new SortedMap< Object, number >( comp_by_id );

const [_key, value] = some.get({ id: 1 });

Perhaps you don’t wish to use this _key, but it is still returned because subsequent operations may sometimes require the key.

Accessing the kernel of the wrapper

Directly manipulate the internal container through kernel and keyCompare properties.

class SortedMap /* .. */ {
  public readonly kernel: Kernel;
  public readonly keyCompare: (a: K, b: K) => number;
}

The cursor of the wrapper is also an encapsulation of the cursor of kernel, denoted as inner.

class SortedMapCursor /* .. */ {
  public inner: C;
}

SortedMap and SortedMultimap encapsulate internal cursors.
SortedSet and SortedMultiset directly return internal cursors.