diff options
| -rw-r--r-- | stdlib/doc-syms.tl | 4 | ||||
| -rw-r--r-- | tests/010/tree.tl | 30 | ||||
| -rw-r--r-- | tree.c | 62 | ||||
| -rw-r--r-- | tree.h | 4 | ||||
| -rw-r--r-- | txr.1 | 56 |
5 files changed, 156 insertions, 0 deletions
diff --git a/stdlib/doc-syms.tl b/stdlib/doc-syms.tl index 80922b42..78229519 100644 --- a/stdlib/doc-syms.tl +++ b/stdlib/doc-syms.tl @@ -2003,6 +2003,8 @@ ("tree-case" "N-03D834A5") ("tree-clear" "N-03C88274") ("tree-count" "N-032882F2") + ("tree-del-min" "N-03A56FE7") + ("tree-del-min-node" "N-03A56FE7") ("tree-delete" "N-022035DF") ("tree-delete-node" "N-00772FAE") ("tree-delete-specific-node" "N-009B02CA") @@ -2011,6 +2013,8 @@ ("tree-insert-node" "N-008B4AD9") ("tree-lookup" "N-01D63E47") ("tree-lookup-node" "N-03FE4877") + ("tree-min" "N-02B1B686") + ("tree-min-node" "N-02B1B686") ("tree-next" "N-02443382") ("tree-peek" "N-02443382") ("tree-reset" "N-002A407C") diff --git a/tests/010/tree.tl b/tests/010/tree.tl index 79bab793..56d04fa9 100644 --- a/tests/010/tree.tl +++ b/tests/010/tree.tl @@ -226,3 +226,33 @@ (test (tree-count tr) 2) (tree-insert tr 1 t) (test (tree-count tr) 3)) + +(mtest + (tree-min-node (tree)) nil + (tree-min-node (tree '(1))) #N(1 nil nil) + (tree-min-node (tree '(1 2 3))) #N(1 nil nil)) + +(mtest + (tree-min (tree)) nil + (tree-min (tree '(1))) 1 + (tree-min (tree '(1 2 3))) 1) + +(let ((tr (tree '(1 2 3 4 5 6 7 8 9 10)))) + (mtest + (tree-count tr) 10 + (tree-del-min tr) 1 + (tree-del-min tr) 2 + (tree-del-min tr) 3 + (tree-count tr) 7 + (tree-del-min tr) 4 + (tree-count tr) 6 + (tree-del-min tr) 5 + (tree-del-min tr) 6 + (tree-del-min tr) 7 + (tree-del-min tr) 8 + (tree-count tr) 2 + (tree-del-min tr) 9 + (tree-count tr) 1 + (tree-del-min tr) 10 + (tree-count tr) 0 + (tree-del-min tr) nil)) @@ -636,6 +636,28 @@ val tree_lookup(val tree, val key) return if2(node, node->tn.key); } +val tree_min_node(val tree) +{ + val self = lit("tree-min-node"); + struct tree *tr = coerce(struct tree *, cobj_handle(self, tree, tree_cls)); + val node = tr->root; + + while (node != nil) { + val le = node->tn.left; + if (le == nil) + return node; + node = le; + } + + return nil; +} + +val tree_min(val tree) +{ + val node = tree_min_node(tree); + return if2(node, node->tn.key); +} + val tree_delete_node(val tree, val key) { val self = lit("tree-delete-node"); @@ -656,6 +678,42 @@ val tree_delete_specific_node(val tree, val node) return tr_delete_specific(tree, tr, node); } +val tree_del_min_node(val tree) +{ + val self = lit("tree-min-node"); + struct tree *tr = coerce(struct tree *, cobj_handle(self, tree, tree_cls)); + val node = tr->root, parent = nil;; + + while (node != nil) { + val le = node->tn.left; + + if (le == nil) { + val chld = node->tn.right; + + if (parent) + set(mkloc(parent->tn.left, parent), chld); + else + set(mkloc(tr->root, tree), chld); + + if (2 * --tr->size < tr->max_size) { + tr_rebuild(tree, tr, tr->root, nil, tr->size); + tr->max_size = tr->size; + } + + return node; + } + parent = node; + node = le; + } + + return nil; +} + +val tree_del_min(val tree) +{ + val node = tree_del_min_node(tree); + return if2(node, node->tn.key); +} static val tree_root(val tree) { @@ -1107,9 +1165,13 @@ void tree_init(void) reg_fun(intern(lit("tree-insert"), user_package), func_n3o(tree_insert, 2)); reg_fun(intern(lit("tree-lookup-node"), user_package), func_n2(tree_lookup_node)); reg_fun(intern(lit("tree-lookup"), user_package), func_n2(tree_lookup)); + reg_fun(intern(lit("tree-min-node"), user_package), func_n1(tree_min_node)); + reg_fun(intern(lit("tree-min"), user_package), func_n1(tree_min)); reg_fun(intern(lit("tree-delete-node"), user_package), func_n2(tree_delete_node)); reg_fun(intern(lit("tree-delete"), user_package), func_n2(tree_delete)); reg_fun(intern(lit("tree-delete-specific-node"), user_package), func_n2(tree_delete_specific_node)); + reg_fun(intern(lit("tree-del-min-node"), user_package), func_n1(tree_del_min_node)); + reg_fun(intern(lit("tree-del-min"), user_package), func_n1(tree_del_min)); reg_fun(intern(lit("tree-root"), user_package), func_n1(tree_root)); reg_fun(intern(lit("tree-begin"), user_package), func_n3o(tree_begin, 1)); reg_fun(intern(lit("copy-tree-iter"), user_package), func_n1(copy_tree_iter)); @@ -49,9 +49,13 @@ val tree_insert_node(val tree, val node, val dup); val tree_insert(val tree, val key, val dup); val tree_lookup_node(val tree, val key); val tree_lookup(val tree, val key); +val tree_min_node(val tree); +val tree_min(val tree); val tree_delete_node(val tree, val key); val tree_delete(val tree, val key); val tree_delete_specific_node(val tree, val node); +val tree_del_min_node(val tree); +val tree_del_min(val tree); val tree_begin(val tree, val lowkey, val highkey); val copy_tree_iter(val iter); val replace_tree_iter(val diter, val siter); @@ -54466,6 +54466,62 @@ is informed by key, for efficiency. However, if the tree contains duplicates of that key, then a linear search takes place among the duplicates. +.coNP Functions @ tree-min-node and @ tree-min +.synb +.mets (tree-min-node << tree ) +.mets (tree-min << tree ) +.syne +.desc +The +.code tree-min-node +function returns the node in +.meta tree +which holds the lowest element. If the tree is empty, it returns +.codn nil . + +The +.code tree-min +function returns the lowest element, or else +.code nil +if the tree is empty. + +.coNP Functions @ tree-del-min-node and @ tree-del-min +.synb +.mets (tree-del-min-node << tree ) +.mets (tree-del-min << tree ) +.syne +.desc +The +.code tree-del-min-node +function returns the node in +.meta tree +which has the lowest key, and removes that node from the tree. +If the tree is empty, it returns +.codn nil . + +The +.code tree-del-min +function returns the lowest element and removes it from the tree, or else +.code nil +if the tree is empty. + +The following equivalence holds: + +.verb + (tree-del-min tr) <--> (iflet ((node (tree-del-min-node tr))) + (key node)) +.brev + +Note: +.code tree-insert +together with +.code tree-del-min +provide the basis for using a tree as a priority queue. Elements are +inserted into the queue using +.code tree-insert +and then removed in priority order using +.codn tree-del-min . + .coNP Function @ tree-root .synb .mets (tree-root << tree ) |