fingertree-actually-good

v0.9.0

Published

3 years ago

A javascript implementation of fingertrees that is actually good. i.e. bug free, feature-rich, fast and light-weight.

Downloads

0High
0Medium
0Low

elias-sundqvist

fingertree data structure functional persistent npm

Travis CI npm GitHub

fingertree-actually-good

A good (fast, unit tested, and with full functionality) fingertree implementation in JavaScript.

Installation

npm install fingertree-actually-good

Usage

Importing the library

import fingertree from 'fingertree-actually-good';

API Documentation:

Function: fingertree<MeasureMonoid>

▸ fingertree<MeasureMonoid>(measure: MeasureMonoid): FingerTree‹inferElem‹MeasureMonoid›, inferMeasureVal‹MeasureMonoid›, MeasureMonoid›

Create an empty fingertree which uses the provided measure monoid

Example:

const arrayListMeasure = {
    base: ()=>1,
    sum: (x,y)=>x+y,
    zero: ()=>0
}
const myTree = fingertree(arrayListMeasure)

Type parameters:

▪ MeasureMonoid: Measure‹any, any›

The measure to be used by the tree

Parameters:

Name | Type | Description | ------ | ------ | ------ | measure | MeasureMonoid | The measure monoid that should be used by the tree. |

Returns: FingerTree‹inferElem‹MeasureMonoid›, inferMeasureVal‹MeasureMonoid›, MeasureMonoid›

Interface: Measure <Element, MeasureValue>

A measure can be any monoid.

Type parameters

▪ Element

The type of elements which are measured by the monoid

▪ MeasureValue

The type of values returned returned by the monoid

Example:

const arrayListMeasure = {
    base: ()=>1,
    sum: (x,y)=>x+y,
    zero: ()=>0
}

Methods

base

▸ base(x: Element): MeasureValue

Base is used to compute the initial measure of each element in the tree

Parameters:

Name | Type | Description | ------ | ------ | ------ | x | Element | an initial element of type Element |

Returns: MeasureValue

the initial measure for the element

Example:

// used for array lists
base: () => 1;

sum

▸ sum(x: MeasureValue, y: MeasureValue): MeasureValue

Sum is used to combine the measures of two nodes in the tree. A monoid should be associative, so sum(a,sum(b,c)) === sum(sum(a,b),c)

Parameters:

Name | Type | Description | ------ | ------ | ------ | x | MeasureValue | the measure of the first part | y | MeasureValue | the measure of the second part |

Returns: MeasureValue

the combined measure

Example:

// used for array lists
sum: (x,y) => x+y;

zero

▸ zero(): MeasureValue

The measure of an empty tree.

Returns: MeasureValue

the measure of an empty tree.

Example:

// used for array lists
zero: () => 0;

Class: FingerTree <Element, MeasureValue, MeasureMonoid>

A FingerTree is a persistent functional data structure that can be used to quickly split and combine large sequences arbitrarily. It also gives quick access to the first and last elements of the tree.

Type parameters

▪ Element

The type of elements stored by the tree

▪ MeasureValue

The type of values returned by the measure

▪ MeasureMonoid: Measure‹Element, MeasureValue›

The measure to be used by the tree

Implements

Iterable‹Element›

Methods

[Symbol.iterator]

▸ [Symbol.iterator](): Iterator‹Element›

Iterate over the tree's elements from left to right.

Example

const t = fingertree(myMeasure);
const t2 = t.appendMany([1,2,3,4]);

//Now we can use iteration
// 1. in for loops
for(let i of t2) {console.log(i)}
// > output:
// > 1
// > 2
// > 3
// > 4

// 2. with spread operators
[...t2] // [1,2,3,4]

Returns: Iterator‹Element›

append

▸ append(x: Element): FingerTree‹Element, MeasureValue, MeasureMonoid›

Append a single element to the end of the tree.

Complexity: O(log n)

Amortized Complexity: O(1)

Example:

const t = fingertree(myMeasure).append(1)
t.flatten() // -> [1]
const t2 = t.append(4)
t2.flatten() // -> [1,4]

Parameters:

Name | Type | Description | ------ | ------ | ------ | x | Element | the element to append |

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

a new fingertree with the element appended

appendMany

▸ appendMany(iter: Iterable‹Element›): FingerTree‹Element, MeasureValue, MeasureMonoid›

Append all elements from an iterable to the end of the tree.

Complexity: O(m log n)

