Peak finder

#ifndef PARTITION_HPP
#define PARTITION_HPP

#ifdef __GNUG__
#pragma interface
#endif

#include <boost/iterator/iterator_facade.hpp>
#include <boost/type_traits/is_convertible.hpp>

#include <type_traits>
#include <utility>
#include <functional>
#include <memory>

#define PARTITION_CHECK_IS_ITERATOR_CONVERTIBLE

namespace msa
{

namespace details
{

template < class I, bool valley, bool peak, bool plain, class O >
class partition_iterator_base
        : public boost::iterator_facade<
        partition_iterator_base< I, valley, peak, plain, O >
        , I
        , boost::forward_traversal_tag
        , typename I::reference
        , typename I::difference_type
        >
{

    struct enabler {}; // a private type avoids misuse

    template< class I_, bool valley_, bool peak_, bool plain_ >
    using other_partition_iterator_base = partition_iterator_base< I_, valley_, peak_, plain_, O >;

    //template< class I_, bool valley_, bool peak_, bool plain_ > friend class other_partition_iterator_base;

public :

    ~partition_iterator_base() noexcept = default;

    explicit
    partition_iterator_base(O o_ = O())
        : o(o_)
        , prev()
        , next()
        , invalid()
    { ; }

    template< class I_ >
    explicit
    partition_iterator_base(
            I_ const begin, I_ const end, O o_ = O()
        #if !defined(BOOST_NO_SFINAE) && defined(PARTITION_CHECK_IS_ITERATOR_CONVERTIBLE)
            , typename std::enable_if< std::is_convertible< I_, I >::value, enabler >::type = enabler()
        #endif
            )
        : o(o_)
        , prev(begin)
        , next(begin)
        , invalid(end)
    { ; }

    template< class container >
    explicit
    partition_iterator_base(
            container & container_, O o_ = O()
        #if !defined(BOOST_NO_SFINAE) && defined(PARTITION_CHECK_IS_ITERATOR_CONVERTIBLE)
            , typename std::enable_if< std::is_convertible< typename std::conditional< std::is_const< container >::value, typename container::const_iterator, typename container::iterator >::type, I >::value, enabler >::type = enabler()
        #endif
            )
        : o(o_)
        , prev(container_.begin())
        , next(container_.begin())
        , invalid(container_.end())
    { ; }

    template < class I_, bool valley_, bool peak_, bool plain_ >
    partition_iterator_base(
            other_partition_iterator_base< I_, valley_, peak_, plain_ > const & other
        #if !defined(BOOST_NO_SFINAE) && defined(PARTITION_CHECK_IS_ITERATOR_CONVERTIBLE)
            , typename std::enable_if< std::is_convertible< I_, I >::value, enabler >::type = enabler()
        #endif
            )
        : o(other.o)
        , prev(other.prev)
        , next(other.next)
        , invalid(other.invalid)
    { ; }

    template < class I_, bool valley_, bool peak_, bool plain_ >
    partition_iterator_base(
            other_partition_iterator_base< I_, valley_, peak_, plain_ > && other
        #if !defined(BOOST_NO_SFINAE) && defined(PARTITION_CHECK_IS_ITERATOR_CONVERTIBLE)
            , typename std::enable_if< std::is_convertible< I_, I >::value, enabler >::type = enabler()
        #endif
            )
        : partition_iterator_base(std::move(other.o))
    {
        this->swap(other);
    }

    template < class I_, bool valley_, bool peak_, bool plain_ >
    partition_iterator_base & operator = (
            other_partition_iterator_base< I_, valley_, peak_, plain_ > other
        #if !defined(BOOST_NO_SFINAE) && defined(PARTITION_CHECK_IS_ITERATOR_CONVERTIBLE)
            // defenseless poor thing
        #endif
            ) noexcept
    {
        this->swap(other);
        return *this;
    }


    template < class I_, bool valley_, bool peak_, bool plain_ >
    friend
    void swap(
            partition_iterator_base & lhs
            , other_partition_iterator_base< I_, valley_, peak_, plain_ > & rhs
        #if !defined(BOOST_NO_SFINAE) && defined(PARTITION_CHECK_IS_ITERATOR_CONVERTIBLE)
            , typename boost::detail::enable_if_interoperable< I_, I, enabler >::type = enabler()
        #endif
            ) noexcept
    {
        lhs.swap(rhs);
    }

private :

    friend class boost::iterator_core_access;

    template< class I_, bool valley_, bool peak_, bool plain_ >
    bool equal(
            other_partition_iterator_base< I_, valley_, peak_, plain_ > const & other
        #if !defined(BOOST_NO_SFINAE) && defined(PARTITION_CHECK_IS_ITERATOR_CONVERTIBLE)
            , typename boost::detail::enable_if_interoperable< I_, I, enabler >::type = enabler()
        #endif
            ) const
    {
        return ((prev == other.prev) || ((prev == invalid) && (other.prev == other.invalid)));
    }

    void increment()
    {
        I curr(next);
        if (next != invalid) {
            while (++next != invalid) {
                bool const pc(o(*prev, *curr));
                bool const cp(o(*curr, *prev));
                bool const nc(o(*next, *curr));
                bool const cn(o(*curr, *next));
                if (plain) { // plains borders
                    if ((pc || cp) != (nc || cn)) { // xor: http://stackoverflow.com/questions/1596668
                        break;
                    }
                }
                if (cp && cn) {
                    if (valley) {
                        break;
                    } else {
                        prev = curr;
                    }
                } else if (pc && nc) {
                    if (peak) {
                        break;
                    } else {
                        prev = curr;
                    }
                }
                curr = next;
            }
        }
        prev = curr;
    }

    typename I::reference dereference() const
    {
        return *prev;
    }

private :

    O o;

    I prev;
    I next;
    I invalid;

    template < class I_, bool valley_, bool peak_, bool plain_ >
    void swap(
            other_partition_iterator_base< I_, valley_, peak_, plain_ > & other
        #if !defined(BOOST_NO_SFINAE) && defined(PARTITION_CHECK_IS_ITERATOR_CONVERTIBLE)
            , typename boost::detail::enable_if_interoperable< I_, I, enabler >::type = enabler()
        #endif
            ) noexcept
    {
        using std::swap;
        swap(prev, other.prev);
        swap(next, other.next);
        swap(invalid, other.invalid);
    }

};

template < class container, bool valley, bool peak, bool plain, class O = std::less< typename container::value_type > const >
using partition_iterator = partition_iterator_base< typename container::iterator, valley, peak, plain, O >;
template < class container, bool valley, bool peak, bool plain, class O = std::less< typename container::value_type > const >
using const_partition_iterator = partition_iterator_base< typename container::const_iterator, valley, peak, plain, O >;

template< class container, class O = std::less< typename container::value_type > const >
using peak_iterator = partition_iterator< container, true, false, false, O >;
template< class container, class O = std::less< typename container::value_type > const >
using const_peak_iterator = const_partition_iterator< container, true, false, false, O >;

} // namespace mas::details

using details::partition_iterator;
using details::const_partition_iterator;

using details::peak_iterator;
using details::const_peak_iterator;

} // namespace msa

#endif // PARTITION_HPP