automaton.mli

   1 (******************************************************************************)
   2 (*  SXSI : XPath evaluator                                                    *)
   3 (*  Kim Nguyen (Kim.Nguyen@nicta.com.au)                                      *)
   4 (*  Copyright NICTA 2008                                                      *)
   5 (*  Distributed under the terms of the LGPL (see LICENCE)                     *)
   6 (******************************************************************************)
   7 module State :
   8   sig
   9     type t = int
  10     val mk : unit -> int
  11     val compare : int -> int -> int
  12     val equal : 'a -> 'a -> bool
  13     val hash : 'a -> 'a
  14     val print : Format.formatter -> int -> unit
  15   end
  16 module SSet : Set.S with type elt = State.t
  17 module Transition :
  18   sig
  19     type t =
  20         Label of State.t * TagSet.Xml.t * State.t * State.t
  21       | External of State.t * (Tree.Binary.t -> bool) * State.t * State.t
  22     val source : t -> State.t
  23     val dest1 : t -> State.t
  24     val dest2 : t -> State.t
  25     val cup : t -> t -> t
  26     val cap : t -> t -> t
  27     val neg : t -> t
  28     module HT : Hashtbl.S with type key = State.t
  29     type hashtbl = {
  30       label : (TagSet.Xml.t * State.t * State.t) HT.t;
  31       extern : ((Tree.Binary.t -> bool) * State.t * State.t) HT.t;
  32     }
  33     val empty : unit -> hashtbl
  34     val clear : hashtbl -> unit
  35     val add : hashtbl -> t -> unit
  36     val find_all :
  37       ?accu:t list ->
  38       ?pred_label:(State.t -> TagSet.Xml.t -> State.t -> State.t -> bool) ->
  39       ?pred_extern:(State.t ->
  40                       (Tree.Binary.t -> bool) -> State.t -> State.t -> bool) ->
  41       hashtbl -> State.t -> t list
  42     val find_all_dest : State.t -> hashtbl -> t list
  43     val fold_state :
  44       ('a -> HT.key -> TagSet.Xml.t -> State.t -> State.t -> 'a) ->
  45       ('a -> HT.key -> (Tree.Binary.t -> bool) -> State.t -> State.t -> 'a) ->
  46       hashtbl -> HT.key -> 'a -> 'a
  47   end
  48 module BST : Set.S with type elt = Tree.Binary.t
  49 type t = { initial : SSet.t;
  50            final : SSet.t;
  51            transitions : Transition.hashtbl;
  52            marking : SSet.t;
  53            ignore : SSet.t;
  54            mutable result : BST.t;
  55            mutable numbt : int;
  56            mutable max_states : int;
  57            contains : (string,Tree.Binary.DocIdSet.t) Hashtbl.t;
  58          }
  59 val mk : unit -> t
  60 val dump : Format.formatter -> t -> unit
  61 module BottomUp :
  62   sig
  63
  64     val accepting_among : ?nobrother:bool -> ?strings:Tree.Binary.DocIdSet.t option ->
  65       t -> Tree.Binary.t -> SSet.t -> SSet.t
  66     val accept : ?strings:Tree.Binary.DocIdSet.t option ->
  67       t -> Tree.Binary.t -> bool
  68   end
  69
  70 module TopDown :
  71 sig
  72   val accept : t -> Tree.Binary.t -> bool
  73   val run : t -> Tree.Binary.t -> unit
  74 end