(***********************************************************************)
(*                                                                     *)
(*                                 GALAX                               *)
(*                            XML Query Engine                         *)
(*                                                                     *)
(*  Copyright 2001, Lucent Technologies.                               *)
(*  Distributed only by permission.                                    *)
(*                                                                     *)
(***********************************************************************)

open Bound
open Error
open Fsa
open Dfa
open Intersectfsa
open Reachability

type position = int    (* a symbol is denoted with its position
			  - each symbol as a unique position *)

type 'a regexp = 
  | RSym of ('a * position)
  | RSeq of ('a regexp * 'a regexp) 
  | REmpty
  | RChoice of ('a regexp * 'a regexp) 
  | RNone
  | RPlus of 'a regexp
  | RStar of 'a regexp

module PositionSet : Set.S

(* helper function on Glushkov construction *)
val nullable : 'a regexp -> bool

(* returns a set of position of the expression *)
val pos : 'a regexp -> PositionSet.t

val first : 'a regexp -> PositionSet.t
val last : 'a regexp -> PositionSet.t
val follow : 'a regexp -> position -> PositionSet.t

(* the chi function: it takes a regular expression and a position (integer). *)
(* returns the label at that position. *)
val chi : 'a regexp -> position -> 'a

(* Creates a regular expression in star normal form *)
(* it's a two step process *)
val star_normalize_aux : 'a regexp -> 'a regexp
val star_normalize : 'a regexp -> 'a regexp

(* Create a regular expression from Type AST *)
val normalize_regexp : Xquery_ast.model -> Sym.rgroup_symbol regexp

val build_glushkov : (Sym.rgroup_symbol regexp) -> TypeName_NFA.nfa
val build_dtm_glushkov : (Sym.rgroup_symbol regexp) -> TypeName_DFA.dfa

val print_glushkov : TypeName_NFA.nfa -> unit
val print_dtm_glushkov : TypeName_DFA.dfa -> unit


val includes   : Xquery_ast.model -> Xquery_ast.model -> bool
val intersects : Xquery_ast.model -> Xquery_ast.model -> bool

