Better memory management

3 files changed, 269 insertions, 8 deletions

diff --git a/tests/sheet_test.ml b/tests/sheet_test.ml
index 9218134..3960c4b 100755
--- a/tests/sheet_test.ml
+++ b/tests/sheet_test.ml
@@ -66,6 +66,22 @@ let test_create_direct_cycle ctx = begin
     result
 end
 
+(** Overide the value after a cycle. *)
+let test_recover_from_cycle ctx = begin
+
+  let s = Sheet.Raw.empty
+       |> Sheet.Raw.add (2,2) @@ Expression.load @@ u"=B2 + 1"
+       |> snd |> Sheet.Raw.add (2,2) @@ Expression.load @@ u"=6"
+       |> snd in
+  let result = (Sheet.Raw.get_value (2, 2) s) in
+  let expected = Some (ScTypes.Result (build_num (6))) in
+
+  assert_equal
+    ~msg:(_msg ~expected ~result)
+    expected
+    result
+end
+
 let test_create_indirect_cycle ctx = begin
 
   let s = Sheet.Raw.empty
@@ -160,13 +176,57 @@ let test_update_succs2 ctx = begin
     result
 end
 
+let test_paste_undo ctx = begin
+
+  let empty = Sheet.create Sheet.Raw.empty in
+
+  (* The expected result for the whole test *)
+  let expected = Some (ScTypes.Result (ScTypes.number (DataType.Num.of_int 6))) in
+
+  let sheet = empty
+      |> Tools.Option.test @@ Sheet.move (Actions.Absolute (2, 1))
+      |> Sheet.add (Expression.load @@ u"=6")
+      |> snd
+      |> Tools.Option.test @@ Sheet.move (Actions.Absolute (1, 1))
+      |> Sheet.add (Expression.load @@ u"=B1")
+      |> snd in
+  let result = Sheet.Raw.get_value (1, 1) sheet.Sheet.data in
+
+  (* Ensure the value is correctly evaluated *)
+  assert_equal
+    ~msg:(_msg ~expected ~result)
+    expected
+    result;
+
+  let sheet2 =
+    (* Copy the cell *)
+       fst @@ Sheet.yank sheet
+    |> Tools.Option.test @@ Sheet.move (Actions.Absolute (2, 1))
+    (* Paste it on another value *)
+    |> Sheet.paste
+    |> fst
+    (* Undo the paste *)
+    |> Tools.Option.test @@ Sheet.undo in
+
+  let result = Sheet.Raw.get_value (1, 1) sheet2.Sheet.data in
+
+  (* The value should be the same as the first evaluation *)
+  assert_equal
+    ~msg:(_msg ~expected ~result)
+    expected
+    result
+
+end
+
 let tests = "sheet_test">::: [
-    "test_ref1"     >:: test_create_ref_1;
-    "test_ref2"     >:: test_create_ref_2;
-    "test_cycle1"   >:: test_create_direct_cycle;
-    "test_cycle2"   >:: test_create_indirect_cycle;
-    "test_cycle3"   >:: test_check_cycle3;
-    "test_delete"   >:: test_delete;
-    "test_update_succs1"   >:: test_update_succs1;
-    "test_update_succs2"   >:: test_update_succs2;
+  "test_ref1"           >:: test_create_ref_1;
+  "test_ref2"           >:: test_create_ref_2;
+  "test_cycle1"         >:: test_create_direct_cycle;
+  "test_recover_cycle"  >:: test_recover_from_cycle;
+  "test_cycle2"         >:: test_create_indirect_cycle;
+  "test_cycle3"         >:: test_check_cycle3;
+  "test_delete"         >:: test_delete;
+  "test_update_succs1"  >:: test_update_succs1;
+  "test_update_succs2"  >:: test_update_succs2;
+  "test_paste_undo"     >:: test_paste_undo;
  ]
diff --git a/tests/test.ml b/tests/test.ml
index 2d881ca..ee71cb0 100755
--- a/tests/test.ml
+++ b/tests/test.ml
@@ -9,6 +9,7 @@ let () =
     Expression_test.tests;
     Sheet_test.tests;
     Odf_ExpressionParser_test.tests;
+    Splay_test.tests;
   ]
   in OUnit2.run_test_tt_main tests
 
diff --git a/tests/tree/splay_test.ml b/tests/tree/splay_test.ml
new file mode 100755
index 0000000..3f5fa96
--- /dev/null
+++ b/tests/tree/splay_test.ml
@@ -0,0 +1,200 @@
+open OUnit2

+

+(** Module for the keys *)

+module K = struct

+

+  type 'a t = Int : int -> int t [@@unboxed]

+

+  let comp:type a b. a t -> b t -> (a, b) Tools.cmp = fun a b -> begin

+    match a, b with Int a, Int b ->

+

+    if a < b then

+      Tools.Lt

+    else if a > b then

+      Tools.Gt

+    else

+      Tools.Eq

+  end

+

+  let repr: type a. Format.formatter -> a t -> unit = fun formatter (Int a) ->

+    Format.fprintf formatter "%d" a

+

+end

+

+module SplayTest = Splay.Make(K)

+

+let test_add ctx = begin

+

+  let tree =

