aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorGravatar Peter McGoron 2025-02-17 15:49:16 -0500
committerGravatar Peter McGoron 2025-02-17 15:49:16 -0500
commit849fc866237e3f34da586293f201a981964eeb65 (patch)
treef3dad1bf66844db9c60dace11c3a242966d7a69f
parentmore tests for set-delete, more efficient implementation (diff)
revert change to set-delete
This solution is O(n). Since set-delete is basically set-difference, this should only be used for small sets.
-rw-r--r--mcgoron/weight-balanced-trees/srfi/113/sets.scm16
1 files changed, 7 insertions, 9 deletions
diff --git a/mcgoron/weight-balanced-trees/srfi/113/sets.scm b/mcgoron/weight-balanced-trees/srfi/113/sets.scm
index 964ff87..b3d6b13 100644
--- a/mcgoron/weight-balanced-trees/srfi/113/sets.scm
+++ b/mcgoron/weight-balanced-trees/srfi/113/sets.scm
@@ -104,15 +104,13 @@
(define set-replace! set-replace)
(define (set-delete-all set elements)
- (define cmp (set-element-comparator set))
- (define (delete node)
- (if (null? node)
- '()
- (with-node (node data ("<" left) (">" right))
- (if (member data elements (cute =? cmp <> <>))
- (join2 (delete left) (delete right))
- (join data (delete left) (delete right))))))
- (raw-set cmp (delete (get-node set))))
+ (let ((cmp (set-element-comparator set)))
+ (raw-set
+ cmp
+ (fold (lambda (element node)
+ (delete cmp node element))
+ (get-node set)
+ elements))))
(define set-delete-all! set-delete-all)
(define (set-delete set . elements)