stau.space
Rope data structure implementation in Hare.
1use fmt;
2use strings;
3
4// TODO: docs
5export type Node = struct {
6 left: nullable *Node,
7 right: nullable *Node,
8 data: Leaf,
9 length: size,
10};
11
12// TODO: docs
13fn node_new() Node = Node {
14 left = null,
15 right = null,
16 data = leaf_new(),
17 length = 0: size,
18};
19
20// TODO: docs
21fn node_close(node: *Node) void = {
22 match (node.left) {
23 case null => void;
24 case let left: *Node => node_close(left);
25 };
26 match (node.right) {
27 case null => void;
28 case let right: *Node => node_close(right);
29 };
30 leaf_close(&node.data);
31};
32
33// Caller must free return value. Do not free the passed string or else the
34// internal buffer will become invalid.
35fn node_fromstr(string: str) Node = Node {
36 left = null,
37 right = null,
38 data = leaf_fromstr(string),
39 length = 0: size,
40};
41
42//fn strtonode(data: str) Node = {
43// return data;
44//};
45//
46//fn nodetorope(node: *Node) Rope = {
47// return Rope {
48// left = node,
49// right = null,
50// length = node_length(node)
51// };
52//};
53//
54//fn node_length(node: *Node) size = {
55// return match (*node) {
56// case let leaf: str => yield len(leaf);
57// case let rope: Rope => yield rope_length(&rope);
58// };
59//};
60
61// TODO: docs
62fn print_node(node: *const Node) void = {
63 fmt::print(strings::fromrunes(node.data.buf))!;
64};
65
66// TODO: docs
67fn print_tree(node: nullable *const Node) void = {
68 match (node) {
69 case null => void;
70 case let good: *const Node => {
71 print_tree(good.left);
72 fmt::print(strings::fromrunes(good.data.buf))!;
73 print_tree(good.right);
74 };
75 };
76};
77
78// TODO: docs
79fn node_length(node: nullable *const Node) size = match (node) {
80 case null => yield 0: size;
81 case let good: *const Node => yield if (good.data.length == 0) {
82 yield node_length(good.left) + node_length(good.right);
83 } else {
84 yield good.data.length;
85 };
86};
87
88fn node_index(node: nullable *const Node, idx: size) (rune | indexerror) = {
89 yield match (node) {
90 case null => yield indexerror;
91 case let good: *const Node => yield if (idx < good.length && !(good.left is null)) {
92 yield node_index(good.left, idx);
93 } else if (good.left is null) {
94 yield leaf_at(&good.data, idx);
95 } else {
96 yield node_index(good.right, idx - good.length);
97 };
98 };
99};