X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Flist.lisp;h=55f66c9f3302904abdc725cccf30b28677c0e95f;hb=416152f084604094445a758ff399871132dff2bd;hp=f72c47424bb79aedd9e143e02e20ffd9d811803e;hpb=a530bbe337109d898d5b4a001fc8f1afa3b5dc39;p=sbcl.git diff --git a/src/code/list.lisp b/src/code/list.lisp index f72c474..55f66c9 100644 --- a/src/code/list.lisp +++ b/src/code/list.lisp @@ -11,19 +11,15 @@ (in-package "SB!IMPL") -(file-comment - "$Header$") - ;;;; KLUDGE: comment from CMU CL, what does it mean? ;;;; NSUBLIS, things at the beginning broken. ;;;; -- WHN 20000127 (declaim (maybe-inline - tree-equal list-length nth %setnth nthcdr last make-list append - copy-list copy-alist copy-tree revappend nconc nreconc butlast - nbutlast ldiff member member-if member-if-not tailp adjoin union + tree-equal nth %setnth nthcdr last make-list append + nconc member member-if member-if-not tailp adjoin union nunion intersection nintersection set-difference nset-difference - set-exclusive-or nset-exclusive-or subsetp acons pairlis assoc + set-exclusive-or nset-exclusive-or subsetp acons assoc assoc-if assoc-if-not rassoc rassoc-if rassoc-if-not subst subst-if subst-if-not nsubst nsubst-if nsubst-if-not sublis nsublis)) @@ -293,13 +289,12 @@ ;;; list copying functions -;;; The list is copied correctly even if the list is not terminated by () -;;; The new list is built by cdr'ing splice which is always at the tail -;;; of the new list - (defun copy-list (list) #!+sb-doc - "Returns a new list EQUAL but not EQ to list" + "Returns a new list which is EQUAL to LIST." + ;; The list is copied correctly even if the list is not terminated + ;; by NIL. The new list is built by CDR'ing SPLICE which is always + ;; at the tail of the new list. (if (atom list) list (let ((result (list (car list)))) @@ -313,7 +308,7 @@ (defun copy-alist (alist) #!+sb-doc - "Returns a new association list equal to alist, constructed in space" + "Returns a new association list which is EQUAL to ALIST." (if (atom alist) alist (let ((result @@ -351,16 +346,17 @@ (result y (cons (car top) result))) ((endp top) result))) -;;; NCONC finds the first non-null list, so it can make splice point to a cons. -;;; After finding the first cons element, it holds it in a result variable -;;; while running down successive elements tacking them together. While -;;; tacking lists together, if we encounter a null list, we set the previous -;;; list's last cdr to nil just in case it wasn't already nil, and it could -;;; have been dotted while the null list was the last argument to NCONC. The -;;; manipulation of splice (that is starting it out on a first cons, setting -;;; LAST of splice, and setting splice to ele) inherently handles (nconc x x), -;;; and it avoids running down the last argument to NCONC which allows the last -;;; argument to be circular. +;;; NCONC finds the first non-null list, so it can make splice point +;;; to a cons. After finding the first cons element, it holds it in a +;;; result variable while running down successive elements tacking +;;; them together. While tacking lists together, if we encounter a +;;; null list, we set the previous list's last cdr to nil just in case +;;; it wasn't already nil, and it could have been dotted while the +;;; null list was the last argument to NCONC. The manipulation of +;;; splice (that is starting it out on a first cons, setting LAST of +;;; splice, and setting splice to ele) inherently handles (nconc x x), +;;; and it avoids running down the last argument to NCONC which allows +;;; the last argument to be circular. (defun nconc (&rest lists) #!+sb-doc "Concatenates the lists given as arguments (by changing them)" @@ -399,45 +395,40 @@ ((atom 2nd) 3rd) (rplacd 2nd 3rd))) -(defun butlast (list &optional (n 1)) - #!+sb-doc - "Return a new list the same as LIST without the last N conses. - List must not be circular." - (declare (list list) (type index n)) - (let ((length (do ((list list (cdr list)) - (i 0 (1+ i))) - ((atom list) (1- i))))) - (declare (type index length)) - (unless (< length n) - (do* ((top (cdr list) (cdr top)) - (result (list (car list))) - (splice result) - (count length (1- count))) - ((= count n) result) - (declare (type index count)) - (setq splice (cdr (rplacd splice (list (car top))))))))) - -(defun nbutlast (list &optional (n 1)) - #!+sb-doc - "Modifies List to remove the last N conses. List must not be circular." - (declare (list list) (type index n)) - (let ((length (do ((list list (cdr list)) - (i 0 (1+ i))) - ((atom list) (1- i))))) - (declare (type index length)) - (unless (< length n) - (do ((1st (cdr list) (cdr 1st)) - (2nd list 1st) - (count length (1- count))) - ((= count n) - (rplacd 2nd ()) - list) - (declare (type index count)))))) +(flet (;; Return the number of conses at the head of the + ;; possibly-improper list LIST. (Or if LIST is circular, you + ;; lose.) + (count-conses (list) + (do ((in-list list (cdr in-list)) + (result 0 (1+ result))) + ((atom in-list) + result) + (declare (type index result))))) + (declare (ftype (function (t) index) count-conses)) + (defun butlast (list &optional (n 1)) + (let* ((n-conses-in-list (count-conses list)) + (n-remaining-to-copy (- n-conses-in-list n))) + (declare (type fixnum n-remaining-to-copy)) + (when (plusp n-remaining-to-copy) + (do* ((result (list (first list))) + (rest (rest list) (rest rest)) + (splice result)) + ((zerop (decf n-remaining-to-copy)) + result) + (setf splice + (setf (cdr splice) + (list (first rest)))))))) + (defun nbutlast (list &optional (n 1)) + (let ((n-conses-in-list (count-conses list))) + (unless (< n-conses-in-list n) + (setf (cdr (nthcdr (- n-conses-in-list n 1) list)) + nil) + list)))) (defun ldiff (list object) - "Returns a new list, whose elements are those of List that appear before - Object. If Object is not a tail of List, a copy of List is returned. - List must be a proper list or a dotted list." + "Return a new list, whose elements are those of LIST that appear before + OBJECT. If OBJECT is not a tail of LIST, a copy of LIST is returned. + LIST must be a proper list or a dotted list." (do* ((list list (cdr list)) (result (list ())) (splice result)) @@ -449,16 +440,16 @@ (return (cdr result)) (setq splice (cdr (rplacd splice (list (car list)))))))) -;;; Functions to alter list structure +;;;; functions to alter list structure (defun rplaca (x y) #!+sb-doc - "Changes the car of x to y and returns the new x." + "Change the CAR of X to Y and return the new X." (rplaca x y)) (defun rplacd (x y) #!+sb-doc - "Changes the cdr of x to y and returns the new x." + "Change the CDR of X to Y and return the new X." (rplacd x y)) ;;; The following are for use by SETF. @@ -467,10 +458,9 @@ (defun %rplacd (x val) (rplacd x val) val) +;;; Set the Nth element of LIST to NEWVAL. (defun %setnth (n list newval) (declare (type index n)) - #!+sb-doc - "Sets the Nth element of List (zero based) to Newval." (do ((count n (1- count)) (list list (cdr list))) ((endp list) @@ -492,48 +482,37 @@ (defun identity (thing) #!+sb-doc - "Returns what was passed to it." + "This function simply returns what was passed to it." thing) (defun complement (function) #!+sb-doc - "Builds a new function that returns T whenever FUNCTION returns NIL and - NIL whenever FUNCTION returns T." - #'(lambda (&optional (arg0 nil arg0-p) (arg1 nil arg1-p) (arg2 nil arg2-p) - &rest more-args) - (not (cond (more-args (apply function arg0 arg1 arg2 more-args)) - (arg2-p (funcall function arg0 arg1 arg2)) - (arg1-p (funcall function arg0 arg1)) - (arg0-p (funcall function arg0)) - (t (funcall function)))))) - -(defun constantly (value &optional (val1 nil val1-p) (val2 nil val2-p) - &rest more-values) - #!+sb-doc - "Builds a function that always returns VALUE, and posisbly MORE-VALUES." - (cond (more-values - (let ((list (list* value val1 val2 more-values))) - #'(lambda () - (declare (optimize-interface (speed 3) (safety 0))) - (values-list list)))) - (val2-p - #'(lambda () - (declare (optimize-interface (speed 3) (safety 0))) - (values value val1 val2))) - (val1-p - #'(lambda () - (declare (optimize-interface (speed 3) (safety 0))) - (values value val1))) - (t - #'(lambda () - (declare (optimize-interface (speed 3) (safety 0))) - value)))) + "Return a new function that returns T whenever FUNCTION returns NIL and + NIL whenever FUNCTION returns non-NIL." + (lambda (&optional (arg0 nil arg0-p) (arg1 nil arg1-p) (arg2 nil arg2-p) + &rest more-args) + (not (cond (more-args (apply function arg0 arg1 arg2 more-args)) + (arg2-p (funcall function arg0 arg1 arg2)) + (arg1-p (funcall function arg0 arg1)) + (arg0-p (funcall function arg0)) + (t (funcall function)))))) + +(defun constantly (value) + #!+sb-doc + "Return a function that always returns VALUE." + (lambda () + ;; KLUDGE: This declaration is a hack to make the closure ignore + ;; all its arguments without consing a &REST list or anything. + ;; Perhaps once DYNAMIC-EXTENT is implemented we won't need to + ;; screw around with this kind of thing. -- WHN 2001-04-06 + (declare (optimize (speed 3) (safety 0))) + value)) -;;;; macros for (&key (key #'identity) (test #'eql testp) (test-not nil notp)). +;;;; macros for (&KEY (KEY #'IDENTITY) (TEST #'EQL TESTP) (TEST-NOT NIL NOTP)) -;;; Use these with the following keyword args: +;;; Use these with the following &KEY args: (defmacro with-set-keys (funcall) - `(cond ((and testp notp) (error "Test and test-not both supplied.")) + `(cond ((and testp notp) (error ":TEST and :TEST-NOT were both supplied.")) (notp ,(append funcall '(:key key :test-not test-not))) (t ,(append funcall '(:key key :test test))))) @@ -692,7 +671,7 @@ (defun member (item list &key key (test #'eql testp) (test-not nil notp)) #!+sb-doc "Returns tail of list beginning with first element satisfying EQLity, - :test, or :test-not with a given item." + :TEST, or :TEST-NOT with a given item." (do ((list list (cdr list))) ((null list) nil) (let ((car (car list))) @@ -701,7 +680,7 @@ (defun member-if (test list &key key) #!+sb-doc - "Returns tail of list beginning with first element satisfying test(element)" + "Return tail of LIST beginning with first element satisfying TEST." (do ((list list (Cdr list))) ((endp list) nil) (if (funcall test (apply-key key (car list))) @@ -709,7 +688,7 @@ (defun member-if-not (test list &key key) #!+sb-doc - "Returns tail of list beginning with first element not satisfying test(el)" + "Return tail of LIST beginning with first element not satisfying TEST." (do ((list list (cdr list))) ((endp list) ()) (if (not (funcall test (apply-key key (car list)))) @@ -717,8 +696,8 @@ (defun tailp (object list) #!+sb-doc - "Returns true if Object is the same as some tail of List, otherwise - returns false. List must be a proper list or a dotted list." + "Return true if OBJECT is the same as some tail of LIST, otherwise + returns false. LIST must be a proper list or a dotted list." (do ((list list (cdr list))) ((atom list) (eql list object)) (if (eql object list) @@ -726,7 +705,7 @@ (defun adjoin (item list &key key (test #'eql) (test-not nil notp)) #!+sb-doc - "Add item to list unless it is already a member" + "Add ITEM to LIST unless it is already a member" (declare (inline member)) (if (let ((key-val (apply-key key item))) (if notp @@ -741,7 +720,7 @@ ;;; order. (defun union (list1 list2 &key key (test #'eql testp) (test-not nil notp)) #!+sb-doc - "Returns the union of list1 and list2." + "Return the union of LIST1 and LIST2." (declare (inline member)) (when (and testp notp) (error "Test and test-not both supplied.")) (let ((res list2)) @@ -750,8 +729,8 @@ (push elt res))) res)) -;;; Destination and source are setf-able and many-evaluable. Sets the source -;;; to the cdr, and "conses" the 1st elt of source to destination. +;;; Destination and source are SETF-able and many-evaluable. Set the +;;; SOURCE to the CDR, and "cons" the 1st elt of source to DESTINATION. ;;; ;;; FIXME: needs a more mnemonic name (defmacro steve-splice (source destination) @@ -762,10 +741,10 @@ (defun nunion (list1 list2 &key key (test #'eql testp) (test-not nil notp)) #!+sb-doc - "Destructively returns the union list1 and list2." + "Destructively return the union of LIST1 and LIST2." (declare (inline member)) (if (and testp notp) - (error "Test and test-not both supplied.")) + (error ":TEST and :TEST-NOT were both supplied.")) (let ((res list2) (list1 list1)) (do () @@ -778,7 +757,7 @@ (defun intersection (list1 list2 &key key (test #'eql testp) (test-not nil notp)) #!+sb-doc - "Returns the intersection of list1 and list2." + "Return the intersection of LIST1 and LIST2." (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) @@ -791,7 +770,7 @@ (defun nintersection (list1 list2 &key key (test #'eql testp) (test-not nil notp)) #!+sb-doc - "Destructively returns the intersection of list1 and list2." + "Destructively return the intersection of LIST1 and LIST2." (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) @@ -806,7 +785,7 @@ (defun set-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp)) #!+sb-doc - "Returns the elements of list1 which are not in list2." + "Return the elements of LIST1 which are not in LIST2." (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) @@ -821,7 +800,7 @@ (defun nset-difference (list1 list2 &key key (test #'eql testp) (test-not nil notp)) #!+sb-doc - "Destructively returns the elements of list1 which are not in list2." + "Destructively return the elements of LIST1 which are not in LIST2." (declare (inline member)) (if (and testp notp) (error "Test and test-not both supplied.")) @@ -836,7 +815,7 @@ (defun set-exclusive-or (list1 list2 &key key (test #'eql testp) (test-not nil notp)) #!+sb-doc - "Returns new list of elements appearing exactly once in list1 and list2." + "Return new list of elements appearing exactly once in LIST1 and LIST2." (declare (inline member)) (let ((result nil)) (dolist (elt list1) @@ -847,18 +826,17 @@ (setq result (cons elt result)))) result)) -;;; The outer loop examines list1 while the inner loop examines list2. If an -;;; element is found in list2 "equal" to the element in list1, both are -;;; spliced out. When the end of list1 is reached, what is left of list2 is -;;; tacked onto what is left of list1. The splicing operation ensures that -;;; the correct operation is performed depending on whether splice is at the -;;; top of the list or not - +;;; The outer loop examines list1 while the inner loop examines list2. +;;; If an element is found in list2 "equal" to the element in list1, +;;; both are spliced out. When the end of list1 is reached, what is +;;; left of list2 is tacked onto what is left of list1. The splicing +;;; operation ensures that the correct operation is performed +;;; depending on whether splice is at the top of the list or not (defun nset-exclusive-or (list1 list2 &key (test #'eql) (test-not nil notp) key) #!+sb-doc - "Destructively return a list with elements which appear but once in list1 - and list2." + "Destructively return a list with elements which appear but once in LIST1 + and LIST2." (do ((list1 list1) (list2 list2) (x list1 (cdr x)) @@ -887,7 +865,7 @@ (defun subsetp (list1 list2 &key key (test #'eql testp) (test-not nil notp)) #!+sb-doc - "Returns T if every element in list1 is also in list2." + "Return T if every element in LIST1 is also in LIST2." (declare (inline member)) (dolist (elt list1) (unless (with-set-keys (member (apply-key key elt) list2)) @@ -898,12 +876,12 @@ (defun acons (key datum alist) #!+sb-doc - "Construct a new alist by adding the pair (key . datum) to alist" + "Construct a new alist by adding the pair (KEY . DATUM) to ALIST." (cons (cons key datum) alist)) (defun pairlis (keys data &optional (alist '())) #!+sb-doc - "Construct an association list from keys and data (adding to alist)" + "Construct an association list from KEYS and DATA (adding to ALIST)." (do ((x keys (cdr x)) (y data (cdr y))) ((and (endp x) (endp y)) alist) @@ -950,8 +928,8 @@ (defun assoc-if-not (predicate alist &key key) #!+sb-doc - "Returns the first cons in alist whose car does not satisfiy the Predicate. - If key is supplied, apply it to the car of each cons before testing." + "Returns the first cons in ALIST whose car does not satisfy the PREDICATE. + If KEY is supplied, apply it to the car of each cons before testing." (if key (assoc-guts (not (funcall predicate (funcall key (caar alist))))) (assoc-guts (not (funcall predicate (caar alist)))))) @@ -959,8 +937,8 @@ (defun rassoc (item alist &key key test test-not) (declare (list alist)) #!+sb-doc - "Returns the cons in alist whose cdr is equal (by a given test or EQL) to - the Item." + "Returns the cons in ALIST whose cdr is equal (by a given test or EQL) to + the ITEM." (cond (test (if key (assoc-guts (funcall test item (funcall key (cdar alist))))