lib: deprecate set-diff; extend set operations.

* eval.c (eval_init): Register set-diff under two
names: set-diff and diff. Register new isec and uni
intrinsics.

* lib.c (isec, uni): New functions.

* lib.h (isec, uni): Declared.

* txr.1: Documented new uni and isec functions, new diff
function name, and the deprecation of set-diff and its order
guarantee w.r.t the left sequence.

4 files changed, 164 insertions, 20 deletions

diff --git a/eval.c b/eval.c
index 058c7c09..fbef1b81 100644
--- a/eval.c
+++ b/eval.c
@@ -5435,6 +5435,7 @@ void eval_init(void)
   val not_null_f = func_n1(not_null);
   val me_each_f = func_n2(me_each);
   val me_for_f = func_n2(me_for);
+  val diff_f = func_n4o(set_diff, 2);
 
   protect(&top_vb, &top_fb, &top_mb, &top_smb, &special, &builtin, &dyn_env,
           &op_table, &pm_table, &last_form_evaled, &last_form_expanded,
@@ -6148,7 +6149,10 @@ void eval_init(void)
   reg_fun(intern(lit("find-max"), user_package), func_n3o(find_max, 1));
   reg_fun(intern(lit("find-min"), user_package), func_n3o(find_min, 1));
   reg_fun(intern(lit("multi-sort"), user_package), func_n3o(multi_sort, 2));
-  reg_fun(intern(lit("set-diff"), user_package), func_n4o(set_diff, 2));
+  reg_fun(intern(lit("set-diff"), user_package), diff_f);
+  reg_fun(intern(lit("diff"), user_package), diff_f);
+  reg_fun(intern(lit("isec"), user_package), func_n4o(isec, 2));
+  reg_fun(intern(lit("uni"), user_package), func_n4o(uni, 2));
 
   reg_fun(intern(lit("seqp"), user_package), func_n1(seqp));
   reg_fun(intern(lit("length"), user_package), func_n1(length));
diff --git a/lib.c b/lib.c
index 9e0dc3f5..b8a165f5 100644
--- a/lib.c
+++ b/lib.c
@@ -9285,6 +9285,65 @@ val set_diff(val list1, val list2, val testfun, val keyfun)
   return make_like(out, list_orig);
 }
 