Amortized Complexity: O(m)

where m is the number of appended elements and n is the current number of elements in the list.

Example:

t = fingertree(myMeasure).appendMany([1,2,3])
t.flatten() // -> [1,2,3]

Parameters:

Name | Type | Description | ------ | ------ | ------ | iter | Iterable‹Element› | an iterable of elements |

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

a new fingertree with the elements appended

concat

▸ concat(fingerTree2: FingerTree‹Element, MeasureValue, MeasureMonoid›): FingerTree‹Element, MeasureValue, MeasureMonoid›

Concatenate two fingertrees into a single, bigger, fingertree.

Complexity: O(n log n)

Amortized Complexity: O(n log n)

Example:

const t = fingerTree(myMeasure);
const t1 = t.appendMany([1,2,3,4,5])
t1.flatten() // [1,2,3,4,5]
const t2 = t.appendMany([6,7,8,9,10])
t2.flatten() // [6,7,8,9,10]
const combined t1.concat(t2);
combined.flatten() // [1,2,3,4,5,6,7,8,9,10]

Parameters:

Name | Type | Description | ------ | ------ | ------ | fingerTree2 | FingerTree‹Element, MeasureValue, MeasureMonoid› | The finger tree who's elements will follow this tree. |

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

The concatenated tree

dropUntil

▸ dropUntil(pred: function, offset?: MeasureValue): FingerTree‹Element, MeasureValue, MeasureMonoid›

Make a tree by removing elements from the left until just before the predicate is true for the sum of the removed elements.

Complexity: O(n log n)

Amortized Complexity: O(n log n)

Example:

const arrayListMeasure = {
    base: (x)=>1,
    sum: (x,y)=>x+y,
    zero: ()=>0
}
const t = fingertree(arrayListMeasure).appendMany(['a','b','c','d','e','f','g','h','i','j'])
const t2 = t.dropUntil(x=>x>7)
t2.flatten() // ['h','i','j']

Parameters:

▪ pred: function

A predicate function that takes the measure of the left side and returns a Bool. Should only flip once as the input grows.

▸ (measured: MeasureValue): Boolean

Parameters:

Name | Type | ------ | ------ | measured | MeasureValue |

▪Optional offset: MeasureValue

A constant measure value which the predicate inputs can be offset by.

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

the new tree.

dropWhile

▸ dropWhile(pred: function, offset?: MeasureValue): FingerTree‹Element, MeasureValue, MeasureMonoid›

Make a tree by removing elements from the left until just before the predicate is false for the sum of the removed elements.

Complexity: O(n log n)

Amortized Complexity: O(n log n)

Example:

const arrayListMeasure = {
    base: (x)=>1,
    sum: (x,y)=>x+y,
    zero: ()=>0
}
const t = fingertree(arrayListMeasure).appendMany(['a','b','c','d','e','f','g','h','i','j'])
const t2 = t.dropWhile(x=>x<4)
t2.flatten() // ['d','e','f','g','h','i','j']

Parameters:

▪ pred: function

A predicate function that takes the measure of the left side and returns a Bool. Should only flip once as the input grows.

▸ (measured: MeasureValue): Boolean

Parameters:

Name | Type | ------ | ------ | measured | MeasureValue |

▪Optional offset: MeasureValue

A constant measure value which the predicate inputs can be offset by.

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

the new tree.

firstMatch

▸ firstMatch(pred: function, offset?: MeasureValue): Element

Find the first element such that the monoidal sum of its own measure with everything to the left makes the predicate true.

Example:

const arrayListMeasure = {
    base: (x)=>1,
    sum: (x,y)=>x+y,
    zero: ()=>0
}
const t = fingertree(arrayListMeasure).appendMany(['a','b','c','d','e'])
t.firstMatch(x=>x>=4) // 'd'

Parameters:

▪ pred: function

A predicate function that takes the measure of the left side and returns a Bool. Should only flip once as the input grows.

▸ (measured: MeasureValue): Boolean

Parameters:

Name | Type | ------ | ------ | measured | MeasureValue |

▪Optional offset: MeasureValue

A constant measure value which the predicate inputs can be offset by.

Returns: Element

the matching element

flatten

▸ flatten(): Element[]

Flatten the tree from left to right into a normal javascript array.

Complexity: O(n)

Example:

const t = fingertree(myMeasure);
t.append(1).prepend('h').append("hello").flatten() // ['h',1,"Hello"]

