R7RS weight balanced trees
doc | ||
mcgoron/weight-balanced-trees | ||
tests | ||
.gitignore | ||
README.md | ||
weight-balanced-trees.egg |
Weight Balanced Trees
Weight Balanced Trees with an SRFI interface. Implementation based on Parallel Ordered Sets Using Join.
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 (like QuickCheck).
- Permissive license (Apache 2.0)
Included Libraries
(mcgoron weight-balanced-trees internal)
: low-level operations on tree nodes. Includesjoin
,split
, and binary set operations.(mcgoron weight-balanced-trees srfi 113 set)
: The set operations from SRFI-113, with extra procedures.
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 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").
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.