+val isec(val list1, val list2, val testfun, val keyfun)
+{
+  list_collect_decl (out, ptail);
+  val list_orig = list1;
+
+  list1 = nullify(list1);
+  list2 = nullify(list2);
+
+  testfun = default_arg(testfun, equal_f);
+  keyfun = default_arg(keyfun, identity_f);
+
+  for (; list1; list1 = cdr(list1)) {
+    /* optimization: list2 is a tail of list1, and so we
+       are done, unless the application has a weird test function. */
+    if (list1 == list2) {
+      ptail = list_collect_append(ptail, list1);
+      break;
+    } else {
+      val item = car(list1);
+      val list1_key = funcall1(keyfun, item);
+
+      if (member(list1_key, list2, testfun, keyfun))
+        ptail = list_collect(ptail, item);
+    }
+  }
+
+  return make_like(out, list_orig);
+}
+
+val uni(val list1, val list2, val testfun, val keyfun)
+{
+  list_collect_decl (out, ptail);
+  val list_orig = list1;
+
+  list1 = nullify(list1);
+  list2 = nullify(list2);
+
+  testfun = default_arg(testfun, equal_f);
+  keyfun = default_arg(keyfun, identity_f);
+
+  ptail = list_collect_append(ptail, list1);
+
+  for (; list2; list2 = cdr(list2)) {
+    /* optimization: list2 is a tail of list1, and so we
+       are done, unless the application has a weird test function. */
+    if (list1 == list2) {
+      break;
+    } else {
+      val item = car(list2);
+      val list2_key = funcall1(keyfun, item);
+
+      if (!member(list2_key, list1, testfun, keyfun))
+        ptail = list_collect(ptail, item);
+    }
+  }
+
+  return make_like(out, list_orig);
+}
+
 val copy(val seq)
 {
   switch (type(seq)) {
diff --git a/lib.h b/lib.h
index 9b8c997b..c1a898c2 100644
--- a/lib.h
+++ b/lib.h
@@ -1029,6 +1029,8 @@ val drop_while(val pred, val seq, val keyfun);
 val drop_until(val pred, val seq, val keyfun);
 val in(val seq, val key, val testfun, val keyfun);
 val set_diff(val list1, val list2, val testfun, val keyfun);
+val isec(val list1, val list2, val testfun, val keyfun);
+val uni(val list1, val list2, val testfun, val keyfun);
 val copy(val seq);
 val length(val seq);
 val empty(val seq);
diff --git a/txr.1 b/txr.1
index 0c220e16..d20abc08 100644
--- a/txr.1
+++ b/txr.1
@@ -27213,27 +27213,97 @@ To find the entry holding the maximum value, the
 .code cdr
 function can be specified.
 
-.coNP Function @ set-diff
+.coNP Functions @, uni @ isec and @ diff
 .synb
-.mets (set-diff < seq1 < seq2 >> [ testfun <> [ keyfun ]])
+.mets (uni < seq1 < seq2 >> [ testfun <> [ keyfun ]])
+.mets (isec < seq1 < seq2 >> [ testfun <> [ keyfun ]])
+.mets (diff < seq1 < seq2 >> [ testfun <> [ keyfun ]])
 .syne
 .desc
-The
-.code set-diff
-function treats the sequences
+The functions
+.codn diff ,
+.code isec
+and
+.code uni
+treats the sequences
 .meta seq1
 and
 .meta seq2
-as if they were sets
-and computes the set difference: a sequence which contains those elements in
+as if they were sets.
+
+They respectively compute the set union, set intersection
+and set difference of
 .meta seq1
-which do not occur in
-.metn seq2 .
+and
+.metn seq2 ,
+returning a new sequence: the union sequence,
+intersection sequence and difference sequence.
 
-.code set-diff
-returns a sequence of the same kind as
+The sequences
+.meta seq1
+and
+.meta seq2
+need not be of the same kind.
+The returned sequence is of the same kind as
 .metn seq1 .
 
+Since the input sequences are defined as representing sets, they are assumed
+not to contain duplicate elements. These functions are not required, but may,
+de-duplicate the sequences.
+
+The union sequence produced by
+.code uni
+contains all of the elements which occur in both
+.meta seq1
+and
+.metn seq2 .
+If a given element occurs exactly once only in
+.meta seq1
+or exactly once only in
+.metn seq2 ,
+or exactly once in both sequences, then it occurs exactly once in the union
+sequence.  If a given element occurs at least once in either
+.metn seq1 ,
+.meta seq2
+or both, then it occurs at least once in the union sequence.
+
+The intersection sequence produced by
+.code isec
+contains all of the elements which occur in both
+.meta seq1
+and
+.metn seq2 .
+If a given element occurs exactly once in
+.meta seq1
+and exactly once in
+.metn seq2 ,
+then in occurs exactly once in the intersection sequence.
+If a given element occurs at least once in
+.meta seq1
+and at least once in
+.metn seq2 ,
+then in occurs at least once in the intersection sequence.
+
+The difference sequence produced by
+.code diff
+contains all of the elements which occur in
+.meta seq1
+but do not occur in
+.metn seq2 .
+If an element occurs exactly once in
+.meta seq1
+and does not occur in
+.metn seq2 ,
+then it occurs exactly once in the difference sequence.
+If an element occurs at least once in
+.meta seq1
+and does not occur in
+.metn seq2 ,
+then it occurs at least once in the difference sequence.
+If an element occurs at least once in
+.metn seq2 ,
+then it does not occur in the difference sequence.
+
 Element equivalence is determined by a combination of
 .meta testfun
 and
@@ -27253,15 +27323,24 @@ then the
 .code equal
 function is used.
 
-If
-.meta seq1
-contains duplicate elements which do not occur in
-.meta seq2
-(and thus are preserved in the set difference) then these duplicates appear
-in the resulting
-sequence. Furthermore, the order of the items from
+Note: a function identical to
+.code diff
+named
+.code set-diff
+exists. This became deprecated starting in \*(TX 184.
+For the
+.code set-diff
+function, the requirement was specified to preserve the original
+order of items from
 .meta seq1
-is preserved.
+that survive into the output sequence.
+This requirement is not documented for the
+.code diff
+function, but is
+.I "de facto"
+honored by the implementation for at as long as the
+.code set-diff
+synonym continues to be available.
 
 .coNP Functions @, mapcar @ mappend @ mapcar* and @ mappend*
 .synb