helm/ocaml/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 module type EqualityIndex =
  27   sig
  28     module PosEqSet : Set.S with type elt = Utils.pos * Inference.equality
  29     val arities : (Cic.term, int) Hashtbl.t
  30     type key = Cic.term
  31     type t = Discrimination_tree.DiscriminationTreeIndexing(PosEqSet).t
  32     val empty : t
  33     val retrieve_generalizations : t -> key -> PosEqSet.t
  34     val retrieve_unifiables : t -> key -> PosEqSet.t
  35     val init_index : unit -> unit
  36     val remove_index : t -> Inference.equality -> t
  37     val index : t -> Inference.equality -> t
  38     val in_index : t -> Inference.equality -> bool
  39   end
  40
  41 module DT =
  42 struct
  43     module OrderedPosEquality = struct
  44         type t = Utils.pos * Inference.equality
  45         let compare = Pervasives.compare
  46       end
  47
  48     module PosEqSet = Set.Make(OrderedPosEquality);;
  49
  50     include Discrimination_tree.DiscriminationTreeIndexing(PosEqSet)
  51
  52
  53     (* DISCRIMINATION TREES *)
  54     let init_index () =
  55       Hashtbl.clear arities;
  56     ;;
  57
  58     let remove_index tree equality =
  59       let _, _, (_, l, r, ordering), _, _ = 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 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 in
  79       let meta_convertibility (pos,equality') =
  80         Inference.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 * Inference.equality
  90         let compare = Pervasives.compare
  91       end
  92
  93     module PosEqSet = Set.Make(OrderedPosEquality);;
  94
  95     include Discrimination_tree.DiscriminationTreeIndexing(PosEqSet)
  96
  97
  98     (* DISCRIMINATION TREES *)
  99     let init_index () =
 100       Hashtbl.clear arities;
 101     ;;
 102
 103     let remove_index tree equality =
 104       let _, _, (_, l, r, ordering), _, _ = 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 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 in
 124       let meta_convertibility (pos,equality') =
 125         Inference.meta_convertibility_eq equality equality'
 126       in
 127         in_index tree l meta_convertibility || in_index tree r meta_convertibility
 128 end
 129