From 853e299c38e5514810574b1094136d64ed375831 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Thu, 29 Apr 2021 19:20:15 -0700 Subject: 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. --- tests/010/tree.tl | 29 ++++++++++++++++++++++++++++- 1 file changed, 28 insertions(+), 1 deletion(-) (limited to 'tests/010') 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 -- cgit v1.2.3