Add Vylist.complement for calculating difference between two lists

where one contains another (starting with the first element).

3 files changed, 29 insertions, 0 deletions

diff --git a/src/vylist.ml b/src/vylist.ml
index ec04055..f18801e 100644
--- a/src/vylist.ml
+++ b/src/vylist.ml
@@ -27,3 +27,14 @@ let rec insert_after p x xs =
     | [] -> raise Not_found
     | y :: ys -> if (p y) then y :: x :: ys
                  else y :: (insert_after p x ys)
+
+let complement xs ys =
+    let rec aux xs ys =
+        match xs, ys with
+        | [], _ -> Some ys
+        | _, [] -> assert false (* Can't happen *)
+        | p :: ps, q :: qs -> if p = q then aux ps qs
+                              else None
+    in
+    if List.length xs < List.length ys then aux xs ys
+    else aux ys xs
diff --git a/src/vylist.mli b/src/vylist.mli
index 70f0042..9a713b3 100644
--- a/src/vylist.mli
+++ b/src/vylist.mli
@@ -3,3 +3,4 @@ val remove : ('a -> bool) -> 'a list -> 'a list
 val replace : ('a -> bool) -> 'a -> 'a list -> 'a list
 val insert_before : ('a -> bool) -> 'a -> 'a list -> 'a list
 val insert_after : ('a -> bool) -> 'a -> 'a list -> 'a	list
+val complement : 'a list -> 'a list -> 'a list option
diff --git a/test/vylist_test.ml b/test/vylist_test.ml
index c27aa5c..45336bb 100644
--- a/test/vylist_test.ml
+++ b/test/vylist_test.ml
@@ -41,6 +41,20 @@ let test_insert_before_nonexistent test_ctxt =
     let xs = [1; 2; 3] in
      assert_raises Not_found (fun () -> insert_before ((=) 9) 7 xs)
 
+(* complement returns correct result when one list contains another, in any order *)
+let test_complement_first_is_longer test_ctxt =
+    let xs = [1;2;3;4;5] and ys = [1;2;3] in
+    assert_equal (complement xs ys) (Some [4;5])
+
+let test_complement_second_is_longer test_ctxt =
+    let	xs = [1;2] and ys = [1;2;3;4;5] in
+    assert_equal (complement xs	ys) (Some [3;4;5])
+
+(* complement returns None if one list doesn't contain another *)
+let test_complement_doesnt_contain test_ctxt =
+    let xs = [1;2;3] and ys = [1;4;5;6] in
+    assert_equal (complement xs ys) None
+
 let suite =
     "VyConf list tests" >::: [
         "test_find_existent" >:: test_find_existent;
@@ -51,6 +65,9 @@ let suite =
         "test_replace_element_nonexistent" >:: test_replace_element_nonexistent;
         "test_insert_before_existent" >:: test_insert_before_existent;
         "test_insert_before_nonexistent" >:: test_insert_before_nonexistent;
+        "test_complement_first_is_longer" >:: test_complement_first_is_longer;
+        "test_complement_second_is_longer" >:: test_complement_second_is_longer;
+        "test_complement_doesnt_contain" >:: test_complement_doesnt_contain;
     ]
 
 let () =