blob: bb77bc75878ffbb656809003fd13ad674a23c042 (
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
# 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
|
