From 26f1f25a07a2b85b5481f0f5f1612c64bc76d910 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Fri, 7 Mar 2025 07:08:29 -0800 Subject: New feature: range iteration with skip. The notation X..Y..Z now denotes an iterable range, if X..Y is a valid iterable range on its own, and Z is a positive integer. Z gives a step size: 1 takes every element, 2 every other and so on. * lib.c (seq_iter_get_skip, set_iter_peek_skip): New static functions. (si_skip_ops): New static structure. (iter_dynamic): Function relocated earlier in file to avoid forward declaration. (seq_iter_init_with_info): When the iterated object is a range, check for the to element itself being a range. If so, it is potentially a skip iteration. Validate it and implement via a skip iterator referencing a dynamic range iterator. * lib.h (struct seq_iter): New sub-union member, ul.skip. We could use an existing member of type cnum; this is for naming clarity. * tests/012/iter.tl: New tests. * txr.1: Documented. --- lib.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++------- lib.h | 1 + tests/012/iter.tl | 20 ++++++++++++++++ txr.1 | 38 +++++++++++++++++++++++++++++ 4 files changed, 122 insertions(+), 8 deletions(-) diff --git a/lib.c b/lib.c index cf137699..8aeda9ab 100644 --- a/lib.c +++ b/lib.c @@ -859,6 +859,34 @@ static int seq_iter_peek_cat(seq_iter_t *it, val *pval) } } +static int seq_iter_get_skip(seq_iter_t *it, val *pval) +{ + val iter = it->ui.iter; + cnum skip = it->ul.skip; + + if (iter_more(iter)) { + cnum i; + *pval = iter_item(iter); + for (i = 0; i < skip; i++) + iter = iter_step(iter); + return 1; + } + + return 0; +} + +static int seq_iter_peek_skip(seq_iter_t *it, val *pval) +{ + val iter = it->ui.iter; + + if (iter_more(iter)) { + *pval = iter_item(iter); + return 1; + } + + return 0; +} + static void seq_iter_mark_cat(struct seq_iter *it) { gc_mark(it->ul.dargs); @@ -941,6 +969,9 @@ struct seq_iter_ops si_cat_ops = seq_iter_ops_init_mark(seq_iter_get_cat, seq_iter_peek_cat, seq_iter_mark_cat); +struct seq_iter_ops si_skip_ops = seq_iter_ops_init(seq_iter_get_skip, + seq_iter_peek_skip); + static void seq_iter_clone(seq_iter_t *dit, const seq_iter_t *sit) { if (sit->ops->clone) @@ -949,6 +980,14 @@ static void seq_iter_clone(seq_iter_t *dit, const seq_iter_t *sit) *dit = *sit; } +static val iter_dynamic(struct seq_iter *si_orig) +{ + struct seq_iter *si = coerce(struct seq_iter *, + chk_copy_obj(coerce(mem_t *, si_orig), + sizeof *si)); + return cobj(coerce(mem_t *, si), seq_iter_cls, &seq_iter_cobj_ops); +} + void seq_iter_init_with_info(val self, seq_iter_t *it, seq_info_t si) { it->inf = si; @@ -964,6 +1003,30 @@ void seq_iter_init_with_info(val self, seq_iter_t *it, seq_info_t si) break; } + if (rangep(rt)) { + val rtf = from(rt); + val rtt = to(rt); + + if (!integerp(rtt) || !plusp(rtt)) { + uw_throwf(type_error_s, + lit("~a: skip amount ~s in ~s..~s..~s " + "must be positive integer"), + self, rtt, rf, rtf, rtt, nao); + } else if (rtt == one) { + rt = rtf; + } else { + val rng = rcons(rf, rtf); + seq_iter_t lower_iter; + + seq_iter_init_with_info(self, &lower_iter, seq_info(rng)); + + it->ui.iter = iter_dynamic(&lower_iter); + it->ul.skip = c_num(rtt, self); + it->ops = &si_skip_ops; + return; + } + } + if (less(rf, rt)) switch (type(rf)) { case NUM: num_range_fwd: @@ -1277,14 +1340,6 @@ val iter_begin(val obj) } } -static val iter_dynamic(struct seq_iter *si_orig) -{ - struct seq_iter *si = coerce(struct seq_iter *, - chk_copy_obj(coerce(mem_t *, si_orig), - sizeof *si)); - return cobj(coerce(mem_t *, si), seq_iter_cls, &seq_iter_cobj_ops); -} - val iter_more(val iter) { val self = lit("iter-more"); diff --git a/lib.h b/lib.h index 649fc291..2d2b5e4e 100644 --- a/lib.h +++ b/lib.h @@ -454,6 +454,7 @@ typedef struct seq_iter { cnum len; val vbound; cnum cbound; + cnum skip; val next; val dargs; } ul; diff --git a/tests/012/iter.tl b/tests/012/iter.tl index cebbca55..f0be1b91 100644 --- a/tests/012/iter.tl +++ b/tests/012/iter.tl @@ -174,3 +174,23 @@ (iterp (fun list)) nil (iterp #/regex/) nil (iterp #(vec)) nil) + +(mtest + (list-seq 0..10..-1) :error + (list-seq 0..10..0) :error + (list-seq 0..10..#\a) :error + (list-seq 0..10..1) (0 1 2 3 4 5 6 7 8 9) + (list-seq 0..10..2) (0 2 4 6 8) + (list-seq 0..10..3) (0 3 6 9) + (list-seq 0..10..5) (0 5) + (list-seq 0..10..9) (0 9) + (list-seq 0..10..10) (0) + (list-seq 0..10..1000) (0)) + +(mtest + (list-seq "AA".."CC"..1) ("AA" "AB" "AC" "BA" "BB" "BC" "CA" "CB" "CC") + (list-seq "AA".."CC"..2) ("AA" "AC" "BB" "CA" "CC") + (list-seq "AA".."CC"..3) ("AA" "BA" "CA") + (list-seq "AA".."CC"..8) ("AA" "CC") + (list-seq "AA".."CC"..9) ("AA") + (list-seq "AA".."CC"..999) ("AA")) diff --git a/txr.1 b/txr.1 index 0409b569..48c9002e 100644 --- a/txr.1 +++ b/txr.1 @@ -40078,6 +40078,44 @@ iterates over the strings and .codn "CA" . +A ranges of any kind may be derived into a +.IR "skip range" : +a range which skips elements. A skip range is expressed by a range +whose +.code to +element is a range, whose +.code to +element is a positive integer. This can be notated by an expression +which uses two instances of the +.code .. +(dot dot) range notation, +.codn X..Y..Z , +where +.code X..Y +must be a valid iterable range on its own, and +.code Z +must evaluate to a positive integer. +For instance +.code 0..10..2 +denotes a skip range which traverses the values +.codn 0 , +.codn 2 , +.codn 4 , +.code 6 +and +.codn 8 . +This syntax is equivalent to +.codn "(rcons 0 (rcons 10 2))" . +The implementation may be understood in terms of cascaded iteration +objects. In the abstract semantics, when +.code 0..10..2 +is passed to +.codn iter-begin , +a range iterator is first constructed for the range +.codn 1..10 . +Then a skip iterator is constructed, which takes every other element +from the range iterator. That skip iterator is returned. + Search trees are iterable. Iteration entails an in-order visits of the elements of a tree. A tree iterator created by .code tree-begin -- cgit v1.2.3