AutoLISP: Removing consecutive duplicates in list

user_14693180 0
Viewed 237

I've been looking for an efficient way of removing consecutive duplicates in a list of points.

My original thinking was to loop through the elements of the list making a comparison with the (n-1)th element and removing it if its equal. But then it is not trivial to remove an element in a list and using another function would make it inefficient.

I am aware of Lee Mac's RemoveOnce function but I don't know how to modify it to make a comparison between consecutive elements of a list.

The goal as an example would be the following:

List = (p1 p2 p3 p3 p3 p2 p2 p4)

List_without_consecutive_duplicates = (p1 p2 p3 p2 p4)

Thanks!

autolisp lisp
2 Answers

Here is one way which I think is legal AutoLISP:

(defun remove-successive-duplicates (l / results current)
  (cond
   ((null l)
    l)
   (t
    (setq current (car l)
          results (list current))
    (foreach e (cdr l)
      (cond
       ((not (eq e current))
        (setq current e
              results (cons e results)))))
    (reverse results))))

You can do better than this if there are destructive functions on lists which it looks like there are not, or if there are list filtering functions which it also looks like there are not.

Here is another way which is much prettier but will cause stack overflows with long lists:

(defun remove-successive-duplicates (l)
  (cond
   ((or (null l) (null (cdr l)))
    l)
   (t
    (cons (car l) (remove-current-duplicates-loop (cdr l) (car l))))))

(defun remove-successive-duplicates-loop (l current)
  (cond
   ((null (cdr l))
    (cond
     ((eq (car l) current)
      '())
     (t
      l)))
   ((eq (car l) current)
    (remove-successive-duplicates-loop (cdr l) current))
   (t
    (cons (car l) (remove-successive-duplicates-loop (cdr l) (car l))))))
Admin1

Here's an iterative method:

(defun remcondupes ( l / r )
    (while l
        (if (not (equal (car l) (cadr l) 1e-8))
            (setq r (cons (car l) r))
        )
        (setq l (cdr l))
    )
    (reverse r)
)

And here's a recursive method:

(defun remcondupes ( l )
    (if l
        (if (equal (car l) (cadr l) 1e-8)
            (remcondupes (cdr l))
            (cons (car l) (remcondupes (cdr l)))
        )
    )
)

In both of the above, the first element in the list is compared to the second using the equal function with a tolerance of 1e-8 (since we're comparing points), with the first element discarded if this test is validated.

Testing:

_$ (setq p1 '(1.2 2.3) p2 '(3.4 4.5) p3 '(5.6 6.7) p4 '(7.8 8.9))
(7.8 8.9)
_$ (setq lst (list p1 p2 p3 p3 p3 p2 p2 p4))
((1.2 2.3) (3.4 4.5) (5.6 6.7) (5.6 6.7) (5.6 6.7) (3.4 4.5) (3.4 4.5) (7.8 8.9))
_$ (remcondupes lst)
((1.2 2.3) (3.4 4.5) (5.6 6.7) (3.4 4.5) (7.8 8.9))

EDIT:

Alternatively, to account for consecutive points each successively within the comparison tolerance (per Will's comments below), you might consider the following variations:

(defun remcondupes ( l / r )
    (while l
        (if (equal (car l) (cadr l) 1e-8)
            (setq l (cons (car l) (cddr l)))
            (setq r (cons (car l) r)
                  l (cdr l)
            )
        )
    )
    (reverse r)
)

(defun remcondupes ( l )
    (if l
        (if (equal (car l) (cadr l) 1e-8)
            (remcondupes (cons (car l) (cddr l)))
            (cons (car l) (remcondupes (cdr  l)))
        )
    )
)
user_75315980
Related