| ... |
... |
@@ -750,6 +750,28 @@ |
|
750
|
750
|
15)
|
|
751
|
751
|
|
|
752
|
752
|
(declaim (start-block list-to-hashtable union intersection set-difference))
|
|
|
753
|
+
|
|
|
754
|
+;; Main code to process a set function. INIT-RES initializes the
|
|
|
755
|
+;; value of RES, which holds the result of the set function.
|
|
|
756
|
+;; TEST-FORM is a form that tests whether to add the item from LIST1
|
|
|
757
|
+;; to RES.
|
|
|
758
|
+(defmacro process-set-body (init-res invert-p test-form)
|
|
|
759
|
+ `(let ((res ,init-res))
|
|
|
760
|
+ (dolist (item list1)
|
|
|
761
|
+ (when ,(if invert-p
|
|
|
762
|
+ `(not ,test-form)
|
|
|
763
|
+ test-form)
|
|
|
764
|
+ (push item res)))
|
|
|
765
|
+ res))
|
|
|
766
|
+
|
|
|
767
|
+(defmacro process-set (init-res invert-p)
|
|
|
768
|
+ `(let ((hashtable (list-to-hashtable list2 key test test-not)))
|
|
|
769
|
+ (if hashtable
|
|
|
770
|
+ (process-set-body ,init-res ,invert-p
|
|
|
771
|
+ (nth-value 1 (gethash (apply-key key item) hashtable)))
|
|
|
772
|
+ (process-set-body ,init-res ,invert-p
|
|
|
773
|
+ (with-set-keys (member (apply-key key item) list2))))))
|
|
|
774
|
+
|
|
753
|
775
|
;; Convert a list to a hashtable. The hashtable does not handle
|
|
754
|
776
|
;; duplicated values in the list. Returns the hashtable.
|
|
755
|
777
|
(defun list-to-hashtable (list key test test-not)
|
| ... |
... |
@@ -791,17 +813,7 @@ |
|
791
|
813
|
(declare (inline member))
|
|
792
|
814
|
(when (and testp notp)
|
|
793
|
815
|
(error (intl:gettext "Test and test-not both supplied.")))
|
|
794
|
|
- (let ((res list2)
|
|
795
|
|
- (hashtable (list-to-hashtable list2 key test test-not)))
|
|
796
|
|
- (cond (hashtable
|
|
797
|
|
- (dolist (item list1)
|
|
798
|
|
- (unless (nth-value 1 (gethash (apply-key key item) hashtable))
|
|
799
|
|
- (push item res))))
|
|
800
|
|
- ((null hashtable)
|
|
801
|
|
- (dolist (item list1)
|
|
802
|
|
- (unless (with-set-keys (member (apply-key key item) list2))
|
|
803
|
|
- (push item res)))))
|
|
804
|
|
- res))
|
|
|
816
|
+ (process-set list2 t))
|
|
805
|
817
|
|
|
806
|
818
|
|
|
807
|
819
|
(defun intersection (list1 list2 &key key
|
| ... |
... |
@@ -810,20 +822,7 @@ |
|
810
|
822
|
(declare (inline member))
|
|
811
|
823
|
(if (and testp notp)
|
|
812
|
824
|
(error "Test and test-not both supplied."))
|
|
813
|
|
- (let ((hashtable
|
|
814
|
|
- (list-to-hashtable list2 key test test-not)))
|
|
815
|
|
- (cond (hashtable
|
|
816
|
|
- (let ((res nil))
|
|
817
|
|
- (dolist (item list1)
|
|
818
|
|
- (when (nth-value 1 (gethash (apply-key key item) hashtable))
|
|
819
|
|
- (push item res)))
|
|
820
|
|
- res))
|
|
821
|
|
- ((null hashtable)
|
|
822
|
|
- (let ((res nil))
|
|
823
|
|
- (dolist (elt list1)
|
|
824
|
|
- (if (with-set-keys (member (apply-key key elt) list2))
|
|
825
|
|
- (push elt res)))
|
|
826
|
|
- res)))))
|
|
|
825
|
+ (process-set nil nil))
|
|
827
|
826
|
|
|
828
|
827
|
(defun set-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp))
|
|
829
|
828
|
"Returns the elements of list1 which are not in list2."
|
| ... |
... |
@@ -834,23 +833,8 @@ |
|
834
|
833
|
(when (null list2)
|
|
835
|
834
|
(return-from set-difference list1))
|
|
836
|
835
|
|
|
837
|
|
- (let ((hashtable
|
|
838
|
|
- (list-to-hashtable list2 key test test-not)))
|
|
839
|
|
- (cond (hashtable
|
|
840
|
|
- ;; list2 was placed in hash table.
|
|
841
|
|
- (let ((res nil))
|
|
842
|
|
- (dolist (item list1)
|
|
843
|
|
- (unless (nth-value 1 (gethash (apply-key key item) hashtable))
|
|
844
|
|
- (push item res)))
|
|
845
|
|
- res))
|
|
846
|
|
- ((null hashtable)
|
|
847
|
|
- ;; Default implementation because we didn't create the hash
|
|
848
|
|
- ;; table.
|
|
849
|
|
- (let ((res nil))
|
|
850
|
|
- (dolist (item list1)
|
|
851
|
|
- (if (not (with-set-keys (member (apply-key key item) list2)))
|
|
852
|
|
- (push item res)))
|
|
853
|
|
- res)))))
|
|
|
836
|
+ (process-set nil t))
|
|
|
837
|
+
|
|
854
|
838
|
|
|
855
|
839
|
(declaim (end-block))
|
|
856
|
840
|
|