text:
@doc raw"""
    AbstractGroupOperation

Abstract type for smooth binary operations $∘$ on elements of a Lie group $\mathcal{G}$:
```math
∘ : \mathcal{G} × \mathcal{G} → \mathcal{G}
```
An operation can be either defined for a specific [`AbstractGroupManifold`](@ref) over
number system `𝔽` or in general, by defining for an operation `Op` the following methods:

    identity_element!(::AbstractGroupManifold{𝔽,Op}, q, q)
    inv!(::AbstractGroupManifold{𝔽,Op}, q, p)
    _compose!(::AbstractGroupManifold{𝔽,Op}, x, p, q)

Note that a manifold is connected with an operation by wrapping it with a decorator,
[`AbstractGroupManifold`](@ref). In typical cases the concrete wrapper
[`GroupManifold`](@ref) can be used.
"""
abstract type AbstractGroupOperation end

"""
    abstract type AbstractGroupDecroatorType <: AbstractDecoratorType

A common decorator type for all group decorators.
It is similar to [`DefaultEmbeddingType`](@ref) but for groups.
"""
abstract type AbstractGroupDecoratorType <: AbstractDecoratorType end

"""
    struct DefaultGroupDecoratorType <: AbstractDecoratorType

The default group decorator type with no special properties.
"""
struct DefaultGroupDecoratorType <: AbstractGroupDecoratorType end
"""
    struct TransparentGroupDecoratorType <: AbstractDecoratorType

A transparent group decorator type that acts transparently, similar to
the [`TransparentIsometricEmbedding`](@ref), i.e. it passes through all metric-related functions such as
logarithmic and exponential map as well as retraction and inverse retractions
to the manifold it decorates.
"""
struct TransparentGroupDecoratorType <: AbstractGroupDecoratorType end

@doc raw"""
    AbstractGroupManifold{𝔽,O<:AbstractGroupOperation} <: AbstractDecoratorManifold{𝔽}

Abstract type for a Lie group, a group that is also a smooth manifold with an
[`AbstractGroupOperation`](@ref), a smooth binary operation. `AbstractGroupManifold`s must
implement at least [`inv`](@ref), [`compose`](@ref), and
[`translate_diff`](@ref).
"""
abstract type AbstractGroupManifold{𝔽,O<:AbstractGroupOperation,T<:AbstractDecoratorType} <:
              AbstractDecoratorManifold{𝔽,T} end

"""
    GroupManifold{𝔽,M<:AbstractManifold{𝔽},O<:AbstractGroupOperation} <: AbstractGroupManifold{𝔽,O}

Decorator for a smooth manifold that equips the manifold with a group operation, thus making
it a Lie group. See [`AbstractGroupManifold`](@ref) for more details.

Group manifolds by default forward metric-related operations to the wrapped manifold.

# Constructor

    GroupManifold(manifold, op)
"""
struct GroupManifold{𝔽,M<:AbstractManifold{𝔽},O<:AbstractGroupOperation} <:
       AbstractGroupManifold{𝔽,O,TransparentGroupDecoratorType}
    manifold::M
    op::O
end

Base.show(io::IO, G::GroupManifold) = print(io, "GroupManifold($(G.manifold), $(G.op))")

const GROUP_MANIFOLD_BASIS_DISAMBIGUATION =
    [AbstractDecoratorManifold, ValidationManifold, VectorBundle]

"""
    base_group(M::AbstractManifold) -> AbstractGroupManifold

Un-decorate `M` until an `AbstractGroupManifold` is encountered.
Return an error if the [`base_manifold`](@ref) is reached without encountering a group.
"""
base_group(M::AbstractDecoratorManifold) = base_group(decorated_manifold(M))
function base_group(::AbstractManifold)
    return error("base_group: no base group found.")
end
base_group(G::AbstractGroupManifold) = G

"""
    base_manifold(M::AbstractGroupManifold, d::Val{N} = Val(-1))

Return the base manifold of `M` that is enhanced with its group.
While functions like `inner` might be overwritten to use the (decorated) manifold
representing the group, the `base_manifold` is the manifold itself.
Hence for this abstract case, just `M` is returned.
"""
base_manifold(M::AbstractGroupManifold, ::Val{N}=Val(-1)) where {N} = M

"""
    base_manifold(M::GroupManifold, d::Val{N} = Val(-1))

Return the base manifold of `M` that is enhanced with its group.
Here, the internally stored enhanced manifold `M.manifold` is returned.
"""
base_manifold(G::GroupManifold, ::Val{N}=Val(-1)) where {N} = G.manifold

decorator_group_dispatch(::AbstractManifold) = Val(false)
function decorator_group_dispatch(M::AbstractDecoratorManifold)
    return decorator_group_dispatch(decorated_manifold(M))
end
decorator_group_dispatch(::AbstractGroupManifold) = Val(true)

function is_group_decorator(M::AbstractManifold)
    return _extract_val(decorator_group_dispatch(M))
end

default_decorator_dispatch(::AbstractGroupManifold) = Val(false)

(op::AbstractGroupOperation)(M::AbstractManifold) = GroupManifold(M, op)
function (::Type{T})(M::AbstractManifold) where {T<:AbstractGroupOperation}
    return GroupManifold(M, T())
end

manifold_dimension(G::GroupManifold) = manifold_dimension(G.manifold)

###################
# Action directions
###################

"""
    ActionDirection

Direction of action on a manifold, either [`LeftAction`](@ref) or [`RightAction`](@ref).
"""
abstract type ActionDirection end

"""
    LeftAction()

Left action of a group on a manifold.
"""
struct LeftAction <: ActionDirection end

"""
    RightAction()

Right action of a group on a manifold.
"""
struct RightAction <: ActionDirection end

"""
    switch_direction(::ActionDirection)

Returns a [`RightAction`](@ref) when given a [`LeftAction`](@ref) and vice versa.
"""
switch_direction(::ActionDirection)
switch_direction(::LeftAction) = RightAction()
switch_direction(::RightAction) = LeftAction()

##################################
# General Identity element methods
##################################

@doc raw"""
    Identity{O<:AbstractGroupOperation}

Represent the group identity element ``e ∈ \mathcal{G}`` on an [`AbstractGroupManifold`](@ref) `G`
with [`AbstractGroupOperation`](@ref) of type `O`.

Similar to the philosophy that points are agnostic of their group at hand, the identity
does not store the group `g` it belongs to. However it depends on the type of the [`AbstractGroupOperation`](@ref) used.

See also [`identity_element`](@ref) on how to obtain the corresponding [`AbstractManifoldPoint`](@ref) or array representation.

# Constructors

    Identity(G::AbstractGroupManifold{𝔽,O})
    Identity(o::O)
    Identity(::Type{O})

create the identity of the corresponding subtype `O<:`[`AbstractGroupOperation`](@ref)
"""
struct Identity{O<:AbstractGroupOperation} end

function Identity(::AbstractGroupManifold{𝔽,O}) where {𝔽,O<:AbstractGroupOperation}
    return Identity{O}()
end
Identity(M::AbstractDecoratorManifold) = Identity(base_group(M))
Identity(::O) where {O<:AbstractGroupOperation} = Identity(O)
Identity(::Type{O}) where {O<:AbstractGroupOperation} = Identity{O}()

# To ensure allocate_result_type works in general if idenitty apears in the tuple
number_eltype(::Identity) = Bool

@doc raw"""
    identity_element(G::AbstractGroupManifold)

Return a point representation of the [`Identity`](@ref) on the [`AbstractGroupManifold`](@ref) `G`.
By default this representation is the default array or number representation.
It should return the corresponding [`AbstractManifoldPoint`](@ref) of points on `G` if
points are not represented by arrays.
"""
identity_element(G::AbstractGroupManifold)
@decorator_transparent_function function identity_element(G::AbstractGroupManifold)
    q = allocate_result(G, identity_element)
    return identity_element!(G, q)
end

@decorator_transparent_signature identity_element!(G::AbstractGroupManifold, p)

function allocate_result(G::AbstractGroupManifold, ::typeof(identity_element))
    return zeros(representation_size(G)...)
end

@doc raw"""
    identity_element(G::AbstractGroupManifold, p)

Return a point representation of the [`Identity`](@ref) on the [`AbstractGroupManifold`](@ref) `G`,
where `p` indicates the type to represent the identity.
"""
identity_element(G::AbstractGroupManifold, p)
@decorator_transparent_function function identity_element(G::AbstractGroupManifold, p)
    q = allocate_result(G, identity_element, p)
    return identity_element!(G, q)
end

@doc raw"""
    identity_element!(G::AbstractGroupManifold, p)

Return a point representation of the [`Identity`](@ref) on the [`AbstractGroupManifold`](@ref) `G`
in place of `p`.
"""
identity_element!(G::AbstractGroupManifold, p)

@doc raw"""
    is_identity(G, q; kwargs)

Check whether `q` is the identity on the [`AbstractGroupManifold`](@ref) `G`, i.e. it is either
the [`Identity`](@ref)`{O}` with the corresponding [`AbstractGroupOperation`](@ref) `O`, or
(approximately) the correct point representation.
"""
is_identity(G::AbstractGroupManifold, q)

@decorator_transparent_function function is_identity(G::AbstractGroupManifold, q; kwargs...)
    return isapprox(G, identity_element(G), q; kwargs...)
end
function is_identity(
    ::AbstractGroupManifold{𝔽,O},
    ::Identity{O};
    kwargs...,
) where {𝔽,O<:AbstractGroupOperation}
    return true
end
is_identity(::AbstractGroupManifold, ::Identity; kwargs...) = false

function isapprox(
    G::AbstractGroupManifold{𝔽,O},
    p::Identity{O},
    q;
    kwargs...,
) where {𝔽,O<:AbstractGroupOperation}
    return is_identity(G, q; kwargs...)
end
function isapprox(
    G::AbstractGroupManifold{𝔽,O},
    p,
    q::Identity{O};
    kwargs...,
) where {𝔽,O<:AbstractGroupOperation}
    return is_identity(G, p; kwargs...)
end
function isapprox(
    G::AbstractGroupManifold{𝔽,O},
    p::Identity{O},
    q::Identity{O};
    kwargs...,
) where {𝔽,O<:AbstractGroupOperation}
    return true
end
function isapprox(
    G::AbstractGroupManifold{𝔽,O},
    p::Identity{O},
    X,
    Y;
    kwargs...,
) where {𝔽,O<:AbstractGroupOperation}
    return isapprox(G, identity_element(G), X, Y; kwargs...)
end
Base.isapprox(::AbstractGroupManifold, ::Identity, ::Identity; kwargs...) = false

function Base.show(io::IO, ::Identity{O}) where {O<:AbstractGroupOperation}
    return print(io, "Identity($O)")
end

function check_point(
    G::AbstractGroupManifold{𝔽,O},
    e::Identity{O};
    kwargs...,
) where {𝔽,M,O<:AbstractGroupOperation}
    return nothing
end

function check_point(
    G::AbstractGroupManifold{𝔽,O1},
    e::Identity{O2};
    kwargs...,
) where {𝔽,M,O1<:AbstractGroupOperation,O2<:AbstractGroupOperation}
    return DomainError(
        e,
        "The Identity $e does not lie on $G, since its the identity with respect to $O2 and not $O1.",
    )
end

##########################
# Group-specific functions
##########################

@doc raw"""
    adjoint_action(G::AbstractGroupManifold, p, X)

Adjoint action of the element `p` of the Lie group `G` on the element `X`
of the corresponding Lie algebra.

It is defined as the differential of the group authomorphism ``Ψ_p(q) = pqp⁻¹`` at
the identity of `G`.

The formula reads
````math
\operatorname{Ad}_p(X) = dΨ_p(e)[X]
````
where $e$ is the identity element of `G`.

Note that the adjoint representation of a Lie group isn't generally faithful.
Notably the adjoint representation of SO(2) is trivial.
"""
adjoint_action(G::AbstractGroupManifold, p, X)
@decorator_transparent_function :intransparent function adjoint_action(
    G::AbstractGroupManifold,
    p,
    Xₑ,
)
    Xₚ = translate_diff(G, p, Identity(G), Xₑ, LeftAction())
    Y = inverse_translate_diff(G, p, p, Xₚ, RightAction())
    return Y
end

function adjoint_action!(G::AbstractGroupManifold, Y, p, Xₑ)
    Xₚ = translate_diff(G, p, Identity(G), Xₑ, LeftAction())
    inverse_translate_diff!(G, Y, p, p, Xₚ, RightAction())
    return Y
end