Returns: Element[]

head

▸ head(): Element

Get the first element in the tree

Complexity: O(1)

Amortized Complexity: O(1)

Example:

const t = fingertree(myMeasure).appendMany([1,2,3,4,5,6])
t.head() // 1

Returns: Element

The first element of the tree

init

▸ init(): FingerTree‹Element, MeasureValue, MeasureMonoid›

Get a new tree with the last element removed

Complexity: O(log n)

Amortized Complexity: O(1)

Example:

const t = fingertree(myMeasure).appendMany([1,2,3,4,5,6])
[...t.init()] // [1,2,3,4,5]

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

A new tree with the last element removed

isEmpty

▸ isEmpty(): Boolean

Check whether the tree is empty

Example

const t = fingertree(myMeasure);
t.isEmpty() // true;
const t2 = t.append(1);
t2.isEmpty() // false;

Returns: Boolean

last

▸ last(): Element

Get the last element in the tree

Complexity: O(1)

Amortized Complexity: O(1)

Example:

const t = fingertree(myMeasure).appendMany([1,2,3,4,5,6])
t.last() // 6

Returns: Element

The first element of the tree

map

▸ map(mapFunction: function): FingerTree‹Element, MeasureValue, MeasureMonoid›

Map each element e of the tree to mapFunction(e)

Example:

const t = fingerTree(myMeasure);
const t1 = t.appendMany([1,2,3,4,5])
const t2 = t1.map(x=>x*2)
t2.flatten() // [2,4,6,8,10]

Parameters:

▪ mapFunction: function

The mapping function

▸ (element: Element): Element

Parameters:

Name | Type | ------ | ------ | element | Element |

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

▸ map<T, M>(mapFunction: function, newMeasure: M): FingerTree‹T, inferMeasureVal‹M›, M›

Map each element e of the tree to mapFunction(e), and replace the measure being used.

Example:

const sumMeasure = {base: x=>x, sum: (x,y)=>x+y, zero: ()=>0};
const prodMeasure = {base: x=>x, sum: (x,y)=>x*y, zero: ()=>1};
const t = fingerTree(sumMeasure);
const t1 = t.appendMany([1,2,3,4,5])
t1.flatten() // [1,2,3,4,5]
t1.measure() // 1+2+3+4+5=15
const t2 = t1.map(x=>x*2, prodMeasure)
t2.flatten() // [2,4,6,8,10]
t2.measure() // 2*4*6*8*10=3840

Type parameters:

▪ T

▪ M: Measure‹T, any›

Parameters:

▪ mapFunction: function

The mapping function

▸ (element: Element): T

Parameters:

Name | Type | ------ | ------ | element | Element |

▪ newMeasure: M

The new measure

Returns: FingerTree‹T, inferMeasureVal‹M›, M›

mapTrue

▸ mapTrue(mapFunction: function, pred: function): FingerTree‹Element, MeasureValue, MeasureMonoid›

Map each element e that evaluates the predicate to true to mapFunction(e) The predicate must, as usual, first always evaluate to false and then always to true, but it has access to a dynamically updating globalMeasure which corresponds to the measure of the entire tree given the changes that have been made so far. This allows for some values to be skipped.

Example:

