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