    -- ------------------------------------------------------------

    {- |
       Module     : Text.XML.HXT.XPath.XPathDataTypes
       Copyright  : Copyright (C) 2006 Uwe Schmidt
       License    : MIT

       Maintainer : Uwe Schmidt (uwe@fh-wedel.de)
       Stability  : experimental
       Portability: portable

       The core data types of XPath.
       The Type NodeSet is based on the module "NavTree" which was adapted from
       HXML (<http://www.flightlab.com/~joe/hxml/>)

    -}

    -- ------------------------------------------------------------

    module Text.XML.HXT.XPath.XPathDataTypes
        ( module Text.XML.HXT.XPath.XPathDataTypes
        , module Text.XML.HXT.XPath.NavTree
        )
    where

    import Data.Function                    ( on )
    import Data.Map                         ( Map )
    import qualified
           Data.Map                         as M

    import Text.XML.HXT.XPath.NavTree
    import Text.XML.HXT.DOM.Interface

    -- -----------------------------------------------------------------------------
    --
    -- Expr

    -- | Represents expression
    --

    data Expr     = GenExpr Op [Expr]             -- ^ generic expression with an operator and one or more operands
                  | PathExpr (Maybe Expr) (Maybe LocationPath)
                                                  -- ^ a path expression contains an optional filter-expression
                                                  -- or an optional locationpath. one expression is urgently
                                                  -- necessary, both are possible
                  | FilterExpr [Expr]             -- ^ filter-expression with zero or more predicates
                  | VarExpr VarName               -- ^ variable
                  | LiteralExpr Literal           -- ^ string
                  | NumberExpr XPNumber           -- ^ number
                  | FctExpr FctName FctArguments  -- ^ a function with a name and an optional list of arguments
                  deriving (Int -> Expr -> ShowS
    [Expr] -> ShowS
    Expr -> String
    (Int -> Expr -> ShowS)
    -> (Expr -> String) -> ([Expr] -> ShowS) -> Show Expr
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> Expr -> ShowS
    showsPrec :: Int -> Expr -> ShowS
    $cshow :: Expr -> String
    show :: Expr -> String
    $cshowList :: [Expr] -> ShowS
    showList :: [Expr] -> ShowS
    Show, Expr -> Expr -> Bool
    (Expr -> Expr -> Bool) -> (Expr -> Expr -> Bool) -> Eq Expr
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: Expr -> Expr -> Bool
    == :: Expr -> Expr -> Bool
    $c/= :: Expr -> Expr -> Bool
    /= :: Expr -> Expr -> Bool
    Eq)

    -- -----------------------------------------------------------------------------
    --
    -- Op

    -- | Represents XPath operators

    data Op       = Or | And | Eq | NEq | Less | Greater | LessEq
                  | GreaterEq |Plus | Minus | Div | Mod | Mult| Unary | Union
                  deriving (Int -> Op -> ShowS
    [Op] -> ShowS
    Op -> String
    (Int -> Op -> ShowS)
    -> (Op -> String) -> ([Op] -> ShowS) -> Show Op
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> Op -> ShowS
    showsPrec :: Int -> Op -> ShowS
    $cshow :: Op -> String
    show :: Op -> String
    $cshowList :: [Op] -> ShowS
    showList :: [Op] -> ShowS
    Show, Op -> Op -> Bool
    (Op -> Op -> Bool) -> (Op -> Op -> Bool) -> Eq Op
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: Op -> Op -> Bool
    == :: Op -> Op -> Bool
    $c/= :: Op -> Op -> Bool
    /= :: Op -> Op -> Bool
    Eq)

    -- -----------------------------------------------------------------------------
    --
    -- |
    -- Represents a floating-point number according the IEEE 754 standard
    --
    -- The standard includes a special Not-a-Number (NaN) value,
    -- positive and negative infinity, positive and negative zero.

    data XPNumber = Float Float  -- ^ floating-point number
                  | NaN          -- ^ not-a-number
                  | NegInf       -- ^ negative infinity
                  | Neg0         -- ^ negative zero
                  | Pos0         -- ^ positive zero
                  | PosInf       -- ^ positive infinity

    instance Show XPNumber
        where
        show :: XPNumber -> String
    show XPNumber
    NaN           = String
    "NaN"
        show XPNumber
    NegInf        = String
    "-Infinity"
        show XPNumber
    Neg0          = String
    "-0"
        show XPNumber
    Pos0          = String
    "0"
        show (Float Float
    f)     = Float -> String
    forall a. Show a => a -> String
    show Float
    f
        show XPNumber
    PosInf        = String
    "Infinity"

    -- Negative zero is equal to positive zero,
    -- equality test with NaN-value is always false
    instance Eq XPNumber
        where
        XPNumber
    NegInf  == :: XPNumber -> XPNumber -> Bool
    == XPNumber
    NegInf  = Bool
    True
        XPNumber
    Pos0    == XPNumber
    Neg0    = Bool
    True
        XPNumber
    Neg0    == XPNumber
    Pos0    = Bool
    True
        XPNumber
    Pos0    == XPNumber
    Pos0    = Bool
    True
        XPNumber
    Neg0    == XPNumber
    Neg0    = Bool
    True
        Float Float
    f == Float Float
    g = Float
    f Float -> Float -> Bool
    forall a. Eq a => a -> a -> Bool
    == Float
    g
        XPNumber
    PosInf  == XPNumber
    PosInf  = Bool
    True
        XPNumber
    _       == XPNumber
    _       = Bool
    False

    instance Ord XPNumber
        where
        XPNumber
    a       <= :: XPNumber -> XPNumber -> Bool
    <= XPNumber
    b       = (XPNumber
    a XPNumber -> XPNumber -> Bool
    forall a. Ord a => a -> a -> Bool
    < XPNumber
    b) Bool -> Bool -> Bool
    || (XPNumber
    a XPNumber -> XPNumber -> Bool
    forall a. Eq a => a -> a -> Bool
    == XPNumber
    b)
        XPNumber
    a       >= :: XPNumber -> XPNumber -> Bool
    >= XPNumber
    b       = (XPNumber
    a XPNumber -> XPNumber -> Bool
    forall a. Ord a => a -> a -> Bool
    > XPNumber
    b) Bool -> Bool -> Bool
    || (XPNumber
    a XPNumber -> XPNumber -> Bool
    forall a. Eq a => a -> a -> Bool
    == XPNumber
    b)
        XPNumber
    a       > :: XPNumber -> XPNumber -> Bool
    >  XPNumber
    b       =  XPNumber
    b XPNumber -> XPNumber -> Bool
    forall a. Ord a => a -> a -> Bool
    < XPNumber
    a

        XPNumber
    NaN     < :: XPNumber -> XPNumber -> Bool
    < XPNumber
    _        = Bool
    False
        XPNumber
    _       < XPNumber
    NaN      = Bool
    False

        XPNumber
    _       < XPNumber
    NegInf   = Bool
    False
        XPNumber
    NegInf  < XPNumber
    _        = Bool
    True

        XPNumber
    Neg0    < XPNumber
    Neg0     = Bool
    False
        XPNumber
    Pos0    < XPNumber
    Pos0     = Bool
    False
        XPNumber
    Pos0    < XPNumber
    Neg0     = Bool
    False
        XPNumber
    Neg0    < XPNumber
    Pos0     = Bool
    False

        XPNumber
    Neg0    < Float Float
    f  = Float
    0 Float -> Float -> Bool
    forall a. Ord a => a -> a -> Bool
    < Float
    f
        XPNumber
    Pos0    < Float Float
    f  = Float
    0 Float -> Float -> Bool
    forall a. Ord a => a -> a -> Bool
    < Float
    f
        Float Float
    f < XPNumber
    Neg0     = Float
    f Float -> Float -> Bool
    forall a. Ord a => a -> a -> Bool
    < Float
    0
        Float Float
    f < XPNumber
    Pos0     = Float
    f Float -> Float -> Bool
    forall a. Ord a => a -> a -> Bool
    < Float
    0

        Float Float
    f < Float Float
    g  = Float
    f Float -> Float -> Bool
    forall a. Ord a => a -> a -> Bool
    < Float
    g

        XPNumber
    PosInf  < XPNumber
    _        = Bool
    False
        XPNumber
    _       < XPNumber
    PosInf   = Bool
    True

    -- -----------------------------------------------------------------------------
    -- | Represents location path
    --
    -- A location path consists of a sequence of one or more location steps.

    data LocationPath = LocPath Path [XStep]
                      deriving (Int -> LocationPath -> ShowS
    [LocationPath] -> ShowS
    LocationPath -> String
    (Int -> LocationPath -> ShowS)
    -> (LocationPath -> String)
    -> ([LocationPath] -> ShowS)
    -> Show LocationPath
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> LocationPath -> ShowS
    showsPrec :: Int -> LocationPath -> ShowS
    $cshow :: LocationPath -> String
    show :: LocationPath -> String
    $cshowList :: [LocationPath] -> ShowS
    showList :: [LocationPath] -> ShowS
    Show, LocationPath -> LocationPath -> Bool
    (LocationPath -> LocationPath -> Bool)
    -> (LocationPath -> LocationPath -> Bool) -> Eq LocationPath
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: LocationPath -> LocationPath -> Bool
    == :: LocationPath -> LocationPath -> Bool
    $c/= :: LocationPath -> LocationPath -> Bool
    /= :: LocationPath -> LocationPath -> Bool
    Eq)

    -- -----------------------------------------------------------------------------
    -- |
    -- A location path is either a relative or an absolute path.

    data Path         = Rel
                      | Abs
                      deriving (Int -> Path -> ShowS
    [Path] -> ShowS
    Path -> String
    (Int -> Path -> ShowS)
    -> (Path -> String) -> ([Path] -> ShowS) -> Show Path
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> Path -> ShowS
    showsPrec :: Int -> Path -> ShowS
    $cshow :: Path -> String
    show :: Path -> String
    $cshowList :: [Path] -> ShowS
    showList :: [Path] -> ShowS
    Show, Path -> Path -> Bool
    (Path -> Path -> Bool) -> (Path -> Path -> Bool) -> Eq Path
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: Path -> Path -> Bool
    == :: Path -> Path -> Bool
    $c/= :: Path -> Path -> Bool
    /= :: Path -> Path -> Bool
    Eq)

    -- | Represents location step
    --
    -- A location step consists of an axis, a node-test and zero or more predicates.

    data XStep        = Step AxisSpec NodeTest [Expr]
                      deriving (Int -> XStep -> ShowS
    [XStep] -> ShowS
    XStep -> String
    (Int -> XStep -> ShowS)
    -> (XStep -> String) -> ([XStep] -> ShowS) -> Show XStep
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> XStep -> ShowS
    showsPrec :: Int -> XStep -> ShowS
    $cshow :: XStep -> String
    show :: XStep -> String
    $cshowList :: [XStep] -> ShowS
    showList :: [XStep] -> ShowS
    Show, XStep -> XStep -> Bool
    (XStep -> XStep -> Bool) -> (XStep -> XStep -> Bool) -> Eq XStep
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: XStep -> XStep -> Bool
    == :: XStep -> XStep -> Bool
    $c/= :: XStep -> XStep -> Bool
    /= :: XStep -> XStep -> Bool
    Eq)

    -- -----------------------------------------------------------------------------
    --
    -- AxisSpec

    -- | Represents XPath axis

    data AxisSpec     = Ancestor
                      | AncestorOrSelf
                      | Attribute
                      | Child
                      | Descendant
                      | DescendantOrSelf
                      | Following
                      | FollowingSibling
                      | Namespace
                      | Parent
                      | Preceding
                      | PrecedingSibling
                      | Self
                      deriving (Int -> AxisSpec -> ShowS
    [AxisSpec] -> ShowS
    AxisSpec -> String
    (Int -> AxisSpec -> ShowS)
    -> (AxisSpec -> String) -> ([AxisSpec] -> ShowS) -> Show AxisSpec
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> AxisSpec -> ShowS
    showsPrec :: Int -> AxisSpec -> ShowS
    $cshow :: AxisSpec -> String
    show :: AxisSpec -> String
    $cshowList :: [AxisSpec] -> ShowS
    showList :: [AxisSpec] -> ShowS
    Show, AxisSpec -> AxisSpec -> Bool
    (AxisSpec -> AxisSpec -> Bool)
    -> (AxisSpec -> AxisSpec -> Bool) -> Eq AxisSpec
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: AxisSpec -> AxisSpec -> Bool
    == :: AxisSpec -> AxisSpec -> Bool
    $c/= :: AxisSpec -> AxisSpec -> Bool
    /= :: AxisSpec -> AxisSpec -> Bool
    Eq)

    -- -----------------------------------------------------------------------------
    --
    -- NodeTest

    -- | Represents XPath node-tests

    --data NodeTest     = NameTest Name     -- ^ name-test
    data NodeTest     = NameTest QName     -- ^ name-test
                      | PI String           -- ^ processing-instruction-test with a literal argument
                      | TypeTest XPathNode  -- ^ all nodetype-tests
                      deriving (Int -> NodeTest -> ShowS
    [NodeTest] -> ShowS
    NodeTest -> String
    (Int -> NodeTest -> ShowS)
    -> (NodeTest -> String) -> ([NodeTest] -> ShowS) -> Show NodeTest
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> NodeTest -> ShowS
    showsPrec :: Int -> NodeTest -> ShowS
    $cshow :: NodeTest -> String
    show :: NodeTest -> String
    $cshowList :: [NodeTest] -> ShowS
    showList :: [NodeTest] -> ShowS
    Show, NodeTest -> NodeTest -> Bool
    (NodeTest -> NodeTest -> Bool)
    -> (NodeTest -> NodeTest -> Bool) -> Eq NodeTest
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: NodeTest -> NodeTest -> Bool
    == :: NodeTest -> NodeTest -> Bool
    $c/= :: NodeTest -> NodeTest -> Bool
    /= :: NodeTest -> NodeTest -> Bool
    Eq)

    -- -----------------------------------------------------------------------------
    --
    -- XPathNode

    -- | Represents nodetype-tests

    data XPathNode    = XPNode            -- ^ all 7 nodetypes
                                          --  (root, element, attribute, namespace, pi, comment, text)
                      | XPCommentNode     -- ^ comment-nodes
                      | XPPINode          -- ^ processing-instruction-nodes
                      | XPTextNode        -- ^ text-nodes: cdata, character data
                      deriving (Int -> XPathNode -> ShowS
    [XPathNode] -> ShowS
    XPathNode -> String
    (Int -> XPathNode -> ShowS)
    -> (XPathNode -> String)
    -> ([XPathNode] -> ShowS)
    -> Show XPathNode
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> XPathNode -> ShowS
    showsPrec :: Int -> XPathNode -> ShowS
    $cshow :: XPathNode -> String
    show :: XPathNode -> String
    $cshowList :: [XPathNode] -> ShowS
    showList :: [XPathNode] -> ShowS
    Show, XPathNode -> XPathNode -> Bool
    (XPathNode -> XPathNode -> Bool)
    -> (XPathNode -> XPathNode -> Bool) -> Eq XPathNode
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: XPathNode -> XPathNode -> Bool
    == :: XPathNode -> XPathNode -> Bool
    $c/= :: XPathNode -> XPathNode -> Bool
    /= :: XPathNode -> XPathNode -> Bool
    Eq)

    -- -----------------------------------------------------------------------------
    --
    -- useful type definitions

    type Name               = (NamePrefix, LocalName)
    type NamePrefix         = String
    type LocalName          = String

    -- | Variable name
    type VarName            = Name

    -- | a string
    type Literal            = String

    -- | Function name
    type FctName            = String

    -- | Function arguments
    type FctArguments       = [Expr]

    -- | Evaluation context
    type Context            = (ConPos ,ConLen, ConNode)

    -- | Context position
    type ConPos             = Int

    -- | Context length
    type ConLen             = Int

    -- | Context node
    type ConNode            = NavXmlTree

    -- -----------------------------------------------------------------------------
    --
    -- XPathValue

    -- | Represents XPath results

    data XPathValue   = XPVNode NodeSet      -- ^ node-set
                      | XPVBool Bool         -- ^ boolean value
                      | XPVNumber XPNumber   -- ^ number according the IEEE 754 standard
                      | XPVString String     -- ^ string value
                      | XPVError String      -- ^ error message with text
                      deriving (Int -> XPathValue -> ShowS
    [XPathValue] -> ShowS
    XPathValue -> String
    (Int -> XPathValue -> ShowS)
    -> (XPathValue -> String)
    -> ([XPathValue] -> ShowS)
    -> Show XPathValue
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> XPathValue -> ShowS
    showsPrec :: Int -> XPathValue -> ShowS
    $cshow :: XPathValue -> String
    show :: XPathValue -> String
    $cshowList :: [XPathValue] -> ShowS
    showList :: [XPathValue] -> ShowS
    Show, XPathValue -> XPathValue -> Bool
    (XPathValue -> XPathValue -> Bool)
    -> (XPathValue -> XPathValue -> Bool) -> Eq XPathValue
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: XPathValue -> XPathValue -> Bool
    == :: XPathValue -> XPathValue -> Bool
    $c/= :: XPathValue -> XPathValue -> Bool
    /= :: XPathValue -> XPathValue -> Bool
    Eq, Eq XPathValue
    Eq XPathValue =>
    (XPathValue -> XPathValue -> Ordering)
    -> (XPathValue -> XPathValue -> Bool)
    -> (XPathValue -> XPathValue -> Bool)
    -> (XPathValue -> XPathValue -> Bool)
    -> (XPathValue -> XPathValue -> Bool)
    -> (XPathValue -> XPathValue -> XPathValue)
    -> (XPathValue -> XPathValue -> XPathValue)
    -> Ord XPathValue
    XPathValue -> XPathValue -> Bool
    XPathValue -> XPathValue -> Ordering
    XPathValue -> XPathValue -> XPathValue
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    $ccompare :: XPathValue -> XPathValue -> Ordering
    compare :: XPathValue -> XPathValue -> Ordering
    $c< :: XPathValue -> XPathValue -> Bool
    < :: XPathValue -> XPathValue -> Bool
    $c<= :: XPathValue -> XPathValue -> Bool
    <= :: XPathValue -> XPathValue -> Bool
    $c> :: XPathValue -> XPathValue -> Bool
    > :: XPathValue -> XPathValue -> Bool
    $c>= :: XPathValue -> XPathValue -> Bool
    >= :: XPathValue -> XPathValue -> Bool
    $cmax :: XPathValue -> XPathValue -> XPathValue
    max :: XPathValue -> XPathValue -> XPathValue
    $cmin :: XPathValue -> XPathValue -> XPathValue
    min :: XPathValue -> XPathValue -> XPathValue
    Ord)

    -- -----------------------------------------------------------------------------
    --
    -- Basic types for navigable tree and filters

    -- | Node of navigable tree representation

    type NavXmlTree         = NavTree XNode

    -- | List of nodes of navigable tree representation

    type NavXmlTrees        = [NavXmlTree]

    -- | Set of navigable trees identified by their document position (NodePath)

    newtype NodeSet         = NS { NodeSet -> Map NodePath NavXmlTree
    unNS :: Map NodePath NavXmlTree }
                              deriving (Int -> NodeSet -> ShowS
    [NodeSet] -> ShowS
    NodeSet -> String
    (Int -> NodeSet -> ShowS)
    -> (NodeSet -> String) -> ([NodeSet] -> ShowS) -> Show NodeSet
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> NodeSet -> ShowS
    showsPrec :: Int -> NodeSet -> ShowS
    $cshow :: NodeSet -> String
    show :: NodeSet -> String
    $cshowList :: [NodeSet] -> ShowS
    showList :: [NodeSet] -> ShowS
    Show)

    -- | path represented as list of indices starting at root

    type NodePath           = [Int]

    -- | A functions that takes a XPath result and returns a XPath result

    type XPathFilter        = XPathValue -> XPathValue

    -- -----------------------------------------------------------------------------

    withXPVNode             :: String -> (NodeSet -> XPathValue) -> XPathFilter
    withXPVNode :: String -> (NodeSet -> XPathValue) -> XPathValue -> XPathValue
    withXPVNode String
    s NodeSet -> XPathValue
    f XPathValue
    n       = case XPathValue
    n of
                              XPVNode NodeSet
    ns            -> NodeSet -> XPathValue
    f NodeSet
    ns
                              e :: XPathValue
    e@(XPVError String
    _)        -> XPathValue
    e
                              XPathValue
    _                     -> String -> XPathValue
    XPVError String
    s

    -- -----------------------------------------------------------------------------

    -- | node set functions

    emptyNodeSet            :: NodeSet
    emptyNodeSet :: NodeSet
    emptyNodeSet            = Map NodePath NavXmlTree -> NodeSet
    NS Map NodePath NavXmlTree
    forall k a. Map k a
    M.empty

    singletonNodeSet        :: NavXmlTree -> NodeSet
    singletonNodeSet :: NavXmlTree -> NodeSet
    singletonNodeSet        = NavXmlTrees -> NodeSet
    toNodeSet (NavXmlTrees -> NodeSet)
    -> (NavXmlTree -> NavXmlTrees) -> NavXmlTree -> NodeSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (NavXmlTree -> NavXmlTrees -> NavXmlTrees
    forall a. a -> [a] -> [a]
    :[])

    nullNodeSet             :: NodeSet -> Bool
    nullNodeSet :: NodeSet -> Bool
    nullNodeSet             = Map NodePath NavXmlTree -> Bool
    forall k a. Map k a -> Bool
    M.null (Map NodePath NavXmlTree -> Bool)
    -> (NodeSet -> Map NodePath NavXmlTree) -> NodeSet -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> Map NodePath NavXmlTree
    unNS

    cardNodeSet             :: NodeSet -> Int
    cardNodeSet :: NodeSet -> Int
    cardNodeSet             = Map NodePath NavXmlTree -> Int
    forall k a. Map k a -> Int
    M.size (Map NodePath NavXmlTree -> Int)
    -> (NodeSet -> Map NodePath NavXmlTree) -> NodeSet -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> Map NodePath NavXmlTree
    unNS

    deleteNodeSet           :: NodePath -> NodeSet -> NodeSet
    deleteNodeSet :: NodePath -> NodeSet -> NodeSet
    deleteNodeSet NodePath
    p         = Map NodePath NavXmlTree -> NodeSet
    NS (Map NodePath NavXmlTree -> NodeSet)
    -> (NodeSet -> Map NodePath NavXmlTree) -> NodeSet -> NodeSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodePath -> Map NodePath NavXmlTree -> Map NodePath NavXmlTree
    forall k a. Ord k => k -> Map k a -> Map k a
    M.delete NodePath
    p (Map NodePath NavXmlTree -> Map NodePath NavXmlTree)
    -> (NodeSet -> Map NodePath NavXmlTree)
    -> NodeSet
    -> Map NodePath NavXmlTree
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> Map NodePath NavXmlTree
    unNS

    insertNodeSet           :: NavXmlTree -> NodeSet -> NodeSet
    insertNodeSet :: NavXmlTree -> NodeSet -> NodeSet
    insertNodeSet NavXmlTree
    t         = Map NodePath NavXmlTree -> NodeSet
    NS (Map NodePath NavXmlTree -> NodeSet)
    -> (NodeSet -> Map NodePath NavXmlTree) -> NodeSet -> NodeSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodePath
    -> NavXmlTree -> Map NodePath NavXmlTree -> Map NodePath NavXmlTree
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    M.insert (NavXmlTree -> NodePath
    forall a. NavTree a -> NodePath
    pathNT NavXmlTree
    t) NavXmlTree
    t (Map NodePath NavXmlTree -> Map NodePath NavXmlTree)
    -> (NodeSet -> Map NodePath NavXmlTree)
    -> NodeSet
    -> Map NodePath NavXmlTree
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> Map NodePath NavXmlTree
    unNS

    unionNodeSet            :: NodeSet -> NodeSet -> NodeSet
    unionNodeSet :: NodeSet -> NodeSet -> NodeSet
    unionNodeSet NodeSet
    ns1        = Map NodePath NavXmlTree -> NodeSet
    NS (Map NodePath NavXmlTree -> NodeSet)
    -> (NodeSet -> Map NodePath NavXmlTree) -> NodeSet -> NodeSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map NodePath NavXmlTree
    -> Map NodePath NavXmlTree -> Map NodePath NavXmlTree
    forall k a. Ord k => Map k a -> Map k a -> Map k a
    M.union (NodeSet -> Map NodePath NavXmlTree
    unNS NodeSet
    ns1) (Map NodePath NavXmlTree -> Map NodePath NavXmlTree)
    -> (NodeSet -> Map NodePath NavXmlTree)
    -> NodeSet
    -> Map NodePath NavXmlTree
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> Map NodePath NavXmlTree
    unNS

    unionsNodeSet           :: [NodeSet] -> NodeSet
    unionsNodeSet :: [NodeSet] -> NodeSet
    unionsNodeSet           = Map NodePath NavXmlTree -> NodeSet
    NS (Map NodePath NavXmlTree -> NodeSet)
    -> ([NodeSet] -> Map NodePath NavXmlTree) -> [NodeSet] -> NodeSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Map NodePath NavXmlTree -> NodeSet -> Map NodePath NavXmlTree)
    -> Map NodePath NavXmlTree -> [NodeSet] -> Map NodePath NavXmlTree
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl (\ Map NodePath NavXmlTree
    res NodeSet
    ns -> Map NodePath NavXmlTree
    -> Map NodePath NavXmlTree -> Map NodePath NavXmlTree
    forall k a. Ord k => Map k a -> Map k a -> Map k a
    M.union Map NodePath NavXmlTree
    res (Map NodePath NavXmlTree -> Map NodePath NavXmlTree)
    -> Map NodePath NavXmlTree -> Map NodePath NavXmlTree
    forall a b. (a -> b) -> a -> b
    $ NodeSet -> Map NodePath NavXmlTree
    unNS NodeSet
    ns) Map NodePath NavXmlTree
    forall k a. Map k a
    M.empty

    elemsNodeSet            :: NodeSet -> [(NodePath, NavXmlTree)]
    elemsNodeSet :: NodeSet -> [(NodePath, NavXmlTree)]
    elemsNodeSet            = Map NodePath NavXmlTree -> [(NodePath, NavXmlTree)]
    forall k a. Map k a -> [(k, a)]
    M.toList (Map NodePath NavXmlTree -> [(NodePath, NavXmlTree)])
    -> (NodeSet -> Map NodePath NavXmlTree)
    -> NodeSet
    -> [(NodePath, NavXmlTree)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> Map NodePath NavXmlTree
    unNS

    fromNodeSet             :: NodeSet -> NavXmlTrees
    fromNodeSet :: NodeSet -> NavXmlTrees
    fromNodeSet             = Map NodePath NavXmlTree -> NavXmlTrees
    forall k a. Map k a -> [a]
    M.elems (Map NodePath NavXmlTree -> NavXmlTrees)
    -> (NodeSet -> Map NodePath NavXmlTree) -> NodeSet -> NavXmlTrees
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> Map NodePath NavXmlTree
    unNS

    toNodeSet               :: NavXmlTrees -> NodeSet
    toNodeSet :: NavXmlTrees -> NodeSet
    toNodeSet               = Map NodePath NavXmlTree -> NodeSet
    NS (Map NodePath NavXmlTree -> NodeSet)
    -> (NavXmlTrees -> Map NodePath NavXmlTree)
    -> NavXmlTrees
    -> NodeSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Map NodePath NavXmlTree -> NavXmlTree -> Map NodePath NavXmlTree)
    -> Map NodePath NavXmlTree
    -> NavXmlTrees
    -> Map NodePath NavXmlTree
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl (\ Map NodePath NavXmlTree
    m NavXmlTree
    t -> NodePath
    -> NavXmlTree -> Map NodePath NavXmlTree -> Map NodePath NavXmlTree
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    M.insert (NavXmlTree -> NodePath
    forall a. NavTree a -> NodePath
    pathNT NavXmlTree
    t) NavXmlTree
    t Map NodePath NavXmlTree
    m) Map NodePath NavXmlTree
    forall k a. Map k a
    M.empty

    headNodeSet             :: NodeSet -> NavXmlTree
    headNodeSet :: NodeSet -> NavXmlTree
    headNodeSet             = NavXmlTrees -> NavXmlTree
    forall a. HasCallStack => [a] -> a
    head (NavXmlTrees -> NavXmlTree)
    -> (NodeSet -> NavXmlTrees) -> NodeSet -> NavXmlTree
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> NavXmlTrees
    fromNodeSet

    withNodeSet             :: (NavXmlTrees -> NavXmlTrees) -> NodeSet -> NodeSet
    withNodeSet :: (NavXmlTrees -> NavXmlTrees) -> NodeSet -> NodeSet
    withNodeSet NavXmlTrees -> NavXmlTrees
    f           = NavXmlTrees -> NodeSet
    toNodeSet (NavXmlTrees -> NodeSet)
    -> (NodeSet -> NavXmlTrees) -> NodeSet -> NodeSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NavXmlTrees -> NavXmlTrees
    f (NavXmlTrees -> NavXmlTrees)
    -> (NodeSet -> NavXmlTrees) -> NodeSet -> NavXmlTrees
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> NavXmlTrees
    fromNodeSet

    instance Eq NodeSet where
        == :: NodeSet -> NodeSet -> Bool
    (==)                = [NodePath] -> [NodePath] -> Bool
    forall a. Eq a => a -> a -> Bool
    (==) ([NodePath] -> [NodePath] -> Bool)
    -> (NodeSet -> [NodePath]) -> NodeSet -> NodeSet -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` (Map NodePath NavXmlTree -> [NodePath]
    forall k a. Map k a -> [k]
    M.keys (Map NodePath NavXmlTree -> [NodePath])
    -> (NodeSet -> Map NodePath NavXmlTree) -> NodeSet -> [NodePath]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> Map NodePath NavXmlTree
    unNS)

    instance Ord NodeSet where
        compare :: NodeSet -> NodeSet -> Ordering
    compare             = [NodePath] -> [NodePath] -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare ([NodePath] -> [NodePath] -> Ordering)
    -> (NodeSet -> [NodePath]) -> NodeSet -> NodeSet -> Ordering
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` (Map NodePath NavXmlTree -> [NodePath]
    forall k a. Map k a -> [k]
    M.keys (Map NodePath NavXmlTree -> [NodePath])
    -> (NodeSet -> Map NodePath NavXmlTree) -> NodeSet -> [NodePath]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NodeSet -> Map NodePath NavXmlTree
    unNS)

    -- -----------------------------------------------------------------------------
    --
    -- Env

    -- | XPath environment
    --
    -- All variables are stored in the environment,
    -- each variable name is bound to a value.

    type VarTab             = [(VarName, XPathValue)]
    type KeyTab             = [(QName, String, NavXmlTree)]

    type Env                = (VarTab, KeyTab)

    varEnv                  :: Env
    varEnv :: Env
    varEnv                  = ( [ ((String
    "", String
    "name"), XPNumber -> XPathValue
    XPVNumber XPNumber
    NaN) ]
                              , []
                              )

    -- -----------------------------------------------------------------------------