Add ZDD `keep-avoiders-of` operation
author |
Steve Losh <steve@stevelosh.com> |
date |
Tue, 01 Nov 2016 13:45:11 +0000 |
parents |
7c5b8fa516a2
|
children |
089d9e0ffbc7
|
branches/tags |
(none) |
files |
src/zdd.lisp |
Changes
--- a/src/zdd.lisp Tue Nov 01 13:38:22 2016 +0000
+++ b/src/zdd.lisp Tue Nov 01 13:45:11 2016 +0000
@@ -235,6 +235,22 @@
(zdd-remove-supersets-of% zdd (sort set #'<)))
+(defun zdd-keep-avoiders-of% (zdd set)
+ (ematch* (zdd set)
+ ((_ nil) zdd)
+ (((leaf) _) zdd)
+ (((node var hi lo) (list* el remaining))
+ (cond
+ ((= var el) (zdd-keep-avoiders-of% lo remaining))
+ ((< var el) (zdd-node var
+ (zdd-keep-avoiders-of% hi set)
+ (zdd-keep-avoiders-of% lo set)))
+ ((> var el) (zdd-keep-avoiders-of% zdd remaining))))))
+
+(defun zdd-keep-avoiders-of (zdd set)
+ (zdd-keep-avoiders-of% zdd (sort set #'<)))
+
+
(defun zdd-family (&rest sets)
(reduce #'zdd-union (mapcar #'zdd-set sets)))
@@ -266,10 +282,10 @@
(-<> (zdd-join (zdd-family '(1 2) '(7 8) '())
(zdd-family '(1 5 9) nil)
(zdd-set '(1)))
- (zdd-remove-supersets-of <> '(5 9))
- ; (enumerate <>)
+ (print-enumerated <>)
+ (zdd-keep-avoiders-of <> '(2 7))
+ (print-enumerated <>)
(draw <>)
- (print-enumerated <>)
(zdd-size <>)
)
)