source: trunk/abcl/src/org/armedbear/lisp/remove-duplicates.lisp @ 14196

Last change on this file since 14196 was 12516, checked in by astalla, 11 years ago

Support for user-extensible sequences, adapted from SBCL.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 4.4 KB
Line 
1;;; remove-duplicates.lisp
2;;;
3;;; Copyright (C) 2003-2004 Peter Graves
4;;; $Id: remove-duplicates.lisp 12516 2010-03-03 21:05:41Z astalla $
5;;;
6;;; This program is free software; you can redistribute it and/or
7;;; modify it under the terms of the GNU General Public License
8;;; as published by the Free Software Foundation; either version 2
9;;; of the License, or (at your option) any later version.
10;;;
11;;; This program is distributed in the hope that it will be useful,
12;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
13;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14;;; GNU General Public License for more details.
15;;;
16;;; You should have received a copy of the GNU General Public License
17;;; along with this program; if not, write to the Free Software
18;;; Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19;;;
20;;; As a special exception, the copyright holders of this library give you
21;;; permission to link this library with independent modules to produce an
22;;; executable, regardless of the license terms of these independent
23;;; modules, and to copy and distribute the resulting executable under
24;;; terms of your choice, provided that you also meet, for each linked
25;;; independent module, the terms and conditions of the license of that
26;;; module.  An independent module is a module which is not derived from
27;;; or based on this library.  If you modify this library, you may extend
28;;; this exception to your version of the library, but you are not
29;;; obligated to do so.  If you do not wish to do so, delete this
30;;; exception statement from your version.
31
32(in-package #:system)
33
34(require "EXTENSIBLE-SEQUENCES-BASE")
35
36;;; Adapted from CMUCL.
37
38(defun list-remove-duplicates (list test test-not start end key from-end)
39  (let* ((result (list ()))
40   (splice result)
41   (current list))
42    (do ((index 0 (1+ index)))
43        ((= index start))
44      (setq splice (cdr (rplacd splice (list (car current)))))
45      (setq current (cdr current)))
46    (do ((index start (1+ index)))
47        ((or (and end (= index end))
48             (atom current)))
49      (if (or (and from-end
50       (not (member (apply-key key (car current))
51        (nthcdr (1+ start) result)
52        :test test
53        :test-not test-not
54        :key key)))
55        (and (not from-end)
56       (not (do ((it (apply-key key (car current)))
57           (l (cdr current) (cdr l))
58           (i (1+ index) (1+ i)))
59                          ((or (atom l) (and end (= i end)))
60                           ())
61        (if (if test-not
62          (not (funcall test-not it (apply-key key (car l))))
63          (funcall test it (apply-key key (car l))))
64            (return t))))))
65    (setq splice (cdr (rplacd splice (list (car current))))))
66      (setq current (cdr current)))
67    (do ()
68        ((atom current))
69      (setq splice (cdr (rplacd splice (list (car current)))))
70      (setq current (cdr current)))
71    (cdr result)))
72
73(defun vector-remove-duplicates (vector test test-not start end key from-end
74                                        &optional (length (length vector)))
75  (when (null end) (setf end (length vector)))
76  (let ((result (make-sequence-like vector length))
77  (index 0)
78  (jndex start))
79    (do ()
80        ((= index start))
81      (setf (aref result index) (aref vector index))
82      (setq index (1+ index)))
83    (do ((elt))
84      ((= index end))
85      (setq elt (aref vector index))
86      (unless (or (and from-end
87                       (position (apply-key key elt) result :start start
88                                 :end jndex :test test :test-not test-not :key key))
89      (and (not from-end)
90                       (position (apply-key key elt) vector :start (1+ index)
91                                 :end end :test test :test-not test-not :key key)))
92  (setf (aref result jndex) elt)
93  (setq jndex (1+ jndex)))
94      (setq index (1+ index)))
95    (do ()
96      ((= index length))
97      (setf (aref result jndex) (aref vector index))
98      (setq index (1+ index))
99      (setq jndex (1+ jndex)))
100    (shrink-vector result jndex)))
101
102(defun remove-duplicates (sequence &rest args &key (test #'eql) test-not
103        (start 0) from-end end key)
104  (sequence::seq-dispatch sequence
105    (when sequence
106      (if (and (eq test #'eql)
107         (null test-not)
108         (eql start 0)
109         (null from-end)
110         (null end)
111         (null key))
112    (simple-list-remove-duplicates sequence)
113    (list-remove-duplicates sequence test test-not start end key from-end)))
114    (vector-remove-duplicates sequence test test-not start end key from-end)
115    (apply #'sequence:remove-duplicates sequence args)))
Note: See TracBrowser for help on using the repository browser.