blob: 2bbf78a51922b05794e141740f16e8e12d6889b8 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
# 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
|
