diff options
| -rw-r--r-- | eval.c | 5 | ||||
| -rw-r--r-- | lib.c | 105 | ||||
| -rw-r--r-- | lib.h | 1 | ||||
| -rw-r--r-- | txr.1 | 39 |
4 files changed, 109 insertions, 41 deletions
@@ -6014,7 +6014,6 @@ 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); val length_f = func_n1(length); protect(&top_vb, &top_fb, &top_mb, &top_smb, &special, &builtin, &dyn_env, @@ -6747,8 +6746,8 @@ 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), diff_f); - reg_fun(intern(lit("diff"), user_package), diff_f); + 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("isec"), user_package), func_n4o(isec, 2)); reg_fun(intern(lit("uni"), user_package), func_n4o(uni, 2)); @@ -9930,6 +9930,42 @@ val in(val seq, val item, val testfun, val keyfun) } } +val diff(val seq1, val seq2, val testfun, val keyfun) +{ + val self = lit("diff"); + list_collect_decl (out, ptail); + seq_iter_t si1, si2; + val el1; + + 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)) { + val el1_key = funcall1(keyfun, el1); + val el2; + int found = 0; + + seq_iter_rewind(self, &si2); + + while (seq_get(&si2, &el2)) { + val el2_key = funcall1(keyfun, el2); + + if (funcall2(testfun, el1_key, el2_key)) { + found = 1; + break; + } + } + + if (!found) + ptail = list_collect(ptail, el1); + } + + return make_like(out, seq1); +} + val set_diff(val list1, val list2, val testfun, val keyfun) { list_collect_decl (out, ptail); @@ -9958,63 +9994,62 @@ 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) +val isec(val seq1, val seq2, val testfun, val keyfun) { + val self = lit("isec"); list_collect_decl (out, ptail); - val list_orig = list1; - - list1 = nullify(list1); - list2 = nullify(list2); + seq_iter_t si1, si2; + val el1; 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); + seq_iter_init(self, &si1, seq1); + seq_iter_init(self, &si2, seq2); - if (member(list1_key, list2, testfun, keyfun)) - ptail = list_collect(ptail, item); + while (seq_get(&si1, &el1)) { + val el1_key = funcall1(keyfun, el1); + val el2; + + seq_iter_rewind(self, &si2); + + while (seq_get(&si2, &el2)) { + val el2_key = funcall1(keyfun, el2); + + if (funcall2(testfun, el1_key, el2_key)) { + ptail = list_collect(ptail, el1); + break; + } } } - return make_like(out, list_orig); + return make_like(out, seq1); } -val uni(val list1, val list2, val testfun, val keyfun) +val uni(val seq1, val seq2, val testfun, val keyfun) { + val self = lit("uni"); list_collect_decl (out, ptail); - val list_orig = list1; - - list1 = nullify(list1); - list2 = nullify(list2); + seq_iter_t si1, si2; + val el1, el2; testfun = default_arg(testfun, equal_f); keyfun = default_arg(keyfun, identity_f); - ptail = list_collect_append(ptail, list1); + seq_iter_init(self, &si1, seq1); + seq_iter_init(self, &si2, seq2); - 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); + while (seq_get(&si1, &el1)) + ptail = list_collect(ptail, el1); - if (!member(list2_key, list1, testfun, keyfun)) - ptail = list_collect(ptail, item); - } + while (seq_get(&si2, &el2)) { + val el2_key = funcall1(keyfun, el2); + + if (!member(el2_key, out, testfun, keyfun)) + ptail = list_collect(ptail, el2); } - return make_like(out, list_orig); + return make_like(out, seq1); } val copy(val seq) @@ -1078,6 +1078,7 @@ 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 diff(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); @@ -28728,13 +28728,27 @@ and returning a new sequence: the union sequence, intersection sequence and difference sequence. -The sequences +The arguments .meta seq1 and .meta seq2 -need not be of the same kind. +need not be of the same kind. They may be hash tables. + The returned sequence is of the same kind as .metn seq1 . +If +.meta seq1 +is a hash table, the returned sequence is a list. + +For the purposes of these functions, an input which is a hash table +is considered as if it were a sequence of hash key and hash +value pairs represented as cons cells, the +.code car +slots of which are the hash keys, and the +.code cdr +of which are the hash values. This means that if no +.meta keyfun +is specified, these pairs are taken as keys. Since the input sequences are defined as representing sets, they are assumed not to contain duplicate elements. These functions are not required, but may, @@ -28812,7 +28826,7 @@ then the .code equal function is used. -Note: a function identical to +Note: a function similar to .code diff named .code set-diff @@ -28830,6 +28844,25 @@ function, but is honored by the implementation for at as long as the .code set-diff synonym continues to be available. +The +.code set-diff +function doesn't support hash tables and is inefficient for vectors and +strings. + +Note: these functions are not efficient for the processing of hash tables, +even when both inputs are hashes, the +.meta keyfun +argument is +.codn car , +and +.meta testfun +matches the equality used by both hash table inputs. +If applicable, the operations +.codn hash-uni , +.code hash-isec +and +.code hash-diff +should be used instead. .coNP Functions @, mapcar @, mappend @ mapcar* and @ mappend* .synb |