diff options
| -rw-r--r-- | share/txr/stdlib/doc-syms.tl | 8 | ||||
| -rw-r--r-- | tests/010/tree.tl | 8 | ||||
| -rw-r--r-- | tree.c | 52 | ||||
| -rw-r--r-- | tree.h | 1 | ||||
| -rw-r--r-- | txr.1 | 39 |
5 files changed, 95 insertions, 13 deletions
diff --git a/share/txr/stdlib/doc-syms.tl b/share/txr/stdlib/doc-syms.tl index 084b4228..2355066e 100644 --- a/share/txr/stdlib/doc-syms.tl +++ b/share/txr/stdlib/doc-syms.tl @@ -480,9 +480,9 @@ ("trace" "N-02833733") ("ixany" "N-02391683") ("-rng+" "N-00BEA6DF") + ("*stddebug*" "N-006566FB") ("buf-put-ulong" "N-020CF007") ("tree-insert-node" "N-008B4AD9") - ("*stddebug*" "N-006566FB") ("remq*" "N-00B85CD2") ("reject" "N-031DC0F2") ("signum" "D-001E") @@ -727,6 +727,7 @@ ("iflet" "N-02DA21F6") ("apply" "N-026C3723") ("let" "N-013AF20B") + ("make-similar-tree" "N-030D1EF5") ("refset" "N-01A419FB") ("chain" "N-00C53CF7") ("carray-cptr" "N-03E001C5") @@ -948,7 +949,7 @@ ("carray-blank" "N-00DD8DF1") ("minor" "N-02F0F482") ("cons" "N-02D6CEDA") - ("tree-next" "N-0049D1B0") + ("tree-next" "N-02443382") ("size-t" "N-03258244") ("set-iflags" "N-02061924") ("eilseq" "N-036B1BDB") @@ -1092,6 +1093,7 @@ ("command-put-buf" "N-02AE3A31") ("tree-case" "N-03D834A5") ("exception-subtype-p" "N-02E7F869") + ("tree-peek" "N-02443382") ("dlopen" "N-037C4BFE") ("partition-by" "N-000167DF") ("buf-get-i8" "N-0013E55F") @@ -1977,13 +1979,13 @@ ("wrap*" "N-026DDCEC") ("int-carray" "N-00797A01") ("glob-mark" "N-0188409B") + ("*stdin*" "N-006566FB") ("chr-tolower" "N-015A58D0") ("append-each" "N-0105F01D") ("whilet" "N-0154DC75") ("pppred" "N-038E636C") ("flo-dig" "N-00998CE7") ("opip" "N-01937C5A") - ("*stdin*" "N-006566FB") ("last" "D-0079") ("copy-file" "N-019D6582") ("eisconn" "N-036B1BDB") diff --git a/tests/010/tree.tl b/tests/010/tree.tl index 6a1d4aa1..86a21167 100644 --- a/tests/010/tree.tl +++ b/tests/010/tree.tl @@ -48,6 +48,14 @@ (add (key n)))) (range 0 19)) +(vtest (build (for* ((j (tree-begin tr)) + (i (progn (tree-next j) (tree-next j) (tree-reset j tr))) + (n (tree-peek i))) + ((and n (eq (tree-next i) n))) + ((set n (tree-peek i))) + (add (key n)))) + (range 0 19)) + (defvarl trc (copy-search-tree tr)) (vtest trc tr) @@ -214,6 +214,43 @@ static val tn_find_next(val node, struct tree_iter *trit) } } +static val tn_peek_next(val node, struct tree_iter *trit) +{ + enum tree_iter_state state = trit->state; + int depth = trit->depth; + + for (;;) { + switch (state) { + case tr_visited_nothing: + if (!node) + return nil; + while (node->tn.left) + node = node->tn.left; + return node; + case tr_visited_left: + if (node->tn.right) { + state = tr_visited_nothing; + node = node->tn.right; + continue; + } else { + while (depth > 0) { + val parent = trit->path[--depth]; + if (node == parent->tn.right) { + node = parent; + continue; + } + return parent; + } + return nil; + } + case tr_find_low_prepared: + return node; + default: + internal_error("invalid tree iterator state"); + } + } +} + static void tn_find_low(val node, struct tree_diter *tdi, struct tree *tr, val key) { @@ -820,6 +857,20 @@ val tree_next(val iter) return nil; } +val tree_peek(val iter) +{ + val self = lit("tree-peek"); + struct tree_diter *tdi = coerce(struct tree_diter *, + cobj_handle(self, iter, tree_iter_s)); + + if (tdi->lastnode) { + val node = tn_peek_next(tdi->lastnode, &tdi->ti); + return node; + } + + return nil; +} + val tree_clear(val tree) { val self = lit("tree-clear"); @@ -860,6 +911,7 @@ void tree_init(void) reg_fun(intern(lit("tree-reset"), user_package), func_n2(tree_reset)); reg_fun(intern(lit("tree-reset-at"), user_package), func_n3(tree_reset_at)); reg_fun(intern(lit("tree-next"), user_package), func_n1(tree_next)); + reg_fun(intern(lit("tree-peek"), user_package), func_n1(tree_peek)); reg_fun(intern(lit("tree-clear"), user_package), func_n1(tree_clear)); reg_var(tree_fun_whitelist_s, list(identity_s, equal_s, less_s, nao)); } @@ -48,5 +48,6 @@ val tree_begin_at(val tree, val lowkey); val tree_reset(val iter, val tree); val tree_reset_at(val iter, val tree, val lowkey); val tree_next(val iter); +val tree_peek(val iter); val tree_clear(val tree); void tree_init(void); @@ -51873,35 +51873,54 @@ and .meta low-key arguments. -.coNP Function @ tree-next +.coNP Functions @ tree-next and @ tree-peek .synb .mets (tree-next < iter ) +.mets (tree-peek < iter ) .syne .desc The .code tree-next +and +.code tree-peek function returns the next node in sequence from the tree iterator -.metn iter , -which must be an object of type -.codn tree-iter . -Note: the +.metn iter . +The iterator must be an object of type +.codn tree-iter , +returned by the .code tree-begin -function returns such a -.code tree-iter -object. +or +.code tree-begin-at +functions. -If there are no more nodes to be visited, the function returns +If there are no more nodes to be visited, these functions .codn nil . If, during the traversal of a tree, nodes are inserted or deleted, the behavior of .code tree-next +and +.code tree-peek on .code tree-iter -object that were obtained prior to the insertion or deletion is +objects that were obtained prior to the insertion or deletion is not specified. An attempt to complete the iteration may not successfully visit all keys that should be visited. +The +.code tree-next +function changes the state of the iterator. If +.code tree-next +is invoked repeatedly on the same iterator, it returns successive +nodes of the tree. + +If +.code tree-peek +is invoked more than once on the same iterator without any intervening calls to +.codn tree-next , +it returns the same node; it does not appear to change the state of +the iterator and therefore does not advance through successive nodes. + .coNP Special variable @ *tree-fun-whitelist* .desc The |