Suppose I need to find out if the intersection of an arbitrary number of lists or sequences is empty.
Instead of the obvious O(n2) approach I used a hash table to achieve an O(n) implementation.
Now, loop
mini-language aside, is this idiomatic elisp code? Could it be improved w/o adding a lot of complexity?
You can view the same snippet w/ syntax highlighting on pastebin.
(defun seq-intersect-p (seq1 seq2 &rest sequences)
"Determine if the intersection of SEQ1, SEQ2 and SEQUENCES is non-nil."
(cl-do* ((sequences `(,seq1 ,seq2 ,@sequences) (cdr sequences))
(seq (car sequences) (car sequences))
(elements (make-hash-table :test #'equal))
(intersect-p nil))
((or (seq-empty-p sequences)) intersect-p)
(cl-do* ((seq seq (cdr seq))
(element (car seq) (car seq)))
((or intersect-p (seq-empty-p seq)) intersect-p)
(if (ht-get elements element)
(setf intersect-p t)
(ht-set elements element t)))))
(defun test-seq-intersect-p ()
"Test cases."
(cl-assert (null (seq-intersect-p '()
'())))
(cl-assert (null (seq-intersect-p '(1)
'())))
(cl-assert (null (seq-intersect-p '(1 2)
'(3 4)
'(5 6))))
(cl-assert (seq-intersect-p '(1 2)
'(3 4)
'(5 6)
'(1)))
t)
(test-seq-intersect-p)
You must log in or # to comment.