text:
// ==========================================================================
//                 SeqAn - The Library for Sequence Analysis
// ==========================================================================
// Copyright (c) 2006-2015, 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 seqan
{

// ============================================================================
// 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.
        if (!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 MaxValue<typename Size<DeltaMap<TConfig, TSpec> >::Type>::VALUE;
}

}

#endif // EXTRAS_INCLUDE_SEQAN_JOURNALED_STRING_TREE_DELTA_MAP_H_


text:
from __future__ import print_function
import re

# The following line defines an ascii string used for dynamically refreshing
# the import and progress callbacks on the same terminal line.
# See http://www.termsys.demon.co.uk/vtansi.htm
# \033 is the C-style octal code for an escape character
# [2000D moves the cursor back 2000 columns, this is a brute force way of
# getting to the start of the line.
# [K erases the end of the line
clrLine = "\033[2000D\033[K"

def auto_not_in_place(v=True):
    """Force it to not run in place
    """
    import itkConfig
    itkConfig.NotInPlace = v

def auto_progress(progress_type=1):
    """Set up auto progress report

    progress_type:
        1 or True -> auto progress be used in a terminal
        2 -> simple auto progress (without special characters)
        0 or False -> disable auto progress
    """
    import itkConfig

    if progress_type is True or progress_type == 1:
        itkConfig.ImportCallback = terminal_import_callback
        itkConfig.ProgressCallback = terminal_progress_callback

    elif progress_type == 2:
        itkConfig.ImportCallback = simple_import_callback
        itkConfig.ProgressCallback = simple_progress_callback

    elif progress_type is False or progress_type == 0:
        itkConfig.ImportCallback = None
        itkConfig.ProgressCallback = None

    else:
        raise ValueError("Invalid auto progress type: " + repr(progress_type))

def terminal_progress_callback(name, p):
    """Display the progress of an object and clean the display once complete

    This function can be used with itkConfig.ProgressCallback
    """
    import sys
    print(clrLine + "%s: %f" % (name, p), file=sys.stderr, end="")
    if p == 1:
        print(clrLine, file=sys.stderr, end="")

def terminal_import_callback(name, p):
    """Display the loading of a module and clean the display once complete

    This function can be used with itkConfig.ImportCallback
    """
    import sys
    print(clrLine + "Loading %s... " % name, file=sys.stderr, end="")
    if p == 1:
        print(clrLine, file=sys.stderr, end="")

def simple_import_callback(name, p):
    """Print a message when a module is loading

    This function can be used with itkConfig.ImportCallback
    """
    import sys
    if p == 0:
        print("Loading %s... " % name, file=sys.stderr, end="")
    elif p == 1:
        print("done", file=sys.stderr)

def simple_progress_callback(name, p):
    """Print a message when an object is running

    This function can be used with itkConfig.ProgressCallback
    """
    import sys
    if p == 0:
        print("Running %s... " % name, file=sys.stderr, end="")
    elif p == 1:
        print("done", file=sys.stderr)

def force_load():
    """force itk to load all the submodules"""
    import itk
    for k in dir(itk):
        getattr(itk, k)

import sys

def echo(object, f=sys.stderr):
    """Print an object is f

    If the object has a method Print(), this method is used.
    repr(object) is used otherwise
    """
    print(f, object)
del sys

def size(image_or_filter):
    """Return the size of an image, or of the output image of a filter

    This method take care of updating the needed informations
    """
    # we don't need the entire output, only its size
    image_or_filter.UpdateOutputInformation()
    img = output(image_or_filter)
    return img.GetLargestPossibleRegion().GetSize()

def physical_size(image_or_filter):
    """Return the physical size of an image, or of the output image of a filter

    This method take care of updating the needed informations
    """
    # required because range is overloaded in this module
    import sys
    if sys.version_info >= (3, 0):
      from builtins import range
    else:
      from __builtin__ import range
    spacing_ = spacing(image_or_filter)
    size_ = size(image_or_filter)
    result = []
    for i in range(0, spacing_.Size()):
        result.append(spacing_.GetElement(i) * size_.GetElement(i))
    return result

def spacing(image_or_filter):
    """Return the spacing of an image, or of the output image of a filter

    This method take care of updating the needed informations
    """
    # we don't need the entire output, only its size
    image_or_filter.UpdateOutputInformation()
    img = output(image_or_filter)
    return img.GetSpacing()

