summaryrefslogtreecommitdiff
path: root/lib/heap.ml
diff options
context:
space:
mode:
authorGravatar Stephane Glondu <steph@glondu.net>2010-07-21 09:46:51 +0200
committerGravatar Stephane Glondu <steph@glondu.net>2010-07-21 09:46:51 +0200
commit5b7eafd0f00a16d78f99a27f5c7d5a0de77dc7e6 (patch)
tree631ad791a7685edafeb1fb2e8faeedc8379318ae /lib/heap.ml
parentda178a880e3ace820b41d38b191d3785b82991f5 (diff)
Imported Upstream snapshot 8.3~beta0+13298
Diffstat (limited to 'lib/heap.ml')
-rw-r--r--lib/heap.ml56
1 files changed, 28 insertions, 28 deletions
diff --git a/lib/heap.ml b/lib/heap.ml
index 92aa0070..7ddb4a72 100644
--- a/lib/heap.ml
+++ b/lib/heap.ml
@@ -6,7 +6,7 @@
(* * GNU Lesser General Public License Version 2.1 *)
(************************************************************************)
-(* $Id: heap.ml 5920 2004-07-16 20:01:26Z herbelin $ *)
+(* $Id$ *)
(*s Heaps *)
@@ -16,35 +16,35 @@ module type Ordered = sig
end
module type S =sig
-
+
(* Type of functional heaps *)
type t
(* Type of elements *)
type elt
-
+
(* The empty heap *)
val empty : t
-
+
(* [add x h] returns a new heap containing the elements of [h], plus [x];
complexity $O(log(n))$ *)
val add : elt -> t -> t
-
+
(* [maximum h] returns the maximum element of [h]; raises [EmptyHeap]
when [h] is empty; complexity $O(1)$ *)
val maximum : t -> elt
-
+
(* [remove h] returns a new heap containing the elements of [h], except
- the maximum of [h]; raises [EmptyHeap] when [h] is empty;
- complexity $O(log(n))$ *)
+ the maximum of [h]; raises [EmptyHeap] when [h] is empty;
+ complexity $O(log(n))$ *)
val remove : t -> t
-
+
(* usual iterators and combinators; elements are presented in
arbitrary order *)
val iter : (elt -> unit) -> t -> unit
-
+
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
-
+
end
exception EmptyHeap
@@ -54,9 +54,9 @@ exception EmptyHeap
module Functional(X : Ordered) = struct
(* Heaps are encoded as complete binary trees, i.e., binary trees
- which are full expect, may be, on the bottom level where it is filled
- from the left.
- These trees also enjoy the heap property, namely the value of any node
+ which are full expect, may be, on the bottom level where it is filled
+ from the left.
+ These trees also enjoy the heap property, namely the value of any node
is greater or equal than those of its left and right subtrees.
There are 4 kinds of complete binary trees, denoted by 4 constructors:
@@ -68,7 +68,7 @@ module Functional(X : Ordered) = struct
and [PFP] for a partial tree with a full left subtree and a partial
right subtree. *)
- type t =
+ type t =
| Empty
| FFF of t * X.t * t (* full (full, full) *)
| PPF of t * X.t * t (* partial (partial, full) *)
@@ -78,7 +78,7 @@ module Functional(X : Ordered) = struct
type elt = X.t
let empty = Empty
-
+
(* smart constructors for insertion *)
let p_f l x r = match l with
| Empty | FFF _ -> PFF (l, x, r)
@@ -89,7 +89,7 @@ module Functional(X : Ordered) = struct
| r -> PFP (l, x, r)
let rec add x = function
- | Empty ->
+ | Empty ->
FFF (Empty, x, Empty)
(* insertion to the left *)
| FFF (l, y, r) | PPF (l, y, r) ->
@@ -113,9 +113,9 @@ module Functional(X : Ordered) = struct
| r -> PFP (l, x, r)
let rec remove = function
- | Empty ->
+ | Empty ->
raise EmptyHeap
- | FFF (Empty, _, Empty) ->
+ | FFF (Empty, _, Empty) ->
Empty
| PFF (l, _, Empty) ->
l
@@ -124,30 +124,30 @@ module Functional(X : Ordered) = struct
let xl = maximum l in
let xr = maximum r in
let l' = remove l in
- if X.compare xl xr >= 0 then
- p_f l' xl r
- else
+ if X.compare xl xr >= 0 then
+ p_f l' xl r
+ else
p_f l' xr (add xl (remove r))
(* remove on the right *)
| FFF (l, x, r) | PFP (l, x, r) ->
let xl = maximum l in
let xr = maximum r in
let r' = remove r in
- if X.compare xl xr > 0 then
+ if X.compare xl xr > 0 then
pf_ (add xr (remove l)) xl r'
- else
+ else
pf_ l xr r'
let rec iter f = function
- | Empty ->
+ | Empty ->
()
- | FFF (l, x, r) | PPF (l, x, r) | PFF (l, x, r) | PFP (l, x, r) ->
+ | FFF (l, x, r) | PPF (l, x, r) | PFF (l, x, r) | PFP (l, x, r) ->
iter f l; f x; iter f r
let rec fold f h x0 = match h with
- | Empty ->
+ | Empty ->
x0
- | FFF (l, x, r) | PPF (l, x, r) | PFF (l, x, r) | PFP (l, x, r) ->
+ | FFF (l, x, r) | PPF (l, x, r) | PFF (l, x, r) | PFP (l, x, r) ->
fold f l (fold f r (f x x0))
end