#5864: add a find operation to Set.

git-svn-id: http://caml.inria.fr/svn/ocaml/trunk@13211 f963ae5c-01c2-4b8c-9fe0-0dff7051ff02

3 files changed, 12 insertions, 0 deletions

diff --git a/stdlib/moreLabels.mli b/stdlib/moreLabels.mli
index 5037ce484..bc15cb4bf 100644
--- a/stdlib/moreLabels.mli
+++ b/stdlib/moreLabels.mli
@@ -159,6 +159,7 @@ module Set : sig
       val max_elt : t -> elt
       val choose : t -> elt
       val split: elt -> t -> t * bool * t
+      val find: elt -> t -> elt
     end
   module Make : functor (Ord : OrderedType) -> S with type elt = Ord.t
 end
diff --git a/stdlib/set.ml b/stdlib/set.ml
index 262629253..4e1f4be8c 100644
--- a/stdlib/set.ml
+++ b/stdlib/set.ml
@@ -47,6 +47,7 @@ module type S =
     val max_elt: t -> elt
     val choose: t -> elt
     val split: elt -> t -> t * bool * t
+    val find: elt -> t -> elt
   end
 
 module Make(Ord: OrderedType) =
@@ -348,4 +349,10 @@ module Make(Ord: OrderedType) =
 
     let choose = min_elt
 
+    let rec find x = function
+        Empty -> raise Not_found
+      | Node(l, v, r, _) ->
+          let c = Ord.compare x v in
+          if c = 0 then v
+          else find x (if c < 0 then l else r)
   end
diff --git a/stdlib/set.mli b/stdlib/set.mli
index 22bb455a8..a7ee6b6cd 100644
--- a/stdlib/set.mli
+++ b/stdlib/set.mli
@@ -143,6 +143,10 @@ module type S =
           strictly greater than [x];
           [present] is [false] if [s] contains no element equal to [x],
           or [true] if [s] contains an element equal to [x]. *)
+
+    val find: elt -> t -> elt
+    (** [find x s] returns the element of [s] equal to [x], or raise
+        [Not_found] if no such element exists. *)
   end
 (** Output signature of the functor {!Set.Make}. *)