// ==========================================================================
//                 SeqAn - The Library for Sequence Analysis
// ==========================================================================
// Copyright (c) 2006-2026, Knut Reinert, FU Berlin
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above copyright
//       notice, this list of conditions and the following disclaimer in the
//       documentation and/or other materials provided with the distribution.
//     * Neither the name of Knut Reinert or the FU Berlin nor the names of
//       its contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
// DAMAGE.
//
// ==========================================================================
// Author: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de>
// ==========================================================================

// TODO(holtgrew): Switch to Host interface.

#ifndef SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_BASE_H_
#define SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_BASE_H_

namespace seqan2 {

// ============================================================================
// Forwards
// ============================================================================

template <typename TSpec>
struct GapsIterator;

/*!
 * @defgroup GapsSpecTag Gaps Specialization Tags
 * @brief Tags for specializing the Gaps class.
 */

/*!
 * @tag GapsSpecTag#ArrayGaps
 * @headerfile <seqan/align.h>
 * @brief Tag for the Array Gaps specialization.
 *
 * @signature struct ArrayGaps_;
 * @signature typedef Tag<ArrayGaps_> ArrayGaps;
 */

struct ArrayGaps_;
typedef Tag<ArrayGaps_> ArrayGaps;

// ============================================================================
// Tags, Classes, Enums
// ============================================================================

/*!
 * @defgroup GapDirectionTags Gap Direction Tags
 * @brief Tags to select the direction to which side of a view position an operation should be projected.
 */

/*!
 * @tag GapDirectionTags#LeftOfViewPos
 * @headerfile <seqan/align.h>
 * @brief Projects to the left side of the current view position.
 *
 * @signature struct LeftOfViewPos_;
 *            typedef Tag<LeftOfViewPos_> LeftOfViewPos;
 */

struct LeftOfViewPos_;
typedef Tag<LeftOfViewPos_> LeftOfViewPos;

/*!
 * @tag GapDirectionTags#RightOfViewPos
 * @headerfile <seqan/align.h>
 * @brief Projects to the right side of the current view position.
 *
 * @signature struct RightOfViewPos_;
 *            typedef Tag<RightOfViewPos_> RightOfViewPos;
 */

struct RightOfViewPos_;
typedef Tag<RightOfViewPos_> RightOfViewPos;

// ----------------------------------------------------------------------------
// Class Gaps
// ----------------------------------------------------------------------------

/*!
 * @class Gaps
 * @implements ContainerConcept
 * @headerfile <seqan/align.h>
 * @brief Store the gapped version of a sequence.
 *
 * @signature template <typename TSequence, typename TSpec>
 *            class Gaps;
 *
 * @tparam TSequence The type of the underlying sequence.
 * @tparam TSpec     Tag for specialization.
 *
 * Gaps wrap a @link ContainerConcept Sequence @endlink and allows one to (1) insert gaps into the sequence and (2) select
 * an infix of the gapped sequence (clipping).  The gaps are not inserted into the underlying sequence (source) but
 * stored separately.  Using the clipping is optional and meant for selecting parts of the alignment as a part of the
 * result of a local alignment algorithm.
 *
 * <img src="gaps_illustration.png" title="Illustration of Gaps object and positions with clipping." />
 *
 * In the figure above, the source sequence has seven characters, the gapped sequence has four gaps and thus consists
 * of eleven characters.  The gapped sequence is clipped to start at position 0 in the gapped sequence and to end at
 * position 8 in the gapped sequence (the positions given as half-open intervals <tt>[begin, end)</tt>).
 *
 * The figure shows the three coordinate systems that are used with Gaps objects.  The source position is the position
 * in the underlying sequence.  The unclipped view position is the position in the gapped sequence without gaps.  The
 * view position is the position in the gapped sequence but including the clipping: All (clipped) view positions have
 * the clipping begin position subtracted from them.
 *
 * @section Examples
 *
 * The following example shows the construction of the gaps object from the image above together with some calls to
 * <tt>toViewPosition</tt> and <tt>toSourcePosition</tt>.
 *
 * @include demos/dox/align/gaps_example.cpp
 *
 * The output is as follows:
 *
 * @include demos/dox/align/gaps_example.cpp.stdout
 */

template <typename TSequence, typename TSpec = ArrayGaps>
class Gaps;

template <typename TSequence, typename TSpec>
SEQAN_CONCEPT_IMPL((Gaps<TSequence, TSpec>), (AlignedSequenceConcept));

template <typename TSequence, typename TSpec>
SEQAN_CONCEPT_IMPL((Gaps<TSequence, TSpec> const), (AlignedSequenceConcept));

// ============================================================================
// Metafunctions
// ============================================================================

// ----------------------------------------------------------------------------
// Metafunction Value
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec>
struct Value<Gaps<TSequence, TSpec> >
{
    typedef typename Value<TSequence>::Type           TAlphabet;
    typedef typename GappedValueType<TAlphabet>::Type Type;
};

template <typename TSequence, typename TSpec>
struct Value<Gaps<TSequence, TSpec> const> : Value<Gaps<TSequence, TSpec> >
{};

// ----------------------------------------------------------------------------
// Metafunction Iterator
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec, typename TIteratorSpec>
struct Iterator<Gaps<TSequence, TSpec>, TIteratorSpec>
{
    typedef Iter<Gaps<TSequence, TSpec>, GapsIterator<TSpec> > Type;
};

template <typename TSequence, typename TSpec, typename TIteratorSpec>
struct Iterator<Gaps<TSequence, TSpec> const, TIteratorSpec>
{
    typedef Iter<Gaps<TSequence, TSpec> const, GapsIterator<TSpec> > Type;
};

// ----------------------------------------------------------------------------
// Metafunction GetValue
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec>
struct GetValue<Gaps<TSequence, TSpec> > : Value<Gaps<TSequence, TSpec> >
{};

template <typename TSequence, typename TSpec>
struct GetValue<Gaps<TSequence, TSpec> const> : GetValue<Gaps<TSequence, TSpec> >
{};

// ----------------------------------------------------------------------------
// Metafunction Position
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec>
struct Position<Gaps<TSequence, TSpec> >
{
    typedef typename Position<TSequence>::Type TSeqPos_;
    typedef typename MakeSigned<TSeqPos_>::Type Type;
};

template <typename TSequence, typename TSpec>
struct Position<Gaps<TSequence, TSpec> const> : Position<Gaps<TSequence, TSpec> >
{};

// ----------------------------------------------------------------------------
// Metafunction Reference
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec>
struct Reference<Gaps<TSequence, TSpec> >
{
    typedef typename Iterator<Gaps<TSequence, TSpec>, Standard>::Type TIterator_;
    typedef Proxy<IteratorProxy<TIterator_> > Type;
};

template <typename TSequence, typename TSpec>
struct Reference<Gaps<TSequence, TSpec> const>
{
    typedef typename Iterator<Gaps<TSequence, TSpec> const, Standard>::Type TIterator_;
    typedef Proxy<IteratorProxy<TIterator_> > Type;
};

// ----------------------------------------------------------------------------
// Metafunction Size
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec>
struct Size<Gaps<TSequence, TSpec> >
{
    typedef typename Size<TSequence>::Type Type;
};

template <typename TSequence, typename TSpec>
struct Size<Gaps<TSequence, TSpec> const> : Size<Gaps<TSequence, TSpec> >
{};

// ----------------------------------------------------------------------------
// Metafunction Source
// ----------------------------------------------------------------------------

// TODO(holtgrew): Switch to Hosted Type interface

template <typename TSequence, typename TSpec>
struct Source<Gaps<TSequence, TSpec> >
{
    typedef TSequence Type;
};

template <typename TSequence, typename TSpec>
struct Source<Gaps<TSequence, TSpec> const> : Source<Gaps<TSequence, TSpec> >
{};

// TODO(holtgrew): Also prefix/suffix/infix? Should work!

// ----------------------------------------------------------------------------
// Metafunction IsSequence
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec>
struct IsSequence<Gaps<TSequence, TSpec> >
{
    typedef True Type;
    static const bool VALUE = true;
};

template <typename TSequence, typename TSpec>
struct IsSequence<Gaps<TSequence, TSpec> const> : IsSequence<Gaps<TSequence, TSpec> >
{};


// ============================================================================
// Functions
// ============================================================================

// ----------------------------------------------------------------------------
// Function value()
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec,
          typename TPosition>
inline typename Reference<Gaps<TSequence, TSpec> >::Type
value(Gaps<TSequence, TSpec> & gaps,
      TPosition const clippedViewPos)
{
    return typename Reference<Gaps<TSequence, TSpec> >::Type(begin(gaps, Standard()) + clippedViewPos);
}

template <typename TSequence, typename TSpec,
          typename TPosition>
inline typename Reference<Gaps<TSequence, TSpec> const>::Type
value(Gaps<TSequence, TSpec> const & gaps,
      TPosition const clippedViewPos)
{
    return typename Reference<Gaps<TSequence, TSpec> const>::Type(begin(gaps, Standard()) + clippedViewPos);
}

// ----------------------------------------------------------------------------
// Function iter()
// ----------------------------------------------------------------------------

// From ContainerConcept, only overwriting documentation here.

/*!
 * @fn Gaps#iter
 * @brief Return an iterator to a specific position in the current clipping.
 *
 * @signature TIterator iter(gaps, viewPos[, tag]);
 *
 * @param[in] gaps    The Gaps object to get an iterator into.
 * @param[in] viewPos View position to get an iterator to (Metafunction: @link ContainerConcept#Position @endlink).
 * @param[in] tag     An optional tag for selecting the iterator type.
 *
 * @return TIterator The resulting iterator.  The type is <tt>Iterator<TGaps, TTag>::Type</tt> where <tt>TTag</tt> is
 *                   the type of <tt>tag</tt>.
 */

// TODO(holtgrew): Adding links to implemented sequence. This should be cleaned up once we have better documentation with concepts.
// ----------------------------------------------------------------------------
// Function setSource()
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// Function createSource()
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// Function clearClipping()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#clearClipping
 * @brief Clear clipping from Gaps objects.
 *
 * @signature void clearClipping(gaps);
 *
 * @param[in,out] gaps Object to clear clipping from.
 */

// ----------------------------------------------------------------------------
// Function clearGaps()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#clearGaps
 * @brief Clear gaps from Gaps objects.
 *
 * @signature void clearGaps(gaps);
 *
 * @param[in,out] gaps Object to clear gaps from.
 */

// ----------------------------------------------------------------------------
// Function length()
// ----------------------------------------------------------------------------

// From ContainerConcept, only overwriting documentation here.

/*!
 * @fn Gaps#length
 * @brief Return number of gap and characters between the beginning and the end of the clipping.
 *
 * @signature TSize length(gaps);
 *
 * @param[in] gaps The @link Gaps @endlink object to query for its length.
 *
 * @return TSize The number of gaps and characters between the beginning and the end of the clipping (Metafunction:
 *               @link ContainerConcept#Size @endlink).
 */

// ----------------------------------------------------------------------------
// Function unclippedLength()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#unclippedLength
 * @brief Return length of the gapped sequence without clipping.
 *
 * @signature TSize unclippedLength(gaps);
 *
 * @param[in] gaps The Gaps object to query.
 *
 * @return TSize The result (Metafunction: @link ContainerConcept#Size @endlink).
 */

// ----------------------------------------------------------------------------
// Function toViewPosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#toViewPosition
 * @brief Conversion from source (without gaps or clipping) to view position (including gaps and clipping).
 *
 * @signature TPos toViewPosition(gaps, sourcePos);
 *
 * @param[in] gaps      The gaps object to use for translation.
 * @param[in] sourcePos The source position (in the underlying sequence) to translate.
 *
 * @return TPos The resulting position in the view (Metafunction: @link ContainerConcept#Position @endlink).
 */

// ----------------------------------------------------------------------------
// Function toSourcePosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#toSourcePosition
 * @brief Conversion from view position (including gaps and clipping) to source (without gaps or clipping).
 *
 * @signature TPos toSourcePosition(gaps, viewPos);
 *
 * @param[in] gaps      The gaps object to use for translation.
 * @param[in] sourcePos The view position (including gaps and clipping) to translate.
 *
 * @return TPos The resulting position in the underlying sequence (Metafunction: @link ContainerConcept#Position
 *              @endlink).
 */

template <typename TSequence, typename TSpec, typename TPosition>
inline typename Position<TSequence>::Type
toSourcePosition(Gaps<TSequence, TSpec> const & gaps, TPosition const clippedViewPos)
{
    return toSourcePosition(gaps, clippedViewPos, RightOfViewPos());
}

// ----------------------------------------------------------------------------
// Function isGap()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#isGap
 * @brief Query positions in a Gaps object for being a gap.
 *
 * @signature bool isGap(gaps, viewPos);
 *
 * @param[in] gaps    The Gaps object to query.
 * @param[in] viewPos The view position (including clipping and gaps).
 *
 * @return bool The query result.
 */

template <typename TSequence, typename TSpec, typename TPos>
bool isGap(Gaps<TSequence, TSpec> const & gaps, TPos clippedViewPos)
{
    return isGap(iter(gaps, clippedViewPos, Standard()));
}

// ----------------------------------------------------------------------------
// Function isCharacter()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#isCharacer
 * @brief Query positions in a Gaps object for being a character.
 *
 * @signature bool isCharacter(gaps, viewPos);
 *
 * @param[in] gaps    The Gaps object to query.
 * @param[in] viewPos The view position (including clipping and gaps).
 *
 * @return bool The query result.
 */

template <typename TSequence, typename TSpec, typename TPos>
bool isCharacter(Gaps<TSequence, TSpec> const & gaps, TPos clippedViewPos)
{
    return isCharacter(iter(gaps, clippedViewPos, Standard()));
}

// ----------------------------------------------------------------------------
// Function insertGaps()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#insertGaps
 * @brief Insert gap characters.
 *
 * @signature void insertGaps(gaps, viewPos, count);
 *
 * @param[in,out] gaps    The Gaps object to insert gaps into.
 * @param[in]     viewPos The view position (including clipping and gaps) to insert gaps at.
 * @param[in]     count   The number of gaps to insert.
 */

// ----------------------------------------------------------------------------
// Function insertGap()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#insertGap
 * @brief Insert one gap character.
 *
 * @signature void insertGap(gaps, viewPos);
 *
 * @param[in,out] gaps    The Gaps object to insert gap into.
 * @param[in]     viewPos The view position (including clipping and gaps) to insert the gap at.
 */

// Forward to removeGaps() which has to be implemented in each subclass.

template <typename TSequence, typename TSpec, typename TPosition>
inline void
insertGap(Gaps<TSequence, TSpec> & gaps, TPosition clippedViewPos)
{
    insertGaps(gaps, clippedViewPos, 1u);
}

// ----------------------------------------------------------------------------
// Function removeGaps()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#removeGaps
 * @brief Remove gaps from a Gaps object.
 *
 * @signature TSize removeGaps(gaps, viewPos, count);
 *
 * @param[in,out] gaps    The gaps object to remove gap characters from.
 * @param[in]     viewPos The view positions to remove gap characters from.
 * @param[in]     count   The number of gap characters to remove.
 *
 * @return TSize The number of gap characters removed (Metafunction: @link ContainerConcept#Size @endlink).
 */

// ----------------------------------------------------------------------------
// Function removeGap()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#removeGap
 * @brief Remove one gap from a Gaps object.
 *
 * @signature TSize removeGap(gaps, viewPos);
 *
 * @param[in,out] gaps    The gaps object to remove one gap character from.
 * @param[in]     viewPos The view positions to remove one gap character from.
 *
 * @return TSize The number of gap characters removed (Metafunction: @link ContainerConcept#Size @endlink).
 */

// Forward to removeGaps() which has to be implemented in each subclass.

template <typename TSequence, typename TSpec, typename TPosition>
inline typename Size<Gaps<TSequence, TSpec> >::Type
removeGap(Gaps<TSequence, TSpec> & gaps, TPosition clippedViewPos)
{
    return removeGaps(gaps, clippedViewPos, 1u);
}

// ----------------------------------------------------------------------------
// Function countGaps()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#countGaps
 * @brief The number of gaps following a position.
 *
 * @signature TSize countGaps(gaps, viewPos[, dir]);
 *
 * @param[in] gaps    The Gaps object to query.
 * @param[in] viewPos View position (including clipping and gaps) to query at.
 * @param[in] dir     A tag to specify the counting direction. One of @link GapDirectionTags @endlink.
 *                    Defaults to @link GapDirectionTags#RightOfViewPos @endlink.
 *
 * @return TSize The number of gap characters at <tt>viewPos</tt>  (Metafunction: @link ContainerConcept#Size
 *               @endlink).
 *
 * If the the direction tag is @link GapDirectionTags#RightOfViewPos @endlink the current view position will be
 * included in the count, and excluded when @link GapDirectionTags#LeftOfViewPos @endlink is selected.
 */

template <typename TSequence, typename TSpec,
          typename TPos,
          typename TDirSpec>
typename Size<Gaps<TSequence, TSpec> >::Type
countGaps(Gaps<TSequence, TSpec> const & gaps, TPos const clippedViewPos, TDirSpec const & /*tag*/)
{
    return countGaps(iter(gaps, clippedViewPos, Standard()), TDirSpec());
}

template <typename TSequence, typename TSpec, typename TPos>
typename Size<Gaps<TSequence, TSpec> >::Type
countGaps(Gaps<TSequence, TSpec> const & gaps, TPos const clippedViewPos)
{
    return countGaps(gaps, clippedViewPos, RightOfViewPos());
}

// ----------------------------------------------------------------------------
// Function countLeadingGaps()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#countLeadingGaps
 * @brief The number of leading gaps.
 *
 * @signature TSize countLeadingGaps(gaps);
 *
 * @param[in] gaps    The Gaps object to query.
 *
 * @return TSize The number of leading gap characters  (Metafunction: @link ContainerConcept#Size @endlink).
 */

template <typename TGaps>
inline typename Size<TGaps>::Type
countLeadingGaps(TGaps const & gaps)
{
    return toViewPosition(gaps, 0);
}

// ----------------------------------------------------------------------------
// Function countTrailingGaps()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#countTrailingGaps
 * @brief The number of trailing gaps.
 *
 * @signature TSize countTrailingGaps(gaps);
 *
 * @param[in] gaps    The Gaps object to query.
 *
 * @return TSize The number of trailing gap characters  (Metafunction: @link ContainerConcept#Size @endlink).
 */

template <typename TGaps>
inline typename Size<TGaps>::Type
countTrailingGaps(TGaps const & gaps)
{
    return length(gaps) - toViewPosition(gaps, length(source(gaps)) - 1) - 1;
}

// ----------------------------------------------------------------------------
// Function countGapOpens()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#countGapOpens
 * @brief The number of gap openings.
 *
 * @signature TSize countGapOpens(gaps);
 *
 * @param[in] gaps    The Gaps object to query.
 *
 * @return TSize The total number of gap openings (Metafunction: @link ContainerConcept#Size @endlink).
 */

template <typename TGaps>
inline typename Size<TGaps>::Type
countGapOpens(TGaps const & gaps)
{
    typedef typename Iterator<TGaps const, Standard>::Type   TIter;
    typedef typename Size<TGaps const>::Type                 TCount;

    TCount count = 0;

    TIter it = begin(gaps, Standard());
    TIter itEnd = end(gaps, Standard());

    while (it != itEnd)
    {
        count += isGap(it);
        it += std::max(countGaps(it), (TCount)1);
    }

    SEQAN_ASSERT(it == itEnd);

    return count;
}

// ----------------------------------------------------------------------------
// Function countGapExtensions()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#countGapExtensions
 * @brief The number of gap extensions.
 *
 * @signature TSize countGapExtensions(gaps);
 *
 * @param[in] gaps    The Gaps object to query.
 *
 * @return TSize The total number of gap extensions (Metafunction: @link ContainerConcept#Size @endlink).
 */

template <typename TGaps>
inline typename Size<TGaps>::Type
countGapExtensions(TGaps const & gaps)
{
    typedef typename Iterator<TGaps const, Standard>::Type   TIter;
    typedef typename Size<TGaps const>::Type                 TCount;

    TCount count = 0;

    TIter it = begin(gaps, Standard());
    TIter itEnd = end(gaps, Standard());

    while (it != itEnd)
    {
        count += countGaps(it);
        it += std::max(countGaps(it), (TCount)1);
    }

    SEQAN_ASSERT(it == itEnd);

    return count;
}

// ----------------------------------------------------------------------------
// Function countCharacters()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#countCharacters
 * @brief The number of characters following a position.
 *
 * @signature TSize countCharacters(gaps, viewPos[, dir]);
 *
 * @param[in] gaps    The Gaps object to query.
 * @param[in] viewPos View position (including clipping and gaps) to query at.
 * @param[in] dir     A tag to specify the counting direction. One of @link GapDirectionTags @endlink.
 *                    Defaults to @link GapDirectionTags#RightOfViewPos @endlink.
 *
 * @return TSize The number of non-gaps characters characters at <tt>viewPos</tt> (Metafunction: @link
 *               ContainerConcept#Size @endlink).
 *
 * If the the direction tag is @link GapDirectionTags#RightOfViewPos @endlink the current view position will be
 * included in the count, and excluded when @link GapDirectionTags#LeftOfViewPos @endlink is selected.
 */

template <typename TSequence, typename TSpec,
          typename TPos,
          typename TDirSpec>
typename Size<Gaps<TSequence, TSpec> >::Type
countCharacters(Gaps<TSequence, TSpec> const & gaps,
                TPos const clippedViewPos,
                TDirSpec const & /*dir*/)
{
    return countCharacters(iter(gaps, clippedViewPos, Standard()), TDirSpec());
}

template <typename TSequence, typename TSpec, typename TPos>
typename Size<Gaps<TSequence, TSpec> >::Type
countCharacters(Gaps<TSequence, TSpec> const & gaps, TPos const clippedViewPos)
{
    return countCharacters(gaps, clippedViewPos, RightOfViewPos());
}

// ----------------------------------------------------------------------------
// Function setClippedBeginPosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#setClippedBeginPosition
 * @brief Set the begin position of the clipping.
 *
 * @signature void setClippedBeginPosition(gaps, unclippedViewPos);
 *
 * @param[in,out] gaps             The Gaps object to set the clipping begin position of.
 * @param[in]     unclippedViewPos View position (including gaps but excluding clipping) to set the clipping begin to.
 */

// ----------------------------------------------------------------------------
// Function setClippedEndPosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#setClippedEndPosition
 * @brief Set the end position of the clipping.
 *
 * @signature void setClippedEndPosition(gaps, unclippedViewPos);
 *
 * @param[in,out] gaps             The Gaps object to set the clipping end position of.
 * @param[in]     unclippedViewPos View position (including gaps but excluding clipping) to set the clipping end to.
 */

// ----------------------------------------------------------------------------
// Function clippedBeginPosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#clippedBeginPosition
 * @brief Return begin position of the clipping.
 *
 * @signature TPos clippedBeginPosition(gaps);
 *
 * @param[in] gaps             The Gaps object to query.
 *
 * @return TPos The begin position of the unclipped view  (Metafunction: @link ContainerConcept#Position @endlink).
 *
 * @section Example
 *
 * In the following gaps configuration, the result of <tt>clippedBeginPosition(gaps)</tt> is 1.
 *
 * @code{.txt}
 * clipping                   [     )
 *   (half-open interval)
 *
 * gapped sequence:          X--XXX-XX-
 *
 * source position:          0111234456
 * unclipped view position:  0123456789
 * clipped view position:     0123456
 * @endcode
 */

// ----------------------------------------------------------------------------
// Function clippedEndPosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#clippedEndPosition
 * @brief Return end position of the clipping.
 *
 * @signature TPos clippedEndPosition(gaps);
 *
 * @param[in] gaps             The Gaps object to query.
 *
 * @return TPos The end position of the unclipped view  (Metafunction: @link ContainerConcept#Position @endlink).
 *
 * @section Example
 *
 * In the following gaps configuration, the result of <tt>clippedEndPosition(gaps)</tt> is 7.
 *
 * @code{.txt}
 * clipping                   [     )
 *   (half-open interval)
 *
 * gapped sequence:          X--XXX-XX-
 *
 * source position:          0111234456
 * unclipped view position:  0123456789
 * clipped view position:     0123456
 * @endcode
 */

// ----------------------------------------------------------------------------
// Function setBeginPosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#setBeginPosition
 * @brief Set the begin position of the clipped gapped sequence, given a source position.
 *
 * @signature void setBeginPosition(gaps, sourcePos);
 *
 * @param[in,out] gaps      The Gaps object to set the begin position in.
 * @param[in]     sourcePos Position in the underlying sequence to set clipping to.
 */

// ----------------------------------------------------------------------------
// Function setEndPosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#setEndPosition
 * @brief Set the end position of the clipped gapped sequence, given a source position.
 *
 * @signature void setEndPosition(gaps, sourcePos);
 *
 * @param[in,out] gaps      The Gaps object to set the end position in.
 * @param[in]     sourcePos Position in the underlying sequence to set clipping to.
 */

// ----------------------------------------------------------------------------
// Function beginPosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#beginPosition
 * @brief Return the clipping begin position as a source position.
 *
 * @signature TPos beginPosition(gaps);
 *
 * @param[in] gaps The Gaps object to query.
 *
 * @return TPos The clipping begin position in the source (Metafunction: @link ContainerConcept#Position @endlink).
 *
 * @section Example
 *
 * In the following gaps configuration, the result of <tt>beginPosition(gaps)</tt> is $1$.  The clipping starts in a
 * gap and the source position of the first non-gap character right of the clipping begin has source position 1.
 *
 * @code{.txt}
 * clipping                   [     )
 *   (half-open interval)
 *
 * gapped sequence:          X--XXX-XX-
 *
 * source position:          0111234456
 * unclipped view position:  0123456789
 * clipped view position:     0123456
 * @endcode
 */

// ----------------------------------------------------------------------------
// Function endPosition()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#endPosition
 * @brief Return the clipping end position as a source position.
 *
 * @signature TPos endPosition(gaps);
 *
 * @param[in] gaps The Gaps object to query for the end position as a source position.
 *
 * @return TPos The end position as a source position (Metafunction: @link ContainerConcept#Position @endlink).
 *
 * @section Example
 *
 * In the following gaps configuration, the result of <tt>endPositioN(gaps)</tt> is 4.
 *
 * @code{.txt}
 * clipping                   [     )
 *   (half-open interval)
 *
 * gapped sequence:          X--XXX-XX-
 *
 * source position:          0111234456
 * unclipped view position:  0123456789
 * clipped view position:     0123456
 * @endcode
 */

// ----------------------------------------------------------------------------
// Function write()
// ----------------------------------------------------------------------------

template <typename TTarget, typename TSource, typename TSpec>
inline void
write(TTarget & target,
      Gaps<TSource, TSpec> const & source)
{
    // Print gaps row
    typedef typename Iterator<Gaps<TSource, TSpec> const>::Type TIter;
    TIter begin_ = begin(source);
    TIter end_ = end(source);
    for (; begin_ != end_; ++begin_) {
        if (isGap(begin_))
            writeValue(target, gapValue<char>());
        else
            writeValue(target, convert<char>(getValue(begin_)));
    }
}

// ----------------------------------------------------------------------------
// Function operator<<()                                      [stream operator]
// ----------------------------------------------------------------------------

// TODO(holtgrew): Document appropriately.

template <typename TTarget, typename TSource, typename TSpec>
inline TTarget &
operator<<(TTarget & target, Gaps<TSource, TSpec> const & gaps)
{
    typename DirectionIterator<TTarget, Output>::Type it = directionIterator(target, Output());
    write(it, gaps);
    return target;
}

// ----------------------------------------------------------------------------
// Function _pumpTraceToGaps()
// ----------------------------------------------------------------------------

// Internal function for converting AlignTrace<> objects into alignments in two Gaps objects.  Note that the traceback
// in the trace is stored in reverse, from back to front.  We insert the gaps in descending order of their position.
// The reason is that Gaps<> objects store the gaps in ascending order of coordinates in String<> objects and inserting
// at the end is in O(1) while inserting in the front is O(n).

template <typename TSequenceH, typename TGapsSpecH, typename TSequenceV, typename TGapsSpecV, typename TSize>
void _pumpTraceToGaps(Gaps<TSequenceH, TGapsSpecH> & gapsH,
                      Gaps<TSequenceV, TGapsSpecV> & gapsV,
                      AlignTraceback<TSize> const & trace)
{
    typedef Gaps<TSequenceH, TGapsSpecH> TGapsH;
    typedef typename Iterator<TGapsH, Standard>::Type TGapsHIter;

    typedef Gaps<TSequenceV, TGapsSpecV> TGapsV;
    typedef typename Iterator<TGapsV, Standard>::Type TGapsVIter;

    // TODO(holtgrew): I don't understand the following.  Originally, this function used Align objects, but I did not understand it there either.
    // TODO(rausch): Pump trace into align_ (note: this is relatively slow code here. it could be improved if specialized to the Align Specs).
    clearGaps(gapsH);
    clearClipping(gapsH);
    clearGaps(gapsV);
    clearClipping(gapsV);

    TSize i = length(trace.sizes);  // Scan trace backwards.
    TGapsHIter itH = begin(gapsH);
    TGapsVIter itV = begin(gapsV);
    while (i > 0)
    {
        --i;
        TSize size = trace.sizes[i];
        switch ((int) trace.tvs[i])
        {
        case 1:  // Go horizontal.
            insertGaps(itV, size);
            break;

        case 2:  // Go vertical.
            insertGaps(itH, size);
            break;
        }
        goFurther(itH, size);
        goFurther(itV, size);
    }
}

// ----------------------------------------------------------------------------
// Function source()
// ----------------------------------------------------------------------------

// TODO(holtgrew): Document TSource via metafunctio.

/*!
 * @fn Gaps#source
 * @brief Return underlying object.
 *
 * @signature TSource source(gaps);
 *
 * @param[in] gaps The Gaps object to return the underling sequence for.
 *
 * @return TSource Reference to the source of the Gaps.
 */

// ----------------------------------------------------------------------------
// Function sourceSegment()
// ----------------------------------------------------------------------------

// TODO(holtgrew): Rename/remove?

// We need some forwards for function sourceSegment().

template <typename TSequence, typename TSpec>
inline typename Position<Gaps<TSequence, TSpec> >::Type clippedBeginPosition(Gaps<TSequence, TSpec> const & gaps);
template <typename TSequence, typename TSpec>
inline typename Position<Gaps<TSequence, TSpec> >::Type clippedEndPosition(Gaps<TSequence, TSpec> const & gaps);
template <typename TSequence, typename TSpec, typename TPosition>
inline typename Position<TSequence>::Type
toSourcePosition(Gaps<TSequence, TSpec> const & gaps, TPosition clippedViewPos);

template <typename TSequence, typename TSpec>
inline typename Infix<TSequence>::Type
sourceSegment(Gaps<TSequence, TSpec> const & gaps)
{
    return infix(source(gaps), toSourcePosition(gaps, clippedBeginPosition(gaps)), toSourcePosition(gaps, clippedEndPosition(gaps)));
}

template <typename TSequence, typename TSpec>
inline typename Infix<TSequence>::Type
sourceSegment(Gaps<TSequence, TSpec> & gaps)
{
    return infix(source(gaps), toSourcePosition(gaps, clippedBeginPosition(gaps)), toSourcePosition(gaps, clippedEndPosition(gaps)));
}

// ----------------------------------------------------------------------------
// Function assignSource()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#assignSource
 * @brief Assign the source of a gaps object, copying data.
 *
 * @signature void assignSource(gaps, seq);
 *
 * @param[in,out] gaps The Gaps object to assign the source of.
 * @param[in]     seq  The @link ContainerConcept sequence @endlink to assign to the underlying string.
 */

// TOOD(holtgrew): Switch to Hosted Type?

template <typename TSequence, typename TSpec, typename TValue>
inline void
assignSource(Gaps<TSequence, TSpec> & gaps, TValue const & value)
{
    assign(source(gaps), value);
}

// ----------------------------------------------------------------------------
// Function setSource()
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// Function copyGaps()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#copyGaps
 * @brief Copy gaps from one Gaps object to another (in the clipped view of both arguments).
 *
 * The user is responsible for ensuring that the gaps are over sequences of same length and appropriate clipping.
 *
 * @signature void copyGaps(dest, source);
 *
 * @param[in,out] dest   The destination Gaps object (appropriate clipping, no gaps).
 * @param[in]     source The source Gaps object.
 */

template <typename TDestSource, typename TDestSpec, typename TSourceSource, typename TSourceSpec>
void copyGaps(Gaps<TDestSource, TDestSpec> & dest, Gaps<TSourceSource, TSourceSpec> const & source)
{
    typedef Gaps<TDestSource, TDestSpec> TLhs;
    typedef typename Iterator<TLhs, Standard>::Type TLhsIter;
    typedef Gaps<TSourceSource, TSourceSpec> const TRhs;
    typedef typename Iterator<TRhs, Standard>::Type TRhsIter;

    TLhsIter lhsIt = begin(dest, Standard());
    //TLhsIter lhsItEnd = end(dest, Standard());
    TRhsIter rhsIt = begin(source, Standard());
    TRhsIter rhsItEnd = end(source, Standard());

    for (unsigned num = 0; rhsIt != rhsItEnd; lhsIt += num, rhsIt += num)
    {
        if (isGap(rhsIt))
        {
            num = countGaps(rhsIt);
            insertGaps(lhsIt, num);
        }
        else
        {
            num = countCharacters(rhsIt);
        }

        SEQAN_ASSERT_NOT((lhsIt == end(dest, Standard())) && num > 0);
    }
}

// ----------------------------------------------------------------------------
// Function copyClipping()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#copyClipping
 * @brief Copy clipping information from one Gaps object to another.
 *
 * @signature void copyClipping(dest, source);
 *
 * @param[in,out] dest   The destination Gaps object.
 * @param[in]     source The source Gaps object.
 */

template <typename TDestSource, typename TDestSpec, typename TSourceSource, typename TSourceSpec>
void copyClipping(Gaps<TDestSource, TDestSpec> & dest, Gaps<TSourceSource, TSourceSpec> const & source)
{
    setClippedBeginPosition(dest, clippedBeginPosition(source));
    setClippedEndPosition(dest, clippedEndPosition(source));
}

// ----------------------------------------------------------------------------
// Function clipSemiGlobal()
// ----------------------------------------------------------------------------

/*!
 * @fn Gaps#clipSemiGlobal
 * @brief Clip the Gaps objects to reflect a semi-global alignment.
 *
 * Leading and trailing gaps are clipped in the local Gaps object. The global Gaps object is updated accordingly.
 *
 * @signature void clipSemiGlobal(global, local);
 *
 * @param[in,out] global The global Gaps object.
 * @param[in,out] local  The local Gaps object.
 */

template <typename TGlobalGaps, typename TLocalGaps>
inline void clipSemiGlobal(TGlobalGaps & global, TLocalGaps & local)
{
    typedef typename Size<TLocalGaps>::Type  TGapsSize;

    TGapsSize leadingGaps = countLeadingGaps(local);
    TGapsSize trailingGaps = countTrailingGaps(local);
    TGapsSize globalLenght = length(global);
    TGapsSize localLength = length(local);

    setClippedBeginPosition(global, leadingGaps);
    setClippedBeginPosition(local, leadingGaps);
    setClippedEndPosition(global, globalLenght - trailingGaps);
    setClippedEndPosition(local, localLength - trailingGaps);
}

// ----------------------------------------------------------------------------
// Function clear()
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec>
inline void clearGaps(Gaps<TSequence, TSpec> & gaps);
template <typename TSequence, typename TSpec>
inline void clearClipping(Gaps<TSequence, TSpec> & gaps);

template <typename TSequence, typename TSpec>
inline void clear(Gaps<TSequence, TSpec> & gaps)
{
    clearGaps(gaps);
    clearClipping(gaps);
}

// ----------------------------------------------------------------------------
// Function operator==()
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec>
inline bool operator==(Gaps<TSequence, TSpec> const & lhs,
                       Gaps<TSequence, TSpec> const & rhs)
{
    typename Comparator<Gaps<TSequence, TSpec> >::Type lex(lhs, rhs);
    return isEqual(lex);
}

template <typename TSequence, typename TSpec, typename TRightHandSide>
inline bool operator==(Gaps<TSequence, TSpec> const & lhs,
                       TRightHandSide const & rhs)
{
    typename Comparator<Gaps<TSequence, TSpec> >::Type lex(lhs, rhs);
    return isEqual(lex);
}

// ----------------------------------------------------------------------------
// Function operator!=()
// ----------------------------------------------------------------------------

template <typename TSequence, typename TSpec>
inline bool operator!=(Gaps<TSequence, TSpec> const & lhs,
                       Gaps<TSequence, TSpec> const & rhs)
{
    return !(lhs == rhs);
}


}  // namespace seqan2

#endif  // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_BASE_H_