]> matita.cs.unibo.it Git - helm.git/blob - helm/software/components/tactics/paramodulation/equality_indexing.ml
fix for distro
[helm.git] / helm / software / components / tactics / paramodulation / equality_indexing.ml
1 (* Copyright (C) 2005, HELM Team.
2  * 
3  * This file is part of HELM, an Hypertextual, Electronic
4  * Library of Mathematics, developed at the Computer Science
5  * Department, University of Bologna, Italy.
6  * 
7  * HELM is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  * 
12  * HELM is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with HELM; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20  * MA  02111-1307, USA.
21  * 
22  * For details, see the HELM World-Wide-Web page,
23  * http://cs.unibo.it/helm/.
24  *)
25
26 (* $Id$ *)
27
28 module type EqualityIndex =
29   sig
30     module PosEqSet : Set.S with type elt = Utils.pos * Inference.equality
31     val arities : (Cic.term, int) Hashtbl.t
32     type key = Cic.term
33     type t = Discrimination_tree.DiscriminationTreeIndexing(PosEqSet).t
34     val empty : t
35     val retrieve_generalizations : t -> key -> PosEqSet.t
36     val retrieve_unifiables : t -> key -> PosEqSet.t
37     val init_index : unit -> unit
38     val remove_index : t -> Inference.equality -> t
39     val index : t -> Inference.equality -> t
40     val in_index : t -> Inference.equality -> bool
41   end
42
43 module DT = 
44 struct
45     module OrderedPosEquality = struct
46         type t = Utils.pos * Inference.equality
47         let compare = Pervasives.compare
48       end
49
50     module PosEqSet = Set.Make(OrderedPosEquality);;
51     
52     include Discrimination_tree.DiscriminationTreeIndexing(PosEqSet)
53     
54
55     (* DISCRIMINATION TREES *)
56     let init_index () =
57       Hashtbl.clear arities;
58     ;;
59
60     let remove_index tree equality = 
61       let _, _, (_, l, r, ordering), _ = equality in
62         match ordering with
63           | Utils.Gt -> remove_index tree l (Utils.Left, equality)
64           | Utils.Lt -> remove_index tree r (Utils.Right, equality)
65           | _ -> 
66               let tree = remove_index tree r (Utils.Right, equality) in
67                 remove_index tree l (Utils.Left, equality)
68
69     let index tree equality = 
70       let _, _, (_, l, r, ordering), _ = equality in
71         match ordering with
72           | Utils.Gt -> index tree l (Utils.Left, equality)
73           | Utils.Lt -> index tree r (Utils.Right, equality)
74           | _ -> 
75               let tree = index tree r (Utils.Right, equality) in
76                 index tree l (Utils.Left, equality)
77   
78
79     let in_index tree equality = 
80       let _, _, (_, l, r, ordering), _ = equality in
81       let meta_convertibility (pos,equality') = 
82         Inference.meta_convertibility_eq equality equality' 
83       in
84         in_index tree l meta_convertibility || in_index tree r meta_convertibility
85
86   end
87
88 module PT = 
89   struct
90     module OrderedPosEquality = struct
91         type t = Utils.pos * Inference.equality
92         let compare = Pervasives.compare
93       end
94
95     module PosEqSet = Set.Make(OrderedPosEquality);;
96     
97     include Discrimination_tree.DiscriminationTreeIndexing(PosEqSet)
98     
99
100     (* DISCRIMINATION TREES *)
101     let init_index () =
102       Hashtbl.clear arities;
103     ;;
104
105     let remove_index tree equality = 
106       let _, _, (_, l, r, ordering), _ = equality in
107           match ordering with
108           | Utils.Gt -> remove_index tree l (Utils.Left, equality)
109           | Utils.Lt -> remove_index tree r (Utils.Right, equality)
110           | _ -> 
111               let tree = remove_index tree r (Utils.Right, equality) in
112                 remove_index tree l (Utils.Left, equality)
113
114     let index tree equality = 
115       let _, _, (_, l, r, ordering), _ = equality in
116         match ordering with
117           | Utils.Gt -> index tree l (Utils.Left, equality)
118           | Utils.Lt -> index tree r (Utils.Right, equality)
119           | _ -> 
120               let tree = index tree r (Utils.Right, equality) in
121                 index tree l (Utils.Left, equality)
122   
123
124     let in_index tree equality = 
125       let _, _, (_, l, r, ordering), _ = equality in
126       let meta_convertibility (pos,equality') = 
127         Inference.meta_convertibility_eq equality equality' 
128       in
129         in_index tree l meta_convertibility || in_index tree r meta_convertibility
130 end
131