npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

@aureooms/js-fingertree

v6.0.0

Published

Finger Trees for JavaScript

Downloads

6

Readme

:cactus: @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 )

License Version Build Dependencies Dev dependencies GitHub issues Downloads

Code issues Code maintainability Code coverage (cov) Code technical debt Documentation Package size

:woman_teacher: 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.

:cactus: Definition of a Tree

data Tree x = Empty
            | Single x
            | Deep ( Digit x ) ( Tree ( Node x ) ) ( Digit x )

:straight_ruler: Definition of a Measure

Measure = (
  plus = ( x , x ) -> m
  measure = x -> m
  zero = ( ) => m
)

Example of a Measure

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.

:package: How to import

:warning: The code requires regeneratorRuntime 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' ;

:baby: 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' ) ;

:question: 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' ;

:salt: 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' ) ;

:pizza: 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() ;

:last_quarter_moon: Merge

Tree#concat(Tree) -> Tree

Returns the concatenation of two trees.

tree = tree.concat( tree );

:broken_heart: 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 ) ;

:flying_saucer: 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 ) ;

:scroll: References

:link: Links