lisp/emacs-lisp/cl-seq.el

   1 ;;; cl-seq.el --- Common Lisp features, part 3  -*- lexical-binding: t -*-
   2
   3 ;; Copyright (C) 1993, 2001-2014 Free Software Foundation, Inc.
   4
   5 ;; Author: Dave Gillespie <daveg@synaptics.com>
   6 ;; Old-Version: 2.02
   7 ;; Keywords: extensions
   8 ;; Package: emacs
   9
  10 ;; This file is part of GNU Emacs.
  11
  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.
  16
  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.
  21
  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/>.
  24
  25 ;;; Commentary:
  26
  27 ;; These are extensions to Emacs Lisp that provide a degree of
  28 ;; Common Lisp compatibility, beyond what is already built-in
  29 ;; in Emacs Lisp.
  30 ;;
  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.
  33 ;;
  34 ;; Bug reports, comments, and suggestions are welcome!
  35
  36 ;; This file contains the Common Lisp sequence and list functions
  37 ;; which take keyword arguments.
  38
  39 ;; See cl.el for Change Log.
  40
  41
  42 ;;; Code:
  43
  44 (require 'cl-lib)
  45
  46 ;; Keyword parsing.
  47 ;; This is special-cased here so that we can compile
  48 ;; this file independent from cl-macs.
  49
  50 (defmacro cl--parsing-keywords (kwords other-keys &rest body)
  51   (declare (indent 2) (debug (sexp sexp &rest form)))
  52   `(let* ,(mapcar
  53            (lambda (x)
  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)))
  58                (if (eq var :if-not)
  59                    (setq mem `(and ,mem (setq cl-if ,mem) t)))
  60                (list (intern
  61                       (format "cl-%s" (substring (symbol-name var) 1)))
  62                      (if (consp x) `(or ,mem ,(car (cdr x))) mem))))
  63            kwords)
  64      ,@(append
  65         (and (not (eq other-keys t))
  66              (list
  67               (list 'let '((cl-keys-temp cl-keys))
  68                     (list 'while 'cl-keys-temp
  69                           (list 'or (list 'memq '(car cl-keys-temp)
  70                                           (list 'quote
  71                                                 (mapcar
  72                                                  (function
  73                                                   (lambda (x)
  74                                                     (if (consp x)
  75                                                         (car x) x)))
  76                                                  (append kwords
  77                                                          other-keys))))
  78                                 '(car (cdr (memq (quote :allow-other-keys)
  79                                                  cl-keys)))
  80                                 '(error "Bad keyword argument %s"
  81                                         (car cl-keys-temp)))
  82                           '(setq cl-keys-temp (cdr (cdr cl-keys-temp)))))))
  83         body)))
  84
  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))
  88
  89 (defmacro cl--check-test-nokey (item x) ;cl-test cl-if cl-test-not cl-if-not.
  90   (declare (debug edebug-forms))
  91   `(cond
  92     (cl-test (eq (not (funcall cl-test ,item ,x))
  93                  cl-test-not))
  94     (cl-if (eq (not (funcall cl-if ,x)) cl-if-not))
  95     (t (eql ,item ,x))))
  96
  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)))
 100
 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))
 104   `(if cl-test
 105        (eq (not (funcall cl-test ,x ,y)) cl-test-not)
 106      (eql ,x ,y)))
 107
 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)
 113 (defvar cl-key)
 114
 115 ;;;###autoload
 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)))))
 127       (if cl-from-end
 128           (while cl-seq
 129             (setq cl-accum (funcall cl-func (cl--check-key (pop cl-seq))
 130                                     cl-accum)))
 131         (while cl-seq
 132           (setq cl-accum (funcall cl-func cl-accum
 133                                   (cl--check-key (pop cl-seq))))))
 134       cl-accum)))
 135
 136 ;;;###autoload
 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) ()
 142     (if (listp seq)
 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))
 146             (setcar p item)
 147             (setq p (cdr p))))
 148       (or cl-end (setq cl-end (length seq)))
 149       (if (and (= cl-start 0) (= cl-end (length seq)))
 150           (fillarray seq item)
 151         (while (< cl-start cl-end)
 152           (aset seq cl-start item)
 153           (setq cl-start (1+ cl-start)))))
 154     seq))
 155
 156 ;;;###autoload
 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))))))
 171       (if (listp cl-seq1)
 172           (let ((cl-p1 (nthcdr cl-start1 cl-seq1))
 173                 (cl-n1 (if cl-end1 (- cl-end1 cl-start1) 4000000)))
 174             (if (listp cl-seq2)
 175                 (let ((cl-p2 (nthcdr cl-start2 cl-seq2))
 176                       (cl-n (min cl-n1
 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))
 188                                            cl-start2))))
 189         (if (listp 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))))))
 197     cl-seq1))
 198
 199 ;;;###autoload
 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
 207                         (:start 0) :end) ()
 208     (if (<= (or cl-count (setq cl-count 8000000)) 0)
 209         cl-seq
 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
 212                                     cl-from-end)))
 213             (if cl-i
 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))
 217                                                (list :start cl-i))
 218                                              cl-keys))))
 219                   (if (listp cl-seq) cl-res
 220                     (if (stringp cl-seq) (concat cl-res) (vconcat cl-res))))
 221               cl-seq))
 222         (setq cl-end (- (or cl-end 8000000) cl-start))
 223         (if (= cl-start 0)
 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)
 237                            (and (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))))
 242                 cl-seq))
 243           cl-seq)))))
 244
 245 ;;;###autoload
 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))
 253
 254 ;;;###autoload
 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))
 262
 263 ;;;###autoload
 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
 270                         (:start 0) :end) ()
 271     (if (<= (or cl-count (setq cl-count 8000000)) 0)
 272         cl-seq
 273       (if (listp cl-seq)
 274           (if (and cl-from-end (< cl-count 4000000))
 275               (let (cl-i)
 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)))))
 282                   (setq cl-end cl-i))
 283                 cl-seq)
 284             (setq cl-end (- (or cl-end 8000000) cl-start))
 285             (if (= cl-start 0)
 286                 (progn
 287                   (while (and cl-seq
 288                               (> cl-end 0)
 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)))
 298                         (progn
 299                           (setcdr cl-p (cdr (cdr cl-p)))
 300                           (if (= (setq cl-count (1- cl-count)) 0)
 301                               (setq cl-end 1)))
 302                       (setq cl-p (cdr cl-p)))
 303                     (setq cl-end (1- cl-end)))))
 304             cl-seq)
 305         (apply 'cl-remove cl-item cl-seq cl-keys)))))
 306
 307 ;;;###autoload
 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))
 314
 315 ;;;###autoload
 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))
 322
 323 ;;;###autoload
 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))
 329
 330 ;;;###autoload
 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))
 336
 337 (defun cl--delete-duplicates (cl-seq cl-keys cl-copy)
 338   (if (listp cl-seq)
 339       (cl--parsing-keywords
 340           (:test :test-not :key (:start 0) :end :from-end :if)
 341           ()
 342         (if cl-from-end
 343             (let ((cl-p (nthcdr cl-start cl-seq)) cl-i)
 344               (setq cl-end (- (or cl-end (length cl-seq)) cl-start))
 345               (while (> cl-end 1)
 346                 (setq cl-i 0)
 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)))
 356               cl-seq)
 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))
 367                   (progn
 368                     (if cl-copy (setq cl-seq (copy-sequence cl-seq)
 369                                       cl-p (nthcdr (1- cl-start) cl-seq)
 370                                       cl-copy nil))
 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)))
 374             cl-seq)))
 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)))))
 377
 378 ;;;###autoload
 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))
 389         cl-seq
 390       (let ((cl-i (cl--position cl-old cl-seq cl-start cl-end)))
 391         (if (not cl-i)
 392             cl-seq
 393           (setq cl-seq (copy-sequence cl-seq))
 394           (or cl-from-end
 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))))))
 399
 400 ;;;###autoload
 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))
 408
 409 ;;;###autoload
 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))
 417
 418 ;;;###autoload
 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))
 432                     (progn
 433                       (setcar cl-p cl-new)
 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)))
 437           (if cl-from-end
 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))
 441                     (progn
 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))
 446                   (progn
 447                     (aset cl-seq cl-start cl-new)
 448                     (setq cl-count (1- cl-count))))
 449               (setq cl-start (1+ cl-start))))))
 450     cl-seq))
 451
 452 ;;;###autoload
 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))
 459
 460 ;;;###autoload
 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))
 467
 468 ;;;###autoload
 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))))
 476
 477 ;;;###autoload
 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))
 484
 485 ;;;###autoload
 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))
 492
 493 ;;;###autoload
 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)))
 502
 503 (defun cl--position (cl-item cl-seq cl-start &optional cl-end cl-from-end)
 504   (if (listp cl-seq)
 505       (let ((cl-p (nthcdr cl-start cl-seq)))
 506         (or cl-end (setq cl-end 8000000))
 507         (let ((cl-res nil))
 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)))
 512           cl-res))
 513     (or cl-end (setq cl-end (length cl-seq)))
 514     (if cl-from-end
 515         (progn
 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))))
 523
 524 ;;;###autoload
 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))
 531
 532 ;;;###autoload
 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))
 539
 540 ;;;###autoload
 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)))
 553       cl-count)))
 554
 555 ;;;###autoload
 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))
 561
 562 ;;;###autoload
 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))
 568
 569 ;;;###autoload
 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)))
 580     (if cl-from-end
 581         (progn
 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))
 587                (1- cl-end1)))
 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))
 598              cl-start1)))))
 599
 600 ;;;###autoload
 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)))
 615              (cl-if nil) cl-pos)
 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)))))
 626
 627 ;;;###autoload
 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]...)"
 633   (if (nlistp cl-seq)
 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)))))))))
 641
 642 ;;;###autoload
 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))
 649
 650 ;;;###autoload
 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) ()
 660     (let ((cl-res nil))
 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))))
 667
 668 ;;;###autoload
 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))
 675   (if cl-keys
 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)))
 679         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")
 684
 685 ;;;###autoload
 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))
 692
 693 ;;;###autoload
 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))
 700
 701 ;;;###autoload
 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))
 705       cl-list
 706     (cons cl-item cl-list)))
 707
 708 ;;;###autoload
 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))
 714   (if cl-keys
 715       (cl--parsing-keywords (:test :test-not :key :if :if-not) ()
 716         (while (and cl-alist
 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")
 725
 726 ;;;###autoload
 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))
 732
 733 ;;;###autoload
 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))
 739
 740 ;;;###autoload
 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) ()
 747         (while (and cl-alist
 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)))
 753
 754 ;;;###autoload
 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))
 760
 761 ;;;###autoload
 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))
 767
 768 ;;;###autoload
 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)
 778         (t
 779          (or (>= (length cl-list1) (length cl-list2))
 780              (setq cl-list1 (prog1 cl-list2 (setq cl-list2 cl-list1))))
 781          (while cl-list2
 782            (if (or cl-keys (numberp (car cl-list2)))
 783                (setq cl-list1
 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)))
 787            (pop cl-list2))
 788          cl-list1)))
 789
 790 ;;;###autoload
 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
 795 whenever possible.
 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))))
 800
 801 ;;;###autoload
 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)
 812            (let ((cl-res nil))
 813              (or (>= (length cl-list1) (length cl-list2))
 814                  (setq cl-list1 (prog1 cl-list2 (setq cl-list2 cl-list1))))
 815              (while cl-list2
 816                (if (if (or cl-keys (numberp (car cl-list2)))
 817                        (apply 'cl-member (cl--check-key (car cl-list2))
 818                               cl-list1 cl-keys)
 819                      (memq (car cl-list2) cl-list1))
 820                    (push (car cl-list2) cl-res))
 821                (pop cl-list2))
 822              cl-res)))))
 823
 824 ;;;###autoload
 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
 829 whenever possible.
 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)))
 833
 834 ;;;###autoload
 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)
 844       (let ((cl-res nil))
 845         (while cl-list1
 846           (or (if (or cl-keys (numberp (car cl-list1)))
 847                   (apply 'cl-member (cl--check-key (car cl-list1))
 848                          cl-list2 cl-keys)
 849                 (memq (car cl-list1) cl-list2))
 850               (push (car cl-list1) cl-res))
 851           (pop cl-list1))
 852         cl-res))))
 853
 854 ;;;###autoload
 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
 859 whenever possible.
 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)))
 864
 865 ;;;###autoload
 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)))))
 877
 878 ;;;###autoload
 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
 883 whenever possible.
 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)))))
 890
 891 ;;;###autoload
 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)
 900              (while (and cl-list1
 901                          (apply 'cl-member (cl--check-key (car cl-list1))
 902                                 cl-list2 cl-keys))
 903                (pop cl-list1))
 904              (null cl-list1)))))
 905
 906 ;;;###autoload
 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))
 913
 914 ;;;###autoload
 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))
 921
 922 ;;;###autoload
 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
 926 to `setcar').
 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))
 930
 931 ;;;###autoload
 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))
 938
 939 ;;;###autoload
 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))
 946
 947 (defvar cl--alist)
 948
 949 ;;;###autoload
 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))))
 958
 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))
 964       (if (consp cl-tree)
 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)))
 968                 cl-tree
 969               (cons cl-a cl-d)))
 970         cl-tree))))
 971
 972 ;;;###autoload
 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)
 982       (car cl-hold))))
 983
 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)))
 994       (if cl-p
 995           (progn (setcdr cl-tree (cdr (car cl-p))) (setq cl-tree nil))
 996         (setq cl-tree (cdr cl-tree))))))
 997
 998 ;;;###autoload
 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)))
1006
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)))
1012
1013
1014 (run-hooks 'cl-seq-load-hook)
1015
1016 ;; Local variables:
1017 ;; byte-compile-dynamic: t
1018 ;; generated-autoload-file: "cl-loaddefs.el"
1019 ;; End:
1020
1021 ;;; cl-seq.el ends here