@doc raw"""
    inv(G::AbstractGroupManifold, p)

Inverse $p^{-1} ∈ \mathcal{G}$ of an element $p ∈ \mathcal{G}$, such that
$p \circ p^{-1} = p^{-1} \circ p = e ∈ \mathcal{G}$, where $e$ is the [`Identity`](@ref)
element of $\mathcal{G}$.
"""
inv(::AbstractGroupManifold, ::Any...)
@decorator_transparent_function function Base.inv(G::AbstractGroupManifold, p)
    q = allocate_result(G, inv, p)
    return inv!(G, q, p)
end

function Base.inv(
    ::AbstractGroupManifold{𝔽,O},
    e::Identity{O},
) where {𝔽,O<:AbstractGroupOperation}
    return e
end

@decorator_transparent_function function inv!(G::AbstractGroupManifold, q, p)
    return inv!(G.manifold, q, p)
end

function inv!(
    G::AbstractGroupManifold{𝔽,O},
    q,
    ::Identity{O},
) where {𝔽,O<:AbstractGroupOperation}
    return identity_element!(G, q)
end

function Base.copyto!(
    ::AbstractGroupManifold{𝔽,O},
    e::Identity{O},
    ::Identity{O},
) where {𝔽,O<:AbstractGroupOperation}
    return e
end
function Base.copyto!(
    G::AbstractGroupManifold{𝔽,O},
    p,
    ::Identity{O},
) where {𝔽,O<:AbstractGroupOperation}
    return identity_element!(G, p)
end

@doc raw"""
    compose(G::AbstractGroupManifold, p, q)

Compose elements ``p,q ∈ \mathcal{G}`` using the group operation ``p \circ q``.

For implementing composition on a new group manifold, please overload `_compose`
instead so that methods with [`Identity`](@ref) arguments are not ambiguous.
"""
compose(::AbstractGroupManifold, ::Any...)

@decorator_transparent_function function compose(
    G::AbstractGroupManifold{𝔽,Op},
    p,
    q,
) where {𝔽,Op<:AbstractGroupOperation}
    return _compose(G, p, q)
end
function compose(
    ::AbstractGroupManifold{𝔽,Op},
    ::Identity{Op},
    p,
) where {𝔽,Op<:AbstractGroupOperation}
    return p
end
function compose(
    ::AbstractGroupManifold{𝔽,Op},
    p,
    ::Identity{Op},
) where {𝔽,Op<:AbstractGroupOperation}
    return p
end
function compose(
    ::AbstractGroupManifold{𝔽,Op},
    e::Identity{Op},
    ::Identity{Op},
) where {𝔽,Op<:AbstractGroupOperation}
    return e
end

function _compose(G::AbstractGroupManifold, p, q)
    x = allocate_result(G, compose, p, q)
    return _compose!(G, x, p, q)
end

@decorator_transparent_signature compose!(M::AbstractDecoratorManifold, x, p, q)

compose!(G::AbstractGroupManifold, x, q, p) = _compose!(G, x, q, p)
function compose!(
    G::AbstractGroupManifold{𝔽,Op},
    q,
    p,
    ::Identity{Op},
) where {𝔽,Op<:AbstractGroupOperation}
    return copyto!(G, q, p)
end
function compose!(
    G::AbstractGroupManifold{𝔽,Op},
    q,
    ::Identity{Op},
    p,
) where {𝔽,Op<:AbstractGroupOperation}
    return copyto!(G, q, p)
end
function compose!(
    G::AbstractGroupManifold{𝔽,Op},
    q,
    ::Identity{Op},
    e::Identity{Op},
) where {𝔽,Op<:AbstractGroupOperation}
    return identity_element!(G, q)
end
function compose!(
    ::AbstractGroupManifold{𝔽,Op},
    e::Identity{Op},
    ::Identity{Op},
    ::Identity{Op},
) where {𝔽,Op<:AbstractGroupOperation}
    return e
end

transpose(e::Identity) = e

@doc raw"""
    hat(M::AbstractGroupManifold{𝔽,O}, ::Identity{O}, Xⁱ) where {𝔽,O<:AbstractGroupOperation}

Given a basis $e_i$ on the tangent space at a the [`Identity`}(@ref) and tangent
component vector ``X^i``, compute the equivalent vector representation
``X=X^i e_i**, where Einstein summation notation is used:

````math
∧ : X^i ↦ X^i e_i
````

For array manifolds, this converts a vector representation of the tangent
vector to an array representation. The [`vee`](@ref) map is the `hat` map's
inverse.
"""
function hat(
    G::AbstractGroupManifold{𝔽,O},
    ::Identity{O},
    X,
) where {𝔽,O<:AbstractGroupOperation}
    return get_vector_lie(G, X, VeeOrthogonalBasis())
end
function hat!(
    G::AbstractGroupManifold{𝔽,O},
    Y,
    ::Identity{O},
    X,
) where {𝔽,O<:AbstractGroupOperation}
    return get_vector_lie!(G, Y, X, VeeOrthogonalBasis())
end
function hat(M::AbstractManifold, e::Identity, ::Any)
    return throw(ErrorException("On $M there exsists no identity $e"))
end
function hat!(M::AbstractManifold, ::Any, e::Identity, ::Any)
    return throw(ErrorException("On $M there exsists no identity $e"))
end

@doc raw"""
    vee(M::AbstractManifold, p, X)

Given a basis $e_i$ on the tangent space at a point `p` and tangent
vector `X`, compute the vector components $X^i$, such that $X = X^i e_i$, where
Einstein summation notation is used:

````math
\vee : X^i e_i ↦ X^i
````

For array manifolds, this converts an array representation of the tangent
vector to a vector representation. The [`hat`](@ref) map is the `vee` map's
inverse.
"""
function vee(
    M::AbstractGroupManifold{𝔽,O},
    ::Identity{O},
    X,
) where {𝔽,O<:AbstractGroupOperation}
    return get_coordinates_lie(M, X, VeeOrthogonalBasis())
end
function vee!(
    M::AbstractGroupManifold{𝔽,O},
    Y,
    ::Identity{O},
    X,
) where {𝔽,O<:AbstractGroupOperation}
    return get_coordinates_lie!(M, Y, X, VeeOrthogonalBasis())
end
function vee(M::AbstractManifold, e::Identity, ::Any)
    return throw(ErrorException("On $M there exsists no identity $e"))
end
function vee!(M::AbstractManifold, ::Any, e::Identity, ::Any)
    return throw(ErrorException("On $M there exsists no identity $e"))
end

"""
    lie_bracket(G::AbstractGroupManifold, X, Y)

Lie bracket between elements `X` and `Y` of the Lie algebra corresponding to the Lie group `G`.

This can be used to compute the adjoint representation of a Lie algebra.
Note that this representation isn't generally faithful. Notably the adjoint
representation of 𝔰𝔬(2) is trivial.
"""
lie_bracket(G::AbstractGroupManifold, X, Y)
@decorator_transparent_signature lie_bracket(M::AbstractDecoratorManifold, X, Y)

_action_order(p, q, ::LeftAction) = (p, q)
_action_order(p, q, ::RightAction) = (q, p)

@doc raw"""
    translate(G::AbstractGroupManifold, p, q)
    translate(G::AbstractGroupManifold, p, q, conv::ActionDirection=LeftAction()])

Translate group element $q$ by $p$ with the translation $τ_p$ with the specified
`conv`ention, either left ($L_p$) or right ($R_p$), defined as
```math
\begin{aligned}
L_p &: q ↦ p \circ q\\
R_p &: q ↦ q \circ p.
\end{aligned}
```
"""
translate(::AbstractGroupManifold, ::Any...)
@decorator_transparent_function function translate(G::AbstractGroupManifold, p, q)
    return translate(G, p, q, LeftAction())
end
@decorator_transparent_function function translate(
    G::AbstractGroupManifold,
    p,
    q,
    conv::ActionDirection,
)
    return compose(G, _action_order(p, q, conv)...)
end

@decorator_transparent_function function translate!(G::AbstractGroupManifold, X, p, q)
    return translate!(G, X, p, q, LeftAction())
end
@decorator_transparent_function function translate!(
    G::AbstractGroupManifold,
    X,
    p,
    q,
    conv::ActionDirection,
)
    return compose!(G, X, _action_order(p, q, conv)...)
end

@doc raw"""
    inverse_translate(G::AbstractGroupManifold, p, q)
    inverse_translate(G::AbstractGroupManifold, p, q, conv::ActionDirection=LeftAction())

Inverse translate group element $q$ by $p$ with the inverse translation $τ_p^{-1}$ with the
specified `conv`ention, either left ($L_p^{-1}$) or right ($R_p^{-1}$), defined as
```math
\begin{aligned}
L_p^{-1} &: q ↦ p^{-1} \circ q\\
R_p^{-1} &: q ↦ q \circ p^{-1}.
\end{aligned}
```
"""
inverse_translate(::AbstractGroupManifold, ::Any...)
@decorator_transparent_function function inverse_translate(G::AbstractGroupManifold, p, q)
    return inverse_translate(G, p, q, LeftAction())
end
@decorator_transparent_function function inverse_translate(
    G::AbstractGroupManifold,
    p,
    q,
    conv::ActionDirection,
)
    return translate(G, inv(G, p), q, conv)
end

@decorator_transparent_function function inverse_translate!(
    G::AbstractGroupManifold,
    X,
    p,
    q,
)
    return inverse_translate!(G, X, p, q, LeftAction())
end
@decorator_transparent_function function inverse_translate!(
    G::AbstractGroupManifold,
    X,
    p,
    q,
    conv::ActionDirection,
)
    return translate!(G, X, inv(G, p), q, conv)
end

@doc raw"""
    translate_diff(G::AbstractGroupManifold, p, q, X)
    translate_diff(G::AbstractGroupManifold, p, q, X, conv::ActionDirection=LeftAction())

For group elements $p, q ∈ \mathcal{G}$ and tangent vector $X ∈ T_q \mathcal{G}$, compute
the action of the differential of the translation $τ_p$ by $p$ on $X$, with the specified
left or right `conv`ention. The differential transports vectors:
```math
(\mathrm{d}τ_p)_q : T_q \mathcal{G} → T_{τ_p q} \mathcal{G}\\
```
"""
translate_diff(::AbstractGroupManifold, ::Any...)
@decorator_transparent_function function translate_diff(G::AbstractGroupManifold, p, q, X)
    return translate_diff(G, p, q, X, LeftAction())
end
@decorator_transparent_function function translate_diff(
    G::AbstractGroupManifold,
    p,
    q,
    X,
    conv::ActionDirection,
)
    Y = allocate_result(G, translate_diff, X, p, q)
    translate_diff!(G, Y, p, q, X, conv)
    return Y
end

@decorator_transparent_function function translate_diff!(
    G::AbstractGroupManifold,
    Y,
    p,
    q,
    X,
)
    return translate_diff!(G, Y, p, q, X, LeftAction())
end
@decorator_transparent_signature translate_diff!(
    M::AbstractDecoratorManifold,
    Y,
    p,
    q,
    X,
    conv::ActionDirection,
)

@doc raw"""
    inverse_translate_diff(G::AbstractGroupManifold, p, q, X)
    inverse_translate_diff(G::AbstractGroupManifold, p, q, X, conv::ActionDirection=LeftAction())

For group elements $p, q ∈ \mathcal{G}$ and tangent vector $X ∈ T_q \mathcal{G}$, compute
the action on $X$ of the differential of the inverse translation $τ_p$ by $p$, with the
specified left or right `conv`ention. The differential transports vectors:
```math
(\mathrm{d}τ_p^{-1})_q : T_q \mathcal{G} → T_{τ_p^{-1} q} \mathcal{G}\\
```
"""
inverse_translate_diff(::AbstractGroupManifold, ::Any...)
@decorator_transparent_function function inverse_translate_diff(
    G::AbstractGroupManifold,
    p,
    q,
    X,
)
    return inverse_translate_diff(G, p, q, X, LeftAction())
end
@decorator_transparent_function function inverse_translate_diff(
    G::AbstractGroupManifold,
    p,
    q,
    X,
    conv::ActionDirection,
)
    return translate_diff(G, inv(G, p), q, X, conv)
end

@decorator_transparent_function function inverse_translate_diff!(
    G::AbstractGroupManifold,
    Y,
    p,
    q,
    X,
)
    return inverse_translate_diff!(G, Y, p, q, X, LeftAction())
end
@decorator_transparent_function function inverse_translate_diff!(
    G::AbstractGroupManifold,
    Y,
    p,
    q,
    X,
    conv::ActionDirection,
)
    return translate_diff!(G, Y, inv(G, p), q, X, conv)
end

