diff options
author | Kaz Kylheku <kaz@kylheku.com> | 2021-04-29 19:20:15 -0700 |
---|---|---|
committer | Kaz Kylheku <kaz@kylheku.com> | 2021-04-29 19:20:15 -0700 |
commit | 853e299c38e5514810574b1094136d64ed375831 (patch) | |
tree | d90a1490ab52a43bdc08f6d9a87c23c51a82f532 /tests | |
parent | 3c6a8eb20849ee1028b225883beb3f0363ef255b (diff) | |
download | txr-853e299c38e5514810574b1094136d64ed375831.tar.gz txr-853e299c38e5514810574b1094136d64ed375831.tar.bz2 txr-853e299c38e5514810574b1094136d64ed375831.zip |
tree: new tree-begin-at function.
* tree.c (enum tree_iter_state): New iterator state
tr_find_low_prepared dedicated to the tree-begin-at traversal.
This state indicates that tree-next should visit the starting
node that it is given, and then after that, treat anything to
the left of it as having been visited. In the other states,
tree-next does not visit the node it is given but uses it as
the starting point to find the next node.
(tn_find_next): Bugfix here: when navigating the right link,
the function neglected to add the node to the path. But the
logic for backtracking up the path expects this: it checks
whether the node from the path is the parent of a right child.
Somehow this didn't cause a problem for full traversals with
tree-begin; at least the existing test cases don't expose an
issue. It caused a problem for tree-begin-at, though.
(tn_find_low): New static function. This finds the low-key
node in the tree, priming the iterator object with the correct
state and path content to continue the traversal from that
node on . We need the tr_find_low_prepared state in the
iterator in order to visit the low node itself that was found.
(tree_begin_at): New function.
(tree_init): Register tree-begin-at intrinsic.
* tree.h (tree_begin_at): Declared.
* tests/010/tree.tl: New test cases for tree-begin-at.
* txr.1: Documented.
* share/txr/stdlib/doc-syms.tl: Updated.
Diffstat (limited to 'tests')
-rw-r--r-- | tests/010/tree.tl | 29 |
1 files changed, 28 insertions, 1 deletions
diff --git a/tests/010/tree.tl b/tests/010/tree.tl index df454e75..a71308c3 100644 --- a/tests/010/tree.tl +++ b/tests/010/tree.tl @@ -48,6 +48,34 @@ (test trc #T(())) +(test (tree-delete tr 6) 6) + +(vtest (build (for* ((i (tree-begin-at tr 6)) + (n (tree-next i))) + (n) + ((set n (tree-next i))) + (add (key n)))) + (range 7 19)) + +(vtest (build (for* ((i (tree-begin-at tr 0)) + (n (tree-next i))) + (n) + ((set n (tree-next i))) + (add (key n)))) + (append (range 0 5) (range 7 19))) + +(vtest (build (for* ((i (tree-begin-at tr 8)) + (n (tree-next i))) + (n) + ((set n (tree-next i))) + (add (key n)))) + (range 8 19)) + +(test (tree-next (tree-begin-at tr 20)) nil) + +(test (tree-next (tree-begin-at #T(()) 0)) nil) +(test (key (tree-next (tree-begin-at #T(() 1) 1))) 1) + (mtest (tree-delete tr 0) 0 (tree-delete tr 1) 1 @@ -55,7 +83,6 @@ (tree-delete tr 3) 3 (tree-delete tr 4) 4 (tree-delete tr 5) 5 - (tree-delete tr 6) 6 (tree-delete tr 7) 7 (tree-delete tr 8) 8 (tree-delete tr 9) 9 |