@rimbu/sorted

Fast, immutable sorted maps and sets for TypeScript & JavaScript.

@rimbu/sorted provides efficient, type-safe SortedMap and SortedSet implementations. They keep elements in a deterministic sorted order using a configurable comparator (Comp), while offering immutable, persistent semantics and a rich, map/set‑like API.

Use them whenever you need ordered iteration (by key or value), range queries, or index‑based slicing on top of regular map/set behaviour.

Table of Contents

1. Why @rimbu/sorted?
2. Feature Highlights
3. Quick Start
4. Core Concepts & Types
5. Working with SortedMap
6. Working with SortedSet
7. Custom Comparators & Contexts
8. Installation
9. FAQ
10. Ecosystem & Integration
11. Contributing
12. License

Why @rimbu/sorted?

Plain Map / Set in JS don’t know about ordering beyond insertion order. @rimbu/sorted focuses on:

• Sorted views – entries (for maps) and values (for sets) are always kept in sorted order.
• Range queries – stream or slice by key or value ranges and by index ranges.
• Index-based access – get the n‑th smallest key or value directly.
• Immutable operations – updates return new instances with structural sharing.

If you ever needed to sort a map’s entries repeatedly, maintain parallel sorted arrays, or build your own tree structures, SortedMap / SortedSet are usually a better fit.

Feature Highlights

• SortedMap & SortedSet – ordered by a configurable comparator (Comp‑like interface).
• Efficient lookups – map/set semantics with \(O(\log n)\)-style updates on persistent trees.
• Index-aware APIs – getAtIndex, sliceIndex, take, drop, streamRange, streamSliceIndex.
• Configurable contexts – build custom contexts with your own comparison logic and block sizes.
• Immutable & persistent – structural sharing for cheap copies, undo/redo, and change detection.

Try Rimbu (including @rimbu/sorted) live in the browser using the Rimbu Sandbox on CodeSandbox.

Quick Start

import { SortedMap, SortedSet } from '@rimbu/sorted';

// SortedMap: keys are kept in sorted order
const m = SortedMap.of(['b', 2], ['d', 4], ['a', 1], ['c', 3]).asNormal(); // convert to a normal (possibly empty) view

console.log(m.toArray());
// => [['a', 1], ['b', 2], ['c', 3], ['d', 4]]

// SortedSet: values are kept in sorted order
const s = SortedSet.of('b', 'd', 'a', 'c').asNormal();
console.log(s.toArray());
// => ['a', 'b', 'c', 'd']

See the Map docs, Set docs, and the sorted API reference for full details.

Core Concepts & Types

Exported Types

From the main entry:

You can import them via:

import { SortedMap, SortedSet } from '@rimbu/sorted';
// or more granular:
// import { SortedMap } from '@rimbu/sorted/map';
// import { SortedSet } from '@rimbu/sorted/set';

Working with SortedMap

import { SortedMap } from '@rimbu/sorted';

// Construction
const empty = SortedMap.empty<string, number>();
const fromEntries = SortedMap.of(
  ['b', 2],
  ['d', 4],
  ['a', 1],
  ['c', 3]
).asNormal();

// Size & emptiness
empty.isEmpty; // true
fromEntries.size; // 4

// Lookups
fromEntries.hasKey('b'); // true
fromEntries.get('c'); // 3

// Sorted access helpers
fromEntries.min(); // ['a', 1]
fromEntries.maxKey(); // 'd'
fromEntries.getAtIndex(1); // ['b', 2]
fromEntries.getValueAtIndex(-1); // 4 (last value)

// Range queries (by key and by index)
fromEntries.streamRange({ start: 'b', end: 'c' }).toArray(); // [['b', 2], ['c', 3]]

fromEntries.sliceIndex({ start: 1, amount: 2 }).toArray(); // [['b', 2], ['c', 3]]

See the SortedMap API docs for all operations (including builders, contexts, and more advanced methods).

Working with SortedSet

import { SortedSet } from '@rimbu/sorted';

// Construction
const empty = SortedSet.empty<string>();
const values = SortedSet.of('b', 'd', 'a', 'c').asNormal();

// Basic queries
values.has('b'); // true
values.min(); // 'a'
values.max(); // 'd'

// Index‑based access
values.getAtIndex(1); // 'b'
values.getAtIndex(-1); // 'd'

// Range queries
values.streamRange({ start: 'b', end: 'c' }).toArray(); // ['b', 'c']

values.sliceIndex({ start: 1, amount: 2 }).toArray(); // ['b', 'c']

See the SortedSet API docs for the full, strongly‑typed surface.

Custom Comparators & Contexts

By default, SortedMap / SortedSet use a generic comparator that works well for most values. For specialised ordering you can create your own context:

import { SortedSet } from '@rimbu/sorted';

// Comparator compatible with the Comp<UT> interface
const caseInsensitiveStringComp = {
  isComparable: (value: unknown): value is string => typeof value === 'string',
  compare: (a: string, b: string): number =>
    a.toLocaleLowerCase().localeCompare(b.toLocaleLowerCase()),
};

const ciSetContext = SortedSet.createContext<string>({
  comp: caseInsensitiveStringComp,
  // blockSizeBits (optional) controls the underlying tree node size, default 5
});

const ciSet = ciSetContext.of('a', 'B', 'c');
ciSet.has('b'); // true (case‑insensitive)

You can do the same for SortedMap by providing a key comparator. Contexts also expose builder() / createBuilder() for efficient bulk updates.

Installation

Node / Bun / npm / Yarn

npm install @rimbu/sorted
# or
yarn add @rimbu/sorted
# or
bun add @rimbu/sorted
# or
deno add npm:@rimbu/sorted

Browser / ESM

@rimbu/sorted ships both ESM and CJS builds. Use it with any modern bundler (Vite, Webpack, esbuild, Bun, etc.) or directly in Node ESM projects.

FAQ

Q: How is SortedMap different from a regular Map?
SortedMap maintains its keys in sorted order rather than insertion order, and adds index‑based access (getAtIndex, take, sliceIndex, etc.) and range‑based streaming over keys.

Q: Are these collections mutable?
No. All updates return new instances; existing ones remain unchanged and can be safely shared across your application.

Q: What is a “context” and when should I use it?
A context (SortedMap.Context, SortedSet.Context) encapsulates the comparator and tree configuration. Use custom contexts when you need non‑default ordering or want to tune block sizes for your workload.

Q: Do I always need a custom comparator?
No. For most use cases the default comparator is sufficient; custom comparators are useful when domain‑specific ordering (case‑insensitive strings, locale‑aware sorting, domain‑specific ranks, etc.) is required.

Ecosystem & Integration

• Part of the broader Rimbu collection ecosystem – interoperates with @rimbu/hashed, @rimbu/ordered, @rimbu/collection-types, and @rimbu/stream.
• Ideal for modelling ordered indexes, time‑series views, leaderboards, or any domain where sorted iteration and range queries matter.
• Works seamlessly with other Rimbu collections and utilities for building rich, immutable data models.

Explore more at the Rimbu documentation and the sorted API docs.

Contributing

We welcome contributions! See the Contributing guide for details.

Made with contributors-img.

License

MIT © Rimbu contributors. See LICENSE for details.

Attributions

Created and maintained by Arvid Nicolaas. Logo © Rimbu.