@doc raw"""
    exp_lie(G::AbstractGroupManifold, X)

Compute the group exponential of the Lie algebra element `X`. It is equivalent to the
exponential map defined by the [`CartanSchoutenMinus`](@ref) connection.

Given an element $X ∈ 𝔤 = T_e \mathcal{G}$, where $e$ is the [`Identity`](@ref) element of
the group $\mathcal{G}$, and $𝔤$ is its Lie algebra, the group exponential is the map

````math
\exp : 𝔤 → \mathcal{G},
````
such that for $t,s ∈ ℝ$, $γ(t) = \exp (t X)$ defines a one-parameter subgroup with the
following properties:

````math
\begin{aligned}
γ(t) &= γ(-t)^{-1}\\
γ(t + s) &= γ(t) \circ γ(s) = γ(s) \circ γ(t)\\
γ(0) &= e\\
\lim_{t → 0} \frac{d}{dt} γ(t) &= X.
\end{aligned}
````

!!! note
    In general, the group exponential map is distinct from the Riemannian exponential map
    [`exp`](@ref).

```
exp_lie(G::AbstractGroupManifold{𝔽,AdditionOperation}, X) where {𝔽}
```

Compute $q = X$.

    exp_lie(G::AbstractGroupManifold{𝔽,MultiplicationOperation}, X) where {𝔽}

For `Number` and `AbstractMatrix` types of `X`, compute the usual numeric/matrix
exponential,

````math
\exp X = \operatorname{Exp} X = \sum_{n=0}^∞ \frac{1}{n!} X^n.
````
"""
exp_lie(::AbstractGroupManifold, ::Any...)
@decorator_transparent_function function exp_lie(G::AbstractGroupManifold, X)
    q = allocate_result(G, exp_lie, X)
    return exp_lie!(G, q, X)
end

@decorator_transparent_signature exp_lie!(M::AbstractDecoratorManifold, q, X)

@doc raw"""
    log_lie(G::AbstractGroupManifold, q)
    log_lie!(G::AbstractGroupManifold, X, q)

Compute the Lie group logarithm of the Lie group element `q`. It is equivalent to the
logarithmic map defined by the [`CartanSchoutenMinus`](@ref) connection.

Given an element $q ∈ \mathcal{G}$, compute the right inverse of the group exponential map
[`exp_lie`](@ref), that is, the element $\log q = X ∈ 𝔤 = T_e \mathcal{G}$, such that
$q = \exp X$

!!! note
    In general, the group logarithm map is distinct from the Riemannian logarithm map
    [`log`](@ref).

    For matrix Llie groups this is equal to the (matrix) logarithm:

````math
\log q = \operatorname{Log} q = \sum_{n=1}^∞ \frac{(-1)^{n+1}}{n} (q - e)^n,
````

where $e$ here is the [`Identity`](@ref) element, that is, $1$ for numeric $q$ or the
identity matrix $I_m$ for matrix $q ∈ ℝ^{m × m}$.

Since this function handles [`Identity`](@ref) arguments, the preferred function to override
is `_log_lie!`.
"""
log_lie(::AbstractGroupManifold, ::Any...)
@decorator_transparent_function function log_lie(G::AbstractGroupManifold, q)
    X = allocate_result(G, log_lie, q)
    return log_lie!(G, X, q)
end
function log_lie(
    G::AbstractGroupManifold{𝔽,Op},
    ::Identity{Op},
) where {𝔽,Op<:AbstractGroupOperation}
    return zero_vector(G, identity_element(G))
end

@decorator_transparent_function function log_lie!(G::AbstractGroupManifold, X, q)
    return _log_lie!(G, X, q)
end

function log_lie!(
    G::AbstractGroupManifold{𝔽,Op},
    X,
    ::Identity{Op},
) where {𝔽,Op<:AbstractGroupOperation}
    return zero_vector!(G, X, identity_element(G))
end

############################
# Group-specific Retractions
############################

"""
    GroupExponentialRetraction{D<:ActionDirection} <: AbstractRetractionMethod

Retraction using the group exponential [`exp_lie`](@ref) "translated" to any point on the
manifold.

For more details, see
[`retract`](@ref retract(::GroupManifold, p, X, ::GroupExponentialRetraction)).

# Constructor

    GroupExponentialRetraction(conv::ActionDirection = LeftAction())
"""
struct GroupExponentialRetraction{D<:ActionDirection} <: AbstractRetractionMethod end

function GroupExponentialRetraction(conv::ActionDirection=LeftAction())
    return GroupExponentialRetraction{typeof(conv)}()
end

"""
    GroupLogarithmicInverseRetraction{D<:ActionDirection} <: AbstractInverseRetractionMethod

Retraction using the group logarithm [`log_lie`](@ref) "translated" to any point on the
manifold.

For more details, see
[`inverse_retract`](@ref inverse_retract(::GroupManifold, p, q ::GroupLogarithmicInverseRetraction)).

# Constructor

    GroupLogarithmicInverseRetraction(conv::ActionDirection = LeftAction())
"""
struct GroupLogarithmicInverseRetraction{D<:ActionDirection} <:
       AbstractInverseRetractionMethod end

function GroupLogarithmicInverseRetraction(conv::ActionDirection=LeftAction())
    return GroupLogarithmicInverseRetraction{typeof(conv)}()
end

direction(::GroupExponentialRetraction{D}) where {D} = D()
direction(::GroupLogarithmicInverseRetraction{D}) where {D} = D()

@doc raw"""
    retract(
        G::AbstractGroupManifold,
        p,
        X,
        method::GroupExponentialRetraction{<:ActionDirection},
    )

Compute the retraction using the group exponential [`exp_lie`](@ref) "translated" to any
point on the manifold.
With a group translation ([`translate`](@ref)) $τ_p$ in a specified direction, the
retraction is

````math
\operatorname{retr}_p = τ_p \circ \exp \circ (\mathrm{d}τ_p^{-1})_p,
````

where $\exp$ is the group exponential ([`exp_lie`](@ref)), and $(\mathrm{d}τ_p^{-1})_p$ is
the action of the differential of inverse translation $τ_p^{-1}$ evaluated at $p$ (see
[`inverse_translate_diff`](@ref)).
"""
function retract(G::AbstractGroupManifold, p, X, method::GroupExponentialRetraction)
    conv = direction(method)
    Xₑ = inverse_translate_diff(G, p, p, X, conv)
    pinvq = exp_lie(G, Xₑ)
    q = translate(G, p, pinvq, conv)
    return q
end

function retract!(G::AbstractGroupManifold, q, p, X, method::GroupExponentialRetraction)
    conv = direction(method)
    Xₑ = inverse_translate_diff(G, p, p, X, conv)
    pinvq = exp_lie(G, Xₑ)
    return translate!(G, q, p, pinvq, conv)
end

@doc raw"""
    inverse_retract(
        G::AbstractGroupManifold,
        p,
        X,
        method::GroupLogarithmicInverseRetraction{<:ActionDirection},
    )

Compute the inverse retraction using the group logarithm [`log_lie`](@ref) "translated"
to any point on the manifold.
With a group translation ([`translate`](@ref)) $τ_p$ in a specified direction, the
retraction is

````math
\operatorname{retr}_p^{-1} = (\mathrm{d}τ_p)_e \circ \log \circ τ_p^{-1},
````

where $\log$ is the group logarithm ([`log_lie`](@ref)), and $(\mathrm{d}τ_p)_e$ is the
action of the differential of translation $τ_p$ evaluated at the identity element $e$
(see [`translate_diff`](@ref)).
"""
function inverse_retract(G::GroupManifold, p, q, method::GroupLogarithmicInverseRetraction)
    conv = direction(method)
    pinvq = inverse_translate(G, p, q, conv)
    Xₑ = log_lie(G, pinvq)
    return translate_diff(G, p, Identity(G), Xₑ, conv)
end

function inverse_retract!(
    G::AbstractGroupManifold,
    X,
    p,
    q,
    method::GroupLogarithmicInverseRetraction,
)
    conv = direction(method)
    pinvq = inverse_translate(G, p, q, conv)
    Xₑ = log_lie(G, pinvq)
    return translate_diff!(G, X, p, Identity(G), Xₑ, conv)
end

#################################
# Overloads for AdditionOperation
#################################

"""
    AdditionOperation <: AbstractGroupOperation

Group operation that consists of simple addition.
"""
struct AdditionOperation <: AbstractGroupOperation end

const AdditionGroup = AbstractGroupManifold{𝔽,AdditionOperation} where {𝔽}

Base.:+(e::Identity{AdditionOperation}) = e
Base.:+(e::Identity{AdditionOperation}, ::Identity{AdditionOperation}) = e
Base.:+(::Identity{AdditionOperation}, p) = p
Base.:+(p, ::Identity{AdditionOperation}) = p

Base.:-(e::Identity{AdditionOperation}) = e
Base.:-(e::Identity{AdditionOperation}, ::Identity{AdditionOperation}) = e
Base.:-(::Identity{AdditionOperation}, p) = -p
Base.:-(p, ::Identity{AdditionOperation}) = p

Base.:*(e::Identity{AdditionOperation}, p) = e
Base.:*(p, e::Identity{AdditionOperation}) = e
Base.:*(e::Identity{AdditionOperation}, ::Identity{AdditionOperation}) = e

adjoint_action(::AdditionGroup, p, X) = X

adjoint_action!(G::AdditionGroup, Y, p, X) = copyto!(G, Y, p, X)

identity_element(::AdditionGroup, p::Number) = zero(p)

function identity_element!(::AbstractGroupManifold{𝔽,<:AdditionOperation}, p) where {𝔽}
    return fill!(p, zero(eltype(p)))
end

Base.inv(::AdditionGroup, p) = -p
Base.inv(::AdditionGroup, e::Identity) = e

inv!(G::AdditionGroup, q, p) = copyto!(G, q, -p)
inv!(G::AdditionGroup, q, ::Identity{AdditionOperation}) = identity_element!(G, q)
inv!(::AdditionGroup, q::Identity{AdditionOperation}, e::Identity{AdditionOperation}) = q

function is_identity(G::AdditionGroup, q; kwargs...)
    return isapprox(G, q, zero(q); kwargs...)
end
function is_identity(G::AdditionGroup, e::Identity; kwargs...)
    return invoke(is_identity, Tuple{AbstractGroupManifold,typeof(e)}, G, e; kwargs...)
end

_compose(::AdditionGroup, p, q) = p + q

function _compose!(::AdditionGroup, x, p, q)
    x .= p .+ q
    return x
end

translate_diff(::AdditionGroup, p, q, X, ::ActionDirection) = X

translate_diff!(G::AdditionGroup, Y, p, q, X, ::ActionDirection) = copyto!(G, Y, p, X)

inverse_translate_diff(::AdditionGroup, p, q, X, ::ActionDirection) = X

function inverse_translate_diff!(G::AdditionGroup, Y, p, q, X, ::ActionDirection)
    return copyto!(G, Y, p, X)
end

exp_lie(::AdditionGroup, X) = X

exp_lie!(G::AdditionGroup, q, X) = copyto!(G, q, X)

log_lie(::AdditionGroup, q) = q
function log_lie(G::AdditionGroup, ::Identity{AdditionOperation})
    return zero_vector(G, identity_element(G))
end

_log_lie!(G::AdditionGroup, X, q) = copyto!(G, X, q)

lie_bracket(::AdditionGroup, X, Y) = zero(X)

lie_bracket!(::AdditionGroup, Z, X, Y) = fill!(Z, 0)

#######################################
# Overloads for MultiplicationOperation
#######################################

"""
    MultiplicationOperation <: AbstractGroupOperation

Group operation that consists of multiplication.
"""
struct MultiplicationOperation <: AbstractGroupOperation end

const MultiplicationGroup = AbstractGroupManifold{𝔽,MultiplicationOperation} where {𝔽}

Base.:*(e::Identity{MultiplicationOperation}) = e
Base.:*(::Identity{MultiplicationOperation}, p) = p
Base.:*(p, ::Identity{MultiplicationOperation}) = p
Base.:*(e::Identity{MultiplicationOperation}, ::Identity{MultiplicationOperation}) = e
Base.:*(::Identity{MultiplicationOperation}, e::Identity{AdditionOperation}) = e
Base.:*(e::Identity{AdditionOperation}, ::Identity{MultiplicationOperation}) = e

Base.:/(p, ::Identity{MultiplicationOperation}) = p
Base.:/(::Identity{MultiplicationOperation}, p) = inv(p)
Base.:/(e::Identity{MultiplicationOperation}, ::Identity{MultiplicationOperation}) = e

Base.:\(p, ::Identity{MultiplicationOperation}) = inv(p)
Base.:\(::Identity{MultiplicationOperation}, p) = p
Base.:\(e::Identity{MultiplicationOperation}, ::Identity{MultiplicationOperation}) = e

LinearAlgebra.det(::Identity{MultiplicationOperation}) = true
LinearAlgebra.adjoint(e::Identity{MultiplicationOperation}) = e

