[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Bug#943330: ITP: functional-red-black-tree -- fully persistent balanced binary search tree - Node.js library



Package: wnpp
Severity: wishlist
Owner: Jonas Smedegaard <dr@jones.dk>

* Package name     : node-functional-red-black-tree
  Version          : 1.0.1
  Upstream Author  : Mikola Lysenko <mikolalysenko@gmail.com>
* Url              : https://github.com/mikolalysenko/functional-red-black-tree
* Licenses         : Expat
  Programming Lang : JavaScript

 Functional-red-black-tree is a fully persistent red-black tree
 written 100% in JavaScript.
 .
 Functional (or fully persistent) 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 package is neede for ESLint.

I plan to maintain this package in the JavaScript team, keeping 
debianization in following Git repository:

     https://salsa.debian.org/js-team/node-functional-red-black-tree.git


 - Jonas

-- 
 * Jonas Smedegaard - idealist & Internet-arkitekt
 * Tlf.: +45 40843136  Website: http://dr.jones.dk/

 [x] quote me freely  [ ] ask before reusing  [ ] keep private

Attachment: signature.asc
Description: signature


Reply to: