summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorKaz Kylheku <kaz@kylheku.com>2022-08-17 07:07:41 -0700
committerKaz Kylheku <kaz@kylheku.com>2022-08-17 07:07:41 -0700
commita2e0d566ef4d45d4915d43d035f6f21270d70178 (patch)
tree3e709fdf05798077b1eb3e97bc11ccab5bbe1f7f
parentce231e5426cb9f2238158e46032215d5b410bd60 (diff)
downloadtxr-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.c1
-rw-r--r--lib.c37
-rw-r--r--lib.h1
-rw-r--r--stdlib/doc-syms.tl1
-rw-r--r--tests/012/seq.tl15
-rw-r--r--txr.154
6 files changed, 100 insertions, 9 deletions
diff --git a/eval.c b/eval.c
index 7fdc9627..69dc238b 100644
--- a/eval.c
+++ b/eval.c
@@ -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));
diff --git a/lib.c b/lib.c
index b6b94ebb..13ac61ad 100644
--- a/lib.c
+++ b/lib.c
@@ -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)
diff --git a/lib.h b/lib.h
index 4eab1198..2e506e45 100644
--- a/lib.h
+++ b/lib.h
@@ -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))
diff --git a/txr.1 b/txr.1
index e0ba8879..c51b8d96 100644
--- a/txr.1
+++ b/txr.1
@@ -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 )