function identity_element!(::MultiplicationGroup, p::AbstractMatrix)
    return copyto!(p, I)
end

function identity_element!(G::MultiplicationGroup, p::AbstractArray)
    if length(p) == 1
        fill!(p, one(eltype(p)))
    else
        throw(DimensionMismatch("Array $p cannot be set to identity element of group $G"))
    end
    return p
end

function is_identity(G::MultiplicationGroup, q::Number; kwargs...)
    return isapprox(G, q, one(q); kwargs...)
end
function is_identity(G::MultiplicationGroup, q::AbstractVector; kwargs...)
    return length(q) == 1 && isapprox(G, q[], one(q[]); kwargs...)
end
function is_identity(G::MultiplicationGroup, q::AbstractMatrix; kwargs...)
    return isapprox(G, q, I; kwargs...)
end
function is_identity(G::MultiplicationGroup, e::Identity; kwargs...)
    return invoke(is_identity, Tuple{AbstractGroupManifold,typeof(e)}, G, e; kwargs...)
end

LinearAlgebra.mul!(q, ::Identity{MultiplicationOperation}, p) = copyto!(q, p)
LinearAlgebra.mul!(q, p, ::Identity{MultiplicationOperation}) = copyto!(q, p)
function LinearAlgebra.mul!(
    q::AbstractMatrix,
    ::Identity{MultiplicationOperation},
    ::Identity{MultiplicationOperation},
)
    return copyto!(q, I)
end
function LinearAlgebra.mul!(
    q,
    ::Identity{MultiplicationOperation},
    ::Identity{MultiplicationOperation},
)
    return copyto!(q, one(q))
end
function LinearAlgebra.mul!(
    q::Identity{MultiplicationOperation},
    ::Identity{MultiplicationOperation},
    ::Identity{MultiplicationOperation},
)
    return q
end
Base.one(e::Identity{MultiplicationOperation}) = e

Base.inv(::MultiplicationGroup, p) = inv(p)
Base.inv(::MultiplicationGroup, e::Identity{MultiplicationOperation}) = e

inv!(G::MultiplicationGroup, q, p) = copyto!(q, inv(G, p))
function inv!(G::MultiplicationGroup, q, ::Identity{MultiplicationOperation})
    return identity_element!(G, q)
end
function inv!(
    ::MultiplicationGroup,
    q::Identity{MultiplicationOperation},
    e::Identity{MultiplicationOperation},
)
    return q
end

_compose(::MultiplicationGroup, p, q) = p * q

_compose!(::MultiplicationGroup, x, p, q) = mul!_safe(x, p, q)

inverse_translate(::MultiplicationGroup, p, q, ::LeftAction) = p \ q
inverse_translate(::MultiplicationGroup, p, q, ::RightAction) = q / p

function inverse_translate!(G::MultiplicationGroup, x, p, q, conv::ActionDirection)
    return copyto!(x, inverse_translate(G, p, q, conv))
end

function exp_lie!(G::MultiplicationGroup, q, X)
    X isa Union{Number,AbstractMatrix} && return copyto!(q, exp(X))
    return error(
        "exp_lie! not implemented on $(typeof(G)) for vector $(typeof(X)) and element $(typeof(q)).",
    )
end

log_lie!(::MultiplicationGroup, X::AbstractMatrix, q::AbstractMatrix) = log_safe!(X, q)

lie_bracket(::MultiplicationGroup, X, Y) = mul!(X * Y, Y, X, -1, true)

function lie_bracket!(::MultiplicationGroup, Z, X, Y)
    mul!(Z, X, Y)
    mul!(Z, Y, X, -1, true)
    return Z
end

@doc raw"""
    get_vector_lie(G::AbstractGroupManifold, a, B::AbstractBasis)

Reconstruct a tangent vector from the Lie algebra of `G` from cooordinates `a` of a basis `B`.
This is similar to calling [`get_vector`](@ref) at the `p=`[`Identity`](@ref)`(G)`.
"""
function get_vector_lie(G::AbstractGroupManifold, X, B::AbstractBasis)
    return get_vector(G, identity_element(G), X, B)
end
function get_vector_lie!(G::AbstractGroupManifold, Y, X, B::AbstractBasis)
    return get_vector!(G, Y, identity_element(G), X, B)
end

@doc raw"""
    get_coordinates_lie(G::AbstractGroupManifold, X, B::AbstractBasis)

Get the coordinates of an element `X` from the Lie algebra og `G` with respect to a basis `B`.
This is similar to calling [`get_coordinates`](@ref) at the `p=`[`Identity`](@ref)`(G)`.
"""
function get_coordinates_lie(G::AbstractGroupManifold, X, B::AbstractBasis)
    return get_coordinates(G, identity_element(G), X, B)
end
function get_coordinates_lie!(G::AbstractGroupManifold, a, X, B::AbstractBasis)
    return get_coordinates!(G, a, identity_element(G), X, B)
end

# (a) changes / parent.
for f in [
    embed,
    get_basis,
    vector_transport_direction,
    vector_transport_direction!,
    vector_transport_to,
]
    eval(
        quote
            function decorator_transparent_dispatch(
                ::typeof($f),
                ::AbstractGroupManifold{𝔽,O,<:AbstractGroupDecoratorType},
                args...,
            ) where {𝔽,O}
                return Val(:parent)
            end
        end,
    )
end
for f in [
    get_coordinates,
    get_coordinates!,
    get_vector,
    get_vector!,
    inverse_retract!,
    mid_point!,
    project,
    retract!,
    vector_transport_along,
]
    eval(
        quote
            function decorator_transparent_dispatch(
                ::typeof($f),
                ::AbstractGroupManifold{𝔽,O,DefaultGroupDecoratorType},
                args...,
            ) where {𝔽,O}
                return Val(:parent)
            end
        end,
    )
end
# (b) changes / transparencies
for f in [
    check_point,
    check_vector,
    copy,
    copyto!,
    distance,
    exp,
    exp!,
    embed!,
    get_coordinates,
    get_coordinates!,
    get_vector,
    get_vector!,
    inner,
    inverse_retract,
    inverse_retract!,
    isapprox,
    log,
    log!,
    mid_point,
    mid_point!,
    project!,
    project,
    retract,
    retract!,
    vector_transport_along,
    vector_transport_direction,
]
    eval(
        quote
            function decorator_transparent_dispatch(
                ::typeof($f),
                ::AbstractGroupManifold{𝔽,O,<:TransparentGroupDecoratorType},
                args...,
            ) where {𝔽,O}
                return Val(:transparent)
            end
        end,
    )
end

# (c) changes / intransparencies.
for f in [
    compose,
    compose!,
    exp_lie,
    exp_lie!,
    log_lie,
    log_lie!,
    translate,
    translate!,
    translate_diff,
    translate_diff!,
]
    eval(
        quote
            function decorator_transparent_dispatch(
                ::typeof($f),
                ::AbstractGroupManifold,
                args...,
            )
                return Val(:intransparent)
            end
        end,
    )
end
# (d) specials
for f in [vector_transport_along!, vector_transport_direction!, vector_transport_to!]
    eval(
        quote
            function decorator_transparent_dispatch(
                ::typeof($f),
                ::AbstractGroupManifold{𝔽,O,<:TransparentGroupDecoratorType},
                Y,
                p,
                X,
                q,
                ::T,
            ) where {𝔽,O,T}
                return Val(:transparent)
            end
            function decorator_transparent_dispatch(
                ::typeof($f),
                ::AbstractGroupManifold{𝔽,O,<:AbstractGroupDecoratorType},
                Y,
                p,
                X,
                q,
                ::T,
            ) where {𝔽,O,T}
                return Val(:intransparent)
            end
        end,
    )
    for m in [PoleLadderTransport, SchildsLadderTransport, ScaledVectorTransport]
        eval(
            quote
                function decorator_transparent_dispatch(
                    ::typeof($f),
                    ::AbstractGroupManifold{𝔽,O,<:TransparentGroupDecoratorType},
                    Y,
                    p,
                    X,
                    q,
                    ::$m,
                ) where {𝔽,O}
                    return Val(:parent)
                end
                function decorator_transparent_dispatch(
                    ::typeof($f),
                    ::AbstractGroupManifold{𝔽,O,<:AbstractGroupDecoratorType},
                    Y,
                    p,
                    X,
                    q,
                    ::$m,
                ) where {𝔽,O}
                    return Val(:parent)
                end
            end,
        )
    end
end


text:
# include("newtrees.jl")
# using Trees
#
# using AccessMacro
# using Missings
# using LogProbs
# using DataStructures
#
# using StatsFuns.RFunctions: gammarand
#
# using LightGraphs: Graph, add_vertex!, add_edge!, nv
#
# import TikzGraphs: plot
# import Base: show, hash, ==
# import Base: +, -, *, /, zero, one, <
# import Base: start, length, insert!, isempty, convert, getindex, promote_rule, range
# import DataStructures: enqueue!, dequeue!

prob(p::LogProb) = p
# prob(s::Product) = first(s)

##############
### ModInt ###
##############

struct ModInt{n} <: Number
  val::Int
  ModInt{n}(val) where {n} = new(mod(val,n))
end

show{n}(io::IO, a::ModInt{n}) = print(io, "$(a.val) mod $n")

+{n}(a::ModInt{n}, b::ModInt{n}) = ModInt{n}(a.val + b.val)
-{n}(a::ModInt{n}) = n - a.val
-{n}(a::ModInt{n}, b::ModInt{n}) = ModInt{n}(a.val - b.val)
*{n}(a::ModInt{n}, b::ModInt{n}) = ModInt{n}(a.val * b.val)
/{n}(a::ModInt{n}, b::ModInt{n}) = a * invmod(b, n)

<{n}(a::ModInt{n}, b::ModInt{n}) = a.val < b.val

one{n}(a::ModInt{n}) = ModInt{n}(1)
zero{n}(a::ModInt{n}) = ModInt{n}(0)

convert{n}(::Type{ModInt{n}}, x::Int) = ModInt{n}(x)
convert{n}(::Type{Int}, x::ModInt{n}) = x.val

getindex{n}(t::Union{Tuple, Array}, i::ModInt{n}) = getindex(t, i.val + 1)

promote_rule{n}(::Type{ModInt{n}}, ::Type{Int}) = ModInt{n}

############################################
### Generic Categorical Sampling Methods ###
############################################

function categorical_sample(tokens, weights)
    x = rand() * sum(weights)
    cum_weights = zero(eltype(weights))
    for (t, w) in zip(tokens, weights)
        cum_weights += w
        if cum_weights >= x
            return t
        end
    end
    error("categorical sample failed with length(tokens)=$(length(tokens)), weights=$weights")
end

categorical_sample(d::Dict) = categorical_sample(keys(d), values(d))
categorical_sample(v::Vector) = categorical_sample(1:length(v), v)

################################
### Conditional Distribution ###
################################

struct SimpleCond{C, D, S} # context, distribution, support
    dists   :: Dict{C, D}
    support :: S
    SimpleCond(dists::Dict{C, D}, support::S) where {C, D, S} =
        new{C, D, S}(dists, unique(support))
end

function SimpleCond(dists::Associative)
    SimpleCond(
        dists,
        vcat([collect(support(dist)) for dist in values(dists)]...)
    )
end

sample(sc::SimpleCond, context, args...) = sample(sc.dists[context], args...)
logscore(sc::SimpleCond, obs, context) = logscore(sc.dists[context], obs)
rm_obs!(sc::SimpleCond, obs, context) = rm_obs!(sc.dists[context], obs)

score_type(::SimpleCond) = LogProb

function add_obs!{C,D,S}(cond::SimpleCond{C,D,S}, obs, context)
    if !haskey(cond.dists, context)
        cond.dists[context] = D(cond.support)
    end
    add_obs!(cond.dists[context], obs)
end

#############################
### Dirichlet Multinomial ###
#############################

abstract type Distribution{T} end

mutable struct DirCat{T, C} <: Distribution{T}
    counts :: Dict{T, C}
end

DirCat(support, priors) = DirCat(Dict(x => p for (x,p) in zip(support, priors)))
support(dc::DirCat) = keys(dc.counts)

function sample(dc::DirCat)
    weights = [gammarand(c, 1) for c in values(dc.counts)]
    categorical_sample(keys(dc.counts), weights)
end

function logscore(dc::DirCat, obs)
    LogProb(lbeta(sum(values(dc.counts)), 1) - lbeta(dc.counts[obs], 1))
end

function add_obs!(dc::DirCat, obs)
    dc.counts[obs] += 1
end

function rm_obs!(dc::DirCat, obs)
    dc.counts[obs] -= 1
end

##############
### CFRule ###
##############

mutable struct RunningCounter
    n :: Int
end

RunningCounter() = RunningCounter(0)
count!(c::RunningCounter) = c.n += 1

