diff options
| -rw-r--r-- | eval.c | 1 | ||||
| -rw-r--r-- | lib.c | 43 | ||||
| -rw-r--r-- | lib.h | 3 | ||||
| -rw-r--r-- | txr.1 | 32 |
4 files changed, 70 insertions, 9 deletions
@@ -6748,6 +6748,7 @@ void eval_init(void) 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("diff"), user_package), func_n4o(diff, 2)); + reg_fun(intern(lit("symdiff"), user_package), func_n4o(symdiff, 2)); reg_fun(intern(lit("isec"), user_package), func_n4o(isec, 2)); reg_fun(intern(lit("uni"), user_package), func_n4o(uni, 2)); @@ -9994,6 +9994,49 @@ val set_diff(val list1, val list2, val testfun, val keyfun) return make_like(out, list_orig); } +val symdiff(val seq1, val seq2, val testfun, val keyfun) +{ + val self = lit("symdiff"); + list_collect_decl (out, ptail); + seq_iter_t si1, si2; + val el1, el2; + + testfun = default_arg(testfun, equal_f); + keyfun = default_arg(keyfun, identity_f); + + seq_iter_init(self, &si1, seq1); + seq_iter_init(self, &si2, seq2); + + while (seq_get(&si1, &el1)) + ptail = list_collect(ptail, el1); + + while (seq_get(&si2, &el2)) { + val el2_key = funcall1(keyfun, el2); + val *iter; + int found = 0; + + for (iter = &out; *iter; ) { + val elo = us_car(*iter); + val elo_key = funcall1(keyfun, elo); + if (funcall2(testfun, elo_key, el2_key)) { + val del = us_cdr(*iter); + if (deref(ptail) == del) + ptail = mkcloc(*iter); + *iter = del; + found = 1; + break; + } else { + iter = us_cdr_p(*iter); + } + } + + if (!found) + ptail = list_collect(ptail, el2); + } + + return make_like(out, seq1); +} + val isec(val seq1, val seq2, val testfun, val keyfun) { val self = lit("isec"); @@ -544,6 +544,8 @@ val car(val cons); val cdr(val cons); INLINE val us_car(val cons) { return cons->c.car; } INLINE val us_cdr(val cons) { return cons->c.cdr; } +INLINE val *us_car_p(val cons) { return &cons->c.car; } +INLINE val *us_cdr_p(val cons) { return &cons->c.cdr; } val rplaca(val cons, val new_car); val rplacd(val cons, val new_car); val sys_rplaca(val cons, val new_car); @@ -1079,6 +1081,7 @@ 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 diff(val seq1, val seq2, val testfun, val keyfun); +val symdiff(val seq1, val seq2, 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); @@ -28702,31 +28702,32 @@ the leftmost one is reported. See the notes under .code pos-max regarding duplicate maxima. -.coNP Functions @, uni @ isec and @ diff +.coNP Functions @, uni @, isec @ diff and @ symdiff .synb .mets (uni < seq1 < seq2 >> [ testfun <> [ keyfun ]]) .mets (isec < seq1 < seq2 >> [ testfun <> [ keyfun ]]) .mets (diff < seq1 < seq2 >> [ testfun <> [ keyfun ]]) +.mets (symdiff < seq1 < seq2 >> [ testfun <> [ keyfun ]]) .syne .desc The functions -.codn diff , -.code isec +.codn uni , +.codn isec , +.code diff and -.code uni -treats the sequences +.code symdiff +treat the sequences .meta seq1 and .meta seq2 as if they were sets. -They respectively compute the set union, set intersection -and set difference of +They, respectively, compute the set union, set intersection, +set difference and symmetric difference of .meta seq1 and .metn seq2 , -returning a new sequence: the union sequence, -intersection sequence and difference sequence. +returning a new sequence. The arguments .meta seq1 @@ -28807,6 +28808,19 @@ If an element occurs at least once in .metn seq2 , then it does not occur in the difference sequence. +The symmetric difference sequence produced by +.code symdiff +contains all of the elements of +.meta seq1 +which do not occur in +.meta seq2 +and +.IR "vice versa" : +it also contains all of the elements of +.meta seq2 +which do not occur in +.metn seq1 . + Element equivalence is determined by a combination of .meta testfun and |