R7RS weight balanced trees
Find a file
2025-02-17 14:59:44 -05:00
doc add set-contains? test, remove NaNs because they cannot be used in the default comparator 2025-02-16 22:02:46 -05:00
mcgoron/weight-balanced-trees test set-every, set-delete, and set=? 2025-02-17 14:59:44 -05:00
tests test set-every, set-delete, and set=? 2025-02-17 14:59:44 -05:00
.gitignore start testing SRFI 113 tests 2025-02-15 22:57:35 -05:00
README.md update to new test runner 2025-02-14 19:40:13 -05:00
weight-balanced-trees.egg test set-every, set-delete, and set=? 2025-02-17 14:59:44 -05:00

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. Includes join, 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.