diff options
| -rw-r--r-- | eval.c | 2 | ||||
| -rw-r--r-- | lib.c | 28 | ||||
| -rw-r--r-- | lib.h | 2 | ||||
| -rw-r--r-- | tests/012/seq.tl | 20 | ||||
| -rw-r--r-- | txr.1 | 86 |
5 files changed, 138 insertions, 0 deletions
@@ -7280,6 +7280,7 @@ void eval_init(void) reg_fun(intern(lit("proper-list-p"), user_package), proper_list_p_f); } reg_fun(intern(lit("length-list"), user_package), func_n1(length_list)); + reg_fun(intern(lit("length-list-<"), user_package), func_n2(length_list_lt)); reg_fun(intern(lit("mapcar"), user_package), func_n1v(mapcarv)); reg_fun(intern(lit("mapcar*"), user_package), func_n1v(lazy_mapcarv)); @@ -7739,6 +7740,7 @@ void eval_init(void) reg_fun(intern(lit("str-seq"), user_package), func_n1(str_seq)); reg_fun(intern(lit("length"), user_package), length_f); reg_fun(intern(lit("len"), user_package), length_f); + reg_fun(intern(lit("length-<"), user_package), func_n2(length_lt)); reg_fun(intern(lit("empty"), user_package), func_n1(empty)); reg_fun(intern(lit("copy"), user_package), func_n1(copy)); reg_fun(intern(lit("sub"), user_package), func_n3o(sub, 1)); @@ -4857,6 +4857,19 @@ val length_list(val list) return bn_len; } +val length_list_lt(val list, val len) +{ + val self = lit("length-list-lt"); + cnum le = c_num(len, self); + + while (consp(list) && le > 0) { + list = cdr(list); + le--; + } + + return tnil(le > 0); +} + static val length_proper_list(val list) { cnum len = 0; @@ -13147,6 +13160,21 @@ val length(val seq) } } +val length_lt(val seq, val len) +{ + switch (type(seq)) { + case NIL: + return if3(plusp(len), t, nil); + case CONS: + case LCONS: + return length_list_lt(seq, len); + case LSTR: + return length_str_lt(seq, len); + default: + return lt(length(seq), len); + } +} + val sub(val seq, val from, val to) { switch (type(seq)) { @@ -909,6 +909,7 @@ val listp(val obj); val endp(val obj); val proper_list_p(val obj); val length_list(val list); +val length_list_lt(val list, val len); val getplist(val list, val key); val getplist_f(val list, val key, loc found); val memp(val key, val plist); @@ -1052,6 +1053,7 @@ val stringp(val str); val lazy_stringp(val str); val length_str(val str); val coded_length(val str); +val length_lt(val seq, val len); const wchar_t *c_str(val str, val self); val search_str(val haystack, val needle, val start_num, val from_end); val search_str_tree(val haystack, val tree, val start_num, val from_end); diff --git a/tests/012/seq.tl b/tests/012/seq.tl index 95754c67..4b84787d 100644 --- a/tests/012/seq.tl +++ b/tests/012/seq.tl @@ -645,3 +645,23 @@ (flatcar* '(() b . c)) (nil b c) (flatcar* '((()) b . c)) (nil b c) (flatcar* '(((a)) b . c)) (a b c)) + +(mtest + (length-< nil 0) nil + (length-< nil 1) t + (length-< '(a) 1) nil + (length-< '(a) 2) t + (length-< '(a . b) 1) nil + (length-< '(a . b) 2) t) + +(mtest + (length-< "" 0) nil + (length-< "" 1) t + (length-< "a" 1) nil + (length-< "a" 2) t) + +(mtest + (length-< #() 0) nil + (length-< #() 1) t + (length-< #(a) 1) nil + (length-< #(a) 2) t) @@ -22520,6 +22520,62 @@ Common Lisp does not allow the argument to be an atom, except for the empty list .codn nil . +.coNP Function @ length-list-< +.synb +.mets (length-list-< < list << len ) +.syne +.desc +The +.code length-list-< +function determines whether the length of +.metn list , +is less than the integer +.metn len . + +The expression + +.verb + (length-list-< x y) +.brev + +is similar to, but usefully different from + +.verb + (< (length-list x) y) +.brev + +because +.code length-list-< +is required to only traverses +.meta list +far enough to be able to determine the return value. +If the end of the list is reached before +.meta len +conses are encountered, the function returns +.codn t , +otherwise if +.code len +conses are encountered, the function terminates immediately and returns +.codn nil . + +The +.code length-list-< +function is therefore safe to use with infinite lazy lists and circular +lists, for which +.code length +would not terminate. + +Note: there is more generic function +.code length-< +which works with efficiently with different kinds of sequences. + +Note: the +.code length-list-< +is useful in situations when a decision must be made between two +algorithms based on the length of one or more input lists. +The decision can be made without wastefully performing a full pass over the +input lists to measure their length. + .coNP Function @ copy-cons .synb .mets (copy-cons << cons ) @@ -34033,6 +34089,36 @@ An attempt to calculate the length of infinite lazy lists will not terminate. Iterable objects representing infinite ranges, such as integers and characters are invalid arguments. +.coNP Function @ length-< +.synb +.mets (length-< < iterable << len ) +.syne +.desc +The +.code length-< +function efficiently determines whether +.mono +.meti (length << iterable) +.onom +is less than the integer value +.metn len . +In cases when +.meta iterable +would have to be fully traversed in order to measure its length, the +.code length-< +function avoids this traversal, by making use of the functions +.code length-str-< +or +.code length-list-< +as appropriate. + +Note: this function is useful when a decision must be made between +two algorithms, depending on whether the length is less than a certain +small constant. It is also safe on lazy, infinite sequences and +circular lists, for which +.code length +will fail to terminate. + .coNP Function @ empty .synb .mets (empty << iterable ) |