!@thi.ng/sorted-map

!npm downloads

> [!NOTE]
> This is one of 214 standalone projects, maintained as part
> of the @thi.ng/umbrella monorepo
> and anti-framework.
>
> 🚀 Please help me to work full-time on these projects by sponsoring me on
> GitHub. Thank you! ❤️

- About
- SortedMap
- Ranged queries
- SortedSet
- Status
- Related packages
- Installation
- Dependencies
- API
- Basic usage
- Authors
- License

About

Skiplist-based sorted map & set implementation.

This package contains functionality which was previously part of and has been
extracted from the @thi.ng/associative package.

Skiplist based SortedMap &
SortedSet implementing the full ES6 Map/Set APIs and additional features:

- range query iterators (via entries(), keys(), values())
- ICompare,
ICopy,
IEmpty &
IEquiv
implementations
- multiple value additions / updates / deletions via .into(), .dissoc() or
.disj()
- configurable key equality & comparison (incl. default implementations)
- getters w/ optional "not-found" default value

The native ES6 implementations use object reference identity to determine
key containment, but often it's **more practical and useful to use equivalent
value semantics** for this purpose, especially when keys are structured data
(arrays / objects).

Note: It's the user's responsibility to ensure the inserted keys are kept
immutable (even if technically they're not).

$3

Alternative implementation of the ES6 Map API using a Skip list as
backing store and support for configurable key equality and sorting
semantics. Like with sets, uses @thi.ng/equiv & @thi.ng/compare by
default.

William Pugh's (creator of this data structure) description:

> "Skip lists are probabilistic data structures that have the same
asymptotic expected time bounds as balanced trees, are simpler, faster
and use less space."

Data structure description:

- ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
- https://en.wikipedia.org/wiki/Skip_list

#### Ranged queries

``ts
import { defSortedMap } from "@thi.ng/sorted-map";

map = defSortedMap([
["c", 3], ["a", 1], ["d", 4], ["b", 2]
]);
// SortedMap { 'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4 }

// all entries
[...map.entries()]
// [ [ 'd', 4 ], [ 'c', 3 ], [ 'b', 2 ], [ 'a', 1 ] ]

// range query w/ given start key
// also works with keys() and values()
[...map.entries("c")]
// [ [ 'c', 3 ], [ 'd', 4 ] ]

// unknown start keys are ok
[...map.entries("cc")]
// [ [ 'd', 4 ] ]

// range query w/ given MAX key
[...map.entries("c", true)]
// [ [ 'a', 1 ], [ 'b', 2 ], [ 'c', 3 ] ]
`

$3

Sorted set implementation with standard ES6 Set API, customizable value
equality and comparison semantics and additional functionality:

- range queries (via entries, keys, values)
- multiple value addition/deletion via into() and disj()

Furthermore, this class implements the ICopy, IEmpty, ICompare and
IEquiv interfaces defined by @thi.ng/api. The latter two allow
instances to be used as keys themselves in other data types defined in
this (and other) package(s).

This set uses a SortedMap as backing store.

Status

STABLE - used in production

Search or submit any issues for this package

Related packages

- @thi.ng/associative - ES Map/Set-compatible implementations with customizable equality semantics & supporting operations

Installation

`bash
yarn add @thi.ng/sorted-map
`

ESM import:

`ts
import * as sm from "@thi.ng/sorted-map";
`

Browser ESM import:

`html

`

JSDelivr documentation

For Node.js REPL:

`js
const sm = await import("@thi.ng/sorted-map");
`

Package sizes (brotli'd, pre-treeshake): ESM: 1.91 KB

Dependencies

- @thi.ng/api
- @thi.ng/associative
- @thi.ng/checks
- @thi.ng/compare
- @thi.ng/random
- @thi.ng/transducers

Note: @thi.ng/api is in _most_ cases a type-only import (not used at runtime)

API

Generated API docs

$3

`ts
import { defSortedSet, defSortedMap } from "@thi.ng/sorted-map";

// define keys w/ equal values
const a = [1, 2];
const b = [1, 2];

const set = defSortedSet([a, [-1, 2], [-1, -2]]);
// SortedSet { [ -1, -2 ], [ -1, 2 ], [ 1, 2 ] }

// b was not added directly, but the set uses value equality
set.has(b);
// true

const map = defSortedMap([[a, "foo"], [[-1, -2], "bar"]]);
// SortedMap { [ -1, -2 ] => 'bar', [ 1, 2 ] => 'foo' }

// b was not added directly, but the set uses value equality
map.get(b);
// "foo"

// key lookup w/ default value
map.get([3, 4], "n/a");
// "n/a"
`

Authors

- Karsten Schmidt

If this project contributes to an academic publication, please cite it as:

`bibtex
@misc{thing-sorted-map,
title = "@thi.ng/sorted-map",
author = "Karsten Schmidt",
note = "https://thi.ng/sorted-map",
year = 2018
}
``

License

© 2018 - 2026 Karsten Schmidt // Apache License 2.0