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