1	import Base
2	import ./Keys.bend as Keys
3	import ./MemTable.bend as MemTable
4	import ./Sstable.bend as Sstable
5	import ./SortedRun.bend as SortedRun
6	
7	# Merge iterator (Task 6): concat sources (memtable newest-first, then
8	# SSTables newest-level-first) and canonicalize with balanced stable merge;
9	# first-inserted wins ties = newest wins). The range+tombstone filter is
10	# pump+fuel+leaf: String.cmp hands both strings back beside the verdict,
11	# so the key survives the keep/drop decision with no clone primitive.
12	# Order of defs is load-bearing (Bend 2: only backward references).
13	
14	# Scan put2 for the sorted merge iterator.
15	def scan_put2(pair: (String & String) & Cmp, +val: String, acc: List<&2, MemTable.Entry>) -> List<&2, MemTable.Entry>:
16	  match pair:
17	    case ((k3, _), c):
18	      match c:
19	        case LT{}:
20	          Con{MemTable.Entry{k3, Some{val}}, acc}
21	        case EQ{}:
22	          acc
23	        case GT{}:
24	          acc
25	
26	# Scan put for the sorted merge iterator.
27	def scan_put(
28	  pair: (String & String) & Cmp,
29	  +hi: String,
30	  +val: String,
31	  acc: List<&2, MemTable.Entry>
32	) -> List<&2, MemTable.Entry>:
33	  match pair:
34	    case ((k2, _), c):
35	      match c:
36	        case LT{}:
37	          acc
38	        case EQ{}:
39	          scan_put2(String.cmp(k2, hi), val, acc)
40	        case GT{}:
41	          scan_put2(String.cmp(k2, hi), val, acc)
42	
43	# Scan go for the sorted merge iterator.
44	def scan_go(
45	  fuel: Nat,
46	  +lo: String,
47	  +hi: String,
48	  acc: List<&2, MemTable.Entry>,
49	  xs: List<&2, MemTable.Entry>
50	) -> List<&2, MemTable.Entry>:
51	  match fuel:
52	    case 0n:
53	      List.reverse(&2, MemTable.Entry, acc)
54	    case 1n+f:
55	      match xs:
56	        case Nil{}:
57	          List.reverse(&2, MemTable.Entry, acc)
58	        case Con{MemTable.Entry{key, val}, t}:
59	          match val:
60	            case None{}:
61	              scan_go(f, lo, hi, acc, t)
62	            case Some{v}:
63	              scan_go(f, lo, hi, scan_put(String.cmp(key, lo), hi, v, acc), t)
64	
65	# Newest-first concat: memtable entries, then each level's tables in order.
66	def flatten(mem: List<&2, MemTable.Entry>, levels: List<&2, List<&2, MemTable.Entry>>) -> List<&2, MemTable.Entry>:
67	  match levels:
68	    case Nil{}:
69	      mem
70	    case Con{h, t}:
71	      List.append(&2, MemTable.Entry, mem, List.concat(&2, MemTable.Entry, Con{h, t}))
72	
73	# Full merge: sorted, unique, newest version wins each key.
74	def merge(mem: List<&2, MemTable.Entry>, levels: List<&2, List<&2, MemTable.Entry>>) -> List<&2, MemTable.Entry>:
75	  SortedRun.sort_newest(flatten(mem, levels))
76	
77	# Range scan over a merged run: lo <= key < hi, tombstones dropped.
78	def scan(+merged: List<&2, MemTable.Entry>, lo: String, hi: String) -> List<&2, MemTable.Entry>:
79	  scan_go(List.length(&2, MemTable.Entry, merged), lo, hi, Nil{}, merged)
80	
81	# --- Closed-vector laws live in laws/MergeIter.bend (spec laws 4, 5, 10) ---