# 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)`: Exposes an interface like
  [SRFI-113][5], but with extra procedures. This can be used to implement the
  other SRFIs using disjoint container types.

[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 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