1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2% 3% File: PNK:SETS.SL 4% Title: Functions acting on lists as sets 5% Author: Eric Benson 6% Created: 12 December 1981 7% Modified: 23-Mar-84 14:58:07 (Brian Beach) 8% Status: Open Source: BSD License 9% Mode: Lisp 10% Package: Kernel 11% Compiletime: 12% Runtime: 13% 14% (c) Copyright 1983, Hewlett-Packard Company, see the file 15% HP_disclaimer at the root of the PSL file tree 16% 17% (c) Copyright 1982, University of Utah 18% 19% Redistribution and use in source and binary forms, with or without 20% modification, are permitted provided that the following conditions are met: 21% 22% * Redistributions of source code must retain the relevant copyright 23% notice, this list of conditions and the following disclaimer. 24% * Redistributions in binary form must reproduce the above copyright 25% notice, this list of conditions and the following disclaimer in the 26% documentation and/or other materials provided with the distribution. 27% 28% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 29% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 30% THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 31% PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNERS OR 32% CONTRIBUTORS 33% BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 34% CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 35% SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 36% INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 37% CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 38% ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 39% POSSIBILITY OF SUCH DAMAGE. 40% 41%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 42% 43% Revisions: 44% 45% 01-Dec-83 15:01:54 (Brian Beach) 46% Translated from Rlisp to Lisp. 47% 48%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 49 50(de list2set (l) 51 % Remove redundant elements from L 52 (cond ((not (pairp l)) nil) 53 ((member (car l) (cdr l)) (list2set (cdr l))) 54 (t (cons (car l) (list2set (cdr l)))))) 55 56(de list2setq (l) 57 % EQ version of List2Set 58 (cond ((not (pairp l)) nil) 59 % Don't confuse it with SetQ! 60 ((memq (car l) (cdr l)) (list2set (cdr l))) 61 (t (cons (car l) (list2set (cdr l)))))) 62 63(de adjoin (element aset) 64 % Add Element to Set 65 (if (member element aset) 66 aset 67 (cons element aset))) 68 69(de adjoinq (element aset) 70 % EQ version of Adjoin 71 (if (memq element aset) 72 aset 73 (cons element aset))) 74 75(de union (x y) 76 % Set union 77 (if (not (pairp x)) 78 y 79 (union (cdr x) (if (member (car x) y) 80 y 81 (cons (car x) y))))) 82 83(de unionq (x y) 84 % EQ version of UNION 85 (if (not (pairp x)) 86 y 87 (unionq (cdr x) (if (memq (car x) y) 88 y 89 (cons (car x) y))))) 90 91(de xn (u v) 92 % Set intersection 93 (cond ((not (pairp u)) nil) 94 ((member (car u) v) (cons (car u) (xn (cdr u) (delete (car u) v)))) 95 (t (xn (cdr u) v)))) 96 97(de xnq (u v) 98 % EQ version of XN 99 (cond ((null (pairp u)) nil) 100 ((memq (car u) v) (cons (car u) (xn (cdr u) (delq (car u) v)))) 101 (t (xn (cdr u) v)))) 102 103(de intersection (u v) 104 (xn u v)) 105 106(de intersectionq (u v) 107 (xnq u v)) 108 109 110