rule_counter = RunningCounter()

struct CFRule{LHS, RHS} # left hand side and right hand side of the rule
    mappings ::Dict{LHS, Vector{RHS}}
    name :: Symbol
end

==(r1::CFRule, r2::CFRule) = r1.name == r2.name
hash(r::CFRule, h::UInt) = hash(hash(CFRule, hash(r.name)), h)

Base.show(io::IO, r::CFRule) = print(io, "CFRule($(r.name))")

CFRule(pairs::Pair...) =
    CFRule(Dict(pairs...), Symbol("rule", count!(rule_counter)))
CFRule(g::Base.Generator) =
    CFRule(Dict(g), Symbol("rule", count!(rule_counter)))
CFRule(f::Function, lhss, name) =
    CFRule(Dict(lhs => f(lhs) for lhs in lhss), name)
CFRule(f::Function, lhss) =
    CFRule(Dict(lhs => f(lhs) for lhs in lhss), Symbol("rule", count!(rule_counter)))

lhss(r::CFRule) = keys(r.mappings) # aka domain
isapplicable(r::CFRule, lhs) = haskey(r.mappings, lhs)
(r::CFRule)(lhs) = r.mappings[lhs]

###############
### CFState ###
###############

mutable struct CompletionAutomaton{Cat,Comp} # category, completion
    transitions :: Vector{Dict{Cat, Int}}
    completions :: Vector{Vector{Comp}}
end

CompletionAutomaton(Cat::Type, Comp::Type) =
    CompletionAutomaton([Dict{Cat, Int}()], [Vector{Comp}()])

number_of_states(ca::CompletionAutomaton) = length(ca.transitions)
isfinal(ca::CompletionAutomaton, s) = isempty(ca.transitions[s])
is_possible_transition(ca::CompletionAutomaton, s, c) = haskey(ca.transitions[s], c)
transition(ca::CompletionAutomaton, s, c) = ca.transitions[s][c]
completions(ca::CompletionAutomaton, s) = ca.completions[s]

function add_completion!{Cat,Comp}(ca::CompletionAutomaton{Cat,Comp}, comp, categories)
    s = 1
    for c in categories
        if is_possible_transition(ca, s, c)
            s = transition(ca, s, c)
        else
            push!(ca.transitions, Dict{Cat,Int}())
            push!(ca.completions, Vector{Comp}())
            s = ca.transitions[s][c] = number_of_states(ca)
        end
    end
    push!(ca.completions[s], comp)
end

function add_rule!(ca::CompletionAutomaton, r::CFRule)
    for lhs in lhss(r)
        add_completion!(ca, (lhs, r), r(lhs))
    end
end

# mutable struct CFState{C, R} # category and rule
#     completions   :: Vector{Tuple{C, R}}
#     transitions   :: Dict{C, CFState{C, R}}
#     hastransition :: Bool
# end
#
# CFState(C::Type, R::Type) =
#     CFState(Vector{Tuple{C, R}}(), Dict{C, CFState{C, R}}(), false)
#
# hastransition(s::CFState) = s.hastransition
# isfinal(s::CFState) = !s.hastransition
# isfinal(s::Ptr) = !unsafe_pointer_to_objref(s).hastransition ::Bool
#
# is_possible_transition(s::CFState, c) = hastransition(s) && haskey(s.transitions, c)
# transition(s::CFState, c) = s.transitions[c]
#
# function add_rule!(state::CFState{C, R}, r::R) where {C, R}
#     for lhs in lhss(r)
#         s = state
#         for c in r(lhs)
#             if is_possible_transition(s, c)
#                 s = transition(s, c)
#             else
#                 s.hastransition = true
#                 s = s.transitions[c] = CFState(C, R)
#             end
#         end
#         push!(s.completions, (lhs, r))
#     end
# end

#################
### CFGrammar ###
#################

struct CFGrammar{C, T, Cond, F}
    comp_automtn  :: CompletionAutomaton{C, Tuple{C, CFRule{C, C}}}
    startsymbols  :: Vector{C}
    terminal_dict :: Dict{T, Vector{Tuple{C, CFRule{C, T}}}}
    cond          :: Cond # conditional scoring
    dependent_components::F
end

function CFGrammar{C, T}(
        category_rules::Vector{CFRule{C, C}},
        terminal_rules::Vector{CFRule{C, T}},
        startsymbols  ::Vector{C},
        dependent_components=identity::Function
    )
    comp_automtn = CompletionAutomaton(C, Tuple{C, CFRule{C, C}})
    for r in category_rules
        add_rule!(comp_automtn, r)
    end

    terminal_dict = Dict{T, Vector{Tuple{C, CFRule{C, T}}}}()
    for r in terminal_rules
        for lhs in lhss(r)
        t = r(lhs)[1]
            if haskey(terminal_dict, t)
                push!(terminal_dict[t], (lhs, r))
            else
                terminal_dict[t] = [(lhs, r)]
            end
        end
    end

    applicable_rules = Dict{C, Vector{CFRule}}()
    for r in CFRule[category_rules; terminal_rules]
        for c in lhss(r)
            if haskey(applicable_rules, c)
                push!(applicable_rules[c], r)
            else
                applicable_rules[c] = CFRule[r]
            end
        end
    end

    cond = SimpleCond(
        Dict(
            dependent_components(c) => let rules = applicable_rules[c]
                n = length(rules)
                k = count(isa.(rules, CFRule{C, T})) # number terminal rules
                DirCat(rules, [fill(1.0, n-k); fill(1/k, k)])
            end
            for c in keys(applicable_rules)
        )
    )

    CFGrammar(comp_automtn, startsymbols, terminal_dict, cond, dependent_components)
end

dependent_components(g::CFGrammar, c) = g.dependent_components(c)

startstate(g::CFGrammar) = 1
startsymbols(g::CFGrammar) = g.startsymbols

isfinal(g::CFGrammar, s) = isfinal(g.comp_automtn, s)
is_possible_transition(g::CFGrammar, s, c) = is_possible_transition(g.comp_automtn, s, c)
transition(g::CFGrammar, s, c) = transition(g.comp_automtn, s, c)

completions(g::CFGrammar, s::Int) =
    ((c, r, score(g, c, r)) for (c, r) in completions(g.comp_automtn, s))
completions(g::CFGrammar, t) =
    ((c, r, score(g, c, r)) for (c, r) in g.terminal_dict[t])

score(g::CFGrammar, c, r) = logscore(g.cond, r, dependent_components(g, c))

@inline function types{C, T, Cond}(grammar::CFGrammar{C, T, Cond})
    C, T, CFRule{C, C}, CFRule{C, T}, Int, LogProb
end

#############
### Range ###
#############

abstract type ItemRange end

ItemRange(s::Int, e::Int, n::Int, cyclic::Bool) =
    cyclic ? CyclicRange(s, e, n) : IntervalRange(s, e)

start(r::ItemRange) = r.start
_end(r::ItemRange)  = r._end

struct IntervalRange <: ItemRange
    start :: Int
    _end  :: Int
end

length(r::IntervalRange) = _end(r) - start(r)
concatenable(r1::IntervalRange, r2::IntervalRange) = _end(r1) == start(r2)

function *(r1::IntervalRange, r2::IntervalRange)
    @assert concatenable(r1, r2)
    IntervalRange(start(r1), _end(r2))
end

struct CyclicRange{n} <: ItemRange
    start  :: ModInt{n}
    _end   :: ModInt{n}
    length :: Int
end
CyclicRange{n}(s::ModInt{n}, e::ModInt{n}) = CyclicRange(s, e, Int(e-s))
CyclicRange(s::Int, e::Int, n::Int) = CyclicRange(ModInt{n}(s), ModInt{n}(e))

length(r::CyclicRange) = r.length

@inline function concatenable(r1::CyclicRange{n}, r2::CyclicRange{n}) where n
    _end(r1) == start(r2) && length(r1) + length(r2) <= n
end

function *(r1::CyclicRange, r2::CyclicRange)
    @assert concatenable(r1, r2)
    CyclicRange(start(r1), _end(r2), length(r1) + length(r2))
end

# tests
# isbits(CyclicRange{10})
# length(CyclicRange(4, 2, 10)) == 8
# concatenable(CyclicRange(2, 4, 7), CyclicRange(4, 5, 7))
# CyclicRange(2, 4, 7) * CyclicRange(4, 5, 7) == CyclicRange(2, 5, 7)
#
# !concatenable(CyclicRange(2, 4, 7), CyclicRange(5, 6, 7))
# concatenable(CyclicRange(2, 4, 7), CyclicRange(4, 1, 7))
# concatenable(CyclicRange(2, 4, 7), CyclicRange(4, 2, 7))
# !concatenable(CyclicRange(2, 4, 7), CyclicRange(4, 3, 7))

###################
### Completions ###
###################

@access struct TerminalCompletion{T,TR,S}
    terminal :: T
    rule     :: TR
    score    :: S
end

@access struct EdgeCompletion{E,CR,S}
    edge   :: E
    rule   :: CR
    score  :: S
    inloop :: Bool
end
EdgeCompletion(edge, rule, score) = EdgeCompletion(edge, rule, score, false)
@inline function ==(c1::EdgeCompletion, c2::EdgeCompletion)
    c1.edge == c2.edge && c1.rule == c2.rule
end

#################
### Traversal ###
#################

struct Traversal{E,CO,S}
    edge   :: Nullable{E}
    cont   :: CO
    score  :: S
    inloop :: Bool
end
Traversal(edge, cont, score) = Traversal(Nullable(edge), cont, score, false)
Traversal(edge, cont) = Traversal(Nullable(edge), cont, score(edge) * score(cont), false)
hasedge(trav::Traversal) = !isnull(trav.edge)
edge(trav::Traversal) = get(trav.edge)
cont(trav::Traversal) = trav.cont
score(trav::Traversal) = trav.score
inloop(trav::Traversal) = trav.inloop

@inline function ==(t1::Traversal, t2::Traversal)
    if hasedge(t1)
        if hasedge(t2)
            get(t1.edge) == get(t2.edge) && t1.cont == t2.cont
        else
            false
        end
    else
        if hasedge(t2)
            false
        else
            t1.cont == t2.cont
        end
    end
end

###############
### ItemKey ###
###############

abstract type ItemKey{R} end

range(k::ItemKey)  =          k.range
start(k::ItemKey)  =  start(range(k))
_end(k::ItemKey)   =   _end(range(k))
length(k::ItemKey) = length(range(k))

# ==(k1::ItemKey, k2::ItemKey) =
#     getfield(k1,1) == getfield(k2,1) && getfield(k1,2) == getfield(k2,2)
# hash(k::K) where K <: ItemKey =
#     hash(K, hash(getfield(k,1), hash(getfield(k,2))))

struct ConstituentKey{R,C} <: ItemKey{R}
    range    :: R
    category :: C
end
category(k::ConstituentKey) = k.category

struct EdgeKey{R,ST} <: ItemKey{R}
    range :: R
    state :: ST
end
state(k::EdgeKey) = k.state

############
### Item ###
############

abstract type Item end

Item(key, trav::Traversal) = Edge(key, trav)
Item(key, comp::EdgeCompletion) = Constituent(key, comp)

key(item::Item) = item.key
range(item::Item) = range(key(item))
start(item::Item) = start(range(item))
_end(item::Item) = _end(range(item))
length(item::Item) = length(range(item))
isfinished(item::Item) = !(isnull(item.score))
lastpopscore(item::Item) = item.lastpopscore
insidepopnumber(item::Item) = item.insidepopnumber

############
### Edge ###
############

mutable struct Edge{R,ST,S,CO} <: Item
    key             :: EdgeKey{R,ST}
    score           :: Nullable{S}
    lastpopscore    :: S
    insidepopnumber :: Int
    traversals      :: Vector{Traversal{Edge{R,ST,S,CO},CO,S}}
end

@inline function Edge{E,CO,S}(key, trav::Traversal{E,CO,S})
    Edge(key, Nullable{S}(), zero(S), 0, [trav])
end

state(edge::Edge) = state(key(edge))
traversals(edge::Edge) = edge.traversals

@inline function score(edge::Edge)
    if isfinished(edge)
        get(edge.score)
    else
        sum(score(trav) for trav in edge.traversals)
    end
end

function add!(edge::Edge, trav)
    i = findfirst(t->t==trav, edge.traversals)
    if i != 0
        edge.traversals[i] = trav
    else
        push!(edge.traversals, trav)
    end
    nothing
end

###################
### Constituent ###
###################

mutable struct Constituent{R,C,T,CR,TR,ST,S} <: Item
    key                 :: ConstituentKey{R,C}
    score               :: Nullable{S}
    lastpopscore        :: S
    insidepopnumber     :: Int
    terminal_completion :: Nullable{TerminalCompletion{T,TR,S}}
    completions         :: Vector{EdgeCompletion{Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}},CR,S}}
