!@thi.ng/associative

!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
- Why?
- Comparison with ES6 native types
- Status
- Installation
- Dependencies
- Usage examples
- API
- IEquivSet
- ArraySet
- LLSet
- EquivMap
- HashMap
- Authors
- License

About

ES Map/Set-compatible implementations with customizable equality semantics & supporting operations.

> [!IMPORTANT]
> In July 2024 this package was restructured and split-up to extract some
> features into smaller more focused packages:
>
> - @thi.ng/bidir-index
> - @thi.ng/object-utils
> - @thi.ng/sorted-map
> - @thi.ng/sparse-set
> - @thi.ng/trie

- Array based ArraySet, Linked List based LLSet and customizable EquivMap
& HashMap implementing the full ES6 Map/Set APIs and additional features:
- ICopy, IEmpty & IEquiv implementations
- ICompare implementation for sorted types
- multiple value additions / updates / deletions via into(), dissoc()
(maps) and disj() (sets)
- configurable key equality & comparison (incl. default implementations)
- getters w/ optional "not-found" default value
- Polymorphic set operations (union, intersection, difference) - works with both
native and custom Sets and retains their types
- Natural & selective
joins
(incl. key renaming, ported from Clojure)

Please see these packages for some example use cases:

- @thi.ng/cache
- @thi.ng/dgraph
- @thi.ng/ecs
- @thi.ng/rstream-query

$3

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

``ts
// first two objects w/ equal values
const a = [1, 2];
const b = [1, 2];
`

Using native implementations

`ts
const set = new Set();
set.add(a);
set.has(b);
// false

const map = new Map();
map.set(a, "foo");
map.get(b);
// undefined
`

Using custom implementations:

`ts
import { defArraySet } from "@thi.ng/associative";

const set = defArraySet();
set.add(a);
set.add({a: 1});
// ArraySet { [ 1, 2 ], { a: 1 } }
set.has(b);
// true
set.has({a: 1});
// true
`

`ts
import { defLLSet } from "@thi.ng/associative";

const set = defLLSet();
set.add(a);
set.add({a: 1});
// LLSet { [ 1, 2 ], { a: 1 } }

set.has(b);
// true

set.has({a: 1});
// true
`

`ts
import { defEquivMap, ArraySet } from "@thi.ng/associative";

// by default EquivMap uses ArraySet for its canonical keys
// const map = defEquivMap();

// with custom implementation
const map = defEquivMap(null, { keys: ArraySet });
map.set(a, "foo");
// EquivMap { [ 1, 2 ] => 'foo' }

map.get(b);
// "foo"
`

`ts
import { defHashMap } from "@thi.ng/associative";
import { hash } from "@thi.ng/vectors"

// Hash map w/ user supplied hash code function
// (here using hash function for arrays)
const map = defHashMap([], { hash })
map.set([1, 2], "a");
map.set([3, 4, 5], "b");
map.set([1, 2], "c");
// HashMap { [ 1, 2 ] => 'c', [ 3, 4, 5 ] => 'b' }
`

Status

STABLE - used in production

Search or submit any issues for this package

Installation

`bash
yarn add @thi.ng/associative
`

ESM import:

`ts
import * as assoc from "@thi.ng/associative";
`

Browser ESM import:

`html

`

JSDelivr documentation

For Node.js REPL:

`js
const assoc = await import("@thi.ng/associative");
`

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

Dependencies

- @thi.ng/api
- @thi.ng/arrays
- @thi.ng/binary
- @thi.ng/checks
- @thi.ng/dcons
- @thi.ng/equiv
- @thi.ng/object-utils
- @thi.ng/transducers

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

Usage examples

Four projects in this repo's
/examples
directory are using this package:

| Screenshot | Description | Live demo | Source |
|:------------------------------------------------------------------------------------------------------------------------------|:-------------------------------------------------------------------------------------------|:-------------------------------------------------------------|:------------------------------------------------------------------------------------------|
| | Heatmap visualization of this mono-repo's commits | | Source |
| | Augmenting thi.ng/geom shapes for WebGL, using instancing & attribute buffers | Demo | Source |
| | rstream & transducer-based FSM for converting key event sequences into high-level commands | Demo | Source |
| | Responsive image gallery with tag-based Jaccard similarity ranking | Demo | Source |

API

Generated API docs

$3

All Set implementations in this package implement the
IEquivSet
interface, an extension of the native ES6 Set API.

$3

Simple array based Set implementation which by default uses
@thi.ng/equiv
for value equivalence checking.

$3

Similar to ArraySet, but uses
@thi.ng/dcons linked list
as backing storage for values.

$3

This Map implementation uses a native ES6 Map as backing storage for
its key-value pairs and an additional IEquivSet implementation for
canonical keys. By default uses ArraySet for this purpose.

$3

Map implementation w/ standard ES6 Map API, supporting any key type via
hash codes computed via user supplied hash function. Uses Open
Addressing / Linear
Probing to resolve key collisions. Customizable via HashMapOpts
constructor argument. Hash function MUST be given.

Authors

- Karsten Schmidt

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

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

License

© 2017 - 2026 Karsten Schmidt // Apache License 2.0