# HG changeset patch # User Ben Wing # Date 1266895382 21600 # Node ID 7d7ae8db0341d8165761dbe6d712ed0045c096f6 # Parent 545ec923b4ebc784c2eddfe496eea025f109f1ef add functions `stable-union' and `stable-intersection' to do stable set operations -------------------- ChangeLog entries follow: -------------------- lisp/ChangeLog addition: 2010-02-22 Ben Wing * cl-seq.el: * cl-seq.el (stable-union): New. * cl-seq.el (stable-intersection): New. New functions to do stable set operations, i.e. preserve the order of the elements in the argument lists, and prefer LIST1 over LIST2 when ordering the combined result. The result looks as much like LIST1 as possible, followed (in the case of `stable-union') by any necessary elements from LIST2, in order. This is contrary to `union' and `intersection', which are not required to be order- preserving and are not -- they prefer LIST2 and output results in backwards order. diff -r 545ec923b4eb -r 7d7ae8db0341 lisp/ChangeLog --- a/lisp/ChangeLog Mon Feb 22 21:17:47 2010 -0600 +++ b/lisp/ChangeLog Mon Feb 22 21:23:02 2010 -0600 @@ -1,3 +1,17 @@ +2010-02-22 Ben Wing + + * cl-seq.el: + * cl-seq.el (stable-union): New. + * cl-seq.el (stable-intersection): New. + New functions to do stable set operations, i.e. preserve the order + of the elements in the argument lists, and prefer LIST1 over LIST2 + when ordering the combined result. The result looks as much like + LIST1 as possible, followed (in the case of `stable-union') by + any necessary elements from LIST2, in order. This is contrary to + `union' and `intersection', which are not required to be order- + preserving and are not -- they prefer LIST2 and output results in + backwards order. + 2010-02-22 Ben Wing * cl-seq.el: diff -r 545ec923b4eb -r 7d7ae8db0341 lisp/cl-seq.el --- a/lisp/cl-seq.el Mon Feb 22 21:17:47 2010 -0600 +++ b/lisp/cl-seq.el Mon Feb 22 21:23:02 2010 -0600 @@ -850,6 +850,40 @@ (cond ((null cl-list1) cl-list2) ((null cl-list2) cl-list1) (t (apply 'union cl-list1 cl-list2 cl-keys)))) +;; XEmacs addition: NOT IN COMMON LISP. +(defun stable-union (cl-list1 cl-list2 &rest cl-keys) + "Stably combine LIST1 and LIST2 using a set-union operation. +The result list contains all items that appear in either LIST1 or LIST2. +The result is \"stable\" in that it preserves the ordering of elements in +LIST1 and LIST2. The result specifically consists of the elements in LIST1 +in order, followed by any elements in LIST2 that are not also in LIST1, in +the order given in LIST2. +This is a non-destructive function; it makes a copy of the data if necessary +to avoid corrupting the original LIST1 and LIST2. +Keywords supported: :test :test-not :key +See `union' for the meaning of :test, :test-not and :key. + +NOTE: This is *NOT* a function defined by Common Lisp, but an XEmacs +extension." + ;; The standard `union' doesn't produce a "stable" union -- + ;; it iterates over the second list instead of the first one, and returns + ;; the values in backwards order. According to the CLTL2 documentation, + ;; `union' is not required to preserve the ordering of elements in + ;; any fashion, so we add a new function rather than changing the + ;; semantics of `union'. + (cond ((null cl-list1) cl-list2) ((null cl-list2) cl-list1) + ((equal cl-list1 cl-list2) cl-list1) + (t + (append + cl-list1 + (cl-parsing-keywords (:key) (:test :test-not) + (loop for cl-l in cl-list2 + if (not (if (or cl-keys (numberp cl-l)) + (apply 'member* (cl-check-key cl-l) + cl-list1 cl-keys) + (memq cl-l cl-list1))) + collect cl-l)))))) + (defun intersection (cl-list1 cl-list2 &rest cl-keys) "Combine LIST1 and LIST2 using a set-intersection operation. The result list contains all items that appear in both LIST1 and LIST2. @@ -881,6 +915,35 @@ See `union' for the meaning of :test, :test-not and :key." (and cl-list1 cl-list2 (apply 'intersection cl-list1 cl-list2 cl-keys))) +;; XEmacs addition: NOT IN COMMON LISP. +(defun stable-intersection (cl-list1 cl-list2 &rest cl-keys) + "Stably combine LIST1 and LIST2 using a set-intersection operation. +The result list contains all items that appear in both LIST1 and LIST2. +The result is \"stable\" in that it preserves the ordering of elements in +LIST1 that are also in LIST2. +This is a non-destructive function; it makes a copy of the data if necessary +to avoid corrupting the original LIST1 and LIST2. +Keywords supported: :test :test-not :key +See `union' for the meaning of :test, :test-not and :key. + +NOTE: This is *NOT* a function defined by Common Lisp, but an XEmacs +extension." + ;; The standard `intersection' doesn't produce a "stable" intersection -- + ;; it iterates over the second list instead of the first one, and returns + ;; the values in backwards order. According to the CLTL2 documentation, + ;; `intersection' is not required to preserve the ordering of elements in + ;; any fashion, so we add a new function rather than changing the + ;; semantics of `intersection'. + (and cl-list1 cl-list2 + (if (equal cl-list1 cl-list2) cl-list1 + (cl-parsing-keywords (:key) (:test :test-not) + (loop for cl-l in cl-list1 + if (if (or cl-keys (numberp cl-l)) + (apply 'member* (cl-check-key cl-l) + cl-list2 cl-keys) + (memq cl-l cl-list2)) + collect cl-l))))) + (defun set-difference (cl-list1 cl-list2 &rest cl-keys) "Combine LIST1 and LIST2 using a set-difference operation. The result list contains all items that appear in LIST1 but not LIST2.