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 (* $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