dcons

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

• About
  • Status
• Installation
• Dependencies
• API
  • Head centric
  • Tail centric
  • Random Access
  • Insertion
  • Finding
  • Structure
• Authors
• License

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 import:

<script type="module" src="https://cdn.skypack.dev/@thi.ng/dcons"></script>

Skypack documentation

For Node.js REPL:

# with flag only for < v16
node --experimental-repl-await

> const dcons = await import("@thi.ng/dcons");

Package sizes (gzipped, pre-treeshake): ESM: 2.61 KB

Dependencies

• @thi.ng/api
• @thi.ng/checks
• @thi.ng/compare
• @thi.ng/equiv
• @thi.ng/errors
• @thi.ng/random
• @thi.ng/transducers

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