Lazy Fingertree in Go based on Qiao's JavaScript version of Ralf Hinze's and Ross Paterson's Haskell version

The public API is parameterized (defined in adapters.go):

You provide your own object that supports the Measurer[Value, Measurement] interface. Values are in the leaves of the tree and your Measurer computes the Measurements in the Measure() and Sum() methods. Measurements can be any go objects but they should be immutable or there could be trouble. Please see Ralf Hinze's and Ross Paterson's finger tree paper (and the tests) for more information.

Here's the go doc:

lazyfingertree

import "github.com/zot/lazyfingertree"

Package lazyfingertree implements parameterized lazy finger trees. See the [readme](README.md) for details.

Index

• Variables
• type FingerTree
  • func Concat[MS Measurer[V, M], V, M any](trees ...FingerTree[MS, V, M]) FingerTree[MS, V, M]
  • func FromArray[MS Measurer[V, M], V, M any](measurer MS, values []V) FingerTree[MS, V, M]
  • func (t FingerTree[MS, V, M]) AddFirst(value V) FingerTree[MS, V, M]
  • func (t FingerTree[MS, V, M]) AddLast(value V) FingerTree[MS, V, M]
  • func (t FingerTree[MS, V, M]) Concat(other FingerTree[MS, V, M]) FingerTree[MS, V, M]
  • func (t FingerTree[MS, V, M]) DropUntil(pred Predicate[M]) FingerTree[MS, V, M]
  • func (t FingerTree[MS, V, M]) Each(iter IterFunc[V])
  • func (t FingerTree[MS, V, M]) EachReverse(iter IterFunc[V])
  • func (t FingerTree[MS, V, M]) IsEmpty() bool
  • func (t FingerTree[MS, V, M]) Measure() M
  • func (t FingerTree[MS, V, M]) PeekFirst() V
  • func (t FingerTree[MS, V, M]) PeekLast() V
  • func (t FingerTree[MS, V, M]) RemoveFirst() FingerTree[MS, V, M]
  • func (t FingerTree[MS, V, M]) RemoveLast() FingerTree[MS, V, M]
  • func (t FingerTree[MS, V, M]) Split(predicate Predicate[M]) (FingerTree[MS, V, M], FingerTree[MS, V, M])
  • func (t FingerTree[MS, V, M]) String() string
  • func (t FingerTree[MS, V, M]) TakeUntil(pred Predicate[M]) FingerTree[MS, V, M]
  • func (t FingerTree[MS, V, M]) ToSlice() []V
• type IterFunc
• type Measurer
  • func AsMeasurer[V, M any](m any) Measurer[V, M]
• type Predicate

Variables

var ErrBadMeasurer = fmt.Errorf("%w, bad measurer", ErrFingerTree)

var ErrBadValue = fmt.Errorf("%w, bad value", ErrFingerTree)

var ErrEmptyTree = fmt.Errorf("%w, empty tree", ErrFingerTree)

var ErrExpectedNode = fmt.Errorf("%w, expected a node", ErrFingerTree)

var ErrFingerTree = errors.New("finger tree")

var ErrUnsupported = fmt.Errorf("%w, unsupported operation", ErrFingerTree)

type FingerTree

FingerTree is a parameterized wrapper on a low-level finger tree.

type FingerTree[MS Measurer[Value, Measure], Value, Measure any] struct {
    // contains filtered or unexported fields
}

func Concat

func Concat[MS Measurer[V, M], V, M any](trees ...FingerTree[MS, V, M]) FingerTree[MS, V, M]

func FromArray

func FromArray[MS Measurer[V, M], V, M any](measurer MS, values []V) FingerTree[MS, V, M]

Create a finger tree. You shouldn't need to provide the type parameters, Go should be able to infer them from your arguments. So you should just be able to say, t := FromArray(myMeasurer, []Plant{plant1, plant2})

func (FingerTree[MS, V, M]) AddFirst

func (t FingerTree[MS, V, M]) AddFirst(value V) FingerTree[MS, V, M]

Add a value to the start of the tree.

func (FingerTree[MS, V, M]) AddLast

func (t FingerTree[MS, V, M]) AddLast(value V) FingerTree[MS, V, M]

Add a value to the and of the tree.

func (FingerTree[MS, V, M]) Concat

func (t FingerTree[MS, V, M]) Concat(other FingerTree[MS, V, M]) FingerTree[MS, V, M]

Join two finger trees together

func (FingerTree[MS, V, M]) DropUntil

func (t FingerTree[MS, V, M]) DropUntil(pred Predicate[M]) FingerTree[MS, V, M]

Discard all the initial values in the tree that do not satisfy the predicate

func (FingerTree[MS, V, M]) Each

func (t FingerTree[MS, V, M]) Each(iter IterFunc[V])

Iterate through the tree starting at the beginning

func (FingerTree[MS, V, M]) EachReverse

func (t FingerTree[MS, V, M]) EachReverse(iter IterFunc[V])

Iterate through the tree starting at the end

func (FingerTree[MS, V, M]) IsEmpty

func (t FingerTree[MS, V, M]) IsEmpty() bool

Return whether the tree is empty

func (FingerTree[MS, V, M]) Measure

func (t FingerTree[MS, V, M]) Measure() M

Return the measure of all the tree's values

func (FingerTree[MS, V, M]) PeekFirst

func (t FingerTree[MS, V, M]) PeekFirst() V

Return the first value in the tree. Make sure to test whether the tree is empty because this will panic if it is.

func (FingerTree[MS, V, M]) PeekLast

func (t FingerTree[MS, V, M]) PeekLast() V

Return the last value in the tree. Make sure to test whether the tree is empty because this will panic if it is.

func (FingerTree[MS, V, M]) RemoveFirst

func (t FingerTree[MS, V, M]) RemoveFirst() FingerTree[MS, V, M]

Remove the first value in the tree. Make sure to test whether the tree is empty because this will panic if it is.

func (FingerTree[MS, V, M]) RemoveLast

func (t FingerTree[MS, V, M]) RemoveLast() FingerTree[MS, V, M]

Remove the last value in the tree. Make sure to test whether the tree is empty because this will panic if it is.

func (FingerTree[MS, V, M]) Split

func (t FingerTree[MS, V, M]) Split(predicate Predicate[M]) (FingerTree[MS, V, M], FingerTree[MS, V, M])

Split the tree. The first tree is all the starting values that do not satisfy the predicate. The second tree is the first value that satisfies the predicate, followed by the rest of the values.

func (FingerTree[MS, V, M]) String

func (t FingerTree[MS, V, M]) String() string

func (FingerTree[MS, V, M]) TakeUntil

func (t FingerTree[MS, V, M]) TakeUntil(pred Predicate[M]) FingerTree[MS, V, M]

Return all the initial values in the tree that do not satisfy the predicate

func (FingerTree[MS, V, M]) ToSlice

func (t FingerTree[MS, V, M]) ToSlice() []V

Return a slice containing all of the values in the tree

type IterFunc

An IterFunc is a function that takes a value and returns true or false. It's used by [Each] and [EachReverse]. Returning true means to continue iteration. Returning false means to stop.

type IterFunc[V any] func(value V) bool

type Measurer

type Measurer[Value, Measure any] interface {
    // The "zero" measure
    Identity() Measure
    // Return the measure for a value.
    // Measuring a value could technically produce an error but really should not.
    // Make sure to validate inputs or to use a panic if you need error support.
    Measure(value Value) Measure
    // Add two measures together
    Sum(a Measure, b Measure) Measure
}

func AsMeasurer

func AsMeasurer[V, M any](m any) Measurer[V, M]

The measurer interface

type Predicate

A Predicate is a function that takes a measure and returns true or false. It's used by [Split], [TakeUntil], and [DropUntil].

type Predicate[M any] func(measure M) bool

Generated by gomarkdoc