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

    2.3.26 • Public • Published

    dcons

    npm version npm downloads Twitter Follow

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

    About

    Double-linked lists with comprehensive set of operations (incl. optional self-organizing behaviors).

    • ES6 iterator support
    • Stack & queue API (front and/or back)
    • Random node access (read / write, O(n/2))
    • Node insertion (also w/ custom comparator)
    • Node finding (O(n))
    • Node swaps (O(1))
    • Reversing (O(n/2))
    • Rotation (left / right) (O(1))
    • Shuffling (configurable, support custom PRNG)
    • Sorting (Merge sort, w/ custom comparator)
    • Slicing (sublist copies)
    • Splicing (delete and/or insert)
    • release() (emptying, GC friendly)
    • concat() / into()
    • map() / filter() / reduce()
    • compare() / equiv()
    • toJSON() transform (-> array)

    v2.3.0 adds the self-organizing list type SOL (an extension of DCons), which dynamically re-orders items based on certain accesses and offers these two built-in strategies:

    • defMTF() - moves currently accessed element to front of list
    • defTranspose() - swaps currently accessed element with its predecessor

    Only the following operations will trigger the self-organizing behavior:

    • nth()
    • setNth()
    • setTail()
    • find()
    • findWith()

    Btw. Also see @thi.ng/cache for more LRU, MRU implementations based on managed DCons impls...

    Status

    STABLE - used in production

    Search or submit any issues for this package

    Installation

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

    Package sizes (gzipped, pre-treeshake): ESM: 2.11 KB / CJS: 2.19 KB / UMD: 2.29 KB

    Dependencies

    API

    Generated API docs

    Head centric

    • cons()
    • first()
    • drop()
    • setHead()

    Tail centric

    • into()
    • push()
    • peek()
    • pop()
    • setTail()

    Random Access

    • .length
    • nth()
    • nthCell()
    • setNth()

    Insertion

    • insertBefore()
    • insertAfter()
    • insertBeforeNth()
    • insertAfterNth()
    • insertSorted()

    Finding

    • find()
    • findWith()

    Structure

    • copy()
    • concat()
    • slice()
    • splice()
    • swap()
    • shuffle()
    • sort()
    • reverse()
    • rotateLeft()
    • rotateRight()
    • release()

    TODO

    Authors

    Karsten Schmidt

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

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

    License

    © 2017 - 2021 Karsten Schmidt // Apache Software License 2.0

    Install

    npm i @thi.ng/dcons

    DownloadsWeekly Downloads

    3,297

    Version

    2.3.26

    License

    Apache-2.0

    Unpacked Size

    110 kB

    Total Files

    14

    Last publish

    Collaborators

    • avatar