// in this example we double all the odd numbers
const myMeasure = {
   base: (x) => ({
     count: 1,
     firstOddPos: x % 2 ? 0 : Number.POSITIVE_INFINITY,
   }),
   sum: (x, y) => ({
     count: x.count + y.count,
     firstOddPos: Math.min(x.firstOddPos, x.count + y.firstOddPos),
   }),
   zero: () => ({ count: 0, firstOddPos: Number.POSITIVE_INFINITY }),
};
const t = fingertree(myMeasure);
const t2 = t.appendMany([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
const t3 = t2.mapTrue(
   (x) => x * 2,
   (left, glob) => left.count > glob.firstOddPos
);
t3.flatten() // [2, 2, 6, 4, 10, 6, 14, 8, 18, 10];

Parameters:

▪ mapFunction: function

The mapping function

▸ (element: Element, leftInclusiveMeasure: MeasureValue, globalMeasure: MeasureValue): Element

Parameters:

Name | Type | ------ | ------ | element | Element | leftInclusiveMeasure | MeasureValue | globalMeasure | MeasureValue |

▪ pred: function

A predicate function that takes the measure of the left side and returns a Bool. Should only flip once as the input grows.

▸ (leftInclusiveMeasure: MeasureValue, globalMeasure: MeasureValue): Boolean

Parameters:

Name | Type | ------ | ------ | leftInclusiveMeasure | MeasureValue | globalMeasure | MeasureValue |

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

measure

▸ measure(): MeasureValue

Compute the monoidal sum of all the tree's elements using the tree measure. This method is typically fast due to results being cached.

Example:

const prodMeasure = {
    base: (x)=>x,
    sum: (x,y)=>x*y,
    zero: ()=>1
}
const t = fingertree(prodMeasure).appendMany([1,2,3,4,5,6])
t.measure() // 720 (the product of all the numbers in the tree)

Returns: MeasureValue

the monoidal sum of the tree's elements.

prepend

▸ prepend(x: Element): FingerTree‹Element, MeasureValue, MeasureMonoid›

Prepend a single element to the start of the tree.

Complexity: O(log n)

Amortized Complexity: O(1)

Example:

const t = fingertree(myMeasure).prepend(1)
t.flatten() // -> [1]
const t2 = t.prepend(4)
t2.flatten() // -> [4,1]

Parameters:

Name | Type | Description | ------ | ------ | ------ | x | Element | the element to prepend |

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

a new fingertree with the element prepended

prependMany

▸ prependMany(iter: Iterable‹Element›): FingerTree‹Element, MeasureValue, MeasureMonoid›

Prepend all elements from an iterable to the start of the tree. Note that this reverses the elements.

Complexity: O(m log n)

Amortized Complexity: O(m)

where m is the number of appended elements and n is the current number of elements in the list.

Example:

t = fingertree(myMeasure).prependMany([1,2,3])
t.flatten() // -> [3,2,1]

Parameters:

Name | Type | Description | ------ | ------ | ------ | iter | Iterable‹Element› | an iterable of elements |

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

a new fingertree with the elements prepended

split

▸ split(pred: function, offset?: MeasureValue): [FingerTree‹Element, MeasureValue, MeasureMonoid›, FingerTree‹Element, MeasureValue, MeasureMonoid›]

Split the tree at the point where the left side is as large as possible without making the predicate true

Complexity: O(n log n)

Amortized Complexity: O(n log n)

Example:

const arrayListMeasure = {
    base: (x)=>1,
    sum: (x,y)=>x+y,
    zero: ()=>0
}
const t = fingertree(arrayListMeasure).appendMany(['a','b','c','d','e','f','g','h','i','j'])
const [left, right] = t.split(x=>x>7)
left.flatten() // ['a', 'b', 'c', 'd', 'e', 'f', 'g']
right.flatten() // ['h', 'i', 'j']

Parameters:

▪ pred: function

A predicate function that takes the measure of the left side and returns a Bool. Should only flip once as the input grows.

▸ (measured: MeasureValue): Boolean

Parameters:

Name | Type | ------ | ------ | measured | MeasureValue |

▪Optional offset: MeasureValue

A constant measure value which the predicate inputs can be offset by.

Returns: [FingerTree‹Element, MeasureValue, MeasureMonoid›, FingerTree‹Element, MeasureValue, MeasureMonoid›]

the [left, right] split as two new finger trees.

tail

▸ tail(): FingerTree‹Element, MeasureValue, MeasureMonoid›

Get a new tree with the first element removed

Complexity: O(log n)

Amortized Complexity: O(1)

Example:

const t = fingertree(myMeasure).appendMany([1,2,3,4,5,6])
t.tail().flatten() // [2,3,4,5,6]

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

A new tree with the first element removed

takeUntil

▸ takeUntil(pred: function, offset?: MeasureValue): FingerTree‹Element, MeasureValue, MeasureMonoid›

Make a tree by taking elements from the left until just before the predicate is true for the tree measure.

Complexity: O(n log n)

Amortized Complexity: O(n log n)

Example:

const arrayListMeasure = {
    base: (x)=>1,
    sum: (x,y)=>x+y,
    zero: ()=>0
}
const t = fingertree(arrayListMeasure).appendMany(['a','b','c','d','e','f','g','h','i','j'])
const t2 = t.takeUntil(x=>x>7)
t2.flatten() // ['a','b','c','d','e','f','g']

Parameters:

▪ pred: function

A predicate function that takes the measure of the left side and returns a Bool. Should only flip once as the input grows.

▸ (measured: MeasureValue): Boolean

Parameters:

Name | Type | ------ | ------ | measured | MeasureValue |

▪Optional offset: MeasureValue

A constant measure value which the predicate inputs can be offset by.

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

the new tree.

takeWhile

▸ takeWhile(pred: function, offset?: MeasureValue): FingerTree‹Element, MeasureValue, MeasureMonoid›

Make a tree by taking elements from the left until just before the predicate turns false for the tree measure.

Complexity: O(n log n)

Amortized Complexity: O(n log n)

Example:

const arrayListMeasure = {
    base: (x)=>1,
    sum: (x,y)=>x+y,
    zero: ()=>0
}
const t = fingertree(arrayListMeasure).appendMany(['a','b','c','d','e','f','g','h','i','j'])
const t2 = t.takeWhile(x=>x<4)
t2.flatten() // ['a','b','c']

Parameters:

▪ pred: function

A predicate function that takes the measure of the left side and returns a Bool. Should only flip once as the input grows.

▸ (measured: MeasureValue): Boolean

Parameters:

Name | Type | ------ | ------ | measured | MeasureValue |

▪Optional offset: MeasureValue

A constant measure value which the predicate inputs can be offset by.

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

the new tree.

updateFirstMatch

▸ updateFirstMatch(updateFunction: function, pred: function, offset?: MeasureValue): FingerTree‹Element, MeasureValue, MeasureMonoid›

Get a new fingertree where the first matching item is updated.

The first matching item is, similar to split, the first element for which the predicate is evaluated to true. The predicate function must only change once from false to true, going from left to right. And the input is the measure of the left side, including the element itself.

The update is performed by applying the updateFunction function to the matching element.

Example

const arrayListMeasure = {
    base: (x)=>1,
    sum: (x,y)=>x+y,
    zero: ()=>0
}
const t = fingertree(arrayListMeasure)
const t1 = t.appendMany([10,20,30,40,50])
const t2 = t1.updateFirstMatch(x=>x/2, x=>x>2)
t2.flatten() // [10, 20, 15, 40, 50]

Parameters:

▪ updateFunction: function

A function that takes the current first matching element and returns a new element to replace it with.

▸ (element: Element): Element

Parameters:

Name | Type | ------ | ------ | element | Element |

▪ pred: function

A predicate function that takes the measure of the left side and returns a Bool. Should only flip once as the input grows.

▸ (measured: MeasureValue): Boolean

Parameters:

Name | Type | ------ | ------ | measured | MeasureValue |

▪Optional offset: MeasureValue

A constant measure value which the predicate inputs can be offset by.

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

updateHead

▸ updateHead(updateFunction: function): FingerTree‹Element, MeasureValue, MeasureMonoid›

Get a new finger tree with the first element replaced

Parameters:

▪ updateFunction: function

A function that takes the current first element and returns the new one.

Example

const t = fingertree(myMeasure);
const t1 = t.appendMany([1,2,3,4,5])
const t2 = t1.updateHead(x=>x+10);
t2.flatten() // [11,2,3,4,5]

▸ (element: Element): Element

Parameters:

Name | Type | ------ | ------ | element | Element |

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

updateLast

▸ updateLast(updateFunction: function): FingerTree‹Element, MeasureValue, MeasureMonoid›

Get a new finger tree with the last element replaced

Parameters:

▪ updateFunction: function

A function that takes the current last element and returns the new one.

Example

const t = fingertree(myMeasure);
const t1 = t.appendMany([1,2,3,4,5])
const t2 = t1.updateLast(x=>x+10);
t2.flatten() // [1,2,3,4,15]

▸ (element: Element): Element

Parameters:

Name | Type | ------ | ------ | element | Element |

Returns: FingerTree‹Element, MeasureValue, MeasureMonoid›

Benchmark Results

FingerTree#PrependTo0ElemTree x 101,095,757 ops/sec ±4.13% (80 runs sampled)
FingerTree#PrependTo1ElemTree x 95,372,422 ops/sec ±3.93% (77 runs sampled)
FingerTree#PrependTo10ElemTree x 86,550,261 ops/sec ±3.58% (81 runs sampled)
FingerTree#PrependTo100ElemTree x 82,458,431 ops/sec ±5.00% (76 runs sampled)
FingerTree#PrependTo1000ElemTree x 87,829,141 ops/sec ±4.11% (76 runs sampled)
FingerTree#PrependTo10000ElemTree x 70,582,072 ops/sec ±18.48% (67 runs sampled)
FingerTree#PrependTo100000ElemTree x 47,440,836 ops/sec ±54.71% (72 runs sampled)
FingerTree#PrependTo1000000ElemTree x 85,858,594 ops/sec ±4.96% (78 runs sampled)
FingerTree#AppendTo0ElemTree x 98,193,690 ops/sec ±4.15% (80 runs sampled)
FingerTree#AppendTo1ElemTree x 54,093,354 ops/sec ±2.21% (86 runs sampled)
FingerTree#AppendTo10ElemTree x 76,189,385 ops/sec ±3.41% (83 runs sampled)
FingerTree#AppendTo100ElemTree x 74,198,772 ops/sec ±3.27% (78 runs sampled)
FingerTree#AppendTo1000ElemTree x 75,930,306 ops/sec ±3.00% (82 runs sampled)
FingerTree#AppendTo10000ElemTree x 78,203,402 ops/sec ±2.73% (84 runs sampled)
FingerTree#AppendTo100000ElemTree x 76,595,779 ops/sec ±3.12% (82 runs sampled)
FingerTree#AppendTo1000000ElemTree x 77,442,100 ops/sec ±3.29% (83 runs sampled)
FingerTree#TailOf0ElemTree x 63,371,844 ops/sec ±2.77% (85 runs sampled)
FingerTree#TailOf1ElemTree x 34,448,752 ops/sec ±1.26% (90 runs sampled)
FingerTree#TailOf10ElemTree x 12,296,696 ops/sec ±1.47% (91 runs sampled)
FingerTree#TailOf100ElemTree x 5,568,404 ops/sec ±6.42% (84 runs sampled)
FingerTree#TailOf1000ElemTree x 3,704,433 ops/sec ±0.59% (90 runs sampled)
FingerTree#TailOf10000ElemTree x 2,429,494 ops/sec ±1.39% (89 runs sampled)
FingerTree#TailOf100000ElemTree x 1,971,881 ops/sec ±0.58% (90 runs sampled)
FingerTree#TailOf1000000ElemTree x 1,871,120 ops/sec ±1.05% (89 runs sampled)
FingerTree#Measure0ElemTree x 71,492,164 ops/sec ±2.72% (85 runs sampled)
FingerTree#Measure1ElemTree x 57,105,188 ops/sec ±3.49% (82 runs sampled)
FingerTree#Measure10ElemTree x 40,236,396 ops/sec ±4.13% (88 runs sampled)
FingerTree#Measure100ElemTree x 40,104,284 ops/sec ±1.81% (90 runs sampled)
FingerTree#Measure1000ElemTree x 36,061,189 ops/sec ±4.89% (79 runs sampled)
FingerTree#Measure10000ElemTree x 37,208,668 ops/sec ±2.07% (83 runs sampled)
FingerTree#Measure100000ElemTree x 38,298,849 ops/sec ±2.36% (82 runs sampled)
FingerTree#Measure1000000ElemTree x 35,310,729 ops/sec ±9.61% (76 runs sampled)
FingerTree#RandomSplit0ElemTree x 10,631,511 ops/sec ±0.85% (91 runs sampled)
FingerTree#RandomSplit1ElemTree x 5,059,693 ops/sec ±0.89% (87 runs sampled)
FingerTree#RandomSplit10ElemTree x 213,546 ops/sec ±2.46% (85 runs sampled)
FingerTree#RandomSplit100ElemTree x 154,849 ops/sec ±2.54% (91 runs sampled)
FingerTree#RandomSplit1000ElemTree x 91,391 ops/sec ±2.65% (87 runs sampled)
FingerTree#RandomSplit10000ElemTree x 64,809 ops/sec ±1.54% (89 runs sampled)
FingerTree#RandomSplit100000ElemTree x 50,238 ops/sec ±0.64% (91 runs sampled)
FingerTree#RandomSplit1000000ElemTree x 38,263 ops/sec ±1.35% (91 runs sampled)
FingerTree#Concat0ElemTreeWith0ElemTree x 19,896,870 ops/sec ±0.81% (92 runs sampled)
FingerTree#Concat0ElemTreeWith1ElemTree x 19,213,649 ops/sec ±2.59% (88 runs sampled)
FingerTree#Concat0ElemTreeWith10ElemTree x 20,261,738 ops/sec ±0.97% (90 runs sampled)
FingerTree#Concat0ElemTreeWith100ElemTree x 20,073,775 ops/sec ±0.98% (90 runs sampled)
FingerTree#Concat0ElemTreeWith1000ElemTree x 20,414,365 ops/sec ±1.02% (92 runs sampled)
FingerTree#Concat0ElemTreeWith10000ElemTree x 20,613,424 ops/sec ±0.68% (92 runs sampled)
FingerTree#Concat0ElemTreeWith100000ElemTree x 20,544,998 ops/sec ±1.03% (90 runs sampled)
FingerTree#Concat0ElemTreeWith1000000ElemTree x 18,720,799 ops/sec ±3.92% (82 runs sampled)
FingerTree#Concat1ElemTreeWith0ElemTree x 3,614,523 ops/sec ±4.38% (83 runs sampled)
FingerTree#Concat1ElemTreeWith1ElemTree x 3,606,507 ops/sec ±0.50% (90 runs sampled)
FingerTree#Concat1ElemTreeWith10ElemTree x 3,686,210 ops/sec ±0.60% (89 runs sampled)
FingerTree#Concat1ElemTreeWith100ElemTree x 3,640,934 ops/sec ±0.61% (94 runs sampled)
FingerTree#Concat1ElemTreeWith1000ElemTree x 3,607,454 ops/sec ±1.29% (86 runs sampled)
FingerTree#Concat1ElemTreeWith10000ElemTree x 3,125,409 ops/sec ±2.50% (84 runs sampled)
FingerTree#Concat1ElemTreeWith100000ElemTree x 3,009,434 ops/sec ±8.50% (80 runs sampled)
FingerTree#Concat1ElemTreeWith1000000ElemTree x 2,183,878 ops/sec ±30.74% (57 runs sampled)
FingerTree#Concat10ElemTreeWith0ElemTree x 12,335,214 ops/sec ±14.48% (58 runs sampled)
FingerTree#Concat10ElemTreeWith1ElemTree x 2,943,777 ops/sec ±6.16% (73 runs sampled)
FingerTree#Concat10ElemTreeWith10ElemTree x 1,364,459 ops/sec ±4.58% (79 runs sampled)
FingerTree#Concat10ElemTreeWith100ElemTree x 1,594,247 ops/sec ±0.63% (91 runs sampled)
FingerTree#Concat10ElemTreeWith1000ElemTree x 1,584,415 ops/sec ±0.58% (92 runs sampled)
FingerTree#Concat10ElemTreeWith10000ElemTree x 1,609,327 ops/sec ±0.65% (82 runs sampled)
FingerTree#Concat10ElemTreeWith100000ElemTree x 1,163,352 ops/sec ±6.72% (72 runs sampled)
FingerTree#Concat10ElemTreeWith1000000ElemTree x 890,814 ops/sec ±6.15% (66 runs sampled)
FingerTree#Concat100ElemTreeWith0ElemTree x 17,937,603 ops/sec ±5.03% (81 runs sampled)
FingerTree#Concat100ElemTreeWith1ElemTree x 3,804,105 ops/sec ±2.56% (86 runs sampled)
FingerTree#Concat100ElemTreeWith10ElemTree x 1,238,229 ops/sec ±4.42% (76 runs sampled)
FingerTree#Concat100ElemTreeWith100ElemTree x 532,721 ops/sec ±4.50% (83 runs sampled)
FingerTree#Concat100ElemTreeWith1000ElemTree x 472,716 ops/sec ±5.33% (74 runs sampled)
FingerTree#Concat100ElemTreeWith10000ElemTree x 505,303 ops/sec ±4.49% (79 runs sampled)
FingerTree#Concat100ElemTreeWith100000ElemTree x 516,227 ops/sec ±4.92% (78 runs sampled)
FingerTree#Concat100ElemTreeWith1000000ElemTree x 497,876 ops/sec ±4.83% (80 runs sampled)
FingerTree#Concat1000ElemTreeWith0ElemTree x 19,926,982 ops/sec ±0.97% (89 runs sampled)
FingerTree#Concat1000ElemTreeWith1ElemTree x 3,757,808 ops/sec ±1.80% (84 runs sampled)
FingerTree#Concat1000ElemTreeWith10ElemTree x 1,104,399 ops/sec ±5.10% (75 runs sampled)
FingerTree#Concat1000ElemTreeWith100ElemTree x 671,673 ops/sec ±5.25% (76 runs sampled)
FingerTree#Concat1000ElemTreeWith1000ElemTree x 600,555 ops/sec ±2.79% (84 runs sampled)
FingerTree#Concat1000ElemTreeWith10000ElemTree x 478,199 ops/sec ±2.53% (86 runs sampled)
FingerTree#Concat1000ElemTreeWith100000ElemTree x 477,585 ops/sec ±2.47% (87 runs sampled)
FingerTree#Concat1000ElemTreeWith1000000ElemTree x 450,701 ops/sec ±4.17% (86 runs sampled)
FingerTree#Concat10000ElemTreeWith0ElemTree x 19,572,633 ops/sec ±1.04% (91 runs sampled)
FingerTree#Concat10000ElemTreeWith1ElemTree x 3,814,716 ops/sec ±1.00% (89 runs sampled)
FingerTree#Concat10000ElemTreeWith10ElemTree x 1,232,594 ops/sec ±4.26% (75 runs sampled)
FingerTree#Concat10000ElemTreeWith100ElemTree x 774,532 ops/sec ±3.77% (84 runs sampled)
FingerTree#Concat10000ElemTreeWith1000ElemTree x 480,338 ops/sec ±4.29% (81 runs sampled)
FingerTree#Concat10000ElemTreeWith10000ElemTree x 391,378 ops/sec ±3.86% (85 runs sampled)
FingerTree#Concat10000ElemTreeWith100000ElemTree x 348,976 ops/sec ±2.90% (83 runs sampled)
FingerTree#Concat10000ElemTreeWith1000000ElemTree x 370,820 ops/sec ±3.59% (83 runs sampled)
FingerTree#Concat100000ElemTreeWith0ElemTree x 18,840,616 ops/sec ±1.46% (89 runs sampled)
FingerTree#Concat100000ElemTreeWith1ElemTree x 3,411,742 ops/sec ±5.40% (84 runs sampled)
FingerTree#Concat100000ElemTreeWith10ElemTree x 1,295,934 ops/sec ±3.64% (80 runs sampled)
FingerTree#Concat100000ElemTreeWith100ElemTree x 527,559 ops/sec ±7.14% (71 runs sampled)
FingerTree#Concat100000ElemTreeWith1000ElemTree x 421,084 ops/sec ±4.01% (79 runs sampled)
FingerTree#Concat100000ElemTreeWith10000ElemTree x 386,141 ops/sec ±3.50% (84 runs sampled)
FingerTree#Concat100000ElemTreeWith100000ElemTree x 296,544 ops/sec ±8.01% (78 runs sampled)
FingerTree#Concat100000ElemTreeWith1000000ElemTree x 278,959 ops/sec ±3.51% (86 runs sampled)
FingerTree#Concat1000000ElemTreeWith0ElemTree x 15,871,327 ops/sec ±6.83% (77 runs sampled)
FingerTree#Concat1000000ElemTreeWith1ElemTree x 3,275,900 ops/sec ±2.79% (83 runs sampled)
FingerTree#Concat1000000ElemTreeWith10ElemTree x 1,162,888 ops/sec ±5.71% (74 runs sampled)
FingerTree#Concat1000000ElemTreeWith100ElemTree x 689,867 ops/sec ±7.99% (78 runs sampled)
FingerTree#Concat1000000ElemTreeWith1000ElemTree x 399,844 ops/sec ±8.01% (75 runs sampled)
FingerTree#Concat1000000ElemTreeWith10000ElemTree x 335,577 ops/sec ±6.95% (79 runs sampled)
FingerTree#Concat1000000ElemTreeWith100000ElemTree x 317,946 ops/sec ±4.89% (79 runs sampled)
FingerTree#Concat1000000ElemTreeWith1000000ElemTree x 238,679 ops/sec ±5.45% (66 runs sampled)

References

License

LGPL-3.0

Published

Vulnerabilities

Links

Maintainers

Keywords

Readme

fingertree-actually-good

Installation

Usage

Importing the library

API Documentation:

Function: fingertree<MeasureMonoid>

Interface: Measure <Element, MeasureValue>

Type parameters

Methods

base

sum

zero

Class: FingerTree <Element, MeasureValue, MeasureMonoid>

Type parameters

Implements

Methods

[Symbol.iterator]

append

appendMany

concat

dropUntil

dropWhile

firstMatch

flatten

head

init

isEmpty

last

map

mapTrue

measure

prepend

prependMany

split

tail

takeUntil

takeWhile

updateFirstMatch

updateHead

updateLast

Benchmark Results

References

License