Bug#926899: RFP: node-evacuated-functional-red-black-tree -- A purely functional red-black tree data structure (in javascript)
Package: wnpp
Severity: wishlist
* Package name : node-evacuated-functional-red-black-tree
Version : 1.0.1
Upstream Author : Mikola Lysenko
* URL : https://salsa.debian.org/themusicgod1-guest/evacuated-functional-red-black-tree/
* License : MIT
Programming Lang: javascript
Description : A purely functional red-black tree data structure (in javascript)
from it's npm:
"A fully persistent red-black tree written 100% in JavaScript. Works both in node.js
and in the browser via browserify.
Functional (or fully presistent) data structures allow for non-destructive updates.
So if you insert an element into the tree, it returns a new tree with the inserted
element rather than destructively updating the existing tree in place. Doing this
requires using extra memory, and if one were naive it could cost as much as
reallocating the entire tree. Instead, this data structure saves some memory by
recycling references to previously allocated subtrees. This requires using only
O(log(n)) additional memory per update instead of a full O(n) copy.
Some advantages of this is that it is possible to apply insertions and removals to
the tree while still iterating over previous versions of the tree. Functional and
persistent data structures can also be useful in many geometric algorithms like
point location within triangulations or ray queries, and can be used to analyze
the history of executing various algorithms. This added power though comes at a
cost, since it is generally a bit slower to use a functional data structure than an
imperative version. However, if your application needs this behavior then you may
consider using this module."
This version of functional-red-black-tree has been evacuated from the NSA/Microsoft
walled garden. functional-red-black-tree is a prerequisite of eslint ( #743404 ).
Reply to: