Have ideas to improve npm?Join in the discussion! »

    @thi.ng/associative
    TypeScript icon, indicating that this package has built-in type declarations

    5.2.2 • Public • Published

    associative

    npm version npm downloads Twitter Follow

    This project is part of the @thi.ng/umbrella monorepo.

    About

    Alternative Map and Set implementations with customizable equality semantics & supporting operations.

    • Array based ArraySet, Linked List based LLSet, Skiplist based SortedMap & SortedSet and customizable EquivMap implement the full ES6 Map/Set APIs and additional features:
      • range query iterators (via entries(), keys(), values()) (sorted types only)
      • 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
      • fromObject() converters (for maps only)
    • TrieMap for string-based keys and MultiTrie for array-like keys and multiple values per key
    • SparseSet implementations for numeric values
    • 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)
    • Key-value pair inversion for maps and vanilla objects
      • i.e. swaps K => V to V => K
    • Single or multi-property index generation for maps and objects
    • Key selection & renaming / transformations for maps and objects

    Why?

    Please see these packages for some example use cases:

    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
    a = [1, 2];
    b = [1, 2];

    Using native implementations

    set = new Set();
    set.add(a);
    set.has(b);
    // false
    
    map = new Map();
    map.set(a, "foo");
    map.get(b);
    // undefined

    Using custom implementations:

    set = defArraySet();
    set.add(a);
    set.add({a: 1});
    // ArraySet { [ 1, 2 ], { a: 1 } }
    set.has(b);
    // true
    set.has({a: 1});
    // true
    
    set = defLLSet();
    set.add(a);
    set.add({a: 1});
    // LLSet { [ 1, 2 ], { a: 1 } }
    set.has(b);
    // true
    set.has({a: 1});
    // true
    
    // by default EquivMap uses ArraySet for its canonical keys
    map = defEquivMap();
    
    // with custom implementation
    map = defEquivMap(null, { keys: assoc.ArraySet });
    map.set(a, "foo");
    // EquivMap { [ 1, 2 ] => 'foo' }
    map.get(b);
    // "foo"
    
    // Hash map w/ user supplied hash code function
    // (here using `hash` function for arrays)
    import { hash } from "@thi.ng/vectors"
    
    m = defHashMap([], { hash })
    m.set([1, 2], "a");
    m.set([3, 4, 5], "b");
    m.set([1, 2], "c");
    // HashMap { [ 1, 2 ] => 'c', [ 3, 4, 5 ] => 'b' }
    
    set = defSortedSet([a, [-1, 2], [-1, -2]]);
    // SortedSet { [ -1, -2 ], [ -1, 2 ], [ 1, 2 ] }
    set.has(b);
    // true
    
    map = defSortedMap([[a, "foo"], [[-1,-2], "bar"]]);
    // SortedMap { [ -1, -2 ] => 'bar', [ 1, 2 ] => 'foo' }
    map.get(b);
    // "foo"
    
    // key lookup w/ default value
    map.get([3,4], "n/a");
    // "n/a"

    Status

    STABLE - used in production

    Search or submit any issues for this package

    Installation

    yarn add @thi.ng/associative
    // ES module
    <script type="module" src="https://unpkg.com/@thi.ng/associative?module" crossorigin></script>
    
    // UMD
    <script src="https://unpkg.com/@thi.ng/associative/lib/index.umd.js" crossorigin></script>

    Package sizes (gzipped, pre-treeshake): ESM: 6.32 KB / CJS: 6.50 KB / UMD: 6.30 KB

    Dependencies

    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.

    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:

    Ranged queries

    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.

    SparseSet8/16/32

    Sparse sets provide super fast (approx. 4x faster than the native Set impl) insertion & lookups for numeric values in the interval [0..n) . The implementation in this package provides most of the ES6 Set API and internally relies on 2 uint typed arrays, with the actual backing type dependent on n.

    Furthermore, unless (or until) values are being removed from the set, they retain their original insertion order. For some use cases (e.g. deduplication of values), this property can be very useful.

    // create sparse set for value range 0 - 99 (uint8 backed)
    const a = defSparseSet(100);
    a.into([99, 42, 66, 23, 66, 42]);
    // SparseSet8 { 99, 42, 66, 23 }
    
    a.has(66)
    // true
    
    // sparse sets are iterable
    [...a]
    // [ 99, 42, 66, 23 ]
    
    // attempting to add out-of-range values will fail
    a.add(100)
    // SparseSet8 { 99, 42, 66, 23 }
    
    // create sparse set for 16 bit value range 0 - 0xffff (uint16 backed)
    const b = defSparseSet(0x10000);
    // SparseSet16 {}

    TrieMap

    Tries (also called Prefix maps) are useful data structures for search based use cases, auto-complete, text indexing etc. and provide partial key matching (prefixes), suffix iteration for a common prefix, longest matching prefix queries etc.

    The implementations here too feature ES6 Map-like API, similar to other types in this package, with some further trie-specific additions.

    const trie = defTrieMap([
      ["hey", "en"],
      ["hello", "en"],
      ["hallo", "de"],
      ["hallo", "de-at"],
      ["hola", "es"],
      ["hold", "en"],
      ["hej", "se"],
    ]);
    
    trie.knownPrefix("hole")
    // "hol"
    
    [...trie.suffixes("he")]
    // [ "j", "llo", "y" ]
    
    // w/ prefix included
    [...trie.suffixes("he", true)]
    // [ "hej", "hello", "hey" ]

    MultiTrie

    The MultiTrie is similar to TrieMap, but supports array-like keys and multiple values per key. Values are stored in sets whose implementation can be configured via ctor options.

    // init w/ custom value set type (here only for illustration)
    const t = defMultiTrie<string[], string>(null, { vals: () => new ArraySet() });
    
    t.add("to be or not to be".split(" "), 1);
    t.add("to be or not to be".split(" "), 2);
    t.add("to be and to live".split(" "), 3);
    
    t.get("to be or not to be".split(" "))
    // Set(2) { 1, 2 }
    
    t.knownPrefix(["to", "be", "not"]);
    // [ "to", "be" ]
    
    // auto-complete w/ custom separator between words
    [...t.suffixes(["to", "be"], false, "/")]
    // [ "and/to/live", "or/not/to/be" ]

    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 - 2021 Karsten Schmidt // Apache Software License 2.0

    Install

    npm i @thi.ng/associative

    DownloadsWeekly Downloads

    2,448

    Version

    5.2.2

    License

    Apache-2.0

    Unpacked Size

    343 kB

    Total Files

    70

    Last publish

    Collaborators

    • avatar