summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--stdlib/doc-syms.tl4
-rw-r--r--tests/010/tree.tl30
-rw-r--r--tree.c62
-rw-r--r--tree.h4
-rw-r--r--txr.156
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))
diff --git a/tree.c b/tree.c
index 8af798ad..8b3230e3 100644
--- a/tree.c
+++ b/tree.c
@@ -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));
diff --git a/tree.h b/tree.h
index ad1b2327..0948a49a 100644
--- a/tree.h
+++ b/tree.h
@@ -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);
diff --git a/txr.1 b/txr.1
index 4c650f0d..f2af420d 100644
--- a/txr.1
+++ b/txr.1
@@ -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 )