Skiplist-based sorted map & set implementation
npm install @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
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).
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 ] ]
`
Sorted set implementation with standard ES6 Set API, customizable value
equality and comparison semantics and additional functionality:
- range queries (via entries, keys, values)into()
- multiple value addition/deletion via and disj()
Furthermore, this class implements the ICopy, IEmpty, ICompare andIEquiv 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.
STABLE - used in production
Search or submit any issues for this package
- @thi.ng/associative - ES Map/Set-compatible implementations with customizable equality semantics & supporting operations
`bash`
yarn add @thi.ng/sorted-map
ESM import:
`ts`
import * as sm from "@thi.ng/sorted-map";
Browser ESM import:
`html`
For Node.js REPL:
`js`
const sm = await import("@thi.ng/sorted-map");
Package sizes (brotli'd, pre-treeshake): ESM: 1.91 KB
- @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)
`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"
`
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
}
© 2018 - 2026 Karsten Schmidt // Apache License 2.0