// ==========================================================================
//                 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: Rene Rahn <rene.rahn@fu-berlin.de>
// ==========================================================================
// Implements the delta map to efficiently store delta entries ordered by
// their position within the base sequence in ascending order.
// ==========================================================================

#ifndef EXTRAS_INCLUDE_SEQAN_JOURNALED_STRING_TREE_DELTA_MAP_H_
#define EXTRAS_INCLUDE_SEQAN_JOURNALED_STRING_TREE_DELTA_MAP_H_

namespace seqan2
{

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

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

// ----------------------------------------------------------------------------
// Tag DeltaMapIteratorSpec
// ----------------------------------------------------------------------------

struct SpecDeltaMapIterator_;
typedef Tag<SpecDeltaMapIterator_> DeltaMapIteratorSpec;

// ----------------------------------------------------------------------------
// Tag DeltaMapEntriesMember
// ----------------------------------------------------------------------------

struct DeltaMapEntriesMember_;
typedef Tag<DeltaMapEntriesMember_> DeltaMapEntriesMember;

// ----------------------------------------------------------------------------
// Tag DeltaStoreMember
// ----------------------------------------------------------------------------

struct DeltaMapStoreMember_;
typedef Tag<DeltaMapStoreMember_> DeltaMapStoreMember;

// ----------------------------------------------------------------------------
// Class DeltaMap
// ----------------------------------------------------------------------------

// TODO(rrahn): Add demo.
/*!
 * @class DeltaMap
 *
 * @headerfile <seqan/journaled_string_tree.h>
 *
 * @brief Stores delta information and maps them to a common coordinate system.
 *
 * @signature template <typename TConfig>
 *            class DeltaMap
 * @tparam TConfig   A config type to set the types for the different delta values.
 *
 * This map stores delta events, i.e. replacements, insertions and deletions, for multiple sequences
 * based on a common reference sequence. A bitvector is used to store the coverage of a delta.
 * The types of the corresponding delta values must be set with the <tt>TConfig<\tt> object, which can be any
 * object which defines the following types:
 *
 * <tt>TDeltaPos<\tt>: The value type used to store the position of the delta within the reference.
 * <tt>TDeltaSnp<\tt>: The value type used to store SNPs.
 * <tt>TDeltaDel<\tt>: The value type used to store deletions.
 * <tt>TDeltaIns<\tt>: The value type used to store insertions.
 * <tt>TDeltaSV<\tt>:  The value type used to store structural variants.
 *
 * The delta values are stored in a multi-container. To access a delta value at any given iterator position
 * of the delta map the delta type (see @link DeltaTypeTags @endlink) must be known.
 * The function @link DeltaMapIterator#deltaType @endlink can be used to access the id of the corresponding delta event.
 * Given the delta type the function @link DeltaMapIterator#deltaValue @endlink can be used to access the corresponding
 * value.
 *
 * The delta map implements the interfaces of the <b>AssociativeContainerConcept<\b> and is a multi-map.
 */

template <typename TConfig, typename TSpec = Default>
class DeltaMap
{
public:

    typedef typename Member<DeltaMap, DeltaMapEntriesMember>::Type TDeltaEntries;
    typedef typename Member<DeltaMap, DeltaMapStoreMember>::Type TDeltaStore;

