From b83133cbbedbbd4de94e293e439a3e21476619ad Mon Sep 17 00:00:00 2001 From: Quentin Carbonneaux Date: Fri, 13 Feb 2015 22:37:07 -0500 Subject: attempt a new linear scan implementation --- lo3.ml | 58 ---------------------------------------------------------- 1 file changed, 58 deletions(-) delete mode 100644 lo3.ml (limited to 'lo3.ml') diff --git a/lo3.ml b/lo3.ml deleted file mode 100644 index 502fd57..0000000 --- a/lo3.ml +++ /dev/null @@ -1,58 +0,0 @@ -(* Generic binary heaps. *) -module Heap: sig - type 'a t - val create: ('a -> 'a -> int) -> 'a t - val add: 'a t -> 'a -> unit - val pop: 'a t -> 'a option - val top: 'a t -> 'a option -end = struct - type 'a t = - { mutable arr: 'a array - ; mutable len: int - ; cmp: 'a -> 'a -> int - } - - let mkarray n = Array.make n (Obj.magic 0) - let create cmp = {arr = mkarray 2; len = 0; cmp } - let top {arr; len; _} = - if len = 0 then None else Some arr.(1) - let swap arr i j = - let tmp = arr.(i) in - arr.(i) <- arr.(j); - arr.(j) <- tmp - - let rec bblup cmp arr i = - let prnt = i/2 in - if prnt = 0 then () else - if cmp arr.(prnt) arr.(i) < 0 then () else - (swap arr prnt i; bblup cmp arr prnt) - let add ({arr; len; cmp} as hp) x = - let arr = - let alen = Array.length arr in - if alen > len+1 then arr else - let arr' = mkarray (alen * 2) in - Array.blit arr 0 arr' 0 alen; - hp.arr <- arr'; - arr' in - hp.len <- len + 1; - arr.(hp.len) <- x; - bblup cmp arr hp.len - - let rec bbldn cmp arr i len = - let ch0 = 2*i in - let ch1 = ch0 + 1 in - if ch0 > len then () else - let mn = - if ch1 > len then ch0 else - if cmp arr.(ch0) arr.(ch1) < 0 - then ch0 else ch1 in - if cmp arr.(i) arr.(mn) <= 0 then () else - (swap arr i mn; bbldn cmp arr mn len) - let pop ({arr; len; cmp} as hp) = - if len = 0 then None else - let t = top hp in - arr.(1) <- arr.(len); - hp.len <- len - 1; - bbldn cmp arr 1 len; - t -end -- cgit 1.4.1