+     SplayTest.empty

+  |> SplayTest.add (K.Int 1) (-1)

+  |> SplayTest.add (K.Int 3) 2

+  |> SplayTest.add (K.Int 5) 2

+  |> SplayTest.add (K.Int 4) 1 in

+

+  let formatter = Format.str_formatter in

+  SplayTest.repr formatter tree;

+  let str = Format.flush_str_formatter () in

+

+  let expected = "digraph G {\n\

+    \"4\" -> \"3\"\n\

+    \"3\" -> \"1\"\n\

+    \"4\" -> \"5\"\n\

+    }" in

+  let result = str in

+

+  let msg = Printf.sprintf "Expected %s, but got %s." expected result in

+

+  assert_equal

+    ~msg

+    expected

+    result

+end

+

+let test_removeLeaf ctx = begin

+

+  let tree =

+     SplayTest.empty

+  |> SplayTest.remove (K.Int 4)

+  in

+

+  let formatter = Format.str_formatter in

+  SplayTest.repr formatter tree;

+  let str = Format.flush_str_formatter () in

+

+  let expected = "digraph G {}" in

+  let result = str in

+

+  let msg = Printf.sprintf "Expected %s, but got %s." expected result in

+

+  assert_equal

+    ~msg

+    expected

+    result

+end

+

+let test_removeTop ctx = begin

+

+  let tree =

+     SplayTest.empty

+  |> SplayTest.add (K.Int 1) (-1)

+  |> SplayTest.add (K.Int 3) 2

+  |> SplayTest.add (K.Int 5) 2

+  |> SplayTest.add (K.Int 4) 1

+  |> SplayTest.remove (K.Int 4)

+  in

+

+  let formatter = Format.str_formatter in

+  SplayTest.repr formatter tree;

+  let str = Format.flush_str_formatter () in

+

+  let expected = "digraph G {\n\

+    \"3\" -> \"1\"\n\

+    \"3\" -> \"5\"\n\

+    }" in

+  let result = str in

+

+  let msg = Printf.sprintf "Expected %s, but got %s." expected result in

+

+  assert_equal

+    ~msg

+    expected

+    result

+end

+

+let test_removeLeft ctx = begin

+  let tree =

+     SplayTest.empty

+  |> SplayTest.add (K.Int 1) (-1)

+  |> SplayTest.add (K.Int 3) 2

+  |> SplayTest.add (K.Int 5) 2

+  |> SplayTest.add (K.Int 4) 1

+  |> SplayTest.remove (K.Int 3)

+  in

+

+  let formatter = Format.str_formatter in

+  SplayTest.repr formatter tree;

+  let str = Format.flush_str_formatter () in

+

+  let expected = "digraph G {\n\

+    \"1\" -> \"4\"\n\

+    \"4\" -> \"5\"\n\

+    }" in

+  let result = str in

+

+  let msg = Printf.sprintf "Expected %s, but got %s." expected result in

+

+  assert_equal

+    ~msg

+    expected

+    result

+end

+

+(** Remove a value not present in the tree.

+  The tree shall be rebalanced. *)

+let test_removeOutMax ctx = begin

+  let tree =

+     SplayTest.empty

+  |> SplayTest.add (K.Int 1) (-1)

+  |> SplayTest.add (K.Int 3) 2

+  |> SplayTest.add (K.Int 5) 2

+  |> SplayTest.add (K.Int 4) 1

+  |> SplayTest.remove (K.Int 6)

+  in

+

+  let formatter = Format.str_formatter in

+  SplayTest.repr formatter tree;

+  let str = Format.flush_str_formatter () in

+

+  let expected = "digraph G {\n\

+    \"5\" -> \"4\"\n\

+    \"4\" -> \"3\"\n\

+    \"3\" -> \"1\"\n\

+    }" in

+  let result = str in

+

+  let msg = Printf.sprintf "Expected %s, but got %s." expected result in

+

+  assert_equal

+    ~msg

+    expected

+    result

+end

+

+(** Remove the maximum value in the tree *)

+let test_removeMax ctx = begin

+  let tree =

+     SplayTest.empty

+  |> SplayTest.add (K.Int 1) (-1)

+  |> SplayTest.add (K.Int 3) 2

+  |> SplayTest.add (K.Int 5) 2

+  |> SplayTest.add (K.Int 4) 1

+  |> SplayTest.remove (K.Int 5)

+  in

+

+  let formatter = Format.str_formatter in

+  SplayTest.repr formatter tree;

+  let str = Format.flush_str_formatter () in

+

+  let expected = "digraph G {\n\

+    \"4\" -> \"3\"\n\

+    \"3\" -> \"1\"\n\

+    }" in

+  let result = str in

+

+  let msg = Printf.sprintf "Expected %s, but got %s." expected result in

+

+  assert_equal

+    ~msg

+    expected

+    result

+end

+

+let tests = "splay_test">::: [

+  "add"           >:: test_add;

+  "removeLeaf"    >:: test_removeLeaf;

+  "removeTop"     >:: test_removeTop;

+  "removeLeft"    >:: test_removeLeft;

+  "removeMax"     >:: test_removeMax;

+  "removeOutMax"  >:: test_removeOutMax;

+]