Created
February 8, 2019 04:52
-
-
Save ENAML/5a827bf3f725d5e3bd97cb6ae484f1b6 to your computer and use it in GitHub Desktop.
simple diffing of two ordered maps
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| open Base | |
| let left x = `Left(x) | |
| let right x = `Right(x) | |
| let change a b = `Change(a, b) | |
| let rec diff_seqs ?(acc = []) s0 s1 = | |
| let cmp = Poly.compare in | |
| let v_eq = Poly.equal in | |
| match Sequence.next s0, Sequence.next s1 with | |
| | None, None -> List.rev acc | |
| | Some(x0, s0_next), None -> diff_seqs s0_next s1 ~acc:((left x0)::acc) | |
| | None, Some(x1, s1_next) -> diff_seqs s0 s1_next ~acc:((right x1)::acc) | |
| | Some(x0, s0_next), Some(x1, s1_next) -> | |
| let (k0, v0), (k1, v1) = x0, x1 in | |
| let k_diff = cmp k0 k1 in | |
| if k_diff < 0 then (* left is lower *) | |
| diff_seqs s0_next s1 ~acc:((left x0)::acc) | |
| else if k_diff > 0 then (* right is lower *) | |
| diff_seqs s0 s1_next ~acc:((right x1)::acc) | |
| else begin (* equal *) | |
| if v_eq v0 v1 then | |
| diff_seqs s0_next s1_next ~acc:acc | |
| else | |
| diff_seqs s0_next s1_next ~acc:((change x0 x1)::acc) | |
| end | |
| (* simple diff_seqs test *) | |
| let () = | |
| let open Sequence in | |
| let s0 = of_list [(0, "a"); (1, "b"); (2, "c"); (3, "m"); (4, "n"); (5, "m")] in | |
| let s1 = of_list [(0, "a"); (1, "c"); (2, "c"); (4, "n"); (5, "m"); (6, "s")] in | |
| assert begin | |
| Poly.equal | |
| (diff_seqs s0 s1) | |
| [`Change ((1, "b"), (1, "c")); `Left (3, "m"); `Right (6, "s")] | |
| end | |
| let diff_map map0 map1 = | |
| let seq0, seq1 = Map.(to_sequence map0, to_sequence map1) in | |
| diff_seqs ~acc:[] seq0 seq1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment