# Weight Balanced Trees

[Weight Balanced Trees][1] with an SRFI interface. Implementation based on
[Parallel Ordered Sets Using Join][1].

[1]: https://arxiv.org/abs/1602.02120

Benefits of using this library:

* Written in modern Scheme (R7RS).
* Low level access to implementation using
  `(mcgoron weight-balanced-trees internal)` library.
* Implements interface for mapping and set SRFIs.
* Interfaces with other SRFIs, like generators and streams.
* Order can be defined on finite sets of ordered elements.
* Extensively tested using [property testing][2] (like QuickCheck).
* Permissive license (Apache 2.0)

[2]: https://srfi.schemers.org/srfi-252/srfi-252.html

## Included Libraries

* `(mcgoron weight-balanced-trees internal)`: low-level operations on tree
  nodes. Includes `join`, `split`, and binary set operations.
* `(mcgoron weight-balanced-trees srfi 113 set)`: The set operations from
  [SRFI-113][5], with extra procedures.

[5]: https://srfi.schemers.org/srfi-113/srfi-113.html

## Implementation Notes

Tests of set operations are implemented in terms of the SRFI-1 list-set
operations.

The implementation of the SRFI interfaces uses [generators][3] for
iteration whenever a function can terminate in the middle of a set (like
`set-every?`). Generators are usually lightweight, but are intrinsically
mutating.  Some Scheme implementations, like CHICKEN, implement
write-barriers in their garbage collectors, which make mutation slower
(See ["Mutations"][4]).

Alternative implementation strategies include:

* escape continuations (`call/cc` might be slow, `call/ec` is not
  standard, `guard` could be used to emulate escape continuations)
* direct recursion (would have to traverse the whole set before
  terminating)
* sentinel-value return (uglier)

The linear update procedures are the same as the functional procedures.

[3]: https://srfi.schemers.org/srfi-158/srfi-158.html
[4]: https://www.more-magic.net/posts/internals-gc.html