fact: Fixpoint ecompare (m1 m2: t A) : (comparison * flag) := match m1, m2 with | Leaf, _ => if is_empty m2 then (Eq,EOL) else (Lt,EOL) | _, Leaf => if is_empty m1 then (Eq,EOL) else (Gt,EOL) | Node l1 o1 r1, Node l2 o2 r2 => match ecompare l1 l2 with | (Eq,_) => match o1, o2 with | None, None => ecompare r1 r2 | Some d1, Some d2 => elex (cmp d1 d2) (ecompare r1 r2) | None, Some _ => if is_empty r1 then (Lt,EOL) else (Gt,Early) | Some _, None => if is_empty r2 then (Gt,EOL) else (Lt,Early) end | (c,Early) => (c,Early) | (Lt,EOL) => if is_empty2 o1 r1 then (Lt,EOL) else (Gt,Early) | (Gt,EOL) => if is_empty2 o2 r2 then (Gt,EOL) else (Lt,Early) end end.
imports: Coq(Bool PeanoNat BinPos Orders OrdersEx OrdersLists) MMaps(Utils Comparisons Interface)