Re: Suggestions to remove one alist's members from another

[David Kastrup <dak@gnu.org>]

wsnyder@wsnyder.org (Wilson Snyder) writes:

>>> If not, my thought is this: when the list was over some size
>>> I'd determine experimentally, it would instead build a hash
>>> table from in-list and hit the not-alist against that.  When
>>> complete it would unfortunately require a second pass
>>> through the in-alist to return it maintaining the original
>>> order.
>>
>>Why not build a hash table (of the cars of the elements) from not-alist
>>instead?  Then you can just walk in-alist, skipping elements that are in
>>the hash (that is, whose cars are in it) and adding the rest to out-alist
>>and (their cars to) the hash.
>
> Thanks, that's a good improvement. I also would add each
> in-list element after each test for hash membership, as I
> want to eliminate duplicates.
>
> It still seems like this should already exist somewhere...

I am somewhat annoyed to find that some old work of mine done on reftex
seems to have been lost in the course of some upgrades.

Here are some examples how to do stuff like that (written by myself,
in spite of the name):

(defun TeX-delete-dups-by-car (alist &optional keep-list)
  "Return a list of all elements in ALIST, but each car only once.
Elements of KEEP-LIST are not removed even if duplicate."
  ;; Copy of `reftex-uniquify-by-car' (written by David Kastrup).
  (setq keep-list (sort (copy-sequence keep-list) #'string<))
  (setq alist (sort (copy-sequence alist)
		    (lambda (a b)
		      (string< (car a) (car b)))))
  (let ((new alist) elt)
    (while new
      (setq elt (caar new))
      (while (and keep-list (string< (car keep-list) elt))
	(setq keep-list (cdr keep-list)))
      (unless (and keep-list (string= elt (car keep-list)))
	(while (string= elt (car (cadr new)))
	  (setcdr new (cddr new))))
      (setq new (cdr new))))
  alist)

(defun TeX-delete-duplicate-strings (list)
  "Return a list of all strings in LIST, but each only once."
  (setq list (TeX-sort-strings list))
  (let ((new list) elt)
    (while new
      (setq elt (car new))
      (while (string= elt (cadr new))
	(setcdr new (cddr new)))
      (setq new (cdr new))))
  list)

Now that changes the order of elements.  I had versions which did not do
that either, but apparently lost them.

The key is to have the algorithms work on sorted lists.

-- 
David Kastrup