1	import Base
2	
3	# Neutral datatypes shared by src/balanced_search_tree.bend and
4	# spec/balanced_search_tree.bend.
5	
6	type Entry<-K: Data, -V: Data> is Data:
7	  Entry{key: K, val: V}
8	
9	def key(-K: Data, -V: Data, e: Entry<K, V>) -> K:
10	  match e:
11	    case Entry{k, v}:
12	      k
13	
14	def val(-K: Data, -V: Data, e: Entry<K, V>) -> V:
15	  match e:
16	    case Entry{k, v}:
17	      v
18	
19	type Error is Data:
20	  KeyNotFound{}
21	  EmptyTree{}
22	
23	type Op<-K: Data, -V: Data> is Data:
24	  Length{}
25	  Insert{key: K, val: V}
26	  Remove{key: K}
27	  Lookup{key: K}
28	  Contains{key: K}
29	  Min{}
30	  Max{}
31	  LowerBound{key: K}
32	  Range{lo: K, hi: K}
33	  ToList{}
34	
35	type Obs<-K: Data, -V: Data> is Data:
36	  ONat{value: Nat}
37	  OUnit{}
38	  OBool{value: Bool}
39	  OVal{result: Result<&2, &2, Error, V>}
40	  OEntry{result: Result<&2, &2, Error, Entry<K, V>>}
41	  OList{entries: List<&2, Entry<K, V>>}