associative

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

Why?

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

Comparison with ES6 native types

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

Using native implementations

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:

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

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

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"

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

yarn add @thi.ng/associative

ESM import:

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

Browser ESM import:

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

JSDelivr documentation

For Node.js REPL:

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

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

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

IEquivSet

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

ArraySet

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

LLSet

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

EquivMap

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.

HashMap

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:

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

License

© 2017 - 2024 Karsten Schmidt // Apache License 2.0