(* to avoid the need of -rectypes *)
type tree = Foo of (string * tree) list

let rec add_path t l = 
  match l with 
  | [] -> t (* no more path to add *)
  | name::tl -> add_path_aux t name tl

and add_path_aux t name tl =
  match t with
  | Foo [] -> Foo [(name, add_path (Foo []) tl)]
  | Foo ((n, t')::bro) when n = name -> Foo ((n, (add_path t' tl))::bro)
  | Foo (((n, t') as x)::bro) -> 
      let tmp = add_path_aux (Foo bro) name tl in
      match tmp with Foo y -> Foo (x::y)
      
let rec get_frontier t l = 
  match l with 
  | [] -> (match t with Foo bla -> 
            List.map (function (x,Foo []) -> x | (x,_) -> (x^"/")) bla)
  | name::tl -> get_frontier_aux t name tl

and get_frontier_aux (t:tree) name tl =
  match t with
  | Foo [] -> []
  | Foo ((n, t')::bro) when Pcre.pmatch ~pat:("^" ^ name ^ "$") n -> 
      (* since regex are no more "unique" matches, we have to continue 
       * searching on the brothers.
       *)
      get_frontier t' tl @ get_frontier_aux (Foo bro) name tl
  | Foo (_::bro) -> get_frontier_aux (Foo bro) name tl
 
let rec remove_path t path =
  match path with
  | [] -> t
  | name::tl -> remove_path_aux t name tl
      
and remove_path_aux t name tl =
  match t with
  | Foo [] -> assert false 
  | Foo ((n, t')::bro) when n = name -> 
      let tmp = remove_path t' tl in
      (match tmp with
      | Foo [] -> Foo bro
      | Foo x -> Foo ((n, Foo x)::bro))
  | Foo (((n, t') as x)::bro) ->
      let tmp = remove_path_aux (Foo bro) name tl in
      match tmp with Foo y -> Foo (x::y)
  
let split_RE = Pcre.regexp "/"
  
let empty_tree = Foo []

let add_uri suri t =  
  let s = (Pcre.split ~rex:split_RE suri) in
  add_path t s
  
let ls_path path t =
  let s = (Pcre.split ~rex:split_RE path) in
  get_frontier t s

let remove_uri suri t =
  let s = (Pcre.split ~rex:split_RE suri) in
  remove_path t s
  
let save_to_disk path t =
  let o = open_out path in
  Marshal.to_channel o t [];
  close_out o

let load_from_disk path =
  let i = open_in path in
  let t = Marshal.from_channel i in
  close_in i;
  t