end

@inline function Constituent{R,C}(
        key::ConstituentKey{R,C}, comp::TerminalCompletion, grammar
    )
    C_, T, CR, TR, ST, S = types(grammar)
    Constituent(
        key, Nullable{S}(), zero(S), 0, Nullable(comp),
        Vector{EdgeCompletion{Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}},CR,S}}()
    )
end

@inline function Constituent{R,C,T,CR,TR,ST,S}(
        key,
        comp :: EdgeCompletion{Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}},CR,S}
    )
    Constituent(
        key, Nullable{S}(), zero(S), 0,
        Nullable{TerminalCompletion{T,TR,S}}(),
        [comp]
    )
end

category(cont::Constituent) = category(key(cont))
completions(cont::Constituent) = cont.completions

hasterminal(cont::Constituent) = !(isnull(cont.terminal_completion))
terminal_completion(cont::Constituent) = get(cont.terminal_completion)
terminal(cont::Constituent) = get(cont.terminal_completion).terminal

@inline function score(cont::Constituent)
    if isfinished(cont)
        get(cont.score)
    else
        if hasterminal(cont)
            if isempty(completions(cont))
                score(terminal_completion(cont))
            else
                +(
                    score(terminal_completion(cont)),
                    sum(score(comp) for comp in completions(cont))
                )
            end
        else
            sum(score(comp) for comp in completions(cont))
        end
    end
end

function add!(cont::Constituent, comp)
    i = findfirst(c->c==comp, cont.completions)
    if i != 0
        cont.completions[i] = comp
    else
        push!(cont.completions, comp)
    end
    nothing
end

@inline function Traversal{R,C,T,CR,TR,ST,S}(cont::Constituent{R,C,T,CR,TR,ST,S})
    Traversal(Nullable{Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}}}(), cont, score(cont), false)
end

#####################
### ParserLogbook ###
#####################

struct ParserLogbook{R,C,T,CR,TR,ST,S}
    edges :: Dict{EdgeKey{R,ST}, Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}}}
    conts :: Dict{ConstituentKey{R,C}, Constituent{R,C,T,CR,TR,ST,S}}
end

@inline function ParserLogbook(grammar, n::Int, cyclic::Bool)
    R = cyclic ? CyclicRange{n} : IntervalRange
    C,T,CR,TR,ST,S = types(grammar)
    ParserLogbook(
        Dict{EdgeKey{R,ST}, Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}}}(),
        Dict{ConstituentKey{R,C}, Constituent{R,C,T,CR,TR,ST,S}}()
    )
end
discover!(logbook::ParserLogbook, edge::Edge) =
    logbook.edges[key(edge)] = edge
discover!(logbook::ParserLogbook, cont::Constituent) =
    logbook.conts[key(cont)] = cont
isdiscovered(logbook, key::EdgeKey) = haskey(logbook.edges, key)
isdiscovered(logbook, key::ConstituentKey) = haskey(logbook.conts, key)
getitem(logbook, key::EdgeKey) = logbook.edges[key]
getitem(logbook, key::ConstituentKey) = logbook.conts[key]

##################
### ParseChart ###
##################

struct ChartCell{R,C,T,CR,TR,ST,S}
    edges :: Dict{ST, Vector{Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}}}}
    conts :: Dict{C, Vector{Constituent{R,C,T,CR,TR,ST,S}}}
end
@inline function ChartCell(grammar, n::Int, cyclic::Bool)
    R = cyclic ? CyclicRange{n} : IntervalRange
    C,T,CR,TR,ST,S = types(grammar)
    ChartCell(
        Dict{ST, Vector{Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}}}}(),
        Dict{C, Vector{Constituent{R,C,T,CR,TR,ST,S}}}()
    )
end

struct ParseChart{R,C,T,CR,TR,ST,S}
    cells :: Vector{ChartCell{R,C,T,CR,TR,ST,S}}
end
# vector indices begin with 1
# item   indices begin with 0

edges(chart::ParseChart, edge::Edge)        = chart.cells[ _end(edge)+1].edges
edges(chart::ParseChart, cont::Constituent) = chart.cells[start(cont)+1].edges
conts(chart::ParseChart, edge::Edge)        = chart.cells[ _end(edge)+1].conts
conts(chart::ParseChart, cont::Constituent) = chart.cells[start(cont)+1].conts

@inline function push_or_init!(d::Dict, k, v)
    if haskey(d, k)
        push!(d[k], v)
    else
        d[k] = [v]
    end
end
insert!(chart::ParseChart, edge::Edge) =
    push_or_init!(edges(chart, edge), state(edge), edge)
insert!(chart::ParseChart, cont::Constituent) =
    push_or_init!(conts(chart, cont), category(cont), cont)

####################
### InsideAgenda ###
####################

struct InsideAgenda{R,C,T,CR,TR,ST,S}
    edge_queue :: PriorityQueue{Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}}, Int, Base.Order.ForwardOrdering}
    cont_queue :: PriorityQueue{Constituent{R,C,T,CR,TR,ST,S}, Int, Base.Order.ForwardOrdering}
end
function InsideAgenda(grammar, n::Int, cyclic)
    R = cyclic ? CyclicRange{n} : IntervalRange
    C,T,CR,TR,ST,S = types(grammar)
    InsideAgenda(
        PriorityQueue{Edge{R,ST,S,Constituent{R,C,T,CR,TR,ST,S}}, Int}(),
        PriorityQueue{Constituent{R,C,T,CR,TR,ST,S}, Int}()
    )
end
@inline function enqueue!(agenda::InsideAgenda, edge::Edge, just_used)
    agenda.edge_queue[edge] = priority(edge, just_used)
end
@inline function enqueue!(agenda::InsideAgenda, cont::Constituent, just_used)
    agenda.cont_queue[cont] = priority(cont, just_used)
end
@inline function next_is_edge(agenda::InsideAgenda)
    isempty(agenda.cont_queue) || !isempty(agenda.edge_queue) && peek(agenda.edge_queue)[2] < peek(agenda.cont_queue)[2]
end
dequeue_edge!(agenda::InsideAgenda)    = dequeue!(agenda.edge_queue)
dequeue_cont!(agenda::InsideAgenda)    = dequeue!(agenda.cont_queue)
isempty(agenda::InsideAgenda)          = isempty(agenda.edge_queue) && isempty(agenda.cont_queue)
priority(edge::Edge, just_used)        = 4 * length(edge) - 2*!(just_used) - 1
priority(cont::Constituent, just_used) = 4 * length(cont) - 2*!(just_used)

###################
### ParseForest ###
###################

@access struct ParseForest{R,C,T,CR,TR,ST,S}
    heads     :: Vector{Constituent{R,C,T,CR,TR,ST,S}}
    terminals :: Vector{T}
end
function ParseForest(chart::ParseChart, terminals, grammar, cyclic)
    if cyclic
        ParseForest(
            vcat(
                [
                    vcat(
                        map(keys(cell.conts)) do category
                            filter(cell.conts[category]) do cont
                                length(cont) == length(terminals) &&
                                    category in startsymbols(grammar)
                            end
                        end...
                    )
                    for cell in chart.cells
                ]...
            )
            ,
            terminals
        )
    else
        ParseForest(
            vcat(
                map(keys(chart.cells[1].conts)) do category
                    filter(chart.cells[1].conts[category]) do cont
                        length(cont) == length(terminals) &&
                            category in startsymbols(grammar)
                    end
                end...
            ),
            terminals
        )
    end
end
iscomplete(forest::ParseForest) = !isempty(forest.heads)
score(forest::ParseForest) = sum(score(h) for h in forest.heads)

probscore = prob ∘ score

function sample_tree(forest::ParseForest)
    @assert iscomplete(forest)
    head = categorical_sample(heads(forest), probscore.(heads(forest)))
    ParseTree(head, sample_tree(head))
end

function sample_conts(edge::Edge)
    trav = categorical_sample(traversals(edge), probscore.(traversals(edge)))
    if hasedge(trav)
        [sample_conts(get(trav.edge)); trav.cont]
    else
        [cont(trav)]
    end
end

function sample_tree{R,C,T,CR,TR,ST,S}(cont::Constituent{R,C,T,CR,TR,ST,S})
    if hasterminal(cont)
        if isempty(completions(cont))
            comp = terminal_completion(cont)
            [(category(cont), rule(comp))]
        else
            comp = categorical_sample(
                [terminal_completion(cont); completions(cont)],
                [probscore(terminal_completion(cont)); probscore.(completions(cont))]
            )
            if comp isa TerminalCompletion
                [(category(cont), rule(comp))]
            else
                conts = sample_conts(edge(comp))
                [(category(cont), rule(comp)); vcat([sample_tree(cont) for cont in conts]...)]
            end
        end
    else
        comp = categorical_sample(completions(cont), probscore.(completions(cont)))
        conts = sample_conts(edge(comp))
        [(category(cont), rule(comp)); vcat([sample_tree(cont) for cont in conts]...)]
    end
end

best_choice(tokens, weights) = tokens[findmax(weights)[2]]

function best_tree(forest::ParseForest)
    @assert iscomplete(forest)
    head = best_choice(heads(forest), probscore.(heads(forest)))
    ParseTree(head, best_tree(head))
end

function best_conts(edge::Edge)
    trav = best_choice(traversals(edge), probscore.(traversals(edge)))
    if hasedge(trav)
        [best_conts(get(trav.edge)); trav.cont]
    else
        [cont(trav)]
    end
end

function best_tree{R,C,T,CR,TR,ST,S}(cont::Constituent{R,C,T,CR,TR,ST,S})
    if hasterminal(cont)
        if isempty(completions(cont))
            comp = terminal_completion(cont)
            [(category(cont), rule(comp))]
        else
            comp = best_choice(
                [terminal_completion(cont); completions(cont)],
                [probscore(terminal_completion(cont)); probscore.(completions(cont))]
            )
            if comp isa TerminalCompletion
                [(category(cont), rule(comp))]
            else
                conts = best_conts(edge(comp))
                [(category(cont), rule(comp)); vcat([best_tree(cont) for cont in conts]...)]
            end
        end
    else
        comp = best_choice(completions(cont), probscore.(completions(cont)))
        conts = best_conts(edge(comp))
        [(category(cont), rule(comp)); vcat([best_tree(cont) for cont in conts]...)]
    end
end

#################
### ParseTree ###
#################

struct ParseTree{C,T,CR,TR,ST,S,R}
    head  :: Constituent{C,T,CR,TR,ST,S}
    rules :: Vector{R}
end

# function add_obs!(g::CFGrammar, t::ParseTree)
#     for (c, r) in t.rules
#         add_obs!(g.cond, r, dependent_components(g, c))
#     end
# end
#
# function rm_obs!(g::CFGrammar, t::ParseTree)
#     for (c, r) in t.rules
#         rm_obs!(g.cond, r, dependent_components(g, c))
#     end
# end

function show(io::IO, tree::ParseTree)
    print(io, map(first, convert(Tree, tree), uniform_type=false))
end

function convert{R,C,T,CR,TR,ST,S}(::Type{Tree}, tree::ParseTree{R,C,T,CR,TR,ST,S})
    function foo!(nodes, rules)
        if isempty(rules)
            nothing
        else
            c, rule = rules[1]
            node = nodes[1]
            category = node.data[1]
            if isapplicable(rule, category)
                for c in rule(category)
                    add_child!(node, (c, Nullable{typejoin(CR,TR)}()))
                end
                node.data = (node.data[1], Nullable(rule))
                foo!([children(node); nodes[2:end]], rules[2:end])
            else
                foo!(nodes[2:end], rules)
            end
        end
    end
    root = Tree(
        (category(tree.head), Nullable{typejoin(CR,TR)}()),
        Tuple{typejoin(C,T), Nullable{typejoin(CR,TR)}}
    )
    foo!([root], tree.rules)
    root
end

latex_replacements = Dict(
    "^" => "^\\triangle",
    "#" => "\#"
)

function latex_replace(str)
    s = str
    for (k, v) in latex_replacements
        s = replace(s, k, v)
    end
    s
end

function tree_to_graph_and_labels(tree)
    graph = Graph(1)
    labels = [string('$', latex_replace(string(tree.data)), '$')]
    for (i, c) in enumerate(children(tree))
        add_vertex!(graph)
        add_edge!(graph, 1, nv(graph))
        tree_to_graph_and_labels!(c, graph, labels)
    end
    graph, labels
end

function tree_to_graph_and_labels!(tree, graph, labels)
    n = nv(graph)
    push!(labels, string('$', latex_replace(string(tree.data)), '$'))
    for (i, c) in enumerate(children(tree))
        add_vertex!(graph)
        add_edge!(graph, n, nv(graph))
        tree_to_graph_and_labels!(c, graph, labels)
    end
    graph, labels
