(******************************************************************************)
(*  SXSI : XPath evaluator                                                    *)
(*  Kim Nguyen (Kim.Nguyen@nicta.com.au)                                      *)
(*  Copyright NICTA 2008                                                      *)
(*  Distributed under the terms of the LGPL (see LICENCE)                     *)
(******************************************************************************)
module State :
  sig
    type t = int
    val mk : unit -> int
    val compare : int -> int -> int
    val equal : 'a -> 'a -> bool
    val hash : 'a -> 'a
    val print : Format.formatter -> int -> unit
  end
module SSet : Set.S with type elt = State.t
module Transition :
  sig
    type t =
        Label of State.t * TagSet.Xml.t * State.t * State.t
      | External of State.t * (Tree.Binary.t -> bool) * State.t * State.t
    val source : t -> State.t
    val dest1 : t -> State.t
    val dest2 : t -> State.t
    val cup : t -> t -> t
    val cap : t -> t -> t
    val neg : t -> t
    module HT : Hashtbl.S with type key = State.t
    type hashtbl = {
      label : (TagSet.Xml.t * State.t * State.t) HT.t;
      extern : ((Tree.Binary.t -> bool) * State.t * State.t) HT.t;
    }
    val empty : unit -> hashtbl
    val clear : hashtbl -> unit
    val add : hashtbl -> t -> unit
    val find_all :
      ?accu:t list ->
      ?pred_label:(State.t -> TagSet.Xml.t -> State.t -> State.t -> bool) ->
      ?pred_extern:(State.t ->
                      (Tree.Binary.t -> bool) -> State.t -> State.t -> bool) ->
      hashtbl -> State.t -> t list
    val find_all_dest : State.t -> hashtbl -> t list
    val fold_state :
      ('a -> HT.key -> TagSet.Xml.t -> State.t -> State.t -> 'a) ->
      ('a -> HT.key -> (Tree.Binary.t -> bool) -> State.t -> State.t -> 'a) ->
      hashtbl -> HT.key -> 'a -> 'a
  end
module BST : Set.S with type elt = Tree.Binary.t
type t = { initial : SSet.t;
	   final : SSet.t;
 	   transitions : Transition.hashtbl;
	   marking : SSet.t;
	   ignore : SSet.t;
	   mutable result : BST.t;
	   mutable numbt : int;
	   mutable max_states : int;
	   contains : (string,Tree.Binary.DocIdSet.t) Hashtbl.t;
	 }
val mk : unit -> t
val dump : Format.formatter -> t -> unit
module BottomUp :
  sig

    val accepting_among : ?nobrother:bool -> ?strings:Tree.Binary.DocIdSet.t option ->
      t -> Tree.Binary.t -> SSet.t -> SSet.t
    val accept : ?strings:Tree.Binary.DocIdSet.t option -> 
      t -> Tree.Binary.t -> bool
  end

module TopDown :
sig
  val accept : t -> Tree.Binary.t -> bool
  val run : t -> Tree.Binary.t -> unit
end