| ... |
... |
@@ -750,28 +750,25 @@ |
|
750
|
750
|
|
|
751
|
751
|
;; Convert a list to a hashtable. The hashtable does not handle
|
|
752
|
752
|
;; duplicated values in the list. Returns the hashtable.
|
|
753
|
|
-(defun list-to-hashtable (list &key test test-not key)
|
|
|
753
|
+(defun list-to-hashtable (list test test-not key)
|
|
754
|
754
|
;; Don't currently support test-not when converting a list to a hashtable
|
|
755
|
755
|
(unless test-not
|
|
756
|
|
- (let ((hash-test (let ((test-fn (if (and (symbolp test)
|
|
757
|
|
- (fboundp test))
|
|
758
|
|
- (fdefinition test)
|
|
759
|
|
- test)))
|
|
760
|
|
- (case test-fn
|
|
761
|
|
- (#'eq 'eq)
|
|
762
|
|
- (#'eql 'eql)
|
|
763
|
|
- (#'equal 'equal)
|
|
764
|
|
- (#'equalp 'equalp)))))
|
|
|
756
|
+ (let ((hash-test (case test
|
|
|
757
|
+ ((#'eq 'eq) 'eq)
|
|
|
758
|
+ ((#'eql 'eq) 'eql)
|
|
|
759
|
+ ((#'equal 'equal) 'equal)
|
|
|
760
|
+ ((#'equalp 'equalp) 'equalp))))
|
|
765
|
761
|
(unless hash-test
|
|
766
|
762
|
(return-from list-to-hashtable nil))
|
|
767
|
763
|
;; If the list is too short, the hashtable makes things
|
|
768
|
764
|
;; slower. We also need to balance memory usage.
|
|
769
|
|
- (when (< (length list) *min-list-length-for-hashtable*)
|
|
770
|
|
- (return-from list-to-hashtable nil))
|
|
771
|
|
- (let ((hashtable (make-hash-table :test test :size len)))
|
|
772
|
|
- (dolist (item list)
|
|
773
|
|
- (setf (gethash (apply-key key item) hashtable) item))
|
|
774
|
|
- hashtable))))
|
|
|
765
|
+ (let ((len (length list)))
|
|
|
766
|
+ (when (< len *min-list-length-for-hashtable*)
|
|
|
767
|
+ (return-from list-to-hashtable nil))
|
|
|
768
|
+ (let ((hashtable (make-hash-table :test hash-test :size len)))
|
|
|
769
|
+ (dolist (item list)
|
|
|
770
|
+ (setf (gethash (apply-key key item) hashtable) item))
|
|
|
771
|
+ hashtable)))))
|
|
775
|
772
|
|
|
776
|
773
|
;;; UNION -- Public.
|
|
777
|
774
|
;;;
|
| ... |
... |
@@ -850,21 +847,21 @@ |
|
850
|
847
|
(return-from set-difference list1))
|
|
851
|
848
|
|
|
852
|
849
|
(let ((hashtable
|
|
853
|
|
- (list-to-hashtable list2 :key key :test test :test-not test-not)))
|
|
|
850
|
+ (list-to-hashtable list2 key test test-not)))
|
|
854
|
851
|
(cond (hashtable
|
|
855
|
852
|
;; list2 was placed in hash table.
|
|
856
|
|
- (let (diff)
|
|
|
853
|
+ (let ((res nil))
|
|
857
|
854
|
(dolist (item list1)
|
|
858
|
855
|
(unless (nth-value 1 (gethash (apply-key key item) hashtable))
|
|
859
|
|
- (push item diff)))
|
|
860
|
|
- diff))
|
|
|
856
|
+ (push item res)))
|
|
|
857
|
+ res))
|
|
861
|
858
|
((null hashtable)
|
|
862
|
859
|
;; Default implementation because we didn't create the hash
|
|
863
|
860
|
;; table.
|
|
864
|
861
|
(let ((res nil))
|
|
865
|
|
- (dolist (elt list1)
|
|
866
|
|
- (if (not (with-set-keys (member (apply-key key elt) list2)))
|
|
867
|
|
- (push elt res)))
|
|
|
862
|
+ (dolist (item list1)
|
|
|
863
|
+ (if (not (with-set-keys (member (apply-key key item) list2)))
|
|
|
864
|
+ (push item res)))
|
|
868
|
865
|
res)))))
|
|
869
|
866
|
|
|
870
|
867
|
(defun nset-difference (list1 list2 &key key
|