diff options
author | Kaz Kylheku <kaz@kylheku.com> | 2022-08-17 07:07:41 -0700 |
---|---|---|
committer | Kaz Kylheku <kaz@kylheku.com> | 2022-08-17 07:07:41 -0700 |
commit | a2e0d566ef4d45d4915d43d035f6f21270d70178 (patch) | |
tree | 3e709fdf05798077b1eb3e97bc11ccab5bbe1f7f | |
parent | ce231e5426cb9f2238158e46032215d5b410bd60 (diff) | |
download | txr-a2e0d566ef4d45d4915d43d035f6f21270d70178.tar.gz txr-a2e0d566ef4d45d4915d43d035f6f21270d70178.tar.bz2 txr-a2e0d566ef4d45d4915d43d035f6f21270d70178.zip |
New function: search-all
* eval.c (eval_init): search-all intrinsic registered.
* lib.c (search_common): New Boolean argument all,
indicating whether all positions are to be returned.
We must handle this in the two places where empty
key and sequence are handled, and also in the main loop.
A trick is used: the found variable is now bound by
list_collect_decl, but not used for collecting unless
all is true.
(search, rsearch, contains): Pass 0 for all argument
of search_common.
(search_all): New function.
* lib.h (search_all): Declared.
* tests/012/seq.tl: New tests.
* txr.1: Documented.
* stdlib/doc-syms.tl: Regenerated.
-rw-r--r-- | eval.c | 1 | ||||
-rw-r--r-- | lib.c | 37 | ||||
-rw-r--r-- | lib.h | 1 | ||||
-rw-r--r-- | stdlib/doc-syms.tl | 1 | ||||
-rw-r--r-- | tests/012/seq.tl | 15 | ||||
-rw-r--r-- | txr.1 | 54 |
6 files changed, 100 insertions, 9 deletions
@@ -7377,6 +7377,7 @@ void eval_init(void) reg_fun(intern(lit("search"), user_package), func_n4o(search, 2)); reg_fun(intern(lit("rsearch"), user_package), func_n4o(rsearch, 2)); reg_fun(intern(lit("contains"), user_package), func_n4o(contains, 2)); + reg_fun(intern(lit("search-all"), user_package), func_n4o(search_all, 2)); reg_fun(intern(lit("where"), user_package), func_n2(where)); reg_fun(intern(lit("select"), user_package), func_n2(sel)); reg_fun(intern(lit("reject"), user_package), func_n2(reject)); @@ -12763,7 +12763,7 @@ val update(val seq, val fun) return seq; } -static val search_common(val self, int from_right, +static val search_common(val self, int all, int from_right, val seq, val key, val testfun_in, val keyfun_in) { val testfun = default_arg(testfun_in, equal_f); @@ -12774,17 +12774,29 @@ static val search_common(val self, int from_right, seq_iter_init(self, &ki, key); if (si.inf.kind == SEQ_NIL) { - return if3(length(key) == zero, zero, nil); + val kelem; + return if2(!seq_peek(&ki, &kelem), + if3(all, cons(zero, nil), zero)); } else if (ki.inf.kind == SEQ_HASHLIKE || si.inf.kind == SEQ_HASHLIKE) { type_mismatch(lit("~a: hashes not supported"), self, nao); - } else if (ki.inf.kind == SEQ_NIL) { + } else if (!all && ki.inf.kind == SEQ_NIL) { return if3(from_right, length(seq), zero); } else { val selem, kelem; - val pos = zero, found = nil; + val pos = zero; + list_collect_decl (found, ptail); - if (!seq_peek(&ki, &kelem)) + if (!seq_peek(&ki, &kelem)) { + if (all) { + while (seq_get(&si, &selem)) { + ptail = list_collect(ptail, pos); + pos = plus(pos, one); + } + list_collect(ptail, pos); + return found; + } return if3(from_right, length(seq), zero); + } for (;;) { val did_save = nil; @@ -12816,7 +12828,9 @@ static val search_common(val self, int from_right, } if (!more_key) { - if (from_right) + if (all) + ptail = list_collect(ptail, pos); + else if (from_right) found = pos; else return pos; @@ -12834,17 +12848,22 @@ static val search_common(val self, int from_right, val search(val seq, val key, val testfun, val keyfun) { - return search_common(lit("search"), 0, seq, key, testfun, keyfun); + return search_common(lit("search"), 0, 0, seq, key, testfun, keyfun); } val rsearch(val seq, val key, val testfun, val keyfun) { - return search_common(lit("rsearch"), 1, seq, key, testfun, keyfun); + return search_common(lit("rsearch"), 0, 1, seq, key, testfun, keyfun); } val contains(val key, val seq, val testfun, val keyfun) { - return search_common(lit("contains"), 0, seq, key, testfun, keyfun); + return search_common(lit("contains"), 0, 0, seq, key, testfun, keyfun); +} + +val search_all(val seq, val key, val testfun, val keyfun) +{ + return search_common(lit("search-all"), 1, 0, seq, key, testfun, keyfun); } static val lazy_where_func(val iter, val lcons) @@ -1252,6 +1252,7 @@ val update(val seq, val fun); val search(val seq, val key, val from, val to); val contains(val key, val seq, val testfun, val keyfun); val rsearch(val seq, val key, val from, val to); +val search_all(val seq, val key, val testfun, val keyfun); val where(val func, val seq); val sel(val seq, val where); val reject(val seq, val where); diff --git a/stdlib/doc-syms.tl b/stdlib/doc-syms.tl index 98a4b668..5d056427 100644 --- a/stdlib/doc-syms.tl +++ b/stdlib/doc-syms.tl @@ -1679,6 +1679,7 @@ ("scan" "N-03E989D0") ("scan-until-match" "N-00EFD668") ("search" "N-015D8676") + ("search-all" "N-01F7174D") ("search-regex" "N-0250D465") ("search-regst" "N-0250D465") ("search-str" "N-0257180F") diff --git a/tests/012/seq.tl b/tests/012/seq.tl index 4a1be8dd..a65d8ffa 100644 --- a/tests/012/seq.tl +++ b/tests/012/seq.tl @@ -501,6 +501,7 @@ [count #1="abc" '("abc" "abc" "abc" #1# "abc" #1#" abc") eq] 2)) (mtest + (search "" "") 0 (search "abcde" "ab") 0 (search "abcde" "bc") 1 (search "abcde" "cd") 2 @@ -510,6 +511,7 @@ (search "abcde" "x") nil) (mtest + (search nil nil) 0 (search '#"a b c d e" '#"a b") 0 (search '#"a b c d e" '#"b c") 1 (search '#"a b c d e" '#"c d") 2 @@ -519,6 +521,7 @@ (search '#"a b c d e" '#"x") nil) (mtest + (rsearch nil nil) 0 (rsearch "abcde" "ab") 0 (rsearch "abcde" "bc") 1 (rsearch "abcde" "cd") 2 @@ -535,3 +538,15 @@ (rsearch '#"a b c d e" '#"e") 4 (rsearch '#"a b c d e" nil) 5 (rsearch '#"a b c d e" '#"x") nil) + +(mtest + (search-all "" "") (0) + (search-all "xxxxx" "y") nil + (search-all "xxxxx" "x") (0 1 2 3 4) + (search-all "xxx" "") (0 1 2 3)) + +(mtest + (search-all nil nil) (0) + (search-all '#"x x x x x" '#"y") nil + (search-all '#"x x x x x" '#"x") (0 1 2 3 4) + (search-all '#"x x x" "") (0 1 2 3)) @@ -34004,6 +34004,60 @@ thereby effectively declaring that the rightmost match for an empty key occurs at the imaginary position past the element of .metn haystack . +.coNP Function @ search-all +.synb +.mets (search-all < haystack < needle >> [ testfun <> [ keyfun ]) +.syne +.desc +The +.code search-all +function is closely related to the +.code search +and +.code rsearch +functions. Whereas those two functions return the leftmost or rightmost +position, respectively, of +.meta needle +within +.metn haystack , +the +.code search-all +function returns a list of all the positions where +.meta needle +occurs. The positions of overlapping matches are included in the list. + +If +.meta needle +is not found in +.metn haystack , +.code search-all +returns the empty list +.codn nil . + +If +.meta needle +is empty, then +.code search-all +returns a list of all positions in +.meta haystack +including the one position past the last element. In this situation, if +.meta haystack +is empty, the list +.code "(0)" +is returned. If +.meta haystack +contains one item, then the list +.code "(0 1)" +is returned and so forth. + +In all situations in which +.code search-all +returns a non-empty list, the first element of that list is what +.code search +would return for the same arguments, and the last element is what +.code rsearch +would return. + .coNP Functions @ ref and @ refset .synb .mets (ref < sequence << index ) |