fact: Fixpoint twothree_modify (m : twothree V) {T} (k_ok : twothree V -> T) (k_splice_up : twothree V -> K -> V -> twothree V -> T) {struct m} : T := match m with | Leaf => match def with | Some v => k_splice_up Leaf k v Leaf | None => k_ok Leaf end | Two l k' v' r => match RD_K k k' with | Eq => match upd v' with | Some v' => k_ok (Two l k v' r) | None => remove_greatest l (fun _ => k_ok r) (fun k v l => k_ok (Two l k v r)) end | Lt => twothree_modify l (fun l => k_ok (Two l k' v' r)) (fun l'' k'' v'' r'' => k_ok (Three l'' k'' v'' r'' k' v' r)) | Gt => twothree_modify r (fun r => k_ok (Two l k' v' r)) (fun l'' k'' v'' r'' => k_ok (Three l k' v' l'' k'' v'' r'')) end | Three l k1 v1 m k2 v2 r => match RD_K k k1 with | Eq => match upd v1 with | Some v' => k_ok (Three l k v' m k2 v2 r) | None => remove_greatest l (fun _ => k_ok (Two m k2 v2 r)) (fun k1 v1 l => k_ok (Three l k1 v2 m k2 v2 r)) end | Lt => twothree_modify l (fun l' => k_ok (Three l' k1 v1 m k2 v2 r)) (fun l' k' v' r' => k_splice_up (Two l' k' v' r') k1 v1 (Two m k2 v2 r)) | Gt => match RD_K k k2 with | Eq => match upd v2 with | Some v2 => k_ok (Three l k1 v1 m k v2 r) | None => remove_greatest m (fun _ => k_ok (Two l k1 v1 r)) (fun k' v' m' => k_ok (Three l k1 v1 m' k' v' r)) end | Lt => twothree_modify m (fun m' => k_ok (Three l k1 v1 m' k2 v2 r)) (fun l' k' v' r' => k_splice_up (Two l k1 v1 l') k' v' (Two r' k2 v2 r)) | Gt => twothree_modify r (fun r' => k_ok (Three l k1 v1 m k2 v2 r')) (fun l' k' v' r' => k_splice_up (Two l k1 v1 m) k2 v2 (Two l' k' v' r')) end end end.
imports: Coq.Lists.List ExtLib.Core.RelDec ExtLib.Structures.Maps ExtLib.Structures.Monads ExtLib.Structures.Reducible