@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

``ts
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

$3

From the main entry:

| Name | Description |
| -------------------------- | --------------------------------------------------------------------------------------------------- |
| SortedMap | Immutable, type‑invariant map whose keys are kept in sorted order. |
| SortedMap.NonEmpty | Non‑empty refinement of SortedMap with stronger guarantees. |
| SortedMap.Context | Factory/context for creating SortedMap instances with a given key comparator and tree parameters. |
| SortedMap.Builder | Mutable builder for efficiently constructing or mutating a SortedMap before freezing it. |
| SortedSet | Immutable, type‑invariant set of values kept in sorted order. |
| SortedSet.NonEmpty | Non‑empty refinement of SortedSet. |
| SortedSet.Context | Factory/context for creating SortedSet instances with a given comparator and tree parameters. |
| SortedSet.Builder | Mutable builder for efficiently constructing or mutating a SortedSet before freezing it. |

You can import them via:

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

---

Working with SortedMap

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

// Construction
const empty = SortedMap.empty();
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

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

// Construction
const empty = SortedSet.empty();
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:

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

// Comparator compatible with the Comp 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({
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

$3

`sh
npm install @rimbu/sorted


or

yarn add @rimbu/sorted

or

bun add @rimbu/sorted

or

deno add npm:@rimbu/sorted
`

$3

@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.