]> matita.cs.unibo.it Git - helm.git/blob - components/tactics/paramodulation/equality_indexing.ml
"the thesis becomes" now always performs a change.
[helm.git] / 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 * Equality.equality
31     type t = Discrimination_tree.DiscriminationTreeIndexing(PosEqSet).t
32     val empty : t
33     val retrieve_generalizations : t -> Cic.term -> PosEqSet.t
34     val retrieve_unifiables : t -> Cic.term -> PosEqSet.t
35     val init_index : unit -> unit
36     val remove_index : t -> Equality.equality -> t
37     val index : t -> Equality.equality -> t
38     val in_index : t -> Equality.equality -> bool
39   end
40
41 module DT = 
42 struct
43     module OrderedPosEquality = struct
44         type t = Utils.pos * Equality.equality
45         let compare (p1,e1) (p2,e2) = 
46           let rc = Pervasives.compare p1 p2 in
47             if rc = 0 then Equality.compare e1 e2 else rc
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
58     let remove_index tree equality = 
59       let _, _, (_, l, r, ordering), _,_ = Equality.open_equality equality in
60         match ordering with
61           | Utils.Gt -> remove_index tree l (Utils.Left, equality)
62           | Utils.Lt -> remove_index tree r (Utils.Right, equality)
63           | _ -> 
64               let tree = remove_index tree r (Utils.Right, equality) in
65                 remove_index tree l (Utils.Left, equality)
66
67     let index tree equality = 
68       let _, _, (_, l, r, ordering), _,_ = Equality.open_equality equality in
69         match ordering with
70           | Utils.Gt -> index tree l (Utils.Left, equality)
71           | Utils.Lt -> index tree r (Utils.Right, equality)
72           | _ -> 
73               let tree = index tree r (Utils.Right, equality) in
74                 index tree l (Utils.Left, equality)
75   
76
77     let in_index tree equality = 
78       let _, _, (_, l, r, ordering), _,_ = Equality.open_equality equality in
79       let meta_convertibility (pos,equality') = 
80         Equality.meta_convertibility_eq equality equality' 
81       in
82         in_index tree l meta_convertibility || in_index tree r meta_convertibility
83
84   end
85
86 module PT = 
87   struct
88     module OrderedPosEquality = struct
89         type t = Utils.pos * Equality.equality
90         let compare (p1,e1) (p2,e2) = 
91           let rc = Pervasives.compare p1 p2 in
92             if rc = 0 then Equality.compare e1 e2 else rc
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
103     let remove_index tree equality = 
104       let _, _, (_, l, r, ordering), _,_ = Equality.open_equality equality in
105           match ordering with
106           | Utils.Gt -> remove_index tree l (Utils.Left, equality)
107           | Utils.Lt -> remove_index tree r (Utils.Right, equality)
108           | _ -> 
109               let tree = remove_index tree r (Utils.Right, equality) in
110                 remove_index tree l (Utils.Left, equality)
111
112     let index tree equality = 
113       let _, _, (_, l, r, ordering), _,_ = Equality.open_equality equality in
114         match ordering with
115           | Utils.Gt -> index tree l (Utils.Left, equality)
116           | Utils.Lt -> index tree r (Utils.Right, equality)
117           | _ -> 
118               let tree = index tree r (Utils.Right, equality) in
119                 index tree l (Utils.Left, equality)
120   
121
122     let in_index tree equality = 
123       let _, _, (_, l, r, ordering), _,_ = Equality.open_equality equality in
124       let meta_convertibility (pos,equality') = 
125         Equality.meta_convertibility_eq equality equality' 
126       in
127         in_index tree l meta_convertibility || in_index tree r meta_convertibility
128 end
129