Commits

David Powers committed deaa654

simple test harness

Comments (0)

Files changed (6)

+#!/usr/bin/env bash
+
+ocamlopt -c map_intf.ml
+ocamlopt -c unbalanced_tree.ml
+ocamlopt -c treap.ml
+ocamlopt map_intf.cmx treap.cmx unbalanced_tree.cmx test_harness.ml -o test

low/trees/map_interface.ml

-module type S = sig
-  type 'a t
-
-  val empty : t
-
-  val find : 'a t -> 'a -> 'a option
-  val insert : 'a t -> 'a -> 'a t
-  val remove : 'a t -> 'a -> 'a t
-end

low/trees/map_intf.ml

+module type S = sig
+  type 'a t
+
+  val name : string
+
+  val empty : 'a t
+
+  val find : 'a t -> 'a -> 'a option
+  val insert : 'a t -> 'a -> 'a t
+  val remove : 'a t -> 'a -> 'a t
+end

low/trees/test_harness.ml

-module Data_generator : sig
+module List = ListLabels
+
+module Generator : sig
   type t
 
   val create : init:(unit -> 'state) -> ('state -> int * 'state) -> t
   val reset : t -> unit
   val next : t -> int
+  val iter_n : t -> int -> (int -> unit) -> unit
+  val fold_n : t -> int -> init:'a -> ('a -> int -> 'a) -> 'a
 end = struct
   type t =
     {
 
   let reset t = t.reset ()
   let next t = t.next ()
+
+  let fold_n t n ~init f =
+    let rec loop acc n =
+      if n = 0 then acc
+      else loop (f acc (next t)) (n - 1)
+    in
+    loop init n
+  ;;
+
+  let iter_n t n f =
+    let f () n = f n in
+    fold_n t n ~init:() f
+  ;;
 end
 
-let in_order      = Data_generator.create ~init:(fun () -> 0) (fun v -> v, v + 1)
-let reverse_order = Data_generator.create ~init:(fun () -> max_int) (fun v -> v, v - 1)
+let in_order      = Generator.create ~init:(fun () -> 0) (fun v -> v, v + 1)
+let reverse_order = Generator.create ~init:(fun () -> max_int) (fun v -> v, v - 1)
 
 let random =
   let init () = Random.State.make [| 1; 7; 23; 4 |] in
-  Data_generator.create ~init (fun s -> Random.State.bits s, s)
+  Generator.create ~init (fun s -> Random.State.bits s, s)
 ;;
+
+module Test : sig
+  type t
+
+  val run : t -> (module Map_intf.S) -> unit
+  val create : name:string -> ((module Map_intf.S) -> unit) -> t
+end = struct
+  type t = {
+    name : string;
+    f : (module Map_intf.S) -> unit
+  }
+
+  let create ~name f = { name; f }
+
+  let run t map_module =
+    let module Map = (val map_module : Map_intf.S) in
+    Printf.printf "running: %s on %s\n" t.name Map.name;
+    t.f map_module
+  ;;
+end
+
+let tests = [
+  Test.create "in-order insert" (fun map_module ->
+    let module Map = (val map_module : Map_intf.S) in
+    let _ =
+      Generator.fold_n in_order 1_000 ~init:Map.empty (fun acc i -> Map.insert acc i)
+    in
+    ())
+]
+
+let map_modules = [
+  (module Treap : Map_intf.S);
+  (module Unbalanced_tree : Map_intf.S);
+]
+
+let run_tests () =
+  List.iter tests ~f:(fun test ->
+    List.iter map_modules ~f:(fun map -> Test.run test map))
+;;
+
+let () = run_tests ()
+
 (* Treap implementation *)
 
+let name = "treap"
+
 (* The first int in each branch holds a random number generated
    at the time of insertion *)
 type 'a t =
    determines a node for x should exist. Then, as long as x is not the root of the tree
    and has a larger priority number than its parent z, perform a tree rotation that
    reverses the parent-child relation between x and z. *)
-let rec add' t v =
+let rec insert' t v =
   match t with
   | Empty        ->
     Some (Leaf (Random.bits (), v))
     let c = compare v v' in
     if c = 0 then None
     else if c < 0 then
-      maybe_right_rotate (Node (rand, v', Empty, Empty)) (add' Empty v)
+      maybe_right_rotate (Node (rand, v', Empty, Empty)) (insert' Empty v)
     else
-      maybe_left_rotate (Node (rand, v', Empty, Empty)) (add' Empty v)
+      maybe_left_rotate (Node (rand, v', Empty, Empty)) (insert' Empty v)
   | Node (rand, v', l, r) ->
     let c = compare v v' in
     if c = 0 then None
     else if c < 0 then
-      maybe_right_rotate t (add' l v)
+      maybe_right_rotate t (insert' l v)
     else
-      maybe_left_rotate t (add' r v)
+      maybe_left_rotate t (insert' r v)
 ;;
 
-let add t v =
-  match add' t v with
+let insert t v =
+  match insert' t v with
   | None   -> t
   | Some t -> t
 ;;
   | Some t -> t
 ;;
 
-module type Map : sig
-  module type Key : sig
-    type t
-  end
-
-  type 'a t
-
-  val empty : 'a t
-
-  val find : 'a t -> Key.t -> 'a option
-  val add : 'a t -> key:Key.t -> data:'a -> 'a t
-  val remove : 'a t -> Key.t -> 'a t
-end
-
 let test () =
   Random.self_init ();
   let max = 10_000_000 in
   let rec loop acc n =
     if n = 0 then acc
-    else loop (add acc n) (n - 1)
+    else loop (insert acc n) (n - 1)
   in
   Printf.printf "adding\n%!";
   let t = loop empty max in
   loop t max
 ;;
 
-let () = test ()
-

low/trees/unbalanced_tree.ml

+let name = "unbalanced"
+
 type 'a t =
   | Empty
   | Node of 'a t * 'a * 'a t