- module PSMap = Map.Make(OrderedPathStringElement);;
-
- type key = PSMap.key
-
- module DiscriminationTree = Trie.Make(PSMap);;
-
- type t = A.t DiscriminationTree.t * (path_string_elem*int) list
- let empty = DiscriminationTree.empty, [] ;;
-
- let iter (dt, _ ) f =
- DiscriminationTree.iter (fun _ x -> f x) dt
- ;;
-
- let index (tree,arity) term info =
- let arity,ps = path_string_of_term arity term in
- let ps_set =
- try DiscriminationTree.find ps tree
- with Not_found -> A.empty in
- let tree = DiscriminationTree.add ps (A.add info ps_set) tree in
- tree,arity
- ;;
-
- let remove_index (tree,arity) term info =
- let arity,ps = path_string_of_term arity term in
- try
- let ps_set = A.remove info (DiscriminationTree.find ps tree) in
- if A.is_empty ps_set then
- DiscriminationTree.remove ps tree,arity
- else
- DiscriminationTree.add ps ps_set tree,arity
- with Not_found ->
- tree,arity
- ;;
-
- let in_index (tree,arity) term test =
- let arity,ps = path_string_of_term arity term in
- try
- let ps_set = DiscriminationTree.find ps tree in
- A.exists test ps_set
- with Not_found ->
- false
- ;;
-
- let head_of_term = function
- | NCic.Appl (hd::tl) -> hd
- | term -> term
- ;;
-
- let rec skip_prods = function
- | NCic.Prod (_,_,t) -> skip_prods t
- | term -> term
- ;;
-
- let rec subterm_at_pos pos term =
- match pos with
- | [] -> term
- | index::pos ->
- match term with
- | NCic.Appl l ->
- (try subterm_at_pos pos (List.nth l index)
- with Failure _ -> raise Not_found)
- | _ -> raise Not_found
- ;;
-
-
- let rec after_t pos term =
- let pos' =
- match pos with
- | [] -> raise Not_found
- | pos ->
- List.fold_right
- (fun i r -> if r = [] then [i+1] else i::r) pos []
- in
- try
- ignore(subterm_at_pos pos' term ); pos'
- with Not_found ->
- let pos, _ =
- List.fold_right
- (fun i (r, b) -> if b then (i::r, true) else (r, true))
- pos ([], false)
- in
- after_t pos term
- ;;
-
-
- let next_t pos term =
- let t = subterm_at_pos pos term in
- try
- let _ = subterm_at_pos [1] t in
- pos @ [1]
- with Not_found ->
- match pos with
- | [] -> [1]
- | pos -> after_t pos term
- ;;
-
- let retrieve_generalizations (tree,arity) term =
- let term = skip_prods term in
- let rec retrieve tree term pos =
- match tree with
- | DiscriminationTree.Node (Some s, _) when pos = [] -> s
- | DiscriminationTree.Node (_, map) ->
- let res =
- let hd_term =
- elem_of_cic (head_of_term (subterm_at_pos pos term))
- in
- if hd_term = Variable then A.empty else
- try
- let n = PSMap.find hd_term map in
- match n with
- | DiscriminationTree.Node (Some s, _) -> s
- | DiscriminationTree.Node (None, _) ->
- let newpos =
- try next_t pos term
- with Not_found -> []
- in
- retrieve n term newpos
- with Not_found ->
- A.empty
- in
- try
- let n = PSMap.find Variable map in
- let newpos = try after_t pos term with Not_found -> [-1] in
- if newpos = [-1] then
- match n with
- | DiscriminationTree.Node (Some s, _) -> A.union s res
- | _ -> res
- else
- A.union res (retrieve n term newpos)
- with Not_found ->
- res
- in
- retrieve tree term []
- ;;