sorted-map

Note

This is one of 199 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).

SortedMap

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

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 ] ]

SortedSet

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

yarn add @thi.ng/sorted-map

ESM import:

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

Browser ESM import:

<script type="module" src="https://esm.run/@thi.ng/sorted-map"></script>

JSDelivr documentation

For Node.js REPL:

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

Package sizes (brotli'd, pre-treeshake): ESM: 1.71 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

Basic usage

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:

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

License

© 2018 - 2024 Karsten Schmidt // Apache License 2.0