    TDeltaEntries  _entries;
    TDeltaStore    _deltaStore;
};

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

// ----------------------------------------------------------------------------
// Metafunction Member                                  [DeltaMapEntriesMember]
// ----------------------------------------------------------------------------

template <typename TConfig, typename TSpec>
struct Member<DeltaMap<TConfig, TSpec>, DeltaMapEntriesMember>
{
    typedef typename Value<DeltaMap<TConfig, TSpec> >::Type TValue_;
    typedef String<TValue_> Type;
};

// ----------------------------------------------------------------------------
// Metafunction Member                                    [DeltaMapStoreMember]
// ----------------------------------------------------------------------------

template <typename TConfig, typename TSpec>
struct Member<DeltaMap<TConfig, TSpec>, DeltaMapStoreMember>
{
    typedef typename TConfig::TSnpValue TSnpValue_;
    typedef typename TConfig::TInsValue TInsValue_;
    typedef typename TConfig::TDelValue TDelValue_;
    typedef typename TConfig::TSVValue TSVValue_;
    typedef impl::DeltaStore<TSnpValue_, TDelValue_, TInsValue_, TSVValue_> Type;
};

// ----------------------------------------------------------------------------
// Metafunction Member
// ----------------------------------------------------------------------------

// Const version.
template <typename TConfig, typename TSpec, typename TTag>
struct Member<DeltaMap<TConfig, TSpec> const, TTag>
{
    typedef typename Member<DeltaMap<TConfig, TSpec>, TTag>::Type const Type;
};

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

/*!
 * @mfn DeltaMap#Value
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns value type for the delta map.
 *
 * @signature Value<TDeltaMap>::Type
 * @tparam TDeltaMap The type to query the value type for.
 * @return TValue The value type to use for <tt>TDeltaMap</tt>.
 */

template <typename TConfig, typename TSpec>
struct Value<DeltaMap<TConfig, TSpec> >
{
    typedef typename Member<DeltaMap<TConfig, TSpec>, DeltaMapStoreMember>::Type TDeltaStore_;
    typedef typename Size<TDeltaStore_>::Type TSize_;
    typedef DeltaMapEntry<typename TConfig::TDeltaPos, TSize_> Type;
};

template <typename TConfig, typename TSpec>
struct Value<DeltaMap<TConfig, TSpec> const>
{
    typedef typename Value<DeltaMap<TConfig, TSpec> >::Type const Type;
};

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

/*!
 * @mfn DeltaMap#Size
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns size type for a delta map.
 *
 * @signature Size<TDeltaMap>::Type
 * @tparam TDeltaMap The type to query the size type for.
 * @return TSize The size type to use for <tt>TDeltaMap</tt>.
 */

template <typename TConfig, typename TSpec>
struct Size<DeltaMap<TConfig, TSpec> >
{
    typedef typename Member<DeltaMap<TConfig, TSpec>, DeltaMapEntriesMember>::Type TEntries;
    typedef typename Size<TEntries>::Type Type;
};

template <typename TConfig, typename TSpec>
struct Size<DeltaMap<TConfig, TSpec> const > :
    Size<DeltaMap<TConfig, TSpec> >{};

// ----------------------------------------------------------------------------
// Metafunction Iterator                                             [Standard]
// ----------------------------------------------------------------------------

/*!
 * @mfn DeltaMap#Iterator
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns iterator type for a delta map.
 *
 * @signature Iterator<TDeltaMap, Standard>::Type
 * @tparam TDeltaMap The type to query the iterator type for.
 * @return TIterator The iterator type to use for <tt>TDeltaMap</tt>. @link DeltaMapIterator @endlink.
 */

//template <typename TConfig, typename TSpec>
//struct Iterator<DeltaMap<TConfig, TSpec>, Standard>
//{
//    typedef DeltaMap<TConfig, TSpec> TDeltaMap_;
//    typedef Iter<TDeltaMap_, DeltaMapIteratorSpec> Type;
//};
//
//template <typename TConfig, typename TSpec>
//struct Iterator<DeltaMap<TConfig, TSpec> const, Standard>
//{
//    typedef DeltaMap<TConfig, TSpec> TDeltaMap_;
//    typedef Iter<TDeltaMap_ const, DeltaMapIteratorSpec> Type;
//};

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

template <typename TConfig, typename TSpec, typename TIteratorSpec>
struct Iterator<DeltaMap<TConfig, TSpec>, Tag<TIteratorSpec> const>
{
    typedef DeltaMap<TConfig, TSpec> TDeltaMap_;
    typedef Iter<TDeltaMap_, DeltaMapIteratorSpec> Type;
};

template <typename TConfig, typename TSpec, typename TIteratorSpec>
struct Iterator<DeltaMap<TConfig, TSpec> const, Tag<TIteratorSpec> const>
{
    typedef DeltaMap<TConfig, TSpec> TDeltaMap_;
    typedef Iter<TDeltaMap_ const, DeltaMapIteratorSpec> Type;
};

// ----------------------------------------------------------------------------
// Metafunction DeltaValue
// ----------------------------------------------------------------------------

/*!
 * @mfn DeltaMap#DeltaValue
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns value type for a specific delta.
 *
 * @signature DeltaValue<TDeltaMap, TType>::Type
 * @tparam TDeltaMap The type of the delta map.
 * @tparam TType     The type of the delta value. One of @link DeltaTypeTags @endlink.
 *
 * The delta map stores four different delta events: SNPs, insertions, deletions and variable replacements.
 * This metafunction returns the correct type for the specified event given the delta type tag.
 */

template <typename TConfig, typename TSpec, typename TDeltaType>
struct DeltaValue<DeltaMap<TConfig, TSpec>, TDeltaType>
{
    typedef DeltaMap<TConfig, TSpec> TDeltaMap_;
    typedef typename Member<TDeltaMap_, DeltaMapStoreMember>::Type TDeltaStore_;
    typedef typename DeltaValue<TDeltaStore_, TDeltaType>::Type Type;
};

template <typename TConfig, typename TSpec, typename TDeltaType>
struct DeltaValue<DeltaMap<TConfig, TSpec> const, TDeltaType>
{
    typedef DeltaMap<TConfig, TSpec> TDeltaMap_;
    typedef typename Member<TDeltaMap_, DeltaMapStoreMember>::Type TDeltaStore_;
    typedef typename DeltaValue<TDeltaStore_ const, TDeltaType>::Type Type;
};

// ----------------------------------------------------------------------------
// Metafunction DeltaCoverage
// ----------------------------------------------------------------------------

/*!
 * @mfn DeltaMap#DeltaCoverage
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns coverage type for a delta map.
 *
 * @signature DeltaCoverage<TDeltaMap>::Type
 * @tparam TDeltaMap The type of the delta map.
 */

template <typename TConfig, typename TSpec>
struct DeltaCoverage<DeltaMap<TConfig, TSpec> >
{
    typedef typename Value<DeltaMap<TConfig, TSpec> >::Type TEntry_;
    typedef typename DeltaCoverage<TEntry_>::Type Type;
};

template <typename TConfig, typename TSpec>
struct DeltaCoverage<DeltaMap<TConfig, TSpec> const>
{
    typedef typename Value<DeltaMap<TConfig, TSpec> >::Type TEntry_;
    typedef typename DeltaCoverage<TEntry_ const>::Type Type;
};

// ============================================================================
// Private Functions
// ============================================================================

namespace impl
{

// ----------------------------------------------------------------------------
// Function impl::lbWrapper
// ----------------------------------------------------------------------------

template <typename TConfig, typename TSpec, typename TEntry, typename TFunctor>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type
lbWrapper(DeltaMap<TConfig, TSpec> const & deltaMap, TEntry const & entry, TFunctor const & f)
{
    return std::lower_bound(begin(deltaMap, Standard()), end(deltaMap, Standard()), entry, f);
}

template <typename TConfig, typename TSpec, typename TEntry, typename TFunctor>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Standard>::Type
lbWrapper(DeltaMap<TConfig, TSpec> & deltaMap, TEntry const & entry, TFunctor const & f)
{
    return std::lower_bound(begin(deltaMap, Standard()), end(deltaMap, Standard()), entry, f);
}

// ----------------------------------------------------------------------------
// Function impl::ubWrapper
// ----------------------------------------------------------------------------

template <typename TConfig, typename TSpec, typename TEntry, typename TFunctor>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type
ubWrapper(DeltaMap<TConfig, TSpec> const & deltaMap, TEntry const & entry, TFunctor const & f)
{
    return std::upper_bound(begin(deltaMap, Standard()), end(deltaMap, Standard()), entry, f);
}

template <typename TConfig, typename TSpec, typename TEntry, typename TFunctor>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Standard>::Type
ubWrapper(DeltaMap<TConfig, TSpec> & deltaMap, TEntry const & entry, TFunctor const & f)
{
    return std::upper_bound(begin(deltaMap, Standard()), end(deltaMap, Standard()), entry, f);
}

// ----------------------------------------------------------------------------
// Function impl::lowerBound();
// ----------------------------------------------------------------------------

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type
lowerBound(DeltaMap<TConfig, TSpec> const & deltaMap,
           TPosition const refPosition,
           DeltaEndType const endType,
           TDeltaType /*deltaType*/)
{
    typedef DeltaMap<TConfig, TSpec> TDeltaMap;
    typedef typename Value<TDeltaMap>::Type TEntry;

    TEntry entry;
    entry.deltaPosition = refPosition;
    entry.deltaRecord.i1 = selectDeltaType(TDeltaType());
    entry.deltaTypeEnd = endType;
    return impl::lbWrapper(deltaMap, entry, DeltaMapEntryPosAndTypeLessThanComparator_());
}

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Standard>::Type
lowerBound(DeltaMap<TConfig, TSpec> & deltaMap,
           TPosition const refPosition,
           DeltaEndType const endType,
           TDeltaType /*deltaType*/)
{
    typedef DeltaMap<TConfig, TSpec> TDeltaMap;
    typedef typename Value<TDeltaMap>::Type TEntry;

    TEntry entry;
    entry.deltaPosition = refPosition;
    entry.deltaRecord.i1 = selectDeltaType(TDeltaType());
    entry.deltaTypeEnd = endType;
    return impl::lbWrapper(deltaMap, entry, DeltaMapEntryPosAndTypeLessThanComparator_());
}

// ----------------------------------------------------------------------------
// Function impl::upperBound();
// ----------------------------------------------------------------------------

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type
upperBound(DeltaMap<TConfig, TSpec> const & deltaMap,
           TPosition const refPosition,
           DeltaEndType const endType,
           TDeltaType /*deltaType*/)
{
    typedef DeltaMap<TConfig, TSpec> TDeltaMap;
    typedef typename Value<TDeltaMap>::Type TEntry;

    TEntry entry;
    entry.deltaPosition = refPosition;
    entry.deltaRecord.i1 = selectDeltaType(TDeltaType());
    entry.deltaTypeEnd = endType;
    return impl::ubWrapper(deltaMap, entry, DeltaMapEntryPosAndTypeLessThanComparator_());
}

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Standard>::Type
upperBound(DeltaMap<TConfig, TSpec> & deltaMap,
           TPosition refPosition,
           DeltaEndType const endType,
           TDeltaType /*deltaType*/)
{
    typedef DeltaMap<TConfig, TSpec> TDeltaMap;
    typedef typename Value<TDeltaMap>::Type TEntry;

    TEntry entry;
    entry.deltaPosition = refPosition;
    entry.deltaRecord.i1 = selectDeltaType(TDeltaType());
    entry.deltaTypeEnd = endType;
    return impl::ubWrapper(deltaMap, entry, DeltaMapEntryPosAndTypeLessThanComparator_());
}

// ----------------------------------------------------------------------------
// Function impl::find();
// ----------------------------------------------------------------------------

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type
find(DeltaMap<TConfig, TSpec> const & deltaMap,
     TPosition const refPosition,
     DeltaEndType const endType,
     TDeltaType /*deltaType*/)
{
    auto it = lowerBound(deltaMap, refPosition, endType, TDeltaType());
    if (it != end(deltaMap, Standard()) &&
        static_cast<TPosition>(getDeltaPosition(*it)) == refPosition &&
        getDeltaRecord(*it).i1 == selectDeltaType(TDeltaType()))
        return it;
    return end(deltaMap, Standard());
}

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Standard>::Type
find(DeltaMap<TConfig, TSpec> & deltaMap,
     TPosition const refPosition,
     DeltaEndType const endType,
     TDeltaType /*deltaType*/)
{
    auto it = lowerBound(deltaMap, refPosition, endType, TDeltaType());
    if (it != end(deltaMap, Standard()) &&
        static_cast<TPosition>(getDeltaPosition(*it)) == refPosition &&
        getDeltaRecord(*it).i1 == selectDeltaType(TDeltaType()))
        return it;
    return end(deltaMap, Standard());
}

// ----------------------------------------------------------------------------
// Function impl::checkNoDuplicate()
// ----------------------------------------------------------------------------

template <typename TDeltaMap, typename TDeltaPos, typename TTag>
inline bool
checkNoDuplicate(TDeltaMap const & map, TDeltaPos pos, TTag /*deltaType*/)
{
    typedef typename Value<TDeltaMap>::Type TEntry;
    typedef typename DeltaPosition<TEntry>::Type TEntryPos;

    auto it = lowerBound(map, pos, TTag());
    if (it != end(map, Standard()))
        if (getDeltaPosition(*it) == static_cast<TEntryPos>(pos))
            return getDeltaRecord(*it).i1 != selectDeltaType(TTag());
    return true;
}

// ----------------------------------------------------------------------------
// Function impl::insert()
// ----------------------------------------------------------------------------

template <typename TDeltaMap, typename TDeltaPos, typename TDeltaValue, typename TCoverage, typename TTag>
inline void
insert(Iter<TDeltaMap, DeltaMapIteratorSpec> const & mapIt,
       TDeltaPos deltaPos,
       TDeltaValue const & deltaValue,
       TCoverage const & coverage,
       TTag const & deltaType)
{
    typedef typename Value<TDeltaMap>::Type TEntry;
    typedef typename DeltaRecord<TEntry>::Type TDeltaRecord;

    insertValue(mapIt._mapPtr->_entries, mapIt - begin(*mapIt._mapPtr, Standard()),
                TEntry(deltaPos, TDeltaRecord(selectDeltaType(deltaType),
                                              addDeltaValue(mapIt._mapPtr->_deltaStore, deltaValue, deltaType)),
                                              coverage,
                                              DeltaEndType::IS_BOTH));
}

template <typename TDeltaMap, typename TDeltaPos, typename TDeltaValue, typename TCoverage>
inline void
insert(Iter<TDeltaMap, DeltaMapIteratorSpec> mapIt,
       TDeltaPos deltaPos,
       TDeltaValue const & deltaValue,
       TCoverage const & coverage,
       DeltaTypeDel const & /*deltaType*/)
{
    typedef typename Value<TDeltaMap>::Type TEntry;
    typedef typename DeltaRecord<TEntry>::Type TDeltaRecord;

    DeltaEndType endType = DeltaEndType::IS_BOTH;
    if (deltaValue > 1)
        endType = DeltaEndType::IS_LEFT;

    auto storePos = addDeltaValue(mapIt._mapPtr->_deltaStore, deltaValue, DeltaTypeDel());
    insertValue(mapIt._mapPtr->_entries, mapIt - begin(*mapIt._mapPtr, Standard()),
                TEntry(deltaPos, TDeltaRecord(DELTA_TYPE_DEL, storePos), coverage, endType));

    if (endType == DeltaEndType::IS_LEFT)
    {
        deltaPos += deltaValue - 1;
        mapIt = lowerBound(*mapIt._mapPtr, deltaPos, DeltaTypeDel());
        insertValue(mapIt._mapPtr->_entries, mapIt - begin(*mapIt._mapPtr, Standard()),
                    TEntry(deltaPos, TDeltaRecord(DELTA_TYPE_DEL, storePos), coverage, DeltaEndType::IS_RIGHT));
    }
}

template <typename TDeltaMap, typename TDeltaPos, typename TDeltaValue, typename TCoverage>
inline void
insert(Iter<TDeltaMap, DeltaMapIteratorSpec> mapIt,
       TDeltaPos deltaPos,
       TDeltaValue const & deltaValue,
       TCoverage const & coverage,
       DeltaTypeSV const & /*deltaType*/)
{
    typedef typename Value<TDeltaMap>::Type TEntry;
    typedef typename DeltaRecord<TEntry>::Type TDeltaRecord;

    DeltaEndType endType = DeltaEndType::IS_BOTH;
    if (deltaValue.i1 > 1)
        endType = DeltaEndType::IS_LEFT;

    auto storePos = addDeltaValue(mapIt._mapPtr->_deltaStore, deltaValue, DeltaTypeSV());
    insertValue(mapIt._mapPtr->_entries, mapIt - begin(*mapIt._mapPtr, Standard()),
                TEntry(deltaPos, TDeltaRecord(DELTA_TYPE_SV, storePos), coverage, endType));

    if (endType == DeltaEndType::IS_LEFT)
    {
        deltaPos += deltaValue.i1 - 1;
        mapIt = lowerBound(*mapIt._mapPtr, deltaPos, DeltaTypeSV());
        insertValue(mapIt._mapPtr->_entries, mapIt - begin(*mapIt._mapPtr, Standard()),
                    TEntry(deltaPos, TDeltaRecord(DELTA_TYPE_SV, storePos), coverage, DeltaEndType::IS_RIGHT));
    }
}

}

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

// ----------------------------------------------------------------------------
// Function lowerBound()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#lowerBound
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Finds the first element that compares not less than the specified key.
 *
 * @signature TIterator lowerBound(deltaMap, pos, type)
 *
 * @param[in] deltaMap  The delta map that is searched for the element.
 * @param[in] pos       The delta position to be searched for.
 * @param[in] type      The type of the delta operation. Must be of type @link DeltaTypeTags @endlink.
 *
 * @return TIterator An @link DeltaMap#Iterator @endlink pointing to the corresponding element.
 *  If the key is not contained @link DeltaMap#end @endlink is returned.
 *
 * @remark The runtime is logarithmic in the size of the map.
 */

// Searches for the position and the delta type.

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type
lowerBound(DeltaMap<TConfig, TSpec> const & deltaMap,
           TPosition const refPosition,
           TDeltaType /*deltaType*/)
{
    return impl::lowerBound(deltaMap, refPosition, DeltaEndType::IS_LEFT, TDeltaType());
}

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Standard>::Type
lowerBound(DeltaMap<TConfig, TSpec> & deltaMap,
           TPosition const refPosition,
           TDeltaType /*deltaType*/)
{
    return impl::lowerBound(deltaMap, refPosition, DeltaEndType::IS_LEFT, TDeltaType());
}

// ----------------------------------------------------------------------------
// Function upperBound()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#upperBound
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Finds the first element that compares not less or equal to the specified key.
 *
 * @signature TIterator upperBound(deltaMap, pos, type)
 *
 * @param[in] deltaMap  The delta map that is searched for the element.
 * @param[in] pos       The delta position to be searched for.
 * @param[in] type      The type of the delta operation. Must be of type @link DeltaTypeTags @endlink.
 *
 * @return TIterator An @link DeltaMap#Iterator @endlink pointing to the corresponding element.
 *  If the key is not contained @link DeltaMap#end @endlink is returned.
 *
 * @remark The runtime is logarithmic in the size of the map.
 */

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type
upperBound(DeltaMap<TConfig, TSpec> const & deltaMap,
           TPosition const refPosition,
           TDeltaType /*deltaType*/)
{
    return impl::upperBound(deltaMap, refPosition, DeltaEndType::IS_BOTH, TDeltaType());
}

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Standard>::Type
upperBound(DeltaMap<TConfig, TSpec> & deltaMap,
           TPosition const refPosition,
           TDeltaType /*deltaType*/)
{
    return impl::upperBound(deltaMap, refPosition, DeltaEndType::IS_BOTH, TDeltaType());
}

// ----------------------------------------------------------------------------
// Function find()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#find
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Finds the element specified by the given delta position and delta type.
 *
 * @signature TIterator find(deltaMap, pos, type)
 *
 * @param[in] deltaMap  The delta map that is searched for the element.
 * @param[in] pos       The delta position to be searched for.
 * @param[in] type      The type of the delta operation. Must be of type @link DeltaTypeTags @endlink.
 *
 * @return TIterator An @link DeltaMap#Iterator @endlink pointing to the corresponding element.
 *  If the key is not contained @link DeltaMap#end @endlink is returned.
 *
 * @remark The runtime is logarithmic in the size of the map.
 */

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type
find(DeltaMap<TConfig, TSpec> const & deltaMap,
     TPosition const refPosition,
     TDeltaType /*deltaType*/)
{
    return impl::find(deltaMap, refPosition, DeltaEndType::IS_LEFT, TDeltaType());
}

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Standard>::Type
find(DeltaMap<TConfig, TSpec> & deltaMap,
     TPosition const refPosition,
     TDeltaType /*deltaType*/)
{
    return impl::find(deltaMap, refPosition, DeltaEndType::IS_LEFT, TDeltaType());
}

// ----------------------------------------------------------------------------
// Function count()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#count
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Counts the number of elements that compare equal to the specified key.
 *
 * @signature TSize count(deltaMap, pos, type)
 *
 * @param[in] deltaMap  The delta map that is searched for the element.
 * @param[in] pos       The delta position to be searched for.
 * @param[in] type      The type of the delta operation. Must be of type @link DeltaTypeTags @endlink.
 *
 * @return TSize the number of elements with the specified key. Of type @link DeltaMap#Size @endlink.
 *
 * @remark The runtime is logarithmic in the size of the map.
 */

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline typename Size<DeltaMap<TConfig, TSpec> >::Type
count(DeltaMap<TConfig, TSpec> const & deltaMap,
      TPosition refPosition,
      Tag<TDeltaType> /*deltaType*/)
{
    auto itB = lowerBound(deltaMap, refPosition, Tag<TDeltaType>());
    auto count = 0;
    while (itB != end(deltaMap, Standard()) &&
           static_cast<TPosition>(getDeltaPosition(*itB)) == refPosition &&
           getDeltaRecord(*itB).i1 == selectDeltaType(Tag<TDeltaType>()))
    {
        ++count;
        ++itB;
    }
    return count;
}

// ----------------------------------------------------------------------------
// Function equalRange()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#equalRange
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns the range over all elements comparing equal to the specified key.
 *
 * @signature Pair<TIterator> equalRange(deltaMap, pos, type)
 *
 * @param[in] deltaMap  The delta map that is searched for the element.
 * @param[in] pos       The delta position to be searched for.
 * @param[in] type      The type of the delta operation. Must be of type @link DeltaTypeTags @endlink.
 *
 * @return Pair<TIterator> A @link Pair @endlink of iterator types @link DeltaMap#Iterator @endlink. The first value points
 *  to the first element that compares not less than the specified key or to the @link DeltaMap#end @endlink if such an elment could not be found.
 * The second value points to the first element that does not compare less than or equal to the specified key or to the @link DeltaMap#end @endlink if such an elment could not be found.
 *
 * @remark The runtime is logarithmic in the size of the map.
 */

template <typename TConfig, typename TSpec, typename TPosition, typename TDeltaType>
inline Pair<typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type>
equalRange(DeltaMap<TConfig, TSpec> const & deltaMap, TPosition refPosition, TDeltaType /*deltaType*/)
{
    auto rBeg = lowerBound(deltaMap, refPosition, TDeltaType());
    auto rEnd = upperBound(deltaMap, refPosition, TDeltaType());
    return Pair<typename Iterator<DeltaMap<TConfig, TSpec> const, Standard>::Type>(rBeg, rEnd);
}

// ----------------------------------------------------------------------------
// Function insert()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#insert
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Inserts a new delta entry.
 *
 * @signature bool insert(deltaMap, pos, val, cov, type);
 *
 * @param[in,out] deltaMap  The map to insert the new delta operation. Of type @link DeltaMap @endlink.
 * @param[in]     pos       The position of the inserted delta entry.
 * @param[in]     deltaVal  The value of the delta operation.
 * @param[in]     cov       The coverage of the delta operation.
 * @param[in]     type      A specifier to select the correct delta type. One of @link DeltaTypeTags @endlink.
 *
 *
 * @remark The map is implemented as a vector and the insertion time is linear in worst case.
 */

// TODO(rrahn): Change to return iterator as specified for insert of associative containers of the STL.
template <typename TConfig, typename TSpec, typename TDeltaPos, typename TDeltaValue,
          typename TCoverage, typename TDeltaType>
inline void
insert(DeltaMap<TConfig, TSpec> & deltaMap,
       TDeltaPos deltaPos,
       TDeltaValue const & value,
       TCoverage const & coverage,
       TDeltaType const & /*deltaType*/)
{
    if (SEQAN_UNLIKELY(empty(deltaMap)))
        reserve(deltaMap._entries, 1);

    auto it = upperBound(deltaMap, deltaPos, TDeltaType());
    impl::insert(it, deltaPos, value, coverage, TDeltaType());
}

// ----------------------------------------------------------------------------
// Function erase()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#erase
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Erases an existing delta entry.
 *
 * @signature bool erase(deltaMap, pos, type);
 *
 * @param[in,out] deltaMap  The map to erase the delta from. Of type @link DeltaMap @endlink.
 * @param[in]     pos       The position of the targeted delta entry.
 * @param[in]     type      The type of the targeted delta entry. One of @link DeltaTypeTags @endlink.
 *
 * @return bool <tt>false<\tt> if such an entry does not exist, <tt>true<\tt> otherwise.
 *
 * @remark The map is implemented as a vector and the insertion time is linear in worst case.
 */

// TODO(rrahn): Change to return iterator as specified for insert of associative containers of the STL.
// This is the key based method.
// Also implement the iterator base method.
// TODO(rrahn): Put position and delta type into a key type.
template <typename TConfig, typename TSpec, typename TDeltaPos, typename TDeltaType>
inline typename Size<DeltaMap<TConfig, TSpec> >::Type
erase(DeltaMap<TConfig, TSpec> & deltaMap,
      TDeltaPos deltaPos,
      TDeltaType /*deltaType*/)
{
    typedef DeltaMap<TConfig, TSpec> TDeltaMap;
    typedef typename Member<TDeltaMap, DeltaMapStoreMember>::Type TStore;
    typedef typename Value<TDeltaMap>::Type TEntry;
    typedef typename Size<TStore>::Type TStoreSize;

    if (SEQAN_UNLIKELY(empty(deltaMap)))  // Check for empty deltaMap.
        return false;

    auto itRange = equalRange(deltaMap, deltaPos, TDeltaType());
    auto count = itRange.i2 - itRange.i1;
    if (itRange.i1 == end(deltaMap, Standard()))
        return count;  // If lower bound is at end, there is no element with the given key.

    for (auto it = itRange.i1; it != itRange.i2; ++it)
    {
        // Find potential right end of this delta.
        SEQAN_IF_CONSTEXPR (!IsSameType<TDeltaType, DeltaTypeIns>::VALUE)
        {
            auto itR = impl::find(deltaMap,
                                  deltaPos + deletionSize(deltaMap._deltaStore, getDeltaRecord(*it).i2, TDeltaType()) - 1,
                                  DeltaEndType::IS_RIGHT,
                                  TDeltaType());

            SEQAN_ASSERT_LEQ(position(it, deltaMap), position(itR, deltaMap));
            if (it != itR)
            {
                erase(deltaMap._entries, itR - begin(deltaMap, Standard()));
                ++count;  // Increase count number by removed entry.
            }
        }

        // Erase the delta record from the corresponding delta store.
        TStoreSize storePos = getDeltaRecord(*it).i2;
        SEQAN_ASSERT_LT(storePos, length(getDeltaStore(deltaMap._deltaStore, TDeltaType())));
        eraseDeltaValue(deltaMap._deltaStore, storePos, TDeltaType());
        // Update record position for all entries.
        forEach(deltaMap, [storePos](TEntry & entry)
        {
            if (getDeltaRecord(entry).i1 == selectDeltaType(TDeltaType()) && getDeltaRecord(entry).i2 > storePos)
                --getDeltaRecord(entry).i2;  // Decrease record position by one.
        });
    }

    // Erase all entries in the range of equal values.
    erase(deltaMap._entries, position(itRange.i1, deltaMap), position(itRange.i2, deltaMap));

    return count;
}

// ----------------------------------------------------------------------------
// Function begin()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#begin
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns an iterator pointing to the beginning of the map.
 *
 * @signature TIterator begin(deltaMap, tag)
 *
 * @param[in] deltaMap  The map to get the iterator for.
 * @param[in] tag       The iterator tag. Of type @link ContainerIteratorTags @endlink.
 *
 * @return TIterator An iterator of type @link DeltaMap#Iterator @endlink pointing to the beginning of the map.
 */

template <typename TConfig, typename TSpec, typename TIteratorSpec>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Tag<TIteratorSpec> const>::Type
begin(DeltaMap<TConfig, TSpec> & deltaMap, Tag<TIteratorSpec> const /*tag*/)
{
    return typename Iterator<DeltaMap<TConfig, TSpec>, Tag<TIteratorSpec> const>::Type(deltaMap, 0);
}

template <typename TConfig, typename TSpec, typename TIteratorSpec>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Tag<TIteratorSpec> const>::Type
begin(DeltaMap<TConfig, TSpec> const & deltaMap, Tag<TIteratorSpec> const/*tag*/)
{
    return typename Iterator<DeltaMap<TConfig, TSpec> const, Tag<TIteratorSpec> const>::Type(deltaMap, 0);
}

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

template <typename TConfig, typename TSpec, typename TIteratorSpec, typename TPos>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Tag<TIteratorSpec> const>::Type
iter(DeltaMap<TConfig, TSpec> & deltaMap,
     TPos const & pos,
     Tag<TIteratorSpec> const /*tag*/)
{
    return typename Iterator<DeltaMap<TConfig, TSpec>, Tag<TIteratorSpec> const>::Type(deltaMap, pos);
}

template <typename TConfig, typename TSpec, typename TIteratorSpec, typename TPos>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Tag<TIteratorSpec> const>::Type
iter(DeltaMap<TConfig, TSpec> const & deltaMap,
     TPos const & pos,
     Tag<TIteratorSpec> const &/*tag*/)
{
    return typename Iterator<DeltaMap<TConfig, TSpec> const, Tag<TIteratorSpec> const>::Type(deltaMap, pos);
}

// ----------------------------------------------------------------------------
// Function end()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#end
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns an iterator pointing to the end of the map.
 *
 * @signature TIterator end(deltaMap, tag)
 *
 * @param[in] deltaMap  The map to get the iterator for.
 * @param[in] tag       The iterator tag. Of type @link ContainerIteratorTags @endlink.
 *
 * @return TIterator An iterator of type @link DeltaMap#Iterator @endlink pointing to the end of the map.
 */

template <typename TConfig, typename TSpec, typename TIteratorSpec>
inline typename Iterator<DeltaMap<TConfig, TSpec>, Tag<TIteratorSpec> const>::Type
end(DeltaMap<TConfig, TSpec> & deltaMap, Tag<TIteratorSpec> const /*tag*/)
{
    return typename Iterator<DeltaMap<TConfig, TSpec>, Tag<TIteratorSpec> const>::Type(deltaMap, size(deltaMap));
}

template <typename TConfig, typename TSpec, typename TIteratorSpec>
inline typename Iterator<DeltaMap<TConfig, TSpec> const, Tag<TIteratorSpec> const>::Type
end(DeltaMap<TConfig, TSpec> const & deltaMap, Tag<TIteratorSpec> const /*tag*/)
{
    return typename Iterator<DeltaMap<TConfig, TSpec> const, Tag<TIteratorSpec> const>::Type(deltaMap, size(deltaMap));
}

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

/*!
 * @fn DeltaMap#clear
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Clears the delta map.
 *
 * @signature clear(deltaMap)
 *
 * @param[in,out] deltaMap  The map to be cleared.
 */

template <typename TConfig, typename TSpec>
inline void
clear(DeltaMap<TConfig, TSpec> & deltaMap)
{
    clear(deltaMap._entries);
    clear(deltaMap._deltaStore);
}

// ----------------------------------------------------------------------------
// Function empty()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#empty
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Checks if the delta map is empty.
 *
 * @signature bool empty(deltaMap)
 *
 * @param[in] deltaMap  The map to be checked for.
 *
 * @return bool <tt>true</tt> if empty, otherwise <tt>false</tt>
 */

template <typename TConfig, typename TSpec>
inline bool
empty(DeltaMap<TConfig, TSpec> const & deltaMap)
{
    return empty(deltaMap._entries);
}

// ----------------------------------------------------------------------------
// Function size()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#size
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns the number of mapped delta events.
 *
 * @signature TSize size(deltaMap)
 *
 * @param[in] deltaMap  The map to get the size for.
 *
 * @return TSize The number of delta events stored in the map.
 */

template <typename TConfig, typename TSpec>
inline auto
size(DeltaMap<TConfig, TSpec> const & deltaMap) -> decltype(length(deltaMap._entries))
{
    return length(deltaMap._entries);
}

// ----------------------------------------------------------------------------
// Function maxSize()
// ----------------------------------------------------------------------------

/*!
 * @fn DeltaMap#maxSize
 * @headerfile <seqan/journaled_string_tree.h>
 * @brief Returns the number of mapped delta events.
 *
 * @signature TSize size(deltaMap)
 *
 * @param[in] deltaMap  The map to get the size for.
 *
 * @return TSize The number of delta events stored in the map.
 */

template <typename TConfig, typename TSpec>
constexpr typename Size<DeltaMap<TConfig, TSpec> >::Type
maxSize(DeltaMap<TConfig, TSpec> const & /*deltaMap*/)
{
    return std::numeric_limits<typename Size<DeltaMap<TConfig, TSpec> >::Type>::max();
}

}

#endif // EXTRAS_INCLUDE_SEQAN_JOURNALED_STRING_TREE_DELTA_MAP_H_