🌵 @aureooms/js-fingertree
Finger trees for JavaScript. See docs. Parent is @aureooms/js-persistent.
data FingerTree x = Empty
| Single x
| Deep ( Digit x ) ( FingerTree ( Node x ) ) ( Digit x )
-
👩🏫 API reference 📜 References🔗 Links
👩🏫 API reference
The data structure is fully persistent: All methods are pure functions that do not modify their object.
The parent project shows how specialized persistent data structures can be build on top of those methods.
🌵 Definition of a Tree
data Tree x = Empty
| Single x
| Deep ( Digit x ) ( Tree ( Node x ) ) ( Digit x )
📏 Definition of a Measure
Measure = (
plus = ( x , x ) -> m
measure = x -> m
zero = ( ) => m
)
Measure
Example of a The following measure will compute the size of each subtree.
const counter = {
plus : ( x , y ) => x + y ,
measure : x => 1 ,
zero : ( ) => 0 ,
} ;
See also @aureooms/js-measure for more examples of measures and see @aureooms/js-persistent for examples of data structures that can be build on top of this abstraction.
📦 How to import
⚠️ The code requiresregeneratorRuntime
to be defined, for instance by importing regenerator-runtime/runtime.
First, require the polyfill at the entry point of your application:
require( 'regenerator-runtime/runtime' ) ;
// or
import 'regenerator-runtime/runtime.js' ;
Then require what you need from the exported object, for instance the two main
API functions from
and empty
:
const { from , empty } = require( '@aureooms/js-fingertree' ) ;
// or
import { from , empty } from '@aureooms/js-fingertree' ;
👶 How to create a Tree
empty(Measure) -> Tree
Create an empty tree from a measure object.
let tree = empty( counter ) ;
from(Measure, Iterable) -> Tree
Create a tree from a measure object and an iterable.
let tree = from( counter , 'abc' ) ;
❓ Predicates
Tree#measure() -> m
Returns the measure of the tree.
if ( tree.measure() > 1 ) ...
Tree#isEmpty() -> Boolean
Returns true
if the tree is empty, false
otherwise.
return tree.isEmpty() ? 'empty' : 'not empty' ;
🧂 Add values
Tree#push(x) -> Tree
Returns a new tree with an additional value as the new right-most value.
tree = tree.push('k');
Tree#cons(x) -> Tree
Returns a new tree with an additional value as the new left-most value.
tree = tree.cons('g');
Tree#append(Iterable) -> Tree
Equivalent to applying push
to each value of the iterable in order.
tree.append( 'www' ) ;
Tree#prepend(Iterable) -> Tree
Equivalent to applying cons
to each value of the iterable in reverse order.
tree.prepend( 'xyz' ) ;
🍕 Slice
Tree#head() -> x
Returns the left-most value in the tree.
let head = tree.head() ; // 'a'
Tree#last() -> x
Returns the right-most value in the tree.
let last = tree.last() ; // 'b'
Tree#init() -> Tree
Returns a new tree without the right-most value.
while ( ! tree.isEmpty() ) tree = tree.init() ;
Tree#tail() -> Tree
Returns a new tree without the left-most value.
while ( ! tree.isEmpty() ) tree = tree.tail() ;
🌗 Merge
Tree#concat(Tree) -> Tree
Returns the concatenation of two trees.
tree = tree.concat( tree );
💔 Split
The following methods allow you to efficiently split a tree at the value where the measure crosses a given threshold.
Tree#splitTree(Function, m) -> [ Tree , x , Tree ]
Split the tree into a left tree, a middle value, and a right tree according to
a predicate on the measure of the tree increased by a constant measure m
.
The predicate must be monotone, false then true, on prefixes of the values in
left-to-right order. The middle value x
is the value for which the predicate
switches from false to true.
let [ left , middle , right ] = tree.splitTree( measure => measure > 1 , 1 ) ;
Tree#split(Function) -> [ Tree , Tree ]
Split the tree into a left tree and a right tree according to a predicate on the measure of the tree. The predicate must be monotone, false then true, on prefixes of the values in left-to-right order. The left-most value of the right tree is the value for which the predicate switches from false to true.
let [ left , right ] = tree.split( measure => measure > 2 ) ;
Tree#takeUntil(Function) -> Tree
Returns the left tree of Tree#split
.
let left = tree.takeUntil( measure => measure > 2 ) ;
Tree#dropUntil(Function) -> Tree
Returns the right tree of Tree#split
.
let right = tree.dropUntil( measure => measure > 2 ) ;
🛸 Visit
Tree[Symbol.iterator]() -> Iterable
Returns an iterator on the values of the tree in left-to-right order.
for ( const x of tree ) console.log( x ) ;
Tree#reversed() -> Iterable
Returns an iterator on the values of the tree in right-to-left order.
for ( const x of tree.reversed() ) console.log( x ) ;
📜 References
🔗 Links
-
A coffeescript implementation with ZLIB licensing (
✅ the implementation is correct) -
An implementation in Python with Apache licensing (
⚠️ the implementation is missing splitting functionality) -
A JavaScript implementation with MIT licensing (
🚨 the implementation is incorrect)