1	import Base
2	import ./type.bend as R
3	
4	def key(-N: Data, r: R.Rose<N>) -> String:
5	  match r:
6	    case R.Rose{k, _, _}:
7	      k
8	
9	# Every key in a forest, each tree's own key before its children's.
10	def keys(-N: Data, rs: List<&2, R.Rose<N>>) -> List<&2, String>:
11	  match rs:
12	    case []:
13	      []
14	    case r <> rest:
15	      match r:
16	        case R.Rose{k, _, kids}:
17	          k <> List.append(&2, String, keys(N, kids), keys(N, rest))
18	
19	# The first key of a list, "" for none.
20	def first(xs: List<&2, String>) -> String:
21	  match xs:
22	    case []:
23	      ""
24	    case x <> _:
25	      x
26	
27	# Where a key sits: the keys above it, nearest first.
28	type Place is Data:
29	  Place{key: String, above: List<&2, String>}
30	
31	def places(-N: Data, rs: List<&2, R.Rose<N>>, +above: List<&2, String>) -> List<&2, Place>:
32	  match rs:
33	    case []:
34	      []
35	    case r <> rest:
36	      match r:
37	        case R.Rose{+k, _, kids}:
38	          Place{k, above} <> List.append(&2, Place, places(N, kids, k <> above), places(N, rest, above))
39	
40	def found(-N: Data, hit: Bool, v: N, below: Maybe<&2, N>, after: Maybe<&2, N>) -> Maybe<&2, N>:
41	  match hit:
42	    case True{}:
43	      Some{v}
44	    case False{}:
45	      Maybe.or(&2, N, below, after)
46	
47	# The value at a key, if the forest has it.
48	def find(-N: Data, +k: String, rs: List<&2, R.Rose<N>>) -> Maybe<&2, N>:
49	  match rs:
50	    case []:
51	      None{}
52	    case r <> rest:
53	      match r:
54	        case R.Rose{rk, v, kids}:
55	          found(N, String.eq(k, rk), v, find(N, k, kids), find(N, k, rest))