end

plot(tree::Tree) = plot(tree_to_graph_and_labels(tree)...)
plot(tree::ParseTree) = plot(map(first, convert(Tree, tree), uniform_type=false))

######################
### Parser Methods ###
######################

function create_or_update!(key, trav_or_comp, agenda, logbook)
    if isdiscovered(logbook, key)
        item = getitem(logbook, key)
        add!(item, trav_or_comp)
    else
        item = Item(key, trav_or_comp)
        discover!(logbook, item)
    end
    enqueue!(agenda, item, false)
    nothing
end

@noinline function initialize(terminals, grammar, epsilon, cyclic)
    n       = length(terminals)
    chart   = ParseChart([ChartCell(grammar, n, cyclic) for i in 0:(cyclic ? n-1 : n)])
    agenda  = InsideAgenda(grammar, n, cyclic)
    logbook = ParserLogbook(grammar, n, cyclic)

    for (i, terminal) in enumerate(terminals)
        for (category, rule, score) in completions(grammar, terminal)
            cont = Constituent(
                ConstituentKey(ItemRange(i-1, i, n, cyclic), category),
                TerminalCompletion(terminal, rule, score),
                grammar
            )
            discover!(logbook, cont)
            enqueue!(agenda, cont, false)
        end
        if !ismissing(epsilon)
            for (category, rule, score) in completions(grammar, epsilon)
                cont = Constituent(
                    ConstituentKey(ItemRange(i-1, i-1, n, cyclic), category),
                    TerminalCompletion(epsilon, rule, score),
                    grammar
                )
                discover!(logbook, cont)
                enqueue!(agenda, cont, false)
            end
        end
    end
    if !ismissing(epsilon) && !cyclic
        for (category, rule, score) in completions(grammar, epsilon)
            cont = Constituent(
                ConstituentKey(ItemRange(n, n, n, cyclic), category),
                TerminalCompletion(epsilon, rule, score),
                grammar
            )
            discover!(logbook, cont)
            enqueue!(agenda, cont, false)
        end
    end
    chart, agenda, logbook
end

@inline function do_fundamental_rule!(
        edge::Edge, chart, agenda, logbook, grammar, cyclic
    )
    for category in keys(conts(chart, edge))
        if is_possible_transition(grammar, state(edge), category)
            for cont in conts(chart, edge)[category]
                if !cyclic || concatenable(range(edge), range(cont))
                    trav      = Traversal(edge, cont)
                    new_state = transition(grammar, state(edge), category)
                    key       = EdgeKey(range(edge) * range(cont), new_state)
                    create_or_update!(key, trav, agenda, logbook)
                end
            end
        end
    end
    nothing
end

@inline function do_fundamental_rule!(
        cont::Constituent, chart, agenda, logbook, grammar, cyclic
    )
    for state in keys(edges(chart, cont))
        if is_possible_transition(grammar, state, category(cont))
            for edge in edges(chart, cont)[state]
                if !cyclic || concatenable(range(edge), range(cont))
                    trav      = Traversal(edge, cont)
                    new_state = transition(grammar, state, category(cont))
                    key       = EdgeKey(range(edge) * range(cont), new_state)
                    create_or_update!(key, trav, agenda, logbook)
                end
            end
        end
    end
    nothing
end

@inline function introduce_edge!(cont, agenda, logbook, grammar)
    if is_possible_transition(grammar, startstate(grammar), category(cont))
        state = transition(grammar, startstate(grammar), category(cont))
        key   = EdgeKey(range(cont), state)
        create_or_update!(key, Traversal(cont), agenda, logbook)
    end
    nothing
end

@noinline function complete_edge!{R,C,T,CR,TR,ST,S}(
        edge, agenda, logbook::ParserLogbook{R,C,T,CR,TR,ST,S}, grammar
    )
    for (category::C, rule::CR, s::S) in completions(grammar, state(edge))
        key  = ConstituentKey(range(edge), category)
        comp = EdgeCompletion(edge, rule, score(edge) * s)
        create_or_update!(key, comp, agenda, logbook)
    end
    nothing
end

@noinline function process_edge!(
        edge, chart, agenda, logbook, grammar, max_pop_num, cyclic
    )
    s = score(edge)
    edge.insidepopnumber += 1
    if s ≈ lastpopscore(edge) || insidepopnumber(edge) == max_pop_num
        if !isfinal(grammar, state(edge))
            insert!(chart, edge)
        end
        edge.score = Nullable(s) # finish the edge
        do_fundamental_rule!(edge, chart, agenda, logbook, grammar, cyclic)
    else
        complete_edge!(edge, agenda, logbook, grammar)
        edge.lastpopscore = s
        enqueue!(agenda, edge, true)
    end
    nothing
end

@noinline function process_cont!(
        cont, chart, agenda, logbook, grammar, max_pop_num, cyclic
    )
    s = score(cont)
    cont.insidepopnumber += 1
    if s ≈ lastpopscore(cont) || insidepopnumber(cont) == max_pop_num
        insert!(chart, cont)
        cont.score = Nullable(s) # finish the constituent
        do_fundamental_rule!(cont, chart, agenda, logbook, grammar, cyclic)
    else
        introduce_edge!(cont, agenda, logbook, grammar)
        cont.lastpopscore = s
        enqueue!(agenda, cont, true)
    end
    nothing
end

@noinline function loop!(chart, agenda, args...)
    while !isempty(agenda)
        if next_is_edge(agenda)
            process_edge!(dequeue_edge!(agenda), chart, agenda, args...)
        else
            process_cont!(dequeue_cont!(agenda), chart, agenda, args...)
        end
    end
end

@noinline function run_chartparser(
        terminals, grammar; epsilon=missing, max_pop_num=4, cyclic=false
    )
    C, T, CR, TR, ST, S = types(grammar)
    chart, agenda, logbook = initialize(
        T.(terminals), grammar, epsilon, cyclic)
    loop!(chart, agenda, logbook, grammar, max_pop_num, cyclic)
    ParseForest(chart, T.(terminals), grammar, cyclic)
end

############
### Test ###
############

# ascend = CFRule(1:9) do i
#     [i, i+1]
# end
# double = CFRule(1:10) do i
#     [i, i]
# end
# terminate = CFRule(1:10) do i
#     [string(i)]
# end
# grammar = CFGrammar([ascend, double], [terminate], [1])
# exp(score(grammar, 9, terminate))
#
# using BenchmarkTools
# @btime score(run_chartparser(["1" for i in 1:10], grammar))
# @btime score(run_chartparser(["1" for i in 1:60], grammar))
# @btime score(run_chartparser(["1" for i in 1:30], grammar))

# @time forest = run_chartparser(["1" for i in 1:3], grammar);
# t = sample_tree(forest)
#
# using TikzPictures
# save(PDF("test"), TikzGraphs.plot(t))

# chart, agenda, logbook = initialize(["1", "1", "2"], grammar, missing)
# next_is_edge(agenda)
# c = process_cont!(dequeue_cont!(agenda), chart, agenda, logbook, grammar, 4)
# e = dequeue_edge!(agenda)
# t = e.traversals[1]

# @time score(run_chartparser(["1" for i in 1:60], grammar, cyclic=false))
# forest = run_chartparser(["1" for i in 1:60], grammar, cyclic=false);
# sample_tree(forest)

ext: jl


text:
function reduce_points(::Type{AklToussaintHeuristic}, arg0::Collection)
    return jcall(AklToussaintHeuristic, "reducePoints", Collection, (Collection,), arg0)
end


text:
# Groups
#------------------------------------------------------------------------------#
abstract type Group end

abstract type AbelianGroup <: Group end
abstract type ℤ{N} <: AbelianGroup end
abstract type U₁ <: AbelianGroup end

abstract type SU{N} <: Group end
abstract type CU₁ <: Group end

const ℤ₂ = ℤ{2}
const ℤ₃ = ℤ{3}
const ℤ₄ = ℤ{4}
const SU₂ = SU{2}

type_repr(::Type{ℤ₂}) = "ℤ₂"
type_repr(::Type{ℤ₃}) = "ℤ₃"
type_repr(::Type{ℤ₄}) = "ℤ₄"
type_repr(::Type{SU₂}) = "SU₂"

const GroupTuple = Tuple{Vararg{Group}}

abstract type ProductGroup{T<:GroupTuple} <: Group end

×(a::Type{<:Group}, b::Type{<:Group}, c::Type{<:Group}...) = ×(×(a, b), c...)

×(G::Type{<:Group}) = ProductGroup{Tuple{G}}
×(G1::Type{ProductGroup{Tuple{}}}, G2::Type{<:Group}) = ProductGroup{Tuple{G2}}
×(G1::Type{<:Group}, G2::Type{<:Group}) = ProductGroup{Tuple{G1, G2}}
×(G1::Type{ProductGroup{T}}, G2::Type{<:Group}) where {T<:GroupTuple} =
    tuple_type_head(T) × (ProductGroup{tuple_type_tail(T)} × G2)

×(G1::Type{ProductGroup{Tuple{}}}, G2::Type{ProductGroup{T}}) where {T<:GroupTuple} = G2
×(G1::Type{<:Group}, G2::Type{ProductGroup{T}}) where {T<:GroupTuple} =
    ProductGroup{Base.tuple_type_cons(G1, T)}
×(G1::Type{ProductGroup{T1}},
    G2::Type{ProductGroup{T2}}) where {T1<:GroupTuple, T2<:GroupTuple} =
    tuple_type_head(T1) × (ProductGroup{tuple_type_tail(T1)} × G2)

function type_repr(G::Type{<:ProductGroup})
    T = G.parameters[1]
    groups = T.parameters
    if length(groups) == 1
        s = "ProductGroup{Tuple{" * type_repr(groups[1]) * "}}"
    else
        s = "("
        for i = 1:length(groups)
            if i != 1
                s *= " × "
            end
            s *= type_repr(groups[i])
        end
        s *= ")"
    end
    return s
end


text:
#gnum-addition.jl
#addition algorithms between unums, ubounds and gnums.

#general exact addition algorithm.
@generated function __exact_arithmetic_addition!{ESS,FSS,side}(a::Unum{ESS,FSS}, b::Gnum{ESS,FSS}, ::Type{Val{side}})
  mesize::UInt16 = max_esize(ESS)
  mfsize::UInt16 = max_fsize(FSS)
  (FSS < 7) && (mfrac::UInt64 = mask_top(FSS))
  mexp::UInt64 = max_exponent(ESS)

  quote
    a_exp::Int64 = decode_exp(a)
    b_exp::Int64 = decode_exp(b.$side)

    a_dev::UInt64 = is_exp_zero(a) * o64
    b_dev::UInt64 = is_exp_zero(b.$side) * o64

    #derive the "contexts" for each, which is a combination of the exponent and
    #deviation.
    a_ctx::Int64 = a_exp + a_dev
    b_ctx::Int64 = b_exp + b_dev

    #set up a placeholder for the addend.
    addend::Unum{ESS,FSS}
    shift::Int64
    carry::UInt64
    scratchpad_exp::Int64
    scratchpad_dev::UInt64
    @init_sflags()
    #check to see which context is bigger.
    if (a_ctx > b_ctx) || ((a_ctx == b_ctx) && (b_dev != z64))
      #set the placeholder to the value a.
      addend = a
      @preserve_sflags b copy_unum!(b.$side, b.scratchpad)
      #calculate shift as the difference between a and b
      shift = a_ctx - b_ctx
      #set up the carry bit.
      carry = (o64 - a_dev) + ((shift == z64) * (o64 - b_dev))
      scratchpad_exp = a_exp
      scratchpad_dev = a_dev
    else
      #set the placeholder to the value b.
      addend = b.$side
      #move the unum value to the scratchpad.
      @preserve_sflags b put_unum!(a, b, SCRATCHPAD)
      #calculate the shift as the difference between a and b.
      shift = b_ctx - a_ctx
      #set up the carry bit.
      carry = (o64 - b_dev) + ((shift == z64) * (o64 - a_dev))
      scratchpad_exp = b_exp
      scratchpad_dev = b_dev
    end

    #rightshift the scratchpad, then set the invisible bit that may have moved.
    __rightshift_frac_with_underflow_check!(b.scratchpad, shift)
    (shift != 0) && (b_dev == 0) && (set_frac_bit!(b.scratchpad, shift))

    #perform the carried add.
    carry = __carried_add_frac!(carry, addend, b.scratchpad)

    #set esize and exponent parts.
    b.scratchpad.esize = addend.esize
    b.scratchpad.exponent = addend.exponent

    if (scratchpad_dev == z64)
      #for non-subnormal things do the following:
      if (carry > 1)
        scratchpad_exp += 1
        if scratchpad_exp > $mexp
          @preserve_sflags b mmr!(b, b.scratchpad.flags & UNUM_SIGN_MASK, SCRATCHPAD)
        else
          #shift things over by one since we went up in size.
          __rightshift_frac_with_underflow_check!(b.scratchpad, 1)
          #carry from the carry over into the fraction.
          (carry == 3) && set_frac_top!(b.scratchpad)
          #re-encode the exponent.
          (b.scratchpad.esize, b.scratchpad.exponent) = encode_exp(scratchpad_exp)
        end
      end
    else
      #for subnormal values, we have to augment the exponent slightly differently.
      if (carry > 0)
        b.scratchpad.exponent = o64
      end
    end

    #set the fsize.
    b.scratchpad.fsize = $mfsize - min(((b.scratchpad.fsize & UNUM_UBIT_MASK != 0) ? 0 : ctz(b.scratchpad.fraction)), $mfsize)

    #another way to get overflow is: by adding just enough bits to exactly
    #make the binary value for inf or nan.  This should, instead, yield mmr.
    #nb:  the is_inf call here is the UNUM is_inf, which checks across all the
    #bits, not the gnum is_inf, which only looks at the flag in the flags holder.
    __is_nan_or_inf(b.scratchpad) && @preserve_sflags b mmr!(b, b.scratchpad.flags & UNUM_SIGN_MASK, SCRATCHPAD)
    is_mmr(b.scratchpad) && @preserve_sflags b mmr!(b, b.scratchpad.flags & UNUM_SIGN_MASK, SCRATCHPAD)

    copy_unum_with_gflags!(b.scratchpad, b.$side)
  end
