a

1 files changed, 26 insertions, 0 deletions

diff --git a/examples/tree.zc b/examples/tree.zc
new file mode 100644
index 0000000..9ef515e
--- /dev/null
+++ b/examples/tree.zc
@@ -0,0 +1,26 @@
+// a binary search tree where every node owns its children. there's no free
+// anywhere: when the root's block ends, the whole tree goes with it.
+struct node { int v; node* left, right; };
+
+node*.u leaf(int v) { node* n = new(node); n.v = v; return u*n; }
+// n is borrowed; storing a new leaf into it makes n the leaf's owner
+fn insert(node*.m n, int v) {
+	if (v < n.v) { if (n.left) insert(n.left, v); else n.left = leaf(v); }
+	else { if (n.right) insert(n.right, v); else n.right = leaf(v); }
+	return 0;
+}
+fn walk(node* n) { if (!n) return 0; walk(n.left); put_n(n.v); put_c(' '); walk(n.right); return 0; }
+int height(node* n) { if (!n) return 0; int l = height(n.left), r = height(n.right); return 1 + (l > r ? l : r); }
+
+fn main() {
+	let before = live_objects();
+	{
+		node* root = leaf(50);
+		int x = 7;
+		for (int i = 0; i < 30; i++) { x = (x * 37 + 11) % 100; insert(root, x); }
+		walk(root); put_c(10);
+		put_s("height "); put_n(height(root)); put_s(", live objects "); put_n(live_objects() - before); put_c(10);
+	}
+	put_s("after the block: "); put_n(live_objects() - before); put_c(10);
+	return 0;
+}