1 ;;; cl-seq.el --- Common Lisp features, part 3 -*- lexical-binding: t -*-
3 ;; Copyright (C) 1993, 2001-2013 Free Software Foundation, Inc.
5 ;; Author: Dave Gillespie <daveg@synaptics.com>
7 ;; Keywords: extensions
10 ;; This file is part of GNU Emacs.
12 ;; GNU Emacs is free software: you can redistribute it and/or modify
13 ;; it under the terms of the GNU General Public License as published by
14 ;; the Free Software Foundation, either version 3 of the License, or
15 ;; (at your option) any later version.
17 ;; GNU Emacs is distributed in the hope that it will be useful,
18 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
19 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 ;; GNU General Public License for more details.
22 ;; You should have received a copy of the GNU General Public License
23 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
27 ;; These are extensions to Emacs Lisp that provide a degree of
28 ;; Common Lisp compatibility, beyond what is already built-in
31 ;; This package was written by Dave Gillespie; it is a complete
32 ;; rewrite of Cesar Quiroz's original cl.el package of December 1986.
34 ;; Bug reports, comments, and suggestions are welcome!
36 ;; This file contains the Common Lisp sequence and list functions
37 ;; which take keyword arguments.
39 ;; See cl.el for Change Log.
47 ;; This is special-cased here so that we can compile
48 ;; this file independent from cl-macs.
50 (defmacro cl--parsing-keywords (kwords other-keys &rest body)
51 (declare (indent 2) (debug (sexp sexp &rest form)))
54 (let* ((var (if (consp x) (car x) x))
55 (mem `(car (cdr (memq ',var cl-keys)))))
56 (if (eq var :test-not)
57 (setq mem `(and ,mem (setq cl-test ,mem) t)))
59 (setq mem `(and ,mem (setq cl-if ,mem) t)))
61 (format "cl-%s" (substring (symbol-name var) 1)))
62 (if (consp x) `(or ,mem ,(car (cdr x))) mem))))
65 (and (not (eq other-keys t))
67 (list 'let '((cl-keys-temp cl-keys))
68 (list 'while 'cl-keys-temp
69 (list 'or (list 'memq '(car cl-keys-temp)
78 '(car (cdr (memq (quote :allow-other-keys)
80 '(error "Bad keyword argument %s"
82 '(setq cl-keys-temp (cdr (cdr cl-keys-temp)))))))
85 (defmacro cl--check-key (x) ;Expects `cl-key' in context of generated code.
86 (declare (debug edebug-forms))
87 `(if cl-key (funcall cl-key ,x) ,x))
89 (defmacro cl--check-test-nokey (item x) ;cl-test cl-if cl-test-not cl-if-not.
90 (declare (debug edebug-forms))
92 (cl-test (eq (not (funcall cl-test ,item ,x))
94 (cl-if (eq (not (funcall cl-if ,x)) cl-if-not))
97 (defmacro cl--check-test (item x) ;all of the above.
98 (declare (debug edebug-forms))
99 `(cl--check-test-nokey ,item (cl--check-key ,x)))
101 (defmacro cl--check-match (x y) ;cl-key cl-test cl-test-not
102 (declare (debug edebug-forms))
103 (setq x `(cl--check-key ,x) y `(cl--check-key ,y))
105 (eq (not (funcall cl-test ,x ,y)) cl-test-not)
108 ;; Yuck! These vars are set/bound by cl--parsing-keywords to match :if :test
109 ;; and :key keyword args, and they are also accessed (sometimes) via dynamic
110 ;; scoping (and some of those accesses are from macro-expanded code).
111 (defvar cl-test) (defvar cl-test-not)
112 (defvar cl-if) (defvar cl-if-not)
116 (defun cl-reduce (cl-func cl-seq &rest cl-keys)
117 "Reduce two-argument FUNCTION across SEQ.
118 \nKeywords supported: :start :end :from-end :initial-value :key
119 \n(fn FUNCTION SEQ [KEYWORD VALUE]...)"
120 (cl--parsing-keywords (:from-end (:start 0) :end :initial-value :key) ()
121 (or (listp cl-seq) (setq cl-seq (append cl-seq nil)))
122 (setq cl-seq (cl-subseq cl-seq cl-start cl-end))
123 (if cl-from-end (setq cl-seq (nreverse cl-seq)))
124 (let ((cl-accum (cond ((memq :initial-value cl-keys) cl-initial-value)
125 (cl-seq (cl--check-key (pop cl-seq)))
126 (t (funcall cl-func)))))
129 (setq cl-accum (funcall cl-func (cl--check-key (pop cl-seq))
132 (setq cl-accum (funcall cl-func cl-accum
133 (cl--check-key (pop cl-seq))))))
137 (defun cl-fill (seq item &rest cl-keys)
138 "Fill the elements of SEQ with ITEM.
139 \nKeywords supported: :start :end
140 \n(fn SEQ ITEM [KEYWORD VALUE]...)"
141 (cl--parsing-keywords ((:start 0) :end) ()
143 (let ((p (nthcdr cl-start seq))
144 (n (if cl-end (- cl-end cl-start) 8000000)))
145 (while (and p (>= (setq n (1- n)) 0))
148 (or cl-end (setq cl-end (length seq)))
149 (if (and (= cl-start 0) (= cl-end (length seq)))
151 (while (< cl-start cl-end)
152 (aset seq cl-start item)
153 (setq cl-start (1+ cl-start)))))
157 (defun cl-replace (cl-seq1 cl-seq2 &rest cl-keys)
158 "Replace the elements of SEQ1 with the elements of SEQ2.
159 SEQ1 is destructively modified, then returned.
160 \nKeywords supported: :start1 :end1 :start2 :end2
161 \n(fn SEQ1 SEQ2 [KEYWORD VALUE]...)"
162 (cl--parsing-keywords ((:start1 0) :end1 (:start2 0) :end2) ()
163 (if (and (eq cl-seq1 cl-seq2) (<= cl-start2 cl-start1))
164 (or (= cl-start1 cl-start2)
165 (let* ((cl-len (length cl-seq1))
166 (cl-n (min (- (or cl-end1 cl-len) cl-start1)
167 (- (or cl-end2 cl-len) cl-start2))))
168 (while (>= (setq cl-n (1- cl-n)) 0)
169 (cl--set-elt cl-seq1 (+ cl-start1 cl-n)
170 (elt cl-seq2 (+ cl-start2 cl-n))))))
172 (let ((cl-p1 (nthcdr cl-start1 cl-seq1))
173 (cl-n1 (if cl-end1 (- cl-end1 cl-start1) 4000000)))
175 (let ((cl-p2 (nthcdr cl-start2 cl-seq2))
177 (if cl-end2 (- cl-end2 cl-start2) 4000000))))
178 (while (and cl-p1 cl-p2 (>= (setq cl-n (1- cl-n)) 0))
179 (setcar cl-p1 (car cl-p2))
180 (setq cl-p1 (cdr cl-p1) cl-p2 (cdr cl-p2))))
181 (setq cl-end2 (min (or cl-end2 (length cl-seq2))
182 (+ cl-start2 cl-n1)))
183 (while (and cl-p1 (< cl-start2 cl-end2))
184 (setcar cl-p1 (aref cl-seq2 cl-start2))
185 (setq cl-p1 (cdr cl-p1) cl-start2 (1+ cl-start2)))))
186 (setq cl-end1 (min (or cl-end1 (length cl-seq1))
187 (+ cl-start1 (- (or cl-end2 (length cl-seq2))
190 (let ((cl-p2 (nthcdr cl-start2 cl-seq2)))
191 (while (< cl-start1 cl-end1)
192 (aset cl-seq1 cl-start1 (car cl-p2))
193 (setq cl-p2 (cdr cl-p2) cl-start1 (1+ cl-start1))))
194 (while (< cl-start1 cl-end1)
195 (aset cl-seq1 cl-start1 (aref cl-seq2 cl-start2))
196 (setq cl-start2 (1+ cl-start2) cl-start1 (1+ cl-start1))))))
200 (defun cl-remove (cl-item cl-seq &rest cl-keys)
201 "Remove all occurrences of ITEM in SEQ.
202 This is a non-destructive function; it makes a copy of SEQ if necessary
203 to avoid corrupting the original SEQ.
204 \nKeywords supported: :test :test-not :key :count :start :end :from-end
205 \n(fn ITEM SEQ [KEYWORD VALUE]...)"
206 (cl--parsing-keywords (:test :test-not :key :if :if-not :count :from-end
208 (if (<= (or cl-count (setq cl-count 8000000)) 0)
210 (if (or (nlistp cl-seq) (and cl-from-end (< cl-count 4000000)))
211 (let ((cl-i (cl--position cl-item cl-seq cl-start cl-end
214 (let ((cl-res (apply 'cl-delete cl-item (append cl-seq nil)
215 (append (if cl-from-end
216 (list :end (1+ cl-i))
219 (if (listp cl-seq) cl-res
220 (if (stringp cl-seq) (concat cl-res) (vconcat cl-res))))
222 (setq cl-end (- (or cl-end 8000000) cl-start))
224 (while (and cl-seq (> cl-end 0)
225 (cl--check-test cl-item (car cl-seq))
226 (setq cl-end (1- cl-end) cl-seq (cdr cl-seq))
227 (> (setq cl-count (1- cl-count)) 0))))
228 (if (and (> cl-count 0) (> cl-end 0))
229 (let ((cl-p (if (> cl-start 0) (nthcdr cl-start cl-seq)
230 (setq cl-end (1- cl-end)) (cdr cl-seq))))
231 (while (and cl-p (> cl-end 0)
232 (not (cl--check-test cl-item (car cl-p))))
233 (setq cl-p (cdr cl-p) cl-end (1- cl-end)))
234 (if (and cl-p (> cl-end 0))
235 (nconc (cl-ldiff cl-seq cl-p)
236 (if (= cl-count 1) (cdr cl-p)
238 (apply 'cl-delete cl-item
239 (copy-sequence (cdr cl-p))
240 :start 0 :end (1- cl-end)
241 :count (1- cl-count) cl-keys))))
246 (defun cl-remove-if (cl-pred cl-list &rest cl-keys)
247 "Remove all items satisfying PREDICATE in SEQ.
248 This is a non-destructive function; it makes a copy of SEQ if necessary
249 to avoid corrupting the original SEQ.
250 \nKeywords supported: :key :count :start :end :from-end
251 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
252 (apply 'cl-remove nil cl-list :if cl-pred cl-keys))
255 (defun cl-remove-if-not (cl-pred cl-list &rest cl-keys)
256 "Remove all items not satisfying PREDICATE in SEQ.
257 This is a non-destructive function; it makes a copy of SEQ if necessary
258 to avoid corrupting the original SEQ.
259 \nKeywords supported: :key :count :start :end :from-end
260 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
261 (apply 'cl-remove nil cl-list :if-not cl-pred cl-keys))
264 (defun cl-delete (cl-item cl-seq &rest cl-keys)
265 "Remove all occurrences of ITEM in SEQ.
266 This is a destructive function; it reuses the storage of SEQ whenever possible.
267 \nKeywords supported: :test :test-not :key :count :start :end :from-end
268 \n(fn ITEM SEQ [KEYWORD VALUE]...)"
269 (cl--parsing-keywords (:test :test-not :key :if :if-not :count :from-end
271 (if (<= (or cl-count (setq cl-count 8000000)) 0)
274 (if (and cl-from-end (< cl-count 4000000))
276 (while (and (>= (setq cl-count (1- cl-count)) 0)
277 (setq cl-i (cl--position cl-item cl-seq cl-start
278 cl-end cl-from-end)))
279 (if (= cl-i 0) (setq cl-seq (cdr cl-seq))
280 (let ((cl-tail (nthcdr (1- cl-i) cl-seq)))
281 (setcdr cl-tail (cdr (cdr cl-tail)))))
284 (setq cl-end (- (or cl-end 8000000) cl-start))
289 (cl--check-test cl-item (car cl-seq))
290 (setq cl-end (1- cl-end) cl-seq (cdr cl-seq))
291 (> (setq cl-count (1- cl-count)) 0)))
292 (setq cl-end (1- cl-end)))
293 (setq cl-start (1- cl-start)))
294 (if (and (> cl-count 0) (> cl-end 0))
295 (let ((cl-p (nthcdr cl-start cl-seq)))
296 (while (and (cdr cl-p) (> cl-end 0))
297 (if (cl--check-test cl-item (car (cdr cl-p)))
299 (setcdr cl-p (cdr (cdr cl-p)))
300 (if (= (setq cl-count (1- cl-count)) 0)
302 (setq cl-p (cdr cl-p)))
303 (setq cl-end (1- cl-end)))))
305 (apply 'cl-remove cl-item cl-seq cl-keys)))))
308 (defun cl-delete-if (cl-pred cl-list &rest cl-keys)
309 "Remove all items satisfying PREDICATE in SEQ.
310 This is a destructive function; it reuses the storage of SEQ whenever possible.
311 \nKeywords supported: :key :count :start :end :from-end
312 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
313 (apply 'cl-delete nil cl-list :if cl-pred cl-keys))
316 (defun cl-delete-if-not (cl-pred cl-list &rest cl-keys)
317 "Remove all items not satisfying PREDICATE in SEQ.
318 This is a destructive function; it reuses the storage of SEQ whenever possible.
319 \nKeywords supported: :key :count :start :end :from-end
320 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
321 (apply 'cl-delete nil cl-list :if-not cl-pred cl-keys))
324 (defun cl-remove-duplicates (cl-seq &rest cl-keys)
325 "Return a copy of SEQ with all duplicate elements removed.
326 \nKeywords supported: :test :test-not :key :start :end :from-end
327 \n(fn SEQ [KEYWORD VALUE]...)"
328 (cl--delete-duplicates cl-seq cl-keys t))
331 (defun cl-delete-duplicates (cl-seq &rest cl-keys)
332 "Remove all duplicate elements from SEQ (destructively).
333 \nKeywords supported: :test :test-not :key :start :end :from-end
334 \n(fn SEQ [KEYWORD VALUE]...)"
335 (cl--delete-duplicates cl-seq cl-keys nil))
337 (defun cl--delete-duplicates (cl-seq cl-keys cl-copy)
339 (cl--parsing-keywords
340 (:test :test-not :key (:start 0) :end :from-end :if)
343 (let ((cl-p (nthcdr cl-start cl-seq)) cl-i)
344 (setq cl-end (- (or cl-end (length cl-seq)) cl-start))
347 (while (setq cl-i (cl--position (cl--check-key (car cl-p))
348 (cdr cl-p) cl-i (1- cl-end)))
349 (if cl-copy (setq cl-seq (copy-sequence cl-seq)
350 cl-p (nthcdr cl-start cl-seq) cl-copy nil))
351 (let ((cl-tail (nthcdr cl-i cl-p)))
352 (setcdr cl-tail (cdr (cdr cl-tail))))
353 (setq cl-end (1- cl-end)))
354 (setq cl-p (cdr cl-p) cl-end (1- cl-end)
355 cl-start (1+ cl-start)))
357 (setq cl-end (- (or cl-end (length cl-seq)) cl-start))
358 (while (and (cdr cl-seq) (= cl-start 0) (> cl-end 1)
359 (cl--position (cl--check-key (car cl-seq))
360 (cdr cl-seq) 0 (1- cl-end)))
361 (setq cl-seq (cdr cl-seq) cl-end (1- cl-end)))
362 (let ((cl-p (if (> cl-start 0) (nthcdr (1- cl-start) cl-seq)
363 (setq cl-end (1- cl-end) cl-start 1) cl-seq)))
364 (while (and (cdr (cdr cl-p)) (> cl-end 1))
365 (if (cl--position (cl--check-key (car (cdr cl-p)))
366 (cdr (cdr cl-p)) 0 (1- cl-end))
368 (if cl-copy (setq cl-seq (copy-sequence cl-seq)
369 cl-p (nthcdr (1- cl-start) cl-seq)
371 (setcdr cl-p (cdr (cdr cl-p))))
372 (setq cl-p (cdr cl-p)))
373 (setq cl-end (1- cl-end) cl-start (1+ cl-start)))
375 (let ((cl-res (cl--delete-duplicates (append cl-seq nil) cl-keys nil)))
376 (if (stringp cl-seq) (concat cl-res) (vconcat cl-res)))))
379 (defun cl-substitute (cl-new cl-old cl-seq &rest cl-keys)
380 "Substitute NEW for OLD in SEQ.
381 This is a non-destructive function; it makes a copy of SEQ if necessary
382 to avoid corrupting the original SEQ.
383 \nKeywords supported: :test :test-not :key :count :start :end :from-end
384 \n(fn NEW OLD SEQ [KEYWORD VALUE]...)"
385 (cl--parsing-keywords (:test :test-not :key :if :if-not :count
386 (:start 0) :end :from-end) ()
387 (if (or (eq cl-old cl-new)
388 (<= (or cl-count (setq cl-from-end nil cl-count 8000000)) 0))
390 (let ((cl-i (cl--position cl-old cl-seq cl-start cl-end)))
393 (setq cl-seq (copy-sequence cl-seq))
395 (progn (cl--set-elt cl-seq cl-i cl-new)
396 (setq cl-i (1+ cl-i) cl-count (1- cl-count))))
397 (apply 'cl-nsubstitute cl-new cl-old cl-seq :count cl-count
398 :start cl-i cl-keys))))))
401 (defun cl-substitute-if (cl-new cl-pred cl-list &rest cl-keys)
402 "Substitute NEW for all items satisfying PREDICATE in SEQ.
403 This is a non-destructive function; it makes a copy of SEQ if necessary
404 to avoid corrupting the original SEQ.
405 \nKeywords supported: :key :count :start :end :from-end
406 \n(fn NEW PREDICATE SEQ [KEYWORD VALUE]...)"
407 (apply 'cl-substitute cl-new nil cl-list :if cl-pred cl-keys))
410 (defun cl-substitute-if-not (cl-new cl-pred cl-list &rest cl-keys)
411 "Substitute NEW for all items not satisfying PREDICATE in SEQ.
412 This is a non-destructive function; it makes a copy of SEQ if necessary
413 to avoid corrupting the original SEQ.
414 \nKeywords supported: :key :count :start :end :from-end
415 \n(fn NEW PREDICATE SEQ [KEYWORD VALUE]...)"
416 (apply 'cl-substitute cl-new nil cl-list :if-not cl-pred cl-keys))
419 (defun cl-nsubstitute (cl-new cl-old cl-seq &rest cl-keys)
420 "Substitute NEW for OLD in SEQ.
421 This is a destructive function; it reuses the storage of SEQ whenever possible.
422 \nKeywords supported: :test :test-not :key :count :start :end :from-end
423 \n(fn NEW OLD SEQ [KEYWORD VALUE]...)"
424 (cl--parsing-keywords (:test :test-not :key :if :if-not :count
425 (:start 0) :end :from-end) ()
426 (or (eq cl-old cl-new) (<= (or cl-count (setq cl-count 8000000)) 0)
427 (if (and (listp cl-seq) (or (not cl-from-end) (> cl-count 4000000)))
428 (let ((cl-p (nthcdr cl-start cl-seq)))
429 (setq cl-end (- (or cl-end 8000000) cl-start))
430 (while (and cl-p (> cl-end 0) (> cl-count 0))
431 (if (cl--check-test cl-old (car cl-p))
434 (setq cl-count (1- cl-count))))
435 (setq cl-p (cdr cl-p) cl-end (1- cl-end))))
436 (or cl-end (setq cl-end (length cl-seq)))
438 (while (and (< cl-start cl-end) (> cl-count 0))
439 (setq cl-end (1- cl-end))
440 (if (cl--check-test cl-old (elt cl-seq cl-end))
442 (cl--set-elt cl-seq cl-end cl-new)
443 (setq cl-count (1- cl-count)))))
444 (while (and (< cl-start cl-end) (> cl-count 0))
445 (if (cl--check-test cl-old (aref cl-seq cl-start))
447 (aset cl-seq cl-start cl-new)
448 (setq cl-count (1- cl-count))))
449 (setq cl-start (1+ cl-start))))))
453 (defun cl-nsubstitute-if (cl-new cl-pred cl-list &rest cl-keys)
454 "Substitute NEW for all items satisfying PREDICATE in SEQ.
455 This is a destructive function; it reuses the storage of SEQ whenever possible.
456 \nKeywords supported: :key :count :start :end :from-end
457 \n(fn NEW PREDICATE SEQ [KEYWORD VALUE]...)"
458 (apply 'cl-nsubstitute cl-new nil cl-list :if cl-pred cl-keys))
461 (defun cl-nsubstitute-if-not (cl-new cl-pred cl-list &rest cl-keys)
462 "Substitute NEW for all items not satisfying PREDICATE in SEQ.
463 This is a destructive function; it reuses the storage of SEQ whenever possible.
464 \nKeywords supported: :key :count :start :end :from-end
465 \n(fn NEW PREDICATE SEQ [KEYWORD VALUE]...)"
466 (apply 'cl-nsubstitute cl-new nil cl-list :if-not cl-pred cl-keys))
469 (defun cl-find (cl-item cl-seq &rest cl-keys)
470 "Find the first occurrence of ITEM in SEQ.
471 Return the matching ITEM, or nil if not found.
472 \nKeywords supported: :test :test-not :key :start :end :from-end
473 \n(fn ITEM SEQ [KEYWORD VALUE]...)"
474 (let ((cl-pos (apply 'cl-position cl-item cl-seq cl-keys)))
475 (and cl-pos (elt cl-seq cl-pos))))
478 (defun cl-find-if (cl-pred cl-list &rest cl-keys)
479 "Find the first item satisfying PREDICATE in SEQ.
480 Return the matching item, or nil if not found.
481 \nKeywords supported: :key :start :end :from-end
482 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
483 (apply 'cl-find nil cl-list :if cl-pred cl-keys))
486 (defun cl-find-if-not (cl-pred cl-list &rest cl-keys)
487 "Find the first item not satisfying PREDICATE in SEQ.
488 Return the matching item, or nil if not found.
489 \nKeywords supported: :key :start :end :from-end
490 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
491 (apply 'cl-find nil cl-list :if-not cl-pred cl-keys))
494 (defun cl-position (cl-item cl-seq &rest cl-keys)
495 "Find the first occurrence of ITEM in SEQ.
496 Return the index of the matching item, or nil if not found.
497 \nKeywords supported: :test :test-not :key :start :end :from-end
498 \n(fn ITEM SEQ [KEYWORD VALUE]...)"
499 (cl--parsing-keywords (:test :test-not :key :if :if-not
500 (:start 0) :end :from-end) ()
501 (cl--position cl-item cl-seq cl-start cl-end cl-from-end)))
503 (defun cl--position (cl-item cl-seq cl-start &optional cl-end cl-from-end)
505 (let ((cl-p (nthcdr cl-start cl-seq)))
506 (or cl-end (setq cl-end 8000000))
508 (while (and cl-p (< cl-start cl-end) (or (not cl-res) cl-from-end))
509 (if (cl--check-test cl-item (car cl-p))
510 (setq cl-res cl-start))
511 (setq cl-p (cdr cl-p) cl-start (1+ cl-start)))
513 (or cl-end (setq cl-end (length cl-seq)))
516 (while (and (>= (setq cl-end (1- cl-end)) cl-start)
517 (not (cl--check-test cl-item (aref cl-seq cl-end)))))
518 (and (>= cl-end cl-start) cl-end))
519 (while (and (< cl-start cl-end)
520 (not (cl--check-test cl-item (aref cl-seq cl-start))))
521 (setq cl-start (1+ cl-start)))
522 (and (< cl-start cl-end) cl-start))))
525 (defun cl-position-if (cl-pred cl-list &rest cl-keys)
526 "Find the first item satisfying PREDICATE in SEQ.
527 Return the index of the matching item, or nil if not found.
528 \nKeywords supported: :key :start :end :from-end
529 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
530 (apply 'cl-position nil cl-list :if cl-pred cl-keys))
533 (defun cl-position-if-not (cl-pred cl-list &rest cl-keys)
534 "Find the first item not satisfying PREDICATE in SEQ.
535 Return the index of the matching item, or nil if not found.
536 \nKeywords supported: :key :start :end :from-end
537 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
538 (apply 'cl-position nil cl-list :if-not cl-pred cl-keys))
541 (defun cl-count (cl-item cl-seq &rest cl-keys)
542 "Count the number of occurrences of ITEM in SEQ.
543 \nKeywords supported: :test :test-not :key :start :end
544 \n(fn ITEM SEQ [KEYWORD VALUE]...)"
545 (cl--parsing-keywords (:test :test-not :key :if :if-not (:start 0) :end) ()
546 (let ((cl-count 0) cl-x)
547 (or cl-end (setq cl-end (length cl-seq)))
548 (if (consp cl-seq) (setq cl-seq (nthcdr cl-start cl-seq)))
549 (while (< cl-start cl-end)
550 (setq cl-x (if (consp cl-seq) (pop cl-seq) (aref cl-seq cl-start)))
551 (if (cl--check-test cl-item cl-x) (setq cl-count (1+ cl-count)))
552 (setq cl-start (1+ cl-start)))
556 (defun cl-count-if (cl-pred cl-list &rest cl-keys)
557 "Count the number of items satisfying PREDICATE in SEQ.
558 \nKeywords supported: :key :start :end
559 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
560 (apply 'cl-count nil cl-list :if cl-pred cl-keys))
563 (defun cl-count-if-not (cl-pred cl-list &rest cl-keys)
564 "Count the number of items not satisfying PREDICATE in SEQ.
565 \nKeywords supported: :key :start :end
566 \n(fn PREDICATE SEQ [KEYWORD VALUE]...)"
567 (apply 'cl-count nil cl-list :if-not cl-pred cl-keys))
570 (defun cl-mismatch (cl-seq1 cl-seq2 &rest cl-keys)
571 "Compare SEQ1 with SEQ2, return index of first mismatching element.
572 Return nil if the sequences match. If one sequence is a prefix of the
573 other, the return value indicates the end of the shorter sequence.
574 \nKeywords supported: :test :test-not :key :start1 :end1 :start2 :end2 :from-end
575 \n(fn SEQ1 SEQ2 [KEYWORD VALUE]...)"
576 (cl--parsing-keywords (:test :test-not :key :from-end
577 (:start1 0) :end1 (:start2 0) :end2) ()
578 (or cl-end1 (setq cl-end1 (length cl-seq1)))
579 (or cl-end2 (setq cl-end2 (length cl-seq2)))
582 (while (and (< cl-start1 cl-end1) (< cl-start2 cl-end2)
583 (cl--check-match (elt cl-seq1 (1- cl-end1))
584 (elt cl-seq2 (1- cl-end2))))
585 (setq cl-end1 (1- cl-end1) cl-end2 (1- cl-end2)))
586 (and (or (< cl-start1 cl-end1) (< cl-start2 cl-end2))
588 (let ((cl-p1 (and (listp cl-seq1) (nthcdr cl-start1 cl-seq1)))
589 (cl-p2 (and (listp cl-seq2) (nthcdr cl-start2 cl-seq2))))
590 (while (and (< cl-start1 cl-end1) (< cl-start2 cl-end2)
591 (cl--check-match (if cl-p1 (car cl-p1)
592 (aref cl-seq1 cl-start1))
593 (if cl-p2 (car cl-p2)
594 (aref cl-seq2 cl-start2))))
595 (setq cl-p1 (cdr cl-p1) cl-p2 (cdr cl-p2)
596 cl-start1 (1+ cl-start1) cl-start2 (1+ cl-start2)))
597 (and (or (< cl-start1 cl-end1) (< cl-start2 cl-end2))
601 (defun cl-search (cl-seq1 cl-seq2 &rest cl-keys)
602 "Search for SEQ1 as a subsequence of SEQ2.
603 Return the index of the leftmost element of the first match found;
604 return nil if there are no matches.
605 \nKeywords supported: :test :test-not :key :start1 :end1 :start2 :end2 :from-end
606 \n(fn SEQ1 SEQ2 [KEYWORD VALUE]...)"
607 (cl--parsing-keywords (:test :test-not :key :from-end
608 (:start1 0) :end1 (:start2 0) :end2) ()
609 (or cl-end1 (setq cl-end1 (length cl-seq1)))
610 (or cl-end2 (setq cl-end2 (length cl-seq2)))
611 (if (>= cl-start1 cl-end1)
612 (if cl-from-end cl-end2 cl-start2)
613 (let* ((cl-len (- cl-end1 cl-start1))
614 (cl-first (cl--check-key (elt cl-seq1 cl-start1)))
616 (setq cl-end2 (- cl-end2 (1- cl-len)))
617 (while (and (< cl-start2 cl-end2)
618 (setq cl-pos (cl--position cl-first cl-seq2
619 cl-start2 cl-end2 cl-from-end))
620 (apply 'cl-mismatch cl-seq1 cl-seq2
621 :start1 (1+ cl-start1) :end1 cl-end1
622 :start2 (1+ cl-pos) :end2 (+ cl-pos cl-len)
623 :from-end nil cl-keys))
624 (if cl-from-end (setq cl-end2 cl-pos) (setq cl-start2 (1+ cl-pos))))
625 (and (< cl-start2 cl-end2) cl-pos)))))
628 (defun cl-sort (cl-seq cl-pred &rest cl-keys)
629 "Sort the argument SEQ according to PREDICATE.
630 This is a destructive function; it reuses the storage of SEQ if possible.
631 \nKeywords supported: :key
632 \n(fn SEQ PREDICATE [KEYWORD VALUE]...)"
634 (cl-replace cl-seq (apply 'cl-sort (append cl-seq nil) cl-pred cl-keys))
635 (cl--parsing-keywords (:key) ()
636 (if (memq cl-key '(nil identity))
637 (sort cl-seq cl-pred)
638 (sort cl-seq (function (lambda (cl-x cl-y)
639 (funcall cl-pred (funcall cl-key cl-x)
640 (funcall cl-key cl-y)))))))))
643 (defun cl-stable-sort (cl-seq cl-pred &rest cl-keys)
644 "Sort the argument SEQ stably according to PREDICATE.
645 This is a destructive function; it reuses the storage of SEQ if possible.
646 \nKeywords supported: :key
647 \n(fn SEQ PREDICATE [KEYWORD VALUE]...)"
648 (apply 'cl-sort cl-seq cl-pred cl-keys))
651 (defun cl-merge (cl-type cl-seq1 cl-seq2 cl-pred &rest cl-keys)
652 "Destructively merge the two sequences to produce a new sequence.
653 TYPE is the sequence type to return, SEQ1 and SEQ2 are the two argument
654 sequences, and PREDICATE is a `less-than' predicate on the elements.
655 \nKeywords supported: :key
656 \n(fn TYPE SEQ1 SEQ2 PREDICATE [KEYWORD VALUE]...)"
657 (or (listp cl-seq1) (setq cl-seq1 (append cl-seq1 nil)))
658 (or (listp cl-seq2) (setq cl-seq2 (append cl-seq2 nil)))
659 (cl--parsing-keywords (:key) ()
661 (while (and cl-seq1 cl-seq2)
662 (if (funcall cl-pred (cl--check-key (car cl-seq2))
663 (cl--check-key (car cl-seq1)))
664 (push (pop cl-seq2) cl-res)
665 (push (pop cl-seq1) cl-res)))
666 (cl-coerce (nconc (nreverse cl-res) cl-seq1 cl-seq2) cl-type))))
669 (defun cl-member (cl-item cl-list &rest cl-keys)
670 "Find the first occurrence of ITEM in LIST.
671 Return the sublist of LIST whose car is ITEM.
672 \nKeywords supported: :test :test-not :key
673 \n(fn ITEM LIST [KEYWORD VALUE]...)"
674 (declare (compiler-macro cl--compiler-macro-member))
676 (cl--parsing-keywords (:test :test-not :key :if :if-not) ()
677 (while (and cl-list (not (cl--check-test cl-item (car cl-list))))
678 (setq cl-list (cdr cl-list)))
680 (if (and (numberp cl-item) (not (integerp cl-item)))
681 (member cl-item cl-list)
682 (memq cl-item cl-list))))
683 (autoload 'cl--compiler-macro-member "cl-macs")
686 (defun cl-member-if (cl-pred cl-list &rest cl-keys)
687 "Find the first item satisfying PREDICATE in LIST.
688 Return the sublist of LIST whose car matches.
689 \nKeywords supported: :key
690 \n(fn PREDICATE LIST [KEYWORD VALUE]...)"
691 (apply 'cl-member nil cl-list :if cl-pred cl-keys))
694 (defun cl-member-if-not (cl-pred cl-list &rest cl-keys)
695 "Find the first item not satisfying PREDICATE in LIST.
696 Return the sublist of LIST whose car matches.
697 \nKeywords supported: :key
698 \n(fn PREDICATE LIST [KEYWORD VALUE]...)"
699 (apply 'cl-member nil cl-list :if-not cl-pred cl-keys))
702 (defun cl--adjoin (cl-item cl-list &rest cl-keys)
703 (if (cl--parsing-keywords (:key) t
704 (apply 'cl-member (cl--check-key cl-item) cl-list cl-keys))
706 (cons cl-item cl-list)))
709 (defun cl-assoc (cl-item cl-alist &rest cl-keys)
710 "Find the first item whose car matches ITEM in LIST.
711 \nKeywords supported: :test :test-not :key
712 \n(fn ITEM LIST [KEYWORD VALUE]...)"
713 (declare (compiler-macro cl--compiler-macro-assoc))
715 (cl--parsing-keywords (:test :test-not :key :if :if-not) ()
717 (or (not (consp (car cl-alist)))
718 (not (cl--check-test cl-item (car (car cl-alist))))))
719 (setq cl-alist (cdr cl-alist)))
720 (and cl-alist (car cl-alist)))
721 (if (and (numberp cl-item) (not (integerp cl-item)))
722 (assoc cl-item cl-alist)
723 (assq cl-item cl-alist))))
724 (autoload 'cl--compiler-macro-assoc "cl-macs")
727 (defun cl-assoc-if (cl-pred cl-list &rest cl-keys)
728 "Find the first item whose car satisfies PREDICATE in LIST.
729 \nKeywords supported: :key
730 \n(fn PREDICATE LIST [KEYWORD VALUE]...)"
731 (apply 'cl-assoc nil cl-list :if cl-pred cl-keys))
734 (defun cl-assoc-if-not (cl-pred cl-list &rest cl-keys)
735 "Find the first item whose car does not satisfy PREDICATE in LIST.
736 \nKeywords supported: :key
737 \n(fn PREDICATE LIST [KEYWORD VALUE]...)"
738 (apply 'cl-assoc nil cl-list :if-not cl-pred cl-keys))
741 (defun cl-rassoc (cl-item cl-alist &rest cl-keys)
742 "Find the first item whose cdr matches ITEM in LIST.
743 \nKeywords supported: :test :test-not :key
744 \n(fn ITEM LIST [KEYWORD VALUE]...)"
745 (if (or cl-keys (numberp cl-item))
746 (cl--parsing-keywords (:test :test-not :key :if :if-not) ()
748 (or (not (consp (car cl-alist)))
749 (not (cl--check-test cl-item (cdr (car cl-alist))))))
750 (setq cl-alist (cdr cl-alist)))
751 (and cl-alist (car cl-alist)))
752 (rassq cl-item cl-alist)))
755 (defun cl-rassoc-if (cl-pred cl-list &rest cl-keys)
756 "Find the first item whose cdr satisfies PREDICATE in LIST.
757 \nKeywords supported: :key
758 \n(fn PREDICATE LIST [KEYWORD VALUE]...)"
759 (apply 'cl-rassoc nil cl-list :if cl-pred cl-keys))
762 (defun cl-rassoc-if-not (cl-pred cl-list &rest cl-keys)
763 "Find the first item whose cdr does not satisfy PREDICATE in LIST.
764 \nKeywords supported: :key
765 \n(fn PREDICATE LIST [KEYWORD VALUE]...)"
766 (apply 'cl-rassoc nil cl-list :if-not cl-pred cl-keys))
769 (defun cl-union (cl-list1 cl-list2 &rest cl-keys)
770 "Combine LIST1 and LIST2 using a set-union operation.
771 The resulting list contains all items that appear in either LIST1 or LIST2.
772 This is a non-destructive function; it makes a copy of the data if necessary
773 to avoid corrupting the original LIST1 and LIST2.
774 \nKeywords supported: :test :test-not :key
775 \n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
776 (cond ((null cl-list1) cl-list2) ((null cl-list2) cl-list1)
777 ((equal cl-list1 cl-list2) cl-list1)
779 (or (>= (length cl-list1) (length cl-list2))
780 (setq cl-list1 (prog1 cl-list2 (setq cl-list2 cl-list1))))
782 (if (or cl-keys (numberp (car cl-list2)))
784 (apply 'cl-adjoin (car cl-list2) cl-list1 cl-keys))
785 (or (memq (car cl-list2) cl-list1)
786 (push (car cl-list2) cl-list1)))
791 (defun cl-nunion (cl-list1 cl-list2 &rest cl-keys)
792 "Combine LIST1 and LIST2 using a set-union operation.
793 The resulting list contains all items that appear in either LIST1 or LIST2.
794 This is a destructive function; it reuses the storage of LIST1 and LIST2
796 \nKeywords supported: :test :test-not :key
797 \n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
798 (cond ((null cl-list1) cl-list2) ((null cl-list2) cl-list1)
799 (t (apply 'cl-union cl-list1 cl-list2 cl-keys))))
802 (defun cl-intersection (cl-list1 cl-list2 &rest cl-keys)
803 "Combine LIST1 and LIST2 using a set-intersection operation.
804 The resulting list contains all items that appear in both LIST1 and LIST2.
805 This is a non-destructive function; it makes a copy of the data if necessary
806 to avoid corrupting the original LIST1 and LIST2.
807 \nKeywords supported: :test :test-not :key
808 \n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
809 (and cl-list1 cl-list2
810 (if (equal cl-list1 cl-list2) cl-list1
811 (cl--parsing-keywords (:key) (:test :test-not)
813 (or (>= (length cl-list1) (length cl-list2))
814 (setq cl-list1 (prog1 cl-list2 (setq cl-list2 cl-list1))))
816 (if (if (or cl-keys (numberp (car cl-list2)))
817 (apply 'cl-member (cl--check-key (car cl-list2))
819 (memq (car cl-list2) cl-list1))
820 (push (car cl-list2) cl-res))
825 (defun cl-nintersection (cl-list1 cl-list2 &rest cl-keys)
826 "Combine LIST1 and LIST2 using a set-intersection operation.
827 The resulting list contains all items that appear in both LIST1 and LIST2.
828 This is a destructive function; it reuses the storage of LIST1 and LIST2
830 \nKeywords supported: :test :test-not :key
831 \n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
832 (and cl-list1 cl-list2 (apply 'cl-intersection cl-list1 cl-list2 cl-keys)))
835 (defun cl-set-difference (cl-list1 cl-list2 &rest cl-keys)
836 "Combine LIST1 and LIST2 using a set-difference operation.
837 The resulting list contains all items that appear in LIST1 but not LIST2.
838 This is a non-destructive function; it makes a copy of the data if necessary
839 to avoid corrupting the original LIST1 and LIST2.
840 \nKeywords supported: :test :test-not :key
841 \n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
842 (if (or (null cl-list1) (null cl-list2)) cl-list1
843 (cl--parsing-keywords (:key) (:test :test-not)
846 (or (if (or cl-keys (numberp (car cl-list1)))
847 (apply 'cl-member (cl--check-key (car cl-list1))
849 (memq (car cl-list1) cl-list2))
850 (push (car cl-list1) cl-res))
855 (defun cl-nset-difference (cl-list1 cl-list2 &rest cl-keys)
856 "Combine LIST1 and LIST2 using a set-difference operation.
857 The resulting list contains all items that appear in LIST1 but not LIST2.
858 This is a destructive function; it reuses the storage of LIST1 and LIST2
860 \nKeywords supported: :test :test-not :key
861 \n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
862 (if (or (null cl-list1) (null cl-list2)) cl-list1
863 (apply 'cl-set-difference cl-list1 cl-list2 cl-keys)))
866 (defun cl-set-exclusive-or (cl-list1 cl-list2 &rest cl-keys)
867 "Combine LIST1 and LIST2 using a set-exclusive-or operation.
868 The resulting list contains all items appearing in exactly one of LIST1, LIST2.
869 This is a non-destructive function; it makes a copy of the data if necessary
870 to avoid corrupting the original LIST1 and LIST2.
871 \nKeywords supported: :test :test-not :key
872 \n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
873 (cond ((null cl-list1) cl-list2) ((null cl-list2) cl-list1)
874 ((equal cl-list1 cl-list2) nil)
875 (t (append (apply 'cl-set-difference cl-list1 cl-list2 cl-keys)
876 (apply 'cl-set-difference cl-list2 cl-list1 cl-keys)))))
879 (defun cl-nset-exclusive-or (cl-list1 cl-list2 &rest cl-keys)
880 "Combine LIST1 and LIST2 using a set-exclusive-or operation.
881 The resulting list contains all items appearing in exactly one of LIST1, LIST2.
882 This is a destructive function; it reuses the storage of LIST1 and LIST2
884 \nKeywords supported: :test :test-not :key
885 \n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
886 (cond ((null cl-list1) cl-list2) ((null cl-list2) cl-list1)
887 ((equal cl-list1 cl-list2) nil)
888 (t (nconc (apply 'cl-nset-difference cl-list1 cl-list2 cl-keys)
889 (apply 'cl-nset-difference cl-list2 cl-list1 cl-keys)))))
892 (defun cl-subsetp (cl-list1 cl-list2 &rest cl-keys)
893 "Return true if LIST1 is a subset of LIST2.
894 I.e., if every element of LIST1 also appears in LIST2.
895 \nKeywords supported: :test :test-not :key
896 \n(fn LIST1 LIST2 [KEYWORD VALUE]...)"
897 (cond ((null cl-list1) t) ((null cl-list2) nil)
898 ((equal cl-list1 cl-list2) t)
899 (t (cl--parsing-keywords (:key) (:test :test-not)
901 (apply 'cl-member (cl--check-key (car cl-list1))
907 (defun cl-subst-if (cl-new cl-pred cl-tree &rest cl-keys)
908 "Substitute NEW for elements matching PREDICATE in TREE (non-destructively).
909 Return a copy of TREE with all matching elements replaced by NEW.
910 \nKeywords supported: :key
911 \n(fn NEW PREDICATE TREE [KEYWORD VALUE]...)"
912 (apply 'cl-sublis (list (cons nil cl-new)) cl-tree :if cl-pred cl-keys))
915 (defun cl-subst-if-not (cl-new cl-pred cl-tree &rest cl-keys)
916 "Substitute NEW for elts not matching PREDICATE in TREE (non-destructively).
917 Return a copy of TREE with all non-matching elements replaced by NEW.
918 \nKeywords supported: :key
919 \n(fn NEW PREDICATE TREE [KEYWORD VALUE]...)"
920 (apply 'cl-sublis (list (cons nil cl-new)) cl-tree :if-not cl-pred cl-keys))
923 (defun cl-nsubst (cl-new cl-old cl-tree &rest cl-keys)
924 "Substitute NEW for OLD everywhere in TREE (destructively).
925 Any element of TREE which is `eql' to OLD is changed to NEW (via a call
927 \nKeywords supported: :test :test-not :key
928 \n(fn NEW OLD TREE [KEYWORD VALUE]...)"
929 (apply 'cl-nsublis (list (cons cl-old cl-new)) cl-tree cl-keys))
932 (defun cl-nsubst-if (cl-new cl-pred cl-tree &rest cl-keys)
933 "Substitute NEW for elements matching PREDICATE in TREE (destructively).
934 Any element of TREE which matches is changed to NEW (via a call to `setcar').
935 \nKeywords supported: :key
936 \n(fn NEW PREDICATE TREE [KEYWORD VALUE]...)"
937 (apply 'cl-nsublis (list (cons nil cl-new)) cl-tree :if cl-pred cl-keys))
940 (defun cl-nsubst-if-not (cl-new cl-pred cl-tree &rest cl-keys)
941 "Substitute NEW for elements not matching PREDICATE in TREE (destructively).
942 Any element of TREE which matches is changed to NEW (via a call to `setcar').
943 \nKeywords supported: :key
944 \n(fn NEW PREDICATE TREE [KEYWORD VALUE]...)"
945 (apply 'cl-nsublis (list (cons nil cl-new)) cl-tree :if-not cl-pred cl-keys))
950 (defun cl-sublis (cl-alist cl-tree &rest cl-keys)
951 "Perform substitutions indicated by ALIST in TREE (non-destructively).
952 Return a copy of TREE with all matching elements replaced.
953 \nKeywords supported: :test :test-not :key
954 \n(fn ALIST TREE [KEYWORD VALUE]...)"
955 (cl--parsing-keywords (:test :test-not :key :if :if-not) ()
956 (let ((cl--alist cl-alist))
957 (cl--sublis-rec cl-tree))))
959 (defun cl--sublis-rec (cl-tree) ;Uses cl--alist cl-key/test*/if*.
960 (let ((cl-temp (cl--check-key cl-tree)) (cl-p cl--alist))
961 (while (and cl-p (not (cl--check-test-nokey (car (car cl-p)) cl-temp)))
962 (setq cl-p (cdr cl-p)))
963 (if cl-p (cdr (car cl-p))
965 (let ((cl-a (cl--sublis-rec (car cl-tree)))
966 (cl-d (cl--sublis-rec (cdr cl-tree))))
967 (if (and (eq cl-a (car cl-tree)) (eq cl-d (cdr cl-tree)))
973 (defun cl-nsublis (cl-alist cl-tree &rest cl-keys)
974 "Perform substitutions indicated by ALIST in TREE (destructively).
975 Any matching element of TREE is changed via a call to `setcar'.
976 \nKeywords supported: :test :test-not :key
977 \n(fn ALIST TREE [KEYWORD VALUE]...)"
978 (cl--parsing-keywords (:test :test-not :key :if :if-not) ()
979 (let ((cl-hold (list cl-tree))
980 (cl--alist cl-alist))
981 (cl--nsublis-rec cl-hold)
984 (defun cl--nsublis-rec (cl-tree) ;Uses cl--alist cl-key/test*/if*.
985 (while (consp cl-tree)
986 (let ((cl-temp (cl--check-key (car cl-tree))) (cl-p cl--alist))
987 (while (and cl-p (not (cl--check-test-nokey (car (car cl-p)) cl-temp)))
988 (setq cl-p (cdr cl-p)))
989 (if cl-p (setcar cl-tree (cdr (car cl-p)))
990 (if (consp (car cl-tree)) (cl--nsublis-rec (car cl-tree))))
991 (setq cl-temp (cl--check-key (cdr cl-tree)) cl-p cl--alist)
992 (while (and cl-p (not (cl--check-test-nokey (car (car cl-p)) cl-temp)))
993 (setq cl-p (cdr cl-p)))
995 (progn (setcdr cl-tree (cdr (car cl-p))) (setq cl-tree nil))
996 (setq cl-tree (cdr cl-tree))))))
999 (defun cl-tree-equal (cl-x cl-y &rest cl-keys)
1000 "Return t if trees TREE1 and TREE2 have `eql' leaves.
1001 Atoms are compared by `eql'; cons cells are compared recursively.
1002 \nKeywords supported: :test :test-not :key
1003 \n(fn TREE1 TREE2 [KEYWORD VALUE]...)"
1004 (cl--parsing-keywords (:test :test-not :key) ()
1005 (cl--tree-equal-rec cl-x cl-y)))
1007 (defun cl--tree-equal-rec (cl-x cl-y) ;Uses cl-key/test*.
1008 (while (and (consp cl-x) (consp cl-y)
1009 (cl--tree-equal-rec (car cl-x) (car cl-y)))
1010 (setq cl-x (cdr cl-x) cl-y (cdr cl-y)))
1011 (and (not (consp cl-x)) (not (consp cl-y)) (cl--check-match cl-x cl-y)))
1014 (run-hooks 'cl-seq-load-hook)
1017 ;; byte-compile-dynamic: t
1018 ;; generated-autoload-file: "cl-loaddefs.el"
1021 ;;; cl-seq.el ends here