end

max_stars_repo_name: REX-Computing/unumjl

max_issues_repo_name: REX-Computing/unumjl

max_forks_repo_name: REX-Computing/unumjl


text:
macro count(source, f)
    q = Expr(:quote, f)
    :(QueryOperators.count(QueryOperators.query($(esc(source))), $(esc(f)), $(esc(q))))
end

macro count(source)
    :(QueryOperators.count(QueryOperators.query($(esc(source)))))
end

macro count()
    :( i -> QueryOperators.count(QueryOperators.query(i)))
end

macro groupby(source, elementSelector, resultSelector)
    elementSelector_as_anonym_func = helper_replace_anon_func_syntax(elementSelector)
    resultSelector_as_anonym_func = helper_replace_anon_func_syntax(resultSelector)

 	q_elementSelector = Expr(:quote, elementSelector_as_anonym_func)
	q_resultSelector = Expr(:quote, resultSelector_as_anonym_func)

    return :(QueryOperators.groupby(QueryOperators.query($(esc(source))), $(esc(elementSelector_as_anonym_func)), $(esc(q_elementSelector)), $(esc(resultSelector_as_anonym_func)), $(esc(q_resultSelector)))) |>
        helper_namedtuples_replacement
end

macro groupby(elementSelector, resultSelector)
    elementSelector_as_anonym_func = helper_replace_anon_func_syntax(elementSelector)
    resultSelector_as_anonym_func = helper_replace_anon_func_syntax(resultSelector)

 	q_elementSelector = Expr(:quote, elementSelector_as_anonym_func)
	q_resultSelector = Expr(:quote, resultSelector_as_anonym_func)

    return :( i -> QueryOperators.groupby(QueryOperators.query(i), $(esc(elementSelector_as_anonym_func)), $(esc(q_elementSelector)), $(esc(resultSelector_as_anonym_func)), $(esc(q_resultSelector)))) |>
        helper_namedtuples_replacement
end

macro groupby(elementSelector)
    elementSelector_as_anonym_func = helper_replace_anon_func_syntax(elementSelector)
    resultSelector_as_anonym_func = :(i->i)

 	q_elementSelector = Expr(:quote, elementSelector_as_anonym_func)
	q_resultSelector = Expr(:quote, resultSelector_as_anonym_func)

    return :( i -> QueryOperators.groupby(QueryOperators.query(i), $(esc(elementSelector_as_anonym_func)), $(esc(q_elementSelector)), $(esc(resultSelector_as_anonym_func)), $(esc(q_resultSelector)))) |>
        helper_namedtuples_replacement
end

macro groupjoin(outer, inner, outerKeySelector, innerKeySelector, resultSelector)
    outerKeySelector_as_anonym_func = helper_replace_anon_func_syntax(outerKeySelector)
    innerKeySelector_as_anonym_func = helper_replace_anon_func_syntax(innerKeySelector)
    resultSelector_as_anonym_func = helper_replace_anon_func_syntax(resultSelector)

    q_outerKeySelector = Expr(:quote, outerKeySelector_as_anonym_func)
    q_innerKeySelector = Expr(:quote, innerKeySelector_as_anonym_func)
    q_resultSelector = Expr(:quote, resultSelector_as_anonym_func)

    return :(QueryOperators.groupjoin(QueryOperators.query($(esc(outer))),
            QueryOperators.query($(esc(inner))),
            $(esc(outerKeySelector_as_anonym_func)), $(esc(q_outerKeySelector)),
            $(esc(innerKeySelector_as_anonym_func)), $(esc(q_innerKeySelector)),
            $(esc(resultSelector_as_anonym_func)), $(esc(q_resultSelector)),)) |>
        helper_namedtuples_replacement
end

macro groupjoin(inner, outerKeySelector, innerKeySelector, resultSelector)
    outerKeySelector_as_anonym_func = helper_replace_anon_func_syntax(outerKeySelector)
    innerKeySelector_as_anonym_func = helper_replace_anon_func_syntax(innerKeySelector)
    resultSelector_as_anonym_func = helper_replace_anon_func_syntax(resultSelector)

    q_outerKeySelector = Expr(:quote, outerKeySelector_as_anonym_func)
    q_innerKeySelector = Expr(:quote, innerKeySelector_as_anonym_func)
    q_resultSelector = Expr(:quote, resultSelector_as_anonym_func)

    return :( outer -> QueryOperators.groupjoin(QueryOperators.query(outer),
            QueryOperators.query($(esc(inner))),
            $(esc(outerKeySelector_as_anonym_func)), $(esc(q_outerKeySelector)),
            $(esc(innerKeySelector_as_anonym_func)), $(esc(q_innerKeySelector)),
            $(esc(resultSelector_as_anonym_func)), $(esc(q_resultSelector)),)) |>
        helper_namedtuples_replacement
end

macro join(outer, inner, outerKeySelector, innerKeySelector, resultSelector)
    outerKeySelector_as_anonym_func = helper_replace_anon_func_syntax(outerKeySelector)
    innerKeySelector_as_anonym_func = helper_replace_anon_func_syntax(innerKeySelector)
    resultSelector_as_anonym_func = helper_replace_anon_func_syntax(resultSelector)

    q_outerKeySelector = Expr(:quote, outerKeySelector_as_anonym_func)
    q_innerKeySelector = Expr(:quote, innerKeySelector_as_anonym_func)
    q_resultSelector = Expr(:quote, resultSelector_as_anonym_func)

    return :(QueryOperators.join(QueryOperators.query($(esc(outer))),
            QueryOperators.query($(esc(inner))),
            $(esc(outerKeySelector_as_anonym_func)), $(esc(q_outerKeySelector)),
            $(esc(innerKeySelector_as_anonym_func)), $(esc(q_innerKeySelector)),
            $(esc(resultSelector_as_anonym_func)), $(esc(q_resultSelector)),)) |>
        helper_namedtuples_replacement
end

macro join(inner, outerKeySelector, innerKeySelector, resultSelector)
    outerKeySelector_as_anonym_func = helper_replace_anon_func_syntax(outerKeySelector)
    innerKeySelector_as_anonym_func = helper_replace_anon_func_syntax(innerKeySelector)
    resultSelector_as_anonym_func = helper_replace_anon_func_syntax(resultSelector)

    q_outerKeySelector = Expr(:quote, outerKeySelector_as_anonym_func)
    q_innerKeySelector = Expr(:quote, innerKeySelector_as_anonym_func)
    q_resultSelector = Expr(:quote, resultSelector_as_anonym_func)

    return :( outer -> QueryOperators.join(QueryOperators.query(outer),
            QueryOperators.query($(esc(inner))),
            $(esc(outerKeySelector_as_anonym_func)), $(esc(q_outerKeySelector)),
            $(esc(innerKeySelector_as_anonym_func)), $(esc(q_innerKeySelector)),
            $(esc(resultSelector_as_anonym_func)), $(esc(q_resultSelector)),)) |>
        helper_namedtuples_replacement
end

macro orderby(source, f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, f_as_anonym_func)
    return :(QueryOperators.orderby(QueryOperators.query($(esc(source))), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro orderby(f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, helper_replace_anon_func_syntax(f_as_anonym_func))
    return :( i -> QueryOperators.orderby(QueryOperators.query(i), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro orderby_descending(source, f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, f_as_anonym_func)
    return :(QueryOperators.orderby_descending(QueryOperators.query($(esc(source))), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro orderby_descending(f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, helper_replace_anon_func_syntax(f_as_anonym_func))
    return :( i -> QueryOperators.orderby_descending(QueryOperators.query(i), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro thenby(source, f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, f_as_anonym_func)
    return :(QueryOperators.thenby($(esc(source)), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro thenby(f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, helper_replace_anon_func_syntax(f_as_anonym_func))
    return :( i -> QueryOperators.thenby(i, $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro thenby_descending(source, f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, f_as_anonym_func)
    return :(QueryOperators.thenby_descending($(esc(source)), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro thenby_descending(f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, helper_replace_anon_func_syntax(f_as_anonym_func))
    return :( i -> QueryOperators.thenby_descending(i, $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro map(source, f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, f_as_anonym_func)
    return :(QueryOperators.map(QueryOperators.query($(esc(source))), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro map(f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, f_as_anonym_func)
    return :( i-> QueryOperators.map(QueryOperators.query(i), $(esc(f_as_anonym_func)), $(esc(q))) ) |>
        helper_namedtuples_replacement
end

macro mapmany(source, collectionSelector,resultSelector)
    collectionSelector_as_anonym_func = helper_replace_anon_func_syntax(collectionSelector)
    resultSelector_as_anonym_func = helper_replace_anon_func_syntax(resultSelector)

    collectionSelector_q = Expr(:quote, collectionSelector_as_anonym_func)
    resultSelector_q = Expr(:quote, resultSelector_as_anonym_func)

    return :(QueryOperators.mapmany(QueryOperators.query($(esc(source))),
            $(esc(collectionSelector_as_anonym_func)), $(esc(collectionSelector_q)),
            $(esc(resultSelector_as_anonym_func)), $(esc(resultSelector_q)))) |>
        helper_namedtuples_replacement
end

macro mapmany(collectionSelector,resultSelector)
    collectionSelector_as_anonym_func = helper_replace_anon_func_syntax(collectionSelector)
    resultSelector_as_anonym_func = helper_replace_anon_func_syntax(resultSelector)

    collectionSelector_q = Expr(:quote, collectionSelector_as_anonym_func)
    resultSelector_q = Expr(:quote, resultSelector_as_anonym_func)

    return :( i-> QueryOperators.mapmany(QueryOperators.query(i),
            $(esc(collectionSelector_as_anonym_func)), $(esc(collectionSelector_q)),
            $(esc(resultSelector_as_anonym_func)), $(esc(resultSelector_q)))) |>
        helper_namedtuples_replacement
end

macro filter(source, f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, f_as_anonym_func)
    return :(QueryOperators.filter(QueryOperators.query($(esc(source))), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro filter(f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, helper_replace_anon_func_syntax(f_as_anonym_func))
    return :( i -> QueryOperators.filter(QueryOperators.query(i), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end

macro take(source, n)
    return :(QueryOperators.take(QueryOperators.query($(esc(source))), $(esc(n))))
end

macro take(n)
    return :( i -> QueryOperators.take(QueryOperators.query(i), $(esc(n))))
end

macro drop(source, n)
    return :(QueryOperators.drop(QueryOperators.query($(esc(source))), $(esc(n))))
end

macro drop(n)
    return :( i -> QueryOperators.drop(QueryOperators.query(i), $(esc(n))))
end

macro unique()
    return :( i -> QueryOperators.unique(QueryOperators.query(i), q->q, :(q->q))) |>
        helper_namedtuples_replacement
end

macro unique(f)
    f_as_anonym_func = helper_replace_anon_func_syntax(f)
    q = Expr(:quote, helper_replace_anon_func_syntax(f_as_anonym_func))
    return :( i -> QueryOperators.unique(QueryOperators.query(i), $(esc(f_as_anonym_func)), $(esc(q)))) |>
        helper_namedtuples_replacement
end