Source

ocamlspot / treeset.ml

camlspotter fb1f10e 





camlspotter d0e75b7 
camlspotter fb1f10e 
































camlspotter 8f146aa 
camlspotter fb1f10e 

















camlspotter 8f146aa 
camlspotter fb1f10e 














(***********************************************************************)
(*                                                                     *)
(*                            OCamlSpotter                             *)
(*                                                                     *)
(*                             Jun FURUSE                              *)
(*                                                                     *)
(*   Copyright 2008-2012 Jun Furuse. All rights reserved.              *)
(*   This file is distributed under the terms of the GNU Library       *)
(*   General Public License, with the special exception on linking     *)
(*   described in file LICENSE.                                        *)
(*                                                                     *)
(***********************************************************************)

module type OrderedType = sig
  type t
  val compare : t -> t 
    -> [`Left | `Right | `Includes | `Included | `Same | `Overwrap]
  val split : t -> by:t -> (t * t) option
end

module Make(Ord : OrderedType) = struct

  type elem = Ord.t
  type 'a node = Node of elem * 'a

  module rec Node : (Xset.OrderedType with type t = NodeSet.t node) = struct
    type t = NodeSet.t node
    let compare (Node (t1, _)) (Node (t2, _)) = 
      match Ord.compare t1 t2 with
      | `Left -> -1
      | `Right -> 1
      | _ -> 0
  end
  
  and NodeSet : Xset.S with type elt = 
    Node.t = Xset.Make(Node)

  include NodeSet

  let rec add_node (Node (elem, t0) as node) t = 
    match unsafe_find node t with 
    | None -> add node t
    | Some (Node (elem', t') as node') ->
	match Ord.compare elem elem' with
	| `Left | `Right -> assert false
	| `Includes | `Same -> 
	    add_node (Node (elem, add_node node' t0)) (remove node' t)
	| `Included ->
	    add (Node (elem', add_node node t')) (remove node' t)
	| `Overwrap -> 
	    match Ord.split elem ~by:elem' with
	    | None -> assert false
	    | Some (elem_left, elem_right) ->
		add_node (Node (elem_left, t0))
		  (add_node (Node (elem_right, t0)) t)

  let add_elem elem t = add_node (Node (elem, empty)) t  

  let rec find_path_contains_aux path node t =
    match unsafe_find node t with
    | None -> path
    | Some (Node (elem', t')) ->
	find_path_contains_aux ((elem', t') :: path) node t' 

  let find_path_contains elem t = 
    find_path_contains_aux [] (Node (elem, empty)) t

  let rec iter_elem ~parent f =
    NodeSet.iter (fun (Node (elem, t')) ->
      f ~parent elem;
      iter_elem ~parent: (Some elem) f t')

  let iter_elem f = 
    iter_elem ~parent:None f
    
end
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.