From ade1687a786ec1f9a3222719d434de65948cdd83 Mon Sep 17 00:00:00 2001
From: Sebastien Ferre
Date: Tue, 2 May 2006 15:36:51 +0000
Subject: [PATCH] Add of operation 'find'.
---
setrie.ml | 36 ++++++++++++++++++++++++++++++++++--
1 file changed, 34 insertions(+), 2 deletions(-)
diff --git a/setrie.ml b/setrie.ml
index bf34414..3afe0bb 100644
--- a/setrie.ml
+++ b/setrie.ml
@@ -17,7 +17,7 @@ module type PATH =
val prefix_inter : t -> t -> t * t
end
-module PathLSet : PATH with type elt = int =
+module PathLSet : PATH with type elt = int and type t = int LSet.t =
struct
type elt = int
type t = elt LSet.t
@@ -236,7 +236,7 @@ module Make (Path : PATH) =
t
else if Path.is_empty xs1' then (* vopt must be set to None *)
if child = Nil then brother else Node (ys, None, child, brother)
- else (* element to be removed is in b *)
+ else (* element to be removed is in child *)
let child' = remove2 xs1' child in
if vopt = None && child' = Nil then brother else Node (ys, vopt, child', brother)
else if c < 0 then (* xs is not present *)
@@ -245,6 +245,35 @@ module Make (Path : PATH) =
let brother' = remove2 xs brother in
Node (ys, vopt, child, brother')
+ let rec find : 'b t -> Path.t -> 'b = (* may raise Not_found *)
+ fun (vopt,t) xs ->
+ if Path.is_empty xs
+ then find_vopt vopt
+ else find2 t xs
+ and find2 t xs =
+ if Path.is_empty xs
+ then raise Not_found
+ else
+ match t with
+ | Nil -> raise Not_found
+ | Node (ys, vopt, child, brother) ->
+ let c = Path.compare_head xs ys in
+ if c = 0 then
+ let prefix, xs1', ys1' = Path.prefix_zip xs ys in
+ if not (Path.is_empty ys1') then (* xs is not present *)
+ raise Not_found
+ else if Path.is_empty xs1' then (* result is vopt *)
+ find_vopt vopt
+ else (* result is in child *)
+ find2 child xs1'
+ else if c < 0 then (* xs is not present *)
+ raise Not_found
+ else (* c > 0 *) (* xs is in brother *)
+ find2 brother xs
+ and find_vopt = function
+ | Some v -> v
+ | None -> raise Not_found
+
let rec union : ('b -> 'b -> 'b) -> 'b t -> 'b t -> 'b t =
fun u (vopt1,tree1) (vopt2,tree2) ->
union_vopt u vopt1 vopt2, union2 u tree1 tree2
@@ -407,3 +436,6 @@ module Make (Path : PATH) =
| Some v -> f ys' v
end
+
+
+module Default = Make (PathLSet)
--
2.1.1