(eval-when (:compile-toplevel)
-(defvar *sequence-keyword-info*
+(defparameter *sequence-keyword-info*
;; (name default supplied-p adjustment new-type)
- '((count nil
+ `((count nil
nil
(etypecase count
(null (1- most-positive-fixnum))
(integer (if (minusp count)
0
(1- most-positive-fixnum))))
- (mod #.sb!xc:most-positive-fixnum))))
+ (mod #.sb!xc:most-positive-fixnum))
+ ,@(mapcan (lambda (names)
+ (destructuring-bind (start end length sequence) names
+ (list
+ `(,start
+ 0
+ nil
+ (if (<= 0 ,start ,length)
+ ,start
+ (signal-bounding-indices-bad-error ,sequence
+ ,start ,end))
+ index)
+ `(,end
+ nil
+ nil
+ (if (or (null ,end) (<= ,start ,end ,length))
+ ;; Defaulting of NIL is done inside the
+ ;; bodies, for ease of sharing with compiler
+ ;; transforms.
+ ;;
+ ;; FIXME: defend against non-number non-NIL
+ ;; stuff?
+ ,end
+ (signal-bounding-indices-bad-error ,sequence
+ ,start ,end))
+ (or null index)))))
+ '((start end length sequence)
+ (start1 end1 length1 sequence1)
+ (start2 end2 length2 sequence2)))
+ (key nil
+ nil
+ (and key (%coerce-callable-to-fun key))
+ (or null function))
+ (test #'eql
+ nil
+ (%coerce-callable-to-fun test)
+ function)
+ (test-not nil
+ nil
+ (and test-not (%coerce-callable-to-fun test-not))
+ (or null function))
+ ))
(sb!xc:defmacro define-sequence-traverser (name args &body body)
(multiple-value-bind (body declarations docstring)
- (parse-body body t)
+ (parse-body body :doc-string-allowed t)
(collect ((new-args) (new-declarations) (adjustments))
(dolist (arg args)
- (let ((info (cdr (assoc arg *sequence-keyword-info*))))
- (cond (info
- (destructuring-bind (default supplied-p adjuster type) info
- (new-args `(,arg ,default ,@(when supplied-p (list supplied-p))))
- (adjustments `(,arg ,adjuster))
- (new-declarations `(type ,type ,arg))))
- (t (new-args arg)))))
+ (case arg
+ ;; FIXME: make this robust. And clean.
+ ((sequence)
+ (new-args arg)
+ (adjustments '(length (etypecase sequence
+ (list (length sequence))
+ (vector (length sequence)))))
+ (new-declarations '(type index length)))
+ ((sequence1)
+ (new-args arg)
+ (adjustments '(length1 (etypecase sequence1
+ (list (length sequence1))
+ (vector (length sequence1)))))
+ (new-declarations '(type index length1)))
+ ((sequence2)
+ (new-args arg)
+ (adjustments '(length2 (etypecase sequence2
+ (list (length sequence2))
+ (vector (length sequence2)))))
+ (new-declarations '(type index length2)))
+ ((function predicate)
+ (new-args arg)
+ (adjustments `(,arg (%coerce-callable-to-fun ,arg))))
+ (t (let ((info (cdr (assoc arg *sequence-keyword-info*))))
+ (cond (info
+ (destructuring-bind (default supplied-p adjuster type) info
+ (new-args `(,arg ,default ,@(when supplied-p (list supplied-p))))
+ (adjustments `(,arg ,adjuster))
+ (new-declarations `(type ,type ,arg))))
+ (t (new-args arg)))))))
`(defun ,name ,(new-args)
- ,docstring
+ ,@(when docstring (list docstring))
,@declarations
- (let (,@(adjustments))
+ (let* (,@(adjustments))
(declare ,@(new-declarations))
,@body)))))
(vector-of-checked-length-given-length sequence
declared-length))))))
+(declaim (ftype (function (sequence index) nil) signal-index-too-large-error))
(defun signal-index-too-large-error (sequence index)
(let* ((length (length sequence))
(max-index (and (plusp length)
;; This seems silly, is there something better?
'(integer 0 (0))))))
-(defun signal-end-too-large-error (sequence end)
- (let* ((length (length sequence))
- (max-end length))
- (error 'end-too-large-error
- :datum end
- :expected-type `(integer 0 ,max-end))))
-
+(defun signal-bounding-indices-bad-error (sequence start end)
+ (let ((length (length sequence)))
+ (error 'bounding-indices-bad-error
+ :datum (cons start end)
+ :expected-type `(cons (integer 0 ,length)
+ (or null (integer ,start ,length)))
+ :object sequence)))
\f
(defun elt (sequence index)
#!+sb-doc "Return the element of SEQUENCE specified by INDEX."
(vector (length (truly-the vector sequence)))
(list (length (truly-the list sequence)))))
-(defun make-sequence (type length &key (initial-element NIL iep))
+(defun make-sequence (type length &key (initial-element nil iep))
#!+sb-doc
"Return a sequence of the given TYPE and LENGTH, with elements initialized
- to :INITIAL-ELEMENT."
+ to INITIAL-ELEMENT."
(declare (fixnum length))
- (let ((type (specifier-type type)))
+ (let* ((adjusted-type
+ (typecase type
+ (atom (cond
+ ((eq type 'string) '(vector character))
+ ((eq type 'simple-string) '(simple-array character (*)))
+ (t type)))
+ (cons (cond
+ ((eq (car type) 'string) `(vector character ,@(cdr type)))
+ ((eq (car type) 'simple-string)
+ `(simple-array character ,(if (cdr type)
+ (cdr type)
+ '(*))))
+ (t type)))
+ (t type)))
+ (type (specifier-type adjusted-type)))
(cond ((csubtypep type (specifier-type 'list))
(cond
((type= type (specifier-type 'list))
(if (= length 0)
'nil
(sequence-type-length-mismatch-error type length)))
- ((csubtypep (specifier-type '(cons nil t)) type)
- ;; The above is quite a neat way of finding out if
- ;; there's a type restriction on the CDR of the
- ;; CONS... if there is, I think it's probably fair to
- ;; give up; if there isn't, then the list to be made
- ;; must have a length of more than 0.
- (if (> length 0)
- (make-list length :initial-element initial-element)
- (sequence-type-length-mismatch-error type length)))
+ ((cons-type-p type)
+ (multiple-value-bind (min exactp)
+ (sb!kernel::cons-type-length-info type)
+ (if exactp
+ (unless (= length min)
+ (sequence-type-length-mismatch-error type length))
+ (unless (>= length min)
+ (sequence-type-length-mismatch-error type length)))
+ (make-list length :initial-element initial-element)))
;; We'll get here for e.g. (OR NULL (CONS INTEGER *)),
;; which may seem strange and non-ideal, but then I'd say
;; it was stranger to feed that type in to MAKE-SEQUENCE.
(t (sequence-type-too-hairy (type-specifier type)))))
((csubtypep type (specifier-type 'vector))
- (if (typep type 'array-type)
- ;; KLUDGE: the above test essentially asks "Do we know
- ;; what the upgraded-array-element-type is?" [consider
- ;; (OR STRING BIT-VECTOR)]
- (progn
- (aver (= (length (array-type-dimensions type)) 1))
- (let ((etype (type-specifier
+ (cond
+ (;; is it immediately obvious what the result type is?
+ (typep type 'array-type)
+ (progn
+ (aver (= (length (array-type-dimensions type)) 1))
+ (let* ((etype (type-specifier
(array-type-specialized-element-type type)))
+ (etype (if (eq etype '*) t etype))
(type-length (car (array-type-dimensions type))))
- (unless (or (eq type-length '*)
- (= type-length length))
- (sequence-type-length-mismatch-error type length))
- ;; FIXME: These calls to MAKE-ARRAY can't be
- ;; open-coded, as the :ELEMENT-TYPE argument isn't
- ;; constant. Probably we ought to write a
- ;; DEFTRANSFORM for MAKE-SEQUENCE. -- CSR,
- ;; 2002-07-22
- (if iep
- (make-array length :element-type etype
- :initial-element initial-element)
- (make-array length :element-type etype))))
- (sequence-type-too-hairy (type-specifier type))))
+ (unless (or (eq type-length '*)
+ (= type-length length))
+ (sequence-type-length-mismatch-error type length))
+ ;; FIXME: These calls to MAKE-ARRAY can't be
+ ;; open-coded, as the :ELEMENT-TYPE argument isn't
+ ;; constant. Probably we ought to write a
+ ;; DEFTRANSFORM for MAKE-SEQUENCE. -- CSR,
+ ;; 2002-07-22
+ (if iep
+ (make-array length :element-type etype
+ :initial-element initial-element)
+ (make-array length :element-type etype)))))
+ (t (sequence-type-too-hairy (type-specifier type)))))
(t (bad-sequence-type-error (type-specifier type))))))
\f
;;;; SUBSEQ
(defun vector-subseq* (sequence start &optional end)
(declare (type vector sequence))
- (declare (type fixnum start))
- (declare (type (or null fixnum) end))
- (if (null end)
- (setf end (length sequence))
- (unless (<= end (length sequence))
- (signal-end-too-large-error sequence end)))
+ (declare (type index start))
+ (declare (type (or null index) end))
+ (when (null end)
+ (setf end (length sequence)))
+ (unless (<= 0 start end (length sequence))
+ (signal-bounding-indices-bad-error sequence start end))
(do ((old-index start (1+ old-index))
(new-index 0 (1+ new-index))
(copy (make-sequence-like sequence (- end start))))
(defun list-subseq* (sequence start &optional end)
(declare (type list sequence))
- (declare (type fixnum start))
- (declare (type (or null fixnum) end))
- (if (and end (>= start (the fixnum end)))
- ()
- (let* ((groveled (nthcdr start sequence))
- (result (list (car groveled))))
- (if groveled
- (do ((list (cdr groveled) (cdr list))
- (splice result (cdr (rplacd splice (list (car list)))))
- (index (1+ start) (1+ index)))
- ((or (atom list) (and end (= index (the fixnum end))))
- result)
- (declare (fixnum index)))
- ()))))
-
-;;; SUBSEQ cannot default END to the length of sequence since it is
-;;; not an error to supply NIL for its value. We must test for END
-;;; being NIL in the body of the function, and this is actually done
-;;; in the support routines for other reasons. (See above.)
+ ;; the INDEX declaration isn't actually mandatory, but it's true for
+ ;; all practical purposes.
+ (declare (type index start))
+ (declare (type (or null index) end))
+ (do ((list sequence (cdr list))
+ (index 0 (1+ index))
+ (result nil))
+ (nil)
+ (cond
+ ((null list) (if (or (and end (> end index))
+ (< index start))
+ (signal-bounding-indices-bad-error sequence start end)
+ (return (nreverse result))))
+ ((< index start) nil)
+ ((and end (= index end)) (return (nreverse result)))
+ (t (push (car list) result)))))
+
(defun subseq (sequence start &optional end)
#!+sb-doc
"Return a copy of a subsequence of SEQUENCE starting with element number
(when (null end) (setq end (length sequence)))
(vector-fill sequence item start end))
-;;; FILL cannot default end to the length of sequence since it is not
-;;; an error to supply nil for its value. We must test for end being nil
-;;; in the body of the function, and this is actually done in the support
-;;; routines for other reasons (see above).
-(defun fill (sequence item &key (start 0) end)
+(define-sequence-traverser fill (sequence item &key start end)
#!+sb-doc "Replace the specified elements of SEQUENCE with ITEM."
(seq-dispatch sequence
(list-fill* sequence item start end)
(1- source-index)))
((= target-index (the fixnum (1- target-start))) target-sequence)
(declare (fixnum target-index source-index))
+ ;; disable bounds checking
+ (declare (optimize (safety 0)))
(setf (aref target-sequence target-index)
(aref source-sequence source-index))))
(do ((target-index target-start (1+ target-index))
(= source-index (the fixnum source-end)))
target-sequence)
(declare (fixnum target-index source-index))
+ ;; disable bounds checking
+ (declare (optimize (safety 0)))
(setf (aref target-sequence target-index)
(aref source-sequence source-index)))))
(when (null source-end) (setq source-end (length source-sequence)))
(mumble-replace-from-mumble))
-;;; REPLACE cannot default END arguments to the length of SEQUENCE since it
-;;; is not an error to supply NIL for their values. We must test for ENDs
-;;; being NIL in the body of the function.
-(defun replace (target-sequence source-sequence &key
- ((:start1 target-start) 0)
- ((:end1 target-end))
- ((:start2 source-start) 0)
- ((:end2 source-end)))
+#!+sb-unicode
+(defun simple-character-string-replace-from-simple-character-string*
+ (target-sequence source-sequence
+ target-start target-end source-start source-end)
+ (declare (type (simple-array character (*)) target-sequence source-sequence))
+ (when (null target-end) (setq target-end (length target-sequence)))
+ (when (null source-end) (setq source-end (length source-sequence)))
+ (mumble-replace-from-mumble))
+
+(define-sequence-traverser replace
+ (sequence1 sequence2 &key start1 end1 start2 end2)
#!+sb-doc
"The target sequence is destructively modified by copying successive
elements into it from the source sequence."
- (let ((target-end (or target-end (length target-sequence)))
- (source-end (or source-end (length source-sequence))))
+ (let* (;; KLUDGE: absent either rewriting FOO-REPLACE-FROM-BAR, or
+ ;; excessively polluting DEFINE-SEQUENCE-TRAVERSER, we rebind
+ ;; these things here so that legacy code gets the names it's
+ ;; expecting. We could use &AUX instead :-/.
+ (target-sequence sequence1)
+ (source-sequence sequence2)
+ (target-start start1)
+ (source-start start2)
+ (target-end (or end1 length1))
+ (source-end (or end2 length2)))
(seq-dispatch target-sequence
(seq-dispatch source-sequence
(list-replace-from-list)
(sb!xc:defmacro list-reverse-macro (sequence)
`(do ((new-list ()))
- ((atom ,sequence) new-list)
+ ((endp ,sequence) new-list)
(push (pop ,sequence) new-list)))
) ; EVAL-WHEN
(sb!xc:defmacro vector-nreverse (sequence)
`(let ((length (length (the vector ,sequence))))
- (declare (fixnum length))
- (do ((left-index 0 (1+ left-index))
- (right-index (1- length) (1- right-index))
- (half-length (truncate length 2)))
- ((= left-index half-length) ,sequence)
- (declare (fixnum left-index right-index half-length))
- (rotatef (aref ,sequence left-index)
- (aref ,sequence right-index)))))
+ (when (>= length 2)
+ (do ((left-index 0 (1+ left-index))
+ (right-index (1- length) (1- right-index)))
+ ((<= right-index left-index))
+ (declare (type index left-index right-index))
+ (rotatef (aref ,sequence left-index)
+ (aref ,sequence right-index))))
+ ,sequence))
(sb!xc:defmacro list-nreverse-macro (list)
- `(do ((1st (cdr ,list) (if (atom 1st) 1st (cdr 1st)))
+ `(do ((1st (cdr ,list) (if (endp 1st) 1st (cdr 1st)))
(2nd ,list 1st)
(3rd '() 2nd))
((atom 2nd) 3rd)
(and (vectorp x) (= (length x) 0))))
sequences)
'nil
- (sequence-type-length-mismatch-error type
- ;; FIXME: circular
- ;; list issues. And
- ;; rightward-drift.
- (reduce #'+
- (mapcar #'length
- sequences)))))
- ((csubtypep (specifier-type '(cons nil t)) type)
- (if (notevery (lambda (x) (or (null x)
- (and (vectorp x) (= (length x) 0))))
- sequences)
- (apply #'concat-to-list* sequences)
- (sequence-type-length-mismatch-error type 0)))
+ (sequence-type-length-mismatch-error
+ type
+ ;; FIXME: circular list issues.
+ (reduce #'+ sequences :key #'length))))
+ ((cons-type-p type)
+ (multiple-value-bind (min exactp)
+ (sb!kernel::cons-type-length-info type)
+ (let ((length (reduce #'+ sequences :key #'length)))
+ (if exactp
+ (unless (= length min)
+ (sequence-type-length-mismatch-error type length))
+ (unless (>= length min)
+ (sequence-type-length-mismatch-error type length)))
+ (apply #'concat-to-list* sequences))))
(t (sequence-type-too-hairy (type-specifier type)))))
((csubtypep type (specifier-type 'vector))
(apply #'concat-to-simple* output-type-spec sequences))
ref)
`(do ((index ,start (1+ index))
(value ,initial-value))
- ((= index (the fixnum ,end)) value)
- (declare (fixnum index))
+ ((>= index ,end) value)
(setq value (funcall ,function value
(apply-key ,key (,ref ,sequence index))))))
`(do ((index (1- ,end) (1- index))
(value ,initial-value)
(terminus (1- ,start)))
- ((= index terminus) value)
- (declare (fixnum index terminus))
+ ((<= index terminus) value)
(setq value (funcall ,function
(apply-key ,key (,ref ,sequence index))
value))))
initial-value
ivp)
`(let ((sequence (nthcdr ,start ,sequence)))
- (do ((count (if ,ivp ,start (1+ (the fixnum ,start)))
+ (do ((count (if ,ivp ,start (1+ ,start))
(1+ count))
(sequence (if ,ivp sequence (cdr sequence))
(cdr sequence))
(value (if ,ivp ,initial-value (apply-key ,key (car sequence)))
(funcall ,function value (apply-key ,key (car sequence)))))
- ((= count (the fixnum ,end)) value)
- (declare (fixnum count)))))
+ ((>= count ,end) value))))
(sb!xc:defmacro list-reduce-from-end (function
sequence
end
initial-value
ivp)
- `(let ((sequence (nthcdr (- (the fixnum (length ,sequence))
- (the fixnum ,end))
+ `(let ((sequence (nthcdr (- (length ,sequence) ,end)
(reverse ,sequence))))
- (do ((count (if ,ivp ,start (1+ (the fixnum ,start)))
+ (do ((count (if ,ivp ,start (1+ ,start))
(1+ count))
(sequence (if ,ivp sequence (cdr sequence))
(cdr sequence))
(value (if ,ivp ,initial-value (apply-key ,key (car sequence)))
(funcall ,function (apply-key ,key (car sequence)) value)))
- ((= count (the fixnum ,end)) value)
- (declare (fixnum count)))))
+ ((>= count ,end) value))))
) ; EVAL-WHEN
-(defun reduce (function sequence &key key from-end (start 0)
- end (initial-value nil ivp))
+(define-sequence-traverser reduce
+ (function sequence &key key from-end start end (initial-value nil ivp))
(declare (type index start))
(let ((start start)
- (end (or end (length sequence))))
+ (end (or end length)))
(declare (type index start end))
(cond ((= end start)
(if ivp initial-value (funcall function)))
) ; EVAL-WHEN
(define-sequence-traverser delete
- (item sequence &key from-end (test #'eql) test-not (start 0)
+ (item sequence &key from-end test test-not start
end count key)
#!+sb-doc
"Return a sequence formed by destructively removing the specified ITEM from
the given SEQUENCE."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length)))
- (declare (type index length end))
+ (let ((end (or end length)))
+ (declare (type index end))
(seq-dispatch sequence
(if from-end
(normal-list-delete-from-end)
) ; EVAL-WHEN
(define-sequence-traverser delete-if
- (predicate sequence &key from-end (start 0) key end count)
+ (predicate sequence &key from-end start key end count)
#!+sb-doc
"Return a sequence formed by destructively removing the elements satisfying
the specified PREDICATE from the given SEQUENCE."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length)))
- (declare (type index length end))
+ (let ((end (or end length)))
+ (declare (type index end))
(seq-dispatch sequence
(if from-end
(if-list-delete-from-end)
) ; EVAL-WHEN
(define-sequence-traverser delete-if-not
- (predicate sequence &key from-end (start 0) end key count)
+ (predicate sequence &key from-end start end key count)
#!+sb-doc
"Return a sequence formed by destructively removing the elements not
satisfying the specified PREDICATE from the given SEQUENCE."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length)))
- (declare (type index length end))
+ (let ((end (or end length)))
+ (declare (type index end))
(seq-dispatch sequence
(if from-end
(if-not-list-delete-from-end)
) ; EVAL-WHEN
(define-sequence-traverser remove
- (item sequence &key from-end (test #'eql) test-not (start 0)
+ (item sequence &key from-end test test-not start
end count key)
#!+sb-doc
"Return a copy of SEQUENCE with elements satisfying the test (default is
EQL) with ITEM removed."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length)))
- (declare (type index length end))
+ (let ((end (or end length)))
+ (declare (type index end))
(seq-dispatch sequence
(if from-end
(normal-list-remove-from-end)
(normal-mumble-remove)))))
(define-sequence-traverser remove-if
- (predicate sequence &key from-end (start 0) end count key)
+ (predicate sequence &key from-end start end count key)
#!+sb-doc
- "Return a copy of sequence with elements such that predicate(element)
- is non-null removed"
+ "Return a copy of sequence with elements satisfying PREDICATE removed."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length)))
- (declare (type index length end))
+ (let ((end (or end length)))
+ (declare (type index end))
(seq-dispatch sequence
(if from-end
(if-list-remove-from-end)
(if-mumble-remove)))))
(define-sequence-traverser remove-if-not
- (predicate sequence &key from-end (start 0) end count key)
+ (predicate sequence &key from-end start end count key)
#!+sb-doc
- "Return a copy of sequence with elements such that predicate(element)
- is null removed"
+ "Return a copy of sequence with elements not satisfying PREDICATE removed."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length)))
- (declare (type index length end))
+ (let ((end (or end length)))
+ (declare (type index end))
(seq-dispatch sequence
(if from-end
(if-not-list-remove-from-end)
(declare (fixnum index))
(setq splice (cdr (rplacd splice (list (car current)))))
(setq current (cdr current)))
- (do ((index 0 (1+ index)))
+ (do ((index start (1+ index)))
((or (and end (= index (the fixnum end)))
(atom current)))
(declare (fixnum index))
(if (or (and from-end
- (not (member (apply-key key (car current))
- (nthcdr (1+ start) result)
- :test test
- :test-not test-not
- :key key)))
+ (not (if test-not
+ (member (apply-key key (car current))
+ (nthcdr (1+ start) result)
+ :test-not test-not
+ :key key)
+ (member (apply-key key (car current))
+ (nthcdr (1+ start) result)
+ :test test
+ :key key))))
(and (not from-end)
(not (do ((it (apply-key key (car current)))
(l (cdr current) (cdr l))
())
(declare (fixnum i))
(if (if test-not
- (not (funcall test-not it (apply-key key (car l))))
+ (not (funcall test-not
+ it
+ (apply-key key (car l))))
(funcall test it (apply-key key (car l))))
(return t))))))
(setq splice (cdr (rplacd splice (list (car current))))))
(do ((elt))
((= index end))
(setq elt (aref vector index))
+ ;; FIXME: Relying on POSITION allowing both :TEST and :TEST-NOT
+ ;; arguments simultaneously is a little fragile, since ANSI says
+ ;; we can't depend on it, so we need to remember to keep that
+ ;; extension in our implementation. It'd probably be better to
+ ;; rewrite this to avoid passing both (as
+ ;; LIST-REMOVE-DUPLICATES* was rewritten ca. sbcl-0.7.12.18).
(unless (or (and from-end
- (position (apply-key key elt) result :start start
- :end jndex :test test :test-not test-not :key key))
+ (position (apply-key key elt) result
+ :start start :end jndex
+ :test test :test-not test-not :key key))
(and (not from-end)
- (position (apply-key key elt) vector :start (1+ index)
- :end end :test test :test-not test-not :key key)))
+ (position (apply-key key elt) vector
+ :start (1+ index) :end end
+ :test test :test-not test-not :key key)))
(setf (aref result jndex) elt)
(setq jndex (1+ jndex)))
(setq index (1+ index)))
(setq jndex (1+ jndex)))
(shrink-vector result jndex)))
-(defun remove-duplicates
- (sequence &key (test #'eql) test-not (start 0) from-end end key)
+(define-sequence-traverser remove-duplicates
+ (sequence &key test test-not start end from-end key)
#!+sb-doc
- "The elements of Sequence are compared pairwise, and if any two match,
+ "The elements of SEQUENCE are compared pairwise, and if any two match,
the one occurring earlier is discarded, unless FROM-END is true, in
which case the one later in the sequence is discarded. The resulting
sequence is returned.
:end (if from-end jndex end) :test-not test-not)
(setq jndex (1+ jndex)))))
-(defun delete-duplicates
- (sequence &key (test #'eql) test-not (start 0) from-end end key)
+(define-sequence-traverser delete-duplicates
+ (sequence &key test test-not start end from-end key)
#!+sb-doc
"The elements of SEQUENCE are examined, and if any two match, one is
discarded. The resulting sequence, which may be formed by destroying the
) ; EVAL-WHEN
(define-sequence-traverser substitute
- (new old sequence &key from-end (test #'eql) test-not
- (start 0) count end key)
+ (new old sequence &key from-end test test-not
+ start count end key)
#!+sb-doc
"Return a sequence of the same kind as SEQUENCE with the same elements,
- except that all elements equal to OLD are replaced with NEW. See manual
- for details."
+ except that all elements equal to OLD are replaced with NEW."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length)))
- (declare (type index length end))
+ (let ((end (or end length)))
+ (declare (type index end))
(subst-dispatch 'normal)))
\f
;;;; SUBSTITUTE-IF, SUBSTITUTE-IF-NOT
(define-sequence-traverser substitute-if
- (new test sequence &key from-end (start 0) end count key)
+ (new predicate sequence &key from-end start end count key)
#!+sb-doc
"Return a sequence of the same kind as SEQUENCE with the same elements
- except that all elements satisfying the TEST are replaced with NEW. See
- manual for details."
+ except that all elements satisfying the PRED are replaced with NEW."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length))
- test-not
- old)
+ (let ((end (or end length))
+ (test predicate)
+ (test-not nil)
+ old)
(declare (type index length end))
(subst-dispatch 'if)))
(define-sequence-traverser substitute-if-not
- (new test sequence &key from-end (start 0) end count key)
+ (new predicate sequence &key from-end start end count key)
#!+sb-doc
"Return a sequence of the same kind as SEQUENCE with the same elements
- except that all elements not satisfying the TEST are replaced with NEW.
- See manual for details."
+ except that all elements not satisfying the PRED are replaced with NEW."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length))
- test-not
- old)
+ (let ((end (or end length))
+ (test predicate)
+ (test-not nil)
+ old)
(declare (type index length end))
(subst-dispatch 'if-not)))
\f
;;;; NSUBSTITUTE
(define-sequence-traverser nsubstitute
- (new old sequence &key from-end (test #'eql) test-not
- end count key (start 0))
+ (new old sequence &key from-end test test-not
+ end count key start)
#!+sb-doc
"Return a sequence of the same kind as SEQUENCE with the same elements
- except that all elements equal to OLD are replaced with NEW. The SEQUENCE
- may be destructively modified. See manual for details."
+ except that all elements equal to OLD are replaced with NEW. SEQUENCE
+ may be destructively modified."
(declare (fixnum start))
- (let ((end (or end (length sequence))))
+ (let ((end (or end length)))
(if (listp sequence)
(if from-end
(let ((length (length sequence)))
;;;; NSUBSTITUTE-IF, NSUBSTITUTE-IF-NOT
(define-sequence-traverser nsubstitute-if
- (new test sequence &key from-end (start 0) end count key)
+ (new predicate sequence &key from-end start end count key)
#!+sb-doc
"Return a sequence of the same kind as SEQUENCE with the same elements
- except that all elements satisfying the TEST are replaced with NEW.
- SEQUENCE may be destructively modified. See manual for details."
+ except that all elements satisfying PREDICATE are replaced with NEW.
+ SEQUENCE may be destructively modified."
(declare (fixnum start))
- (let ((end (or end (length sequence))))
+ (let ((end (or end length)))
(declare (fixnum end))
(if (listp sequence)
(if from-end
(let ((length (length sequence)))
(nreverse (nlist-substitute-if*
- new test (nreverse (the list sequence))
+ new predicate (nreverse (the list sequence))
(- length end) (- length start) count key)))
- (nlist-substitute-if* new test sequence
+ (nlist-substitute-if* new predicate sequence
start end count key))
(if from-end
- (nvector-substitute-if* new test sequence -1
+ (nvector-substitute-if* new predicate sequence -1
(1- end) (1- start) count key)
- (nvector-substitute-if* new test sequence 1
+ (nvector-substitute-if* new predicate sequence 1
start end count key)))))
(defun nlist-substitute-if* (new test sequence start end count key)
(setq count (1- count)))))
(define-sequence-traverser nsubstitute-if-not
- (new test sequence &key from-end (start 0) end count key)
+ (new predicate sequence &key from-end start end count key)
#!+sb-doc
"Return a sequence of the same kind as SEQUENCE with the same elements
- except that all elements not satisfying the TEST are replaced with NEW.
- SEQUENCE may be destructively modified. See manual for details."
+ except that all elements not satisfying PREDICATE are replaced with NEW.
+ SEQUENCE may be destructively modified."
(declare (fixnum start))
- (let ((end (or end (length sequence))))
+ (let ((end (or end length)))
(declare (fixnum end))
(if (listp sequence)
(if from-end
(let ((length (length sequence)))
(nreverse (nlist-substitute-if-not*
- new test (nreverse (the list sequence))
+ new predicate (nreverse (the list sequence))
(- length end) (- length start) count key)))
- (nlist-substitute-if-not* new test sequence
+ (nlist-substitute-if-not* new predicate sequence
start end count key))
(if from-end
- (nvector-substitute-if-not* new test sequence -1
+ (nvector-substitute-if-not* new predicate sequence -1
(1- end) (1- start) count key)
- (nvector-substitute-if-not* new test sequence 1
+ (nvector-substitute-if-not* new predicate sequence 1
start end count key)))))
(defun nlist-substitute-if-not* (new test sequence start end count key)
(vector
(with-array-data ((sequence sequence-arg :offset-var offset)
(start start)
- (end (or end (length sequence-arg))))
+ (end (%check-vector-sequence-bounds
+ sequence-arg start end)))
(multiple-value-bind (f p)
(macrolet ((frob2 () '(if from-end
(frob sequence t)
(frob sequence nil))))
(typecase sequence
(simple-vector (frob2))
- (simple-string (frob2))
+ (simple-base-string (frob2))
(t (vector*-frob sequence))))
(declare (type (or index null) p))
- (values f (and p (the index (+ p offset))))))))))
+ (values f (and p (the index (- p offset))))))))))
(defun %find-position (item sequence-arg from-end start end key test)
(macrolet ((frob (sequence from-end)
`(%find-position item ,sequence
) ; EVAL-WHEN
-(defun count-if (test sequence &key from-end (start 0) end key)
+(define-sequence-traverser count-if (pred sequence &key from-end start end key)
#!+sb-doc
- "Return the number of elements in SEQUENCE satisfying TEST(el)."
+ "Return the number of elements in SEQUENCE satisfying PRED(el)."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length)))
+ (let ((end (or end length))
+ (pred (%coerce-callable-to-fun pred)))
(declare (type index end))
(seq-dispatch sequence
(if from-end
- (list-count-if nil t test sequence)
- (list-count-if nil nil test sequence))
+ (list-count-if nil t pred sequence)
+ (list-count-if nil nil pred sequence))
(if from-end
- (vector-count-if nil t test sequence)
- (vector-count-if nil nil test sequence)))))
+ (vector-count-if nil t pred sequence)
+ (vector-count-if nil nil pred sequence)))))
-(defun count-if-not (test sequence &key from-end (start 0) end key)
+(define-sequence-traverser count-if-not
+ (pred sequence &key from-end start end key)
#!+sb-doc
"Return the number of elements in SEQUENCE not satisfying TEST(el)."
(declare (fixnum start))
- (let* ((length (length sequence))
- (end (or end length)))
+ (let ((end (or end length))
+ (pred (%coerce-callable-to-fun pred)))
(declare (type index end))
(seq-dispatch sequence
(if from-end
- (list-count-if t t test sequence)
- (list-count-if t nil test sequence))
+ (list-count-if t t pred sequence)
+ (list-count-if t nil pred sequence))
(if from-end
- (vector-count-if t t test sequence)
- (vector-count-if t nil test sequence)))))
+ (vector-count-if t t pred sequence)
+ (vector-count-if t nil pred sequence)))))
-(defun count (item sequence &key from-end (start 0) end
- key (test #'eql test-p) (test-not nil test-not-p))
+(define-sequence-traverser count
+ (item sequence &key from-end start end
+ key (test #'eql test-p) (test-not nil test-not-p))
#!+sb-doc
"Return the number of elements in SEQUENCE satisfying a test with ITEM,
which defaults to EQL."
;; ANSI Common Lisp has left the behavior in this situation unspecified.
;; (CLHS 17.2.1)
(error ":TEST and :TEST-NOT are both present."))
- (let* ((length (length sequence))
- (end (or end length)))
+ (let ((end (or end length)))
(declare (type index end))
(let ((%test (if test-not-p
(lambda (x)
) ; EVAL-WHEN
-(defun mismatch (sequence1 sequence2 &key from-end (test #'eql) test-not
- (start1 0) end1 (start2 0) end2 key)
+(define-sequence-traverser mismatch
+ (sequence1 sequence2
+ &key from-end test test-not
+ start1 end1 start2 end2 key)
#!+sb-doc
"The specified subsequences of SEQUENCE1 and SEQUENCE2 are compared
element-wise. If they are of equal length and match in every element, the
:FROM-END argument is given, then one plus the index of the rightmost
position in which the sequences differ is returned."
(declare (fixnum start1 start2))
- (let* ((length1 (length sequence1))
- (end1 (or end1 length1))
- (length2 (length sequence2))
+ (let* ((end1 (or end1 length1))
(end2 (or end2 length2)))
- (declare (type index length1 end1 length2 end2))
+ (declare (type index end1 end2))
(match-vars
(seq-dispatch sequence1
(matchify-list (sequence1 start1 length1 end1)
`(do ((main ,main (cdr main))
(jndex start1 (1+ jndex))
(sub (nthcdr start1 ,sub) (cdr sub)))
- ((or (null main) (null sub) (= (the fixnum end1) jndex))
+ ((or (endp main) (endp sub) (<= end1 jndex))
t)
- (declare (fixnum jndex))
- (compare-elements (car main) (car sub))))
+ (declare (type (integer 0) jndex))
+ (compare-elements (car sub) (car main))))
(sb!xc:defmacro search-compare-list-vector (main sub)
`(do ((main ,main (cdr main))
(index start1 (1+ index)))
- ((or (null main) (= index (the fixnum end1))) t)
- (declare (fixnum index))
- (compare-elements (car main) (aref ,sub index))))
+ ((or (endp main) (= index end1)) t)
+ (compare-elements (aref ,sub index) (car main))))
(sb!xc:defmacro search-compare-vector-list (main sub index)
`(do ((sub (nthcdr start1 ,sub) (cdr sub))
(jndex start1 (1+ jndex))
(index ,index (1+ index)))
- ((or (= (the fixnum end1) jndex) (null sub)) t)
- (declare (fixnum jndex index))
- (compare-elements (aref ,main index) (car sub))))
+ ((or (<= end1 jndex) (endp sub)) t)
+ (declare (type (integer 0) jndex))
+ (compare-elements (car sub) (aref ,main index))))
(sb!xc:defmacro search-compare-vector-vector (main sub index)
`(do ((index ,index (1+ index))
(sub-index start1 (1+ sub-index)))
- ((= sub-index (the fixnum end1)) t)
- (declare (fixnum sub-index index))
- (compare-elements (aref ,main index) (aref ,sub sub-index))))
+ ((= sub-index end1) t)
+ (compare-elements (aref ,sub sub-index) (aref ,main index))))
(sb!xc:defmacro search-compare (main-type main sub index)
(if (eq main-type 'list)
(sb!xc:defmacro list-search (main sub)
`(do ((main (nthcdr start2 ,main) (cdr main))
(index2 start2 (1+ index2))
- (terminus (- (the fixnum end2)
- (the fixnum (- (the fixnum end1)
- (the fixnum start1)))))
+ (terminus (- end2 (the (integer 0) (- end1 start1))))
(last-match ()))
((> index2 terminus) last-match)
- (declare (fixnum index2 terminus))
+ (declare (type (integer 0) index2))
(if (search-compare list main ,sub index2)
(if from-end
(setq last-match index2)
(sb!xc:defmacro vector-search (main sub)
`(do ((index2 start2 (1+ index2))
- (terminus (- (the fixnum end2)
- (the fixnum (- (the fixnum end1)
- (the fixnum start1)))))
+ (terminus (- end2 (the (integer 0) (- end1 start1))))
(last-match ()))
((> index2 terminus) last-match)
- (declare (fixnum index2 terminus))
+ (declare (type (integer 0) index2))
(if (search-compare vector ,main ,sub index2)
(if from-end
(setq last-match index2)
) ; EVAL-WHEN
-(defun search (sequence1 sequence2 &key from-end (test #'eql) test-not
- (start1 0) end1 (start2 0) end2 key)
+(define-sequence-traverser search
+ (sequence1 sequence2
+ &key from-end test test-not
+ start1 end1 start2 end2 key)
(declare (fixnum start1 start2))
- (let ((end1 (or end1 (length sequence1)))
- (end2 (or end2 (length sequence2))))
+ (let ((end1 (or end1 length1))
+ (end2 (or end2 length2)))
(seq-dispatch sequence2
(list-search sequence2 sequence1)
(vector-search sequence2 sequence1))))