def origin(image_or_filter):
    """Return the origin of an image, or of the output image of a filter

    This method take care of updating the needed informations
    """
    # we don't need the entire output, only its size
    image_or_filter.UpdateOutputInformation()
    img = output(image_or_filter)
    return img.GetOrigin()

def index(image_or_filter):
    """Return the index of an image, or of the output image of a filter

    This method take care of updating the needed informations
    """
    # we don't need the entire output, only its size
    image_or_filter.UpdateOutputInformation()
    img = output(image_or_filter)
    return img.GetLargestPossibleRegion().GetIndex()

def region(image_or_filter):
    """Return the region of an image, or of the output image of a filter

    This method take care of updating the needed informations
    """
    # we don't need the entire output, only its size
    image_or_filter.UpdateOutputInformation()
    img = output(image_or_filter)
    return img.GetLargestPossibleRegion()

HAVE_NUMPY = True
try:
    import numpy
except ImportError:
    HAVE_NUMPY = False

def _get_itk_pixelid(numpy_array_type):
    """Returns a ITK PixelID given a numpy array."""

    if not HAVE_NUMPY:
        raise ImportError('Numpy not available.')
    import itk
    # This is a Mapping from numpy array types to itk pixel types.
    _np_itk = {numpy.uint8:itk.UC,
                numpy.uint16:itk.US,
                numpy.uint32:itk.UI,
                numpy.uint64:itk.UL,
                numpy.int8:itk.SC,
                numpy.int16:itk.SS,
                numpy.int32:itk.SI,
                numpy.int64:itk.SL,
                numpy.float32:itk.F,
                numpy.float64:itk.D,
                numpy.complex64:itk.complex[itk.F],
                numpy.complex128:itk.complex[itk.D]
                }
    try:
        return _np_itk[numpy_array_type.dtype.type]
    except KeyError as e:
        for key in _np_itk:
            if numpy.issubdtype(numpy_array_type.dtype.type, key):
                return _np_itk[key]
            raise e

def _GetArrayFromImage(image_or_filter, function, keep_axes, update):
    """Get an Array with the content of the image buffer
    """
    # Check for numpy
    if not HAVE_NUMPY:
        raise ImportError('Numpy not available.')
    # Finds the image type
    import itk
    keys = [k for k in itk.PyBuffer.keys() if k[0] == output(image_or_filter).__class__]
    if len(keys ) == 0:
        raise RuntimeError("No suitable template parameter can be found.")
    ImageType = keys[0]
    # Create a numpy array of the type of the input image
    templatedFunction = getattr(itk.PyBuffer[keys[0]], function)
    return templatedFunction(output(image_or_filter), keep_axes, update)

def GetArrayFromImage(image_or_filter, keep_axes=False, update=True):
    """Get an array with the content of the image buffer
    """
    return _GetArrayFromImage(image_or_filter, "GetArrayFromImage", keep_axes, update)

array_from_image = GetArrayFromImage

def GetArrayViewFromImage(image_or_filter, keep_axes=False, update=True):
    """Get an array view with the content of the image buffer
    """
    return _GetArrayFromImage(image_or_filter, "GetArrayViewFromImage", keep_axes, update)

array_view_from_image = GetArrayViewFromImage

def _GetImageFromArray(arr, function, is_vector):
    """Get an ITK image from a Python array.
    """
    if not HAVE_NUMPY:
        raise ImportError('Numpy not available.')
    import itk
    PixelType = _get_itk_pixelid(arr)
    if is_vector:
        Dimension = arr.ndim - 1
        if arr.flags['C_CONTIGUOUS']:
            VectorDimension = arr.shape[-1]
        else:
            VectorDimension = arr.shape[0]
        if PixelType == itk.UC:
            if VectorDimension == 3:
                ImageType = itk.Image[ itk.RGBPixel[itk.UC], Dimension ]
            elif VectorDimension == 4:
                ImageType = itk.Image[ itk.RGBAPixel[itk.UC], Dimension ]
        else:
            ImageType = itk.Image[ itk.Vector[PixelType, VectorDimension] , Dimension]
    else:
        Dimension = arr.ndim
        ImageType = itk.Image[PixelType, Dimension]
    templatedFunction = getattr(itk.PyBuffer[ImageType], function)
    return templatedFunction(arr, is_vector)

def GetImageFromArray(arr, is_vector=False):
    """Get an ITK image from a Python array.
    """
    return _GetImageFromArray(arr, "GetImageFromArray", is_vector)

image_from_array = GetImageFromArray

def GetImageViewFromArray(arr, is_vector=False):
    """Get an ITK image view from a Python array.
    """
    return _GetImageFromArray(arr, "GetImageViewFromArray", is_vector)

image_view_from_array = GetImageFromArray

def _GetArrayFromVnlObject(vnl_object, function):
    """Get an array with the content of vnl_object
    """
    # Check for numpy
    if not HAVE_NUMPY:
        raise ImportError('Numpy not available.')
    # Finds the vnl object type
    import itk
    PixelType = itk.template(vnl_object)[1][0]
    keys = [k for k in itk.PyVnl.keys() if k[0] == PixelType]
    if len(keys ) == 0:
        raise RuntimeError("No suitable template parameter can be found.")
    # Create a numpy array of the type of the vnl object
    templatedFunction = getattr(itk.PyVnl[keys[0]], function)
    return templatedFunction(vnl_object)

def GetArrayFromVnlVector(vnl_vector):
    """Get an array with the content of vnl_vector
    """
    return _GetArrayFromVnlObject(vnl_vector, "GetArrayFromVnlVector")

array_from_vnl_vector = GetArrayFromVnlVector

def GetArrayViewFromVnlVector(vnl_vector):
    """Get an array view of vnl_vector
    """
    return _GetArrayFromVnlObject(vnl_vector, "GetArrayViewFromVnlVector")

array_view_from_vnl_vector = GetArrayFromVnlVector

def GetArrayFromVnlMatrix(vnl_matrix):
    """Get an array with the content of vnl_matrix
    """
    return _GetArrayFromVnlObject(vnl_matrix, "GetArrayFromVnlMatrix")

def GetArrayViewFromVnlMatrix(vnl_matrix):
    """Get an array view of vnl_matrix
    """
    return _GetArrayFromVnlObject(vnl_matrix, "GetArrayViewFromVnlMatrix")

array_from_vnl_matrix = GetArrayFromVnlMatrix

def _GetVnlObjectFromArray(arr, function):
    """Get a vnl object from a Python array.
    """
    if not HAVE_NUMPY:
        raise ImportError('Numpy not available.')
    import itk
    PixelType = _get_itk_pixelid(arr)
    templatedFunction = getattr(itk.PyVnl[PixelType], function)
    return templatedFunction(arr)

def GetVnlVectorFromArray(arr):
    """Get a vnl vector from a Python array.
    """
    return _GetVnlObjectFromArray(arr, "GetVnlVectorFromArray")

vnl_vector_from_array = GetVnlVectorFromArray

def GetVnlMatrixFromArray(arr):
    """Get a vnl matrix from a Python array.
    """
    return _GetVnlObjectFromArray(arr, "GetVnlMatrixFromArray")

vnl_matrix_from_array = GetVnlMatrixFromArray

# return an image
from itkTemplate import image, output

def template(cl):
    """Return the template of a class (or of the class of an object) and
    its parameters

    template() returns a tuple with 2 elements:
        - the first one is the itkTemplate object
        - the second is a tuple containing the template parameters
    """
    from itkTemplate import itkTemplate
    return itkTemplate.__class_to_template__[class_(cl)]

def ctype(s):
    """Return the c type corresponding to the string passed in parameter

    The string can contain some extra spaces.
    see also itkCType
    """
    from itkTypes import itkCType

    ret = itkCType.GetCType(" ".join(s.split()))
    if ret is None:
        raise KeyError("Unrecognized C type '%s'" % s)
    return ret

def class_(obj):
    """Return a class from an object

    Often in itk, the __class__ is not what the user is expecting.
    class_() should do a better job
    """
    import inspect
    if inspect.isclass(obj):
        # obj is already a class !
        return obj
    else:
        return obj.__class__

def range(image_or_filter):
    """Return the range of values in a image of in the output image of a filter

    The minimum and maximum values are returned in a tuple: (min, max)
    range() take care of updating the pipeline
    """
    import itk
    img = output(image_or_filter)
    img.UpdateOutputInformation()
    img.Update()
    # don't put that calculator in the automatic pipeline
    tmp_auto_pipeline = auto_pipeline.current
    auto_pipeline.current = None
    comp = itk.MinimumMaximumImageCalculator[img].New(Image=img)
    auto_pipeline.current = tmp_auto_pipeline
    comp.Compute()
    return (comp.GetMinimum(), comp.GetMaximum())

def imwrite(image_or_filter, filename, compression=False):
    """Write a image or the output image of a filter to a file.

    The writer is instantiated with the image type of the image in
    parameter (or, again, with the output image of the filter in parameter).
    """
    import itk
    img = output(image_or_filter)
    img.UpdateOutputInformation()
    # don't put that writer in the automatic pipeline
    tmp_auto_pipeline = auto_pipeline.current
    auto_pipeline.current = None
    writer = itk.ImageFileWriter[img].New(
        Input=img,
        FileName=filename,
        UseCompression=compression)
    auto_pipeline.current = tmp_auto_pipeline
    writer.Update()

def imread(filename, pixel_type=None):
    """Read an image from a file or series of files and return an itk.Image.

    The reader is instantiated with the image type of the image file if
    `pixel_type` is not provided (default). The dimension of the image is
    automatically found. If the given filename is a list or a tuple, the
    reader will use an itk.ImageSeriesReader object to read the files.
    """
    import itk
    if type(filename) in [list, tuple]:
        TemplateReaderType=itk.ImageSeriesReader
        io_filename=filename[0]
        increase_dimension=True
        kwargs={'FileNames':filename}
    else:
        TemplateReaderType=itk.ImageFileReader
        io_filename=filename
        increase_dimension=False
        kwargs={'FileName':filename}
    if pixel_type:
        imageIO = itk.ImageIOFactory.CreateImageIO(io_filename, itk.ImageIOFactory.ReadMode)
        if not imageIO:
            raise RuntimeError("No ImageIO is registered to handle the given file.")
        imageIO.SetFileName(io_filename)
        imageIO.ReadImageInformation()
        dimension = imageIO.GetNumberOfDimensions()
        # Increase dimension if last dimension is not of size one.
        if increase_dimension and imageIO.GetDimensions(dimension-1) != 1:
            dimension += 1
        ImageType=itk.Image[pixel_type,dimension]
        reader = TemplateReaderType[ImageType].New(**kwargs)
    else:
        reader = TemplateReaderType.New(**kwargs)
    reader.Update()
    return reader.GetOutput()

def search(s, case_sensitive=False):  # , fuzzy=True):
    """Search for a class name in the itk module.
    """
    s = s.replace(" ", "")
    if not case_sensitive:
        s = s.lower()
    import itk
    names = sorted(dir(itk))
    # exact match first
    if case_sensitive:
        res = [n for n in names if s == n]
    else:
        res = [n for n in names if s == n.lower()]
    # then exact match inside the name
    if case_sensitive:
        res += [n for n in names if s in n and s != n]
    else:
        res += [n for n in names if s in n.lower() and s != n.lower()]
#     if fuzzy:
#         try:
# everything now requires editdist
#             import editdist
#             if case_sensitive:
#                 res.sort(key=lambda x: editdist.distance(x, s))
#             else:
#                 res.sort(key=lambda x: (editdist.distance(x.lower(), s), x))
#         except:
#             pass
    return res

# Helpers for set_inputs snake case to CamelCase keyword argument conversion
_snake_underscore_re = re.compile('(_)([a-z0-9A-Z])')
def _underscore_upper(matchobj):
    return matchobj.group(2).upper()
def _snake_to_camel(keyword):
    camel = keyword[0].upper()
    if _snake_underscore_re.search(keyword[1:]):
        return camel + _snake_underscore_re.sub(_underscore_upper, keyword[1:])
    return camel + keyword[1:]

def set_inputs(new_itk_object, args=[], kargs={}):
    """Set the inputs of the given objects, according to the non named or the
    named parameters in args and kargs

    This function tries to assign all the non named parameters in the input of
    the new_itk_object
    - the first non named parameter in the first input, etc.

    The named parameters are used by calling the method with the same name
    prefixed by 'Set'.
    set_inputs( obj, kargs={'Threshold': 10} ) calls obj.SetThreshold(10)

    This is the function use in the enhanced New() method to manage the inputs.
    It can be used to produce a similar behavior:

    def SetInputs(self, *args, **kargs):
        import itk
        itk.set_inputs(self, *args, **kargs)
    """
    # try to get the images from the filters in args
    args = [output(arg) for arg in args]

    # args without name are filter used to set input image
    #
    # count SetInput calls to call SetInput, SetInput2, SetInput3, ...
    # useful with filter which take 2 input (or more) like SubtractImageFiler
    # Ex: subtract image2.png to image1.png and save the result in result.png
    # r1 = itk.ImageFileReader.US2.New(FileName='image1.png')
    # r2 = itk.ImageFileReader.US2.New(FileName='image2.png')
    # s = itk.SubtractImageFilter.US2US2US2.New(r1, r2)
    # itk.ImageFileWriter.US2.New(s, FileName='result.png').Update()
    try:
        for setInputNb, arg in enumerate(args):
            methodName = 'SetInput%i' % (setInputNb + 1)
            if methodName in dir(new_itk_object):
                # first try to use methods called SetInput1, SetInput2, ...
                # those method should have more chances to work in case of
                # multiple input types
                getattr(new_itk_object, methodName)(arg)
            else:
                # no method called SetInput?
                # try with the standard SetInput(nb, input)
                new_itk_object.SetInput(setInputNb, arg)
    except TypeError as e:
        # the exception have (at least) to possible reasons:
        # + the filter don't take the input number as first argument
        # + arg is an object of wrong type
        #
        # if it's not the first input, re-raise the exception
        if setInputNb != 0:
            raise e
        # it's the first input, try to use the SetInput() method without input
        # number
        new_itk_object.SetInput(args[0])
        # but raise an exception if there is more than 1 argument
        if len(args) > 1:
            raise TypeError('Object accept only 1 input.')
    except AttributeError:
        # There is no SetInput() method, try SetImage
        # but before, check the number of inputs
        if len(args) > 1:
            raise TypeError('Object accept only 1 input.')
        methodList = ['SetImage', 'SetInputImage']
        methodName = None
        for m in methodList:
            if m in dir(new_itk_object):
                methodName = m
        if methodName:
            getattr(new_itk_object, methodName)(args[0])
        else:
            raise AttributeError('No method found to set the input.')

    # named args : name is the function name, value is argument(s)
    for attribName, value in kargs.items():
        # use Set as prefix. It allow to use a shorter and more intuitive
        # call (Ex: itk.ImageFileReader.UC2.New(FileName='image.png')) than
        # with the full name
        # (Ex: itk.ImageFileReader.UC2.New(SetFileName='image.png'))
        if attribName not in ["auto_progress", "template_parameters"]:
            if attribName.islower():
                attribName = _snake_to_camel(attribName)
            attrib = getattr(new_itk_object, 'Set' + attribName)

           # Do not use try-except mechanism as this leads to
            # segfaults. Instead limit the number of types that are
            # tested. The list of tested type could maybe be replaced by
            # a test that would check for iterables.
            if type(value) in [list, tuple]:
                try:
                    output_value = [output(x) for x in value]
                    attrib(*output_value)
                except:
                    attrib(output(value))
            else:
                attrib(output(value))

class templated_class:

    """This class is used to mimic the behavior of the templated C++ classes.

    It is used this way:

    class CustomClass:
        # class definition here
    CustomClass = templated_class(CustomClass)

    customObject = CustomClass[template, parameters].New()

    The template parameters are passed to the custom class constructor as a
    named parameter 'template_parameters' in a tuple.

    The custom class may implement a static method
    check_template_parameters(parameters) which should raise an exception if
    the template parameters provided are not suitable to instantiate the custom
    class.
    """

    def __init__(self, cls):
        """cls is the custom class
        """
        self.__cls__ = cls
        self.__templates__ = {}

    def New(self, *args, **kargs):
        """Use the parameters to infer the types of the template parameters.
        """
        # extract the types from the arguments to instantiate the class
        import itk
        types = tuple(itk.class_(o) for o in args)
        return self[types].New(*args, **kargs)

    def __getitem__(self, template_parameters):
        """Return a pair class-template parameters ready to be instantiated.

        The template parameters may be validated if the custom class provide
        the static method check_template_parameters(parameters).
        """
        if not isinstance(template_parameters, tuple):
            template_parameters = (template_parameters,)
        return (
            templated_class.__templated_class_and_parameters__(
                self,
                template_parameters)
        )

    def check_template_parameters(self, template_parameters):
        """Check the template parameters passed in parameter.
        """
        # this method is there mainly to make possible to reuse it in the
        # custom class constructor after having used templated_class().
        # Without that, the following example doesn't work:
        #
        # class CustomClass:
        #     def __init__(self, *args, **kargs):
        #         template_parameters = kargs["template_parameters"]
        #         CustomClass.check_template_parameters(template_parameters)
        # other init stuff
        #     def check_template_parameters(template_parameters):
        # check, really
        #         pass
        #    CustomClass = templated_class(CustomClass)
        #
        self.__cls__.check_template_parameters(template_parameters)

    def add_template(self, name, params):
        if not isinstance(params, list) and not isinstance(params, tuple):
            params = (params,)
        params = tuple(params)
        val = self[params]
        self.__templates__[params] = val
        setattr(self, name, val)

    def add_image_templates(self, *args):
        import itk
        if args == []:
            return
        combinations = [[t] for t in args[0]]
        for types in args[1:]:
            temp = []
            for t in types:
                for c in combinations:
                    temp.append(c + [t])
            combinations = temp
        for d in itk.DIMS:
            for c in combinations:
                parameters = []
                name = ""
                for t in c:
                    parameters.append(itk.Image[t, d])
                    name += "I" + t.short_name + str(d)
                self.add_template(name, tuple(parameters))

    class __templated_class_and_parameters__:

        """Inner class used to store the pair class-template parameters ready
        to instantiate.
        """

        def __init__(self, templated_class, template_parameters):
            self.__templated_class__ = templated_class
            self.__template_parameters__ = template_parameters
            if "check_template_parameters" in dir(templated_class.__cls__):
                templated_class.__cls__.check_template_parameters(
                    template_parameters)

        def New(self, *args, **kargs):
            """A New() method to mimic the ITK default behavior, even if the
            class doesn't provide any New() method.
            """
            kargs["template_parameters"] = self.__template_parameters__
            if "New" in dir(self.__templated_class__.__cls__):
                obj = self.__templated_class__.__cls__.New(*args, **kargs)
            else:
                obj = self.__templated_class__.__cls__(*args, **kargs)
            setattr(
                obj,
                "__template_parameters__",
                self.__template_parameters__)
            setattr(obj, "__templated_class__", self.__templated_class__)
            return obj

        def __call__(self, *args, **kargs):
            return self.New(*args, **kargs)

    def keys(self):
        return self.__templates__.keys()

    # everything after this comment is for dict interface
    # and is a copy/paste from DictMixin
    # only methods to edit dictionary are not there
    def __iter__(self):
        for k in self.keys():
            yield k

    def has_key(self, key):
        try:
            value = self[key]
        except KeyError:
            return False
        return True

    def __contains__(self, key):
        return key in self

    # third level takes advantage of second level definitions
    def iteritems(self):
        for k in self:
            yield (k, self[k])

    def iterkeys(self):
        return self.__iter__()

    # fourth level uses definitions from lower levels
    def itervalues(self):
        for _, v in self.iteritems():
            yield v

    def values(self):
        return [v for _, v in self.iteritems()]

    def items(self):
        return list(self.iteritems())

    def get(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            return default

    def __len__(self):
        return len(self.keys())

class pipeline:

    """A convenient class to store the reference to the filters of a pipeline

    With this class, a method can create a pipeline of several filters and
    return it without losing the references to the filters in this pipeline.
    The pipeline object act almost like a filter (it has a GetOutput() method)
    and thus can be simply integrated in another pipeline.
    """

    def __init__(self, *args, **kargs):
        self.clear()
        self.input = None
        set_inputs(self, args, kargs)

    def connect(self, filter):
        """Connect a new filter to the pipeline

        The output of the first filter will be used as the input of this
        one and the filter passed as parameter will be added to the list
        """
        if self.GetOutput() is not None:
            set_inputs(filter, [self.GetOutput()])
        self.append(filter)

    def append(self, filter):
        """Add a new filter to the pipeline

        The new filter will not be connected. The user must connect it.
        """
        self.filters.append(filter)

    def clear(self):
        """Clear the filter list
        """
        self.filters = []

    def GetOutput(self, index=0):
        """Return the output of the pipeline

        If another output is needed, use
        pipeline.filters[-1].GetAnotherOutput() instead of this method,
        subclass pipeline to implement another GetOutput() method, or use
        expose()
        """
        if len(self.filters) == 0:
            return self.GetInput()
        else:
            filter = self.filters[-1]
            if hasattr(filter, "__getitem__"):
                return filter[index]
            try:
                return filter.GetOutput(index)
            except:
                if index == 0:
                    return filter.GetOutput()
                else:
                    raise ValueError("Index can only be 0 on that object")

    def SetInput(self, input):
        """Set the input of the pipeline
        """
        if len(self.filters) != 0:
            set_inputs(self.filters[0], [input])
        self.input = input

    def GetInput(self):
        """Get the input of the pipeline
        """
        return self.input

    def Update(self):
        """Update the pipeline
        """
        if len(self.filters) > 0:
            return self.filters[-1].Update()

    def UpdateLargestPossibleRegion(self):
        """Update the pipeline
        """
        if len(self.filters) > 0:
            return self.filters[-1].UpdateLargestPossibleRegion()

    def UpdateOutputInformation(self):
        if "UpdateOutputInformation" in dir(self.filters[-1]):
            self.filters[-1].UpdateOutputInformation()
        else:
            self.Update()

    def __len__(self):
        if len(self.filters) == 0:
            return 1
        else:
            return self.filters[-1].GetNumberOfOutputs()

    def __getitem__(self, item):
        return self.GetOutput(item)

    def __call__(self, *args, **kargs):
        set_inputs(self, args, kargs)
        self.UpdateLargestPossibleRegion()
        return self

    def expose(self, name, new_name=None, position=-1):
        """Expose an attribute from a filter of the minipeline.

        Once called, the pipeline instance has a new Set/Get set of methods to
        access directly the corresponding method of one of the filter of the
        pipeline.
        Ex: p.expose( "Radius" )
                p.SetRadius( 5 )
                p.GetRadius( 5 )
        By default, the attribute usable on the pipeline instance has the same
        name than the one of the filter, but it can be changed by providing a
        value to new_name.
        The last filter of the pipeline is used by default, but another one may
        be used by giving its position.
        Ex: p.expose("Radius", "SmoothingNeighborhood", 2)
            p.GetSmoothingNeighborhood()
        """
        if new_name is None:
            new_name = name
        src = self.filters[position]
        ok = False
        set_name = "Set" + name
        if set_name in dir(src):
            setattr(self, "Set" + new_name, getattr(src, set_name))
            ok = True
        get_name = "Get" + name
        if get_name in dir(src):
            setattr(self, "Get" + new_name, getattr(src, get_name))
            ok = True
        if not ok:
            raise RuntimeError(
                "No attribute %s at position %s." %
                (name, position))

class auto_pipeline(pipeline):
    current = None

    def __init__(self, *args, **kargs):
        pipeline.__init__(self, *args, **kargs)
        self.Start()

    def Start(self):
        auto_pipeline.current = self

    def Stop(self):
        auto_pipeline.current = None

def down_cast(obj):
    """Down cast an itkLightObject (or a object of a subclass) to its most
    specialized type.
    """
    import itk
    import itkTemplate
    className = obj.GetNameOfClass()
    t = getattr(itk, className)
    if isinstance(t, itkTemplate.itkTemplate):
        for c in t.values():
            try:
                return c.cast(obj)
            except:
                # fail silently for now
                pass
        raise RuntimeError(
            "Can't downcast to a specialization of %s" %
            className)
    else:
        return t.cast(obj)

def attribute_list(i, name):
    """Returns a list of the specified attributes for the objects in the image.

    i: the input LabelImage
    name: the attribute name
    """
    import itk
    i = itk.output(i)
    relabel = itk.StatisticsRelabelLabelMapFilter[i].New(
        i,
        Attribute=name,
        ReverseOrdering=True,
        InPlace=False)
    relabel.UpdateLargestPossibleRegion()
    r = relabel.GetOutput()
    l = []
    for i in range(1, r.GetNumberOfLabelObjects() + 1):
        l.append(r.GetLabelObject(i).__getattribute__("Get" + name)())
    return l

def attributes_list(i, names):
    """Returns a list of the specified attributes for the objects in the image.

    i: the input LabelImage
    name: the attribute name
    """
    import itk
    i = itk.output(i)
    relabel = itk.StatisticsRelabelLabelMapFilter[i].New(
        i,
        Attribute=names[0],
        ReverseOrdering=True,
        InPlace=False)
    relabel.UpdateLargestPossibleRegion()
    r = relabel.GetOutput()
    l = []
    for i in range(1, r.GetNumberOfLabelObjects() + 1):
        attrs = []
        for name in names:
            attrs.append(r.GetLabelObject(i).__getattribute__("Get" + name)())
        l.append(tuple(attrs))
    return l

def attribute_dict(i, name):
    """Returns a dict with the attribute values in keys and a list of the
    corresponding objects in value

    i: the input LabelImage
    name: the name of the attribute
    """
    import itk
    i = itk.output(i)
    relabel = itk.StatisticsRelabelLabelMapFilter[i].New(
        i,
        Attribute=name,
        ReverseOrdering=True,
        InPlace=False)
    relabel.UpdateLargestPossibleRegion()
    r = relabel.GetOutput()
    d = {}
    for i in range(1, r.GetNumberOfLabelObjects() + 1):
        lo = r.GetLabelObject(i)
        v = lo.__getattribute__("Get" + name)()
        l = d.get(v, [])
        l.append(lo)
        d[v] = l
    return d

def number_of_objects(i):
    """Returns the number of objets in the image.

    i: the input LabelImage
    """
    import itk
    i.UpdateLargestPossibleRegion()
    i = itk.output(i)
    return i.GetNumberOfLabelObjects()

def ipython_kw_matches(text):
    """Match named ITK object's named parameters"""
    import IPython
    import itk
    import re
    import inspect
    import itkTemplate
    regexp = re.compile(r'''
                    '.*?' |  # single quoted strings or
                    ".*?" |  # double quoted strings or
                    \w+     |  # identifier
                    \S  # other characters
                    ''', re.VERBOSE | re.DOTALL)
    ip = IPython.get_ipython()
    if "." in text:  # a parameter cannot be dotted
        return []
    # 1. Find the nearest identifier that comes before an unclosed
    # parenthesis e.g. for "foo (1+bar(x), pa", the candidate is "foo".
    if ip.Completer.readline:
        textUntilCursor = ip.Completer.readline.get_line_buffer()[:ip.Completer.readline.get_endidx()]
    else:
        # IPython >= 5.0.0, which is based on the Python Prompt Toolkit
        textUntilCursor = ip.Completer.text_until_cursor

    tokens = regexp.findall(textUntilCursor)
    tokens.reverse()
    iterTokens = iter(tokens)
    openPar = 0
    for token in iterTokens:
        if token == ')':
            openPar -= 1
        elif token == '(':
            openPar += 1
            if openPar > 0:
                # found the last unclosed parenthesis
                break
    else:
        return []
    # 2. Concatenate dotted names ("foo.bar" for "foo.bar(x, pa" )
    ids = []
    isId = re.compile(r'\w+$').match
    while True:
        try:
            ids.append(iterTokens.next())
            if not isId(ids[-1]):
                ids.pop()
                break
            if not iterTokens.next() == '.':
                break
        except StopIteration:
            break
    # lookup the candidate callable matches either using global_matches
    # or attr_matches for dotted names
    if len(ids) == 1:
        callableMatches = ip.Completer.global_matches(ids[0])
    else:
        callableMatches = ip.Completer.attr_matches('.'.join(ids[::-1]))
    argMatches = []
    for callableMatch in callableMatches:
        # drop the .New at this end, so we can search in the class members
        if callableMatch.endswith(".New"):
            callableMatch = callableMatch[:-4]
        elif not re.findall('([A-Z])', callableMatch):  # True if snake case
            # Split at the last '.' occurence
            splitted = callableMatch.split('.')
            namespace = splitted[:-1]
            function_name = splitted[-1]
            # Find corresponding object name
            object_name = _snake_to_camel(function_name)
            # Check that this object actually exists
            try:
                objectCallableMatch = ".".join(namespace + [object_name])
                eval(objectCallableMatch, ip.Completer.namespace)
                # Reconstruct full object name
                callableMatch = objectCallableMatch
            except AttributeError:
                # callableMatch is not a snake case function with a
                # corresponding object.
                pass
        try:
            object = eval(callableMatch, ip.Completer.namespace)
            if isinstance(object, itkTemplate.itkTemplate):
                # this is a template - lets grab the first entry to search for
                # the methods
                object = object.values()[0]
            namedArgs = []
            isin = isinstance(object, itk.LightObject)
            if inspect.isclass(object):
                issub = issubclass(object, itk.LightObject)
            if isin or (inspect.isclass(object) and issub):
                namedArgs = [n[3:] for n in dir(object) if n.startswith("Set")]
        except Exception as e:
            print(e)
            continue
        for namedArg in namedArgs:
            if namedArg.startswith(text):
                argMatches.append(u"%s=" % namedArg)
    return argMatches

# install progress callback and custom completer if we are in ipython
# interpreter
try:
    import itkConfig
    import IPython
    if IPython.get_ipython():
        IPython.get_ipython().Completer.matchers.insert(0, ipython_kw_matches)
    # some cleanup
    del itkConfig, IPython
except (ImportError, AttributeError):
    # fail silently
    pass

redpajama_set_name: RedPajamaGithub