### 15 releases

0.2.11 | Nov 18, 2023 |
---|---|

0.2.10 | Mar 1, 2022 |

0.2.9 | Nov 26, 2021 |

0.2.4 | Dec 16, 2020 |

0.2.1 | Oct 29, 2018 |

#**322** in Data structures

**42** downloads per month

**MIT**license

61KB

1.5K
SLoC

# FingerTree

Finger trees is a functional representation of persistent sequences
supporting access to the ends in amortized constant time, and concatenation
and splitting in time logarithmic in the size of the smaller piece. It also
has

operation defined in general
form, which can be used to implement sequence, priority queue, search tree,
priority search queue and more data structures.`split`

## Links:

- Original paper: Finger Trees: A Simple General-purpose Data Structure
- Wikipedia article: FingerTree

## Notes:

- This implementation does not use non-regular recursive types as implementation described in the paper. As rust's monomorphization does not play well with such types.
- Implementation abstracts over reference counted types

. Using type family trick.`Rc``/`Arc - Uses strict spine in implementation.
- Iterator returns cloned value, and in general this implementation assumes that value
stored in a tree is cheaply clonable, if it is not you can always put it in a

or anything else.`Rc``/`Arc

## Examples:

`use` `std``::``iter``::`FromIterator`;`
`use` `fingertrees``::``measure``::`Size`;`
`use` `fingertrees``::``monoid``::`Sum`;`
`use` `fingertrees``::``{`FingerTree`,` Measured`,` RcRefs`}``;`
`//` construct `Rc` based finger tree with `Size` measure
`let` ft`:` `FingerTree``<`RcRefs, `_``>` `=` `vec!``[``"`one`"``,` `"`two`"``,` `"`three`"``,` `"`four`"``,` `"`five`"``]`
`.``into_iter``(``)`
`.``map``(`Size`)`
`.``collect``(``)``;`
`assert_eq!``(`ft`.``measure``(``)``,` Sum`(``5``)``)``;`
`//` split with predicate
`let` `(`left`,` right`)` `=` ft`.``split``(``|``measure``|` `*`measure `>` Sum`(``2``)``)``;`
`assert_eq!``(`left`.``measure``(``)``,` Sum`(``2``)``)``;`
`assert_eq!``(``Vec``::`from_iter`(``&`left`)``,` `vec!``[`Size`(``"`one`"``)``,` Size`(``"`two`"``)``]``)``;`
`assert_eq!``(`right`.``measure``(``)``,` Sum`(``3``)``)``;`
`assert_eq!``(``Vec``::`from_iter`(``&`right`)``,` `vec!``[`Size`(``"`three`"``)``,` Size`(``"`four`"``)``,` Size`(``"`five`"``)``]``)``;`
`//` concatenate
`assert_eq!``(`ft`,` left `+` right`)``;`
`//` push values
`assert_eq!``(`
ft`.``push_left``(`Size`(``"`left`"``)``)``.``push_right``(`Size`(``"`right`"``)``)``,`
`vec!``[``"`left`"``,` `"`one`"``,` `"`two`"``,` `"`three`"``,` `"`four`"``,` `"`five`"``,` `"`right`"``]`
`.``into_iter``(``)`
`.``map``(`Size`)`
`.``collect``(``)``,`
`)``;`