Created
December 18, 2013 09:34
-
-
Save voila/8019658 to your computer and use it in GitHub Desktop.
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 Printf | |
module type Ord = | |
sig | |
type t | |
val lt : t -> t -> bool | |
val lte : t -> t -> bool | |
val eq : t -> t -> bool | |
val succ : t -> t | |
end | |
module IntOrd : Ord with type t = int = | |
struct | |
type t = int | |
let lt = (<) | |
let lte = (<=) | |
let eq = (=) | |
let succ x = (* 1001 *) x + 1 | |
end | |
module type Set = | |
sig | |
type elem | |
type set | |
val empty : set | |
val insert : elem -> set -> set | |
val member : elem -> set -> bool | |
end | |
module UnbalSet(Elt : Ord) : Set with type elem = Elt.t = | |
struct | |
type elem = Elt.t | |
type 'a tree = | |
Leaf | |
| Node of 'a tree * 'a * 'a tree | |
type set = elem tree | |
exception Error of string | |
let empty = Leaf | |
(* if the x exists in t, we raise an exception and return t *) | |
let insert x t = | |
(* 1001 *) let rec insert_exn x z = function | |
| Leaf -> | |
(* 1001 *) if x = z then raise (Error "already inserted") | |
else Node (Leaf, x, Leaf) | |
| Node (a, y, b) -> | |
(* 500500 *) if Elt.lt x y then Node (insert_exn x z a, y, b) | |
else Node (a, y, insert_exn x y b) | |
in try insert_exn x (Elt.succ x) t (* so we're sure x <> z *) | |
with Error s -> print_endline s; t | |
(* we assume x is strictly < or > to any node value | |
when we reach a leaf we check x equality with the last node | |
x was superior to, z *) | |
let member x s = | |
(* 1 *) let rec member_aux x s z = | |
(* 1001 *) match s with | |
| Leaf -> x = z | |
| Node(a, y, b) -> | |
if Elt.lt x y then | |
member_aux x a z | |
(* could be x = y, but we assume x > y, and pass down y | |
so we can do check if x = y, when we reach a Leaf *) | |
else | |
member_aux x b y | |
in | |
match s with | |
| Leaf -> false | |
| Node(_, y, _) -> member_aux x s y | |
end | |
module IntSet = UnbalSet (IntOrd) | |
let insert_ordered n s = | |
(* 1 *) for i = 1 to n do | |
(* print_int i; *) | |
s := (IntSet.insert i !s) | |
done | |
let insert_random n max s = | |
(* 1 *) for i = 1 to n do | |
(* print_int i; *) | |
s := (IntSet.insert (Random.int max) !s) | |
done | |
(* | |
ocamlcp -p f chap2_4.ml -o chap2_4 | |
ocamlrun chap2_4 | |
ocamlprof chap2_4.ml > chap2_4_prof.ml | |
*) | |
let main () = | |
(* 1 *) let s = (ref IntSet.empty) in | |
insert_random 10000 100000 s | |
(* | |
let res = IntSet.member 1001 !s in | |
print_endline (string_of_bool res); | |
IntSet.insert 1000 !s | |
*) | |
let _ = main () |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment