Header file range/v3/utility/iterator_concepts.hpp

#include <meta/meta.hpp>

#include <range/v3/utility/move.hpp>

#include <range/v3/utility/swap.hpp>

#include <range/v3/utility/concepts.hpp>

#include <range/v3/utility/functional.hpp>

#include <range/v3/utility/associated_types.hpp>

#include <range/v3/utility/nullptr_v.hpp>

namespace ranges
{
    inline namespace v3
    {
        struct input_iterator_tag;
        
        struct forward_iterator_tag
        : ranges::v3::input_iterator_tag
        {};
        
        struct bidirectional_iterator_tag
        : ranges::v3::forward_iterator_tag
        {};
        
        struct random_access_iterator_tag
        : ranges::v3::bidirectional_iterator_tag
        {};
        
        namespace detail
        {
            template <typename T>
            T upgrade_iterator_category_(T*, void*);
            
            template <typename T>
            ranges::input_iterator_tag upgrade_iterator_category_(T*, std::input_iterator_tag*);
            
            template <typename T>
            ranges::forward_iterator_tag upgrade_iterator_category_(T*, std::forward_iterator_tag*);
            
            template <typename T>
            ranges::bidirectional_iterator_tag upgrade_iterator_category_(T*, std::bidirectional_iterator_tag*);
            
            template <typename T>
            ranges::random_access_iterator_tag upgrade_iterator_category_(T*, std::random_access_iterator_tag*);
            
            template <typename T>
            struct upgrade_iterator_category
            {
                using type = decltype(detail::upgrade_iterator_category_(_nullptr_v<T>(), _nullptr_v<T>()));
            };
            
            template <typename T, typename B>
            meta::nil_ downgrade_iterator_category_(T*, void*, B);
            
            template <typename T, typename B>
            meta::id<T> downgrade_iterator_category_(T*, std::input_iterator_tag*, B);
            
            template <typename T, typename B>
            meta::id<T> downgrade_iterator_category_(T*, std::output_iterator_tag*, B);
            
            template <typename T, typename B>
            meta::id<std::input_iterator_tag> downgrade_iterator_category_(T*, ranges::input_iterator_tag*, B);
            
            template <typename T>
            meta::id<std::forward_iterator_tag> downgrade_iterator_category_(T*, ranges::forward_iterator_tag*, std::true_type);
            
            template <typename T>
            meta::id<std::bidirectional_iterator_tag> downgrade_iterator_category_(T*, ranges::bidirectional_iterator_tag*, std::true_type);
            
            template <typename T>
            meta::id<std::random_access_iterator_tag> downgrade_iterator_category_(T*, ranges::random_access_iterator_tag*, std::true_type);
            
            template <typename Tag, typename Reference>
            struct downgrade_iterator_category
            : decltype(detail::downgrade_iterator_category_(_nullptr_v<Tag>(), _nullptr_v<Tag>(), std::integral_constant<_Bool, std::is_reference<Reference>::value>()))
            {};
        }
        
        template <typename T, typename>
        struct iterator_category;
        
        template <typename T>
        struct iterator_category<T*>
        : meta::lazy::if_<std::is_object<T>, ranges::random_access_iterator_tag>
        {};
        
        template <typename T>
        struct iterator_category<T const>
        : iterator_category<T>
        {};
        
        template <typename T>
        struct iterator_category<T volatile>
        : iterator_category<T>
        {};
        
        template <typename T>
        struct iterator_category<T const volatile>
        : iterator_category<T>
        {};
        
        template <typename T>
        struct iterator_category<T, meta::void_<typename T::iterator_category>>
        : detail::upgrade_iterator_category<typename T::iterator_category>
        {};
        
        namespace concepts
        {
            struct Readable
            : refines<struct ranges::v3::concepts::Movable, struct ranges::v3::concepts::DefaultConstructible>
            {
                template <typename I>
                using value_t = meta::_t<value_type<I>>;
                
                template <typename I>
                using reference_t = decltype(*std::declval<I&>());
                
                template <typename I>
                using rvalue_reference_t = decltype(indirect_move(std::declval<I&>()));
                
                template <typename I>
                using common_reference_t = ranges::common_reference_t<reference_t<I>&&, value_t<I>&>;
                
                template <typename I>
                decltype(concepts::valid_expr(concepts::model_of<CommonReference, reference_t<I>&&, value_t<I>&>(), concepts::model_of<CommonReference, reference_t<I>&&, rvalue_reference_t<I>&&>(), concepts::model_of<CommonReference, rvalue_reference_t<I>&&, value_t<I>const&>(), concepts::model_of<Same, ranges::common_reference_t<reference_t<I>, value_t<I>>, value_t<I>>(), concepts::model_of<Same, ranges::common_reference_t<rvalue_reference_t<I>, value_t<I>>, value_t<I>>())) requires_(I&&);
            };
            
            struct Writable
            : refines<struct ranges::v3::concepts::Movable (_1), struct ranges::v3::concepts::DefaultConstructible (_1)>
            {
                template <typename Out, typename T>
                decltype(concepts::valid_expr(*o=val<T>())) requires_(Out&& o, T&&);
            };
            
            struct IndirectlyMovable
            {
                template <typename I, typename O>
                decltype(concepts::valid_expr(concepts::model_of<Readable, I>(), concepts::model_of<Writable, O, Readable::rvalue_reference_t<I>&&>())) requires_(I&&, O&&);
            };
            
            struct IndirectlyMovableStorable
            : refines<struct ranges::v3::concepts::IndirectlyMovable>
            {
                template <typename I, typename O>
                decltype(concepts::valid_expr(concepts::model_of<IndirectlyMovable, I, O>(), concepts::model_of<Movable, Readable::value_t<I>>(), concepts::model_of<Constructible, Readable::value_t<I>, Readable::rvalue_reference_t<I>&&>(), concepts::model_of<Assignable, Readable::value_t<I>&, Readable::rvalue_reference_t<I>&&>(), concepts::model_of<Writable, O, Readable::value_t<I>&&>())) requires_(I&&, O&&);
            };
            
            struct IndirectlyCopyable
            : refines<struct ranges::v3::concepts::IndirectlyMovable>
            {
                template <typename I, typename O>
                decltype(concepts::valid_expr(concepts::model_of<Writable, O, Readable::reference_t<I>&&>())) requires_(I&&, O&&);
            };
            
            struct IndirectlyCopyableStorable
            : refines<struct ranges::v3::concepts::IndirectlyMovableStorable, struct ranges::v3::concepts::IndirectlyCopyable>
            {
                template <typename I, typename O>
                decltype(concepts::valid_expr(concepts::model_of<Copyable, Readable::value_t<I>>(), concepts::model_of<Constructible, Readable::value_t<I>, Readable::reference_t<I>&&>(), concepts::model_of<Assignable, Readable::value_t<I>&, Readable::reference_t<I>&&>(), concepts::model_of<Writable, O, Readable::common_reference_t<I>&&>(), concepts::model_of<Writable, O, Readable::value_t<I>const&>())) requires_(I&&, O&&);
            };
            
            struct IndirectlySwappable
            {
                template <typename I1, typename I2>
                decltype(concepts::valid_expr(concepts::model_of<Readable, I1>(), concepts::model_of<Readable, I2>(), (ranges::indirect_swap(i1, i2), 42), (ranges::indirect_swap(i1, i1), 42), (ranges::indirect_swap(i2, i2), 42), (ranges::indirect_swap(i2, i1), 42))) requires_(I1&& i1, I2&& i2);
            };
            
            struct WeaklyIncrementable
            : refines<struct ranges::v3::concepts::SemiRegular>
            {
                template <typename I>
                using difference_t = meta::_t<difference_type<I>>;
                
                template <typename I>
                decltype(concepts::valid_expr(concepts::is_true(std::is_integral<difference_t<I>>{}), concepts::has_type<I&>(++i), ((void)i++, 42))) requires_(I&& i);
            };
            
            struct Incrementable
            : refines<struct ranges::v3::concepts::Regular, struct ranges::v3::concepts::WeaklyIncrementable>
            {
                template <typename I>
                decltype(concepts::valid_expr(concepts::has_type<I>(i++))) requires_(I&& i);
            };
            
            struct Iterator
            : refines<struct ranges::v3::concepts::WeaklyIncrementable, struct ranges::v3::concepts::Copyable>
            {
                template <typename I>
                decltype(concepts::valid_expr(*i)) requires_(I&& i);
            };
            
            struct Sentinel
            : refines<struct ranges::v3::concepts::SemiRegular (_1), struct ranges::v3::concepts::Iterator (_2), struct ranges::v3::concepts::WeaklyEqualityComparable>
            {};
            
            struct SizedSentinel
            : refines<struct ranges::v3::concepts::Sentinel>
            {
                template <typename S, typename I, typename D = WeaklyIncrementable::difference_t<I>>
                decltype(concepts::valid_expr(concepts::is_false(disable_sized_sentinel<uncvref_t<S>, uncvref_t<I>>()), concepts::has_type<D>(s-i), concepts::has_type<D>(i-s))) requires_(S&& s, I&& i);
            };
            
            struct OutputIterator
            : refines<struct ranges::v3::concepts::Iterator (_1), struct ranges::v3::concepts::Writable>
            {};
            
            struct InputIterator
            : refines<struct ranges::v3::concepts::Iterator, struct ranges::v3::concepts::Readable>
            {
                template <typename I>
                using category_t = meta::_t<ranges::iterator_category<I>>;
                
                template <typename I>
                decltype(concepts::valid_expr(concepts::model_of<DerivedFrom, category_t<I>, ranges::input_iterator_tag>(), concepts::model_of<Readable>(i++))) requires_(I&& i);
            };
            
            struct ForwardIterator
            : refines<struct ranges::v3::concepts::InputIterator, struct ranges::v3::concepts::Incrementable, struct ranges::v3::concepts::Sentinel (_1, _1)>
            {
                template <typename I>
                decltype(concepts::valid_expr(concepts::model_of<DerivedFrom, category_t<I>, ranges::forward_iterator_tag>())) requires_(I&&);
            };
            
            struct BidirectionalIterator
            : refines<struct ranges::v3::concepts::ForwardIterator>
            {
                template <typename I>
                decltype(concepts::valid_expr(concepts::model_of<DerivedFrom, category_t<I>, ranges::bidirectional_iterator_tag>(), concepts::has_type<I&>(--i), concepts::has_type<I>(i--), concepts::same_type(*i, *i--))) requires_(I&& i);
            };
            
            struct RandomAccessIterator
            : refines<struct ranges::v3::concepts::BidirectionalIterator, struct ranges::v3::concepts::TotallyOrdered, struct ranges::v3::concepts::SizedSentinel (_1, _1)>
            {
                template <typename I, typename V = common_reference_t<I>>
                decltype(concepts::valid_expr(concepts::model_of<DerivedFrom, category_t<I>, ranges::random_access_iterator_tag>(), concepts::has_type<I>(i+(i-i)), concepts::has_type<I>((i-i)+i), concepts::has_type<I>(i-(i-i)), concepts::has_type<I&>(i+=(i-i)), concepts::has_type<I&>(i-=(i-i)), concepts::convertible_to<V>(i[i-i]))) requires_(I&& i);
            };
        }
        
        template <typename T>
        using Readable = concepts::models<concepts::Readable, T>;
        
        template <typename Out, typename T>
        using Writable = concepts::models<concepts::Writable, Out, T>;
        
        template <typename I, typename O>
        using IndirectlyMovable = concepts::models<concepts::IndirectlyMovable, I, O>;
        
        template <typename I, typename O>
        using IndirectlyMovableStorable = concepts::models<concepts::IndirectlyMovableStorable, I, O>;
        
        template <typename I, typename O>
        using IndirectlyCopyable = concepts::models<concepts::IndirectlyCopyable, I, O>;
        
        template <typename I, typename O>
        using IndirectlyCopyableStorable = concepts::models<concepts::IndirectlyCopyableStorable, I, O>;
        
        template <typename I1, typename I2>
        using IndirectlySwappable = concepts::models<concepts::IndirectlySwappable, I1, I2>;
        
        template <typename T>
        using WeaklyIncrementable = concepts::models<concepts::WeaklyIncrementable, T>;
        
        template <typename T>
        using Incrementable = concepts::models<concepts::Incrementable, T>;
        
        template <typename I>
        using Iterator = concepts::models<concepts::Iterator, I>;
        
        template <typename S, typename I>
        using Sentinel = concepts::models<concepts::Sentinel, S, I>;
        
        template <typename S, typename I>
        using SizedSentinel = concepts::models<concepts::SizedSentinel, S, I>;
        
        template <typename I, typename S>
        using IteratorRange = Sentinel<S, I>;
        
        template <typename I, typename S>
        using SizedIteratorRange = SizedSentinel<S, I>;
        
        template <typename Out, typename T>
        using OutputIterator = concepts::models<concepts::OutputIterator, Out, T>;
        
        template <typename I>
        using InputIterator = concepts::models<concepts::InputIterator, I>;
        
        template <typename I>
        using ForwardIterator = concepts::models<concepts::ForwardIterator, I>;
        
        template <typename I>
        using BidirectionalIterator = concepts::models<concepts::BidirectionalIterator, I>;
        
        template <typename I>
        using RandomAccessIterator = concepts::models<concepts::RandomAccessIterator, I>;
        
        template <typename T>
        using iterator_concept = concepts::most_refined<meta::list<concepts::RandomAccessIterator, concepts::BidirectionalIterator, concepts::ForwardIterator, concepts::InputIterator>, T>;
        
        template <typename T>
        using iterator_concept_t = meta::_t<iterator_concept<T>>;
        
        template <typename I>
        using SinglePass = meta::strict_and<Iterator<I>, meta::not_<ForwardIterator<I>>>;
        
        namespace detail
        {
            template <typename I, bool IsReadable = (bool)Readable<I>()>
            struct exclusively_writable_
            {
                template <typename T>
                using invoke = Writable<I, T>;
            };
            
            template <typename I>
            struct exclusively_writable_<I, true>
            {
                template <typename T>
                using invoke = meta::and_<Writable<I, T>, meta::not_<Assignable<concepts::Readable::reference_t<I>&&, T>>>;
            };
        }
        
        template <typename I, typename T>
        using ExclusivelyWritable_ = meta::invoke<detail::exclusively_writable_<I>, T>;
        
        namespace detail
        {
            template <typename I>
            using readable_types_ = meta::list<concepts::Readable::value_t<I>, concepts::Readable::reference_t<I>>;
            
            template <typename ... Is>
            using iter_args_lists_ = meta::push_back<meta::cartesian_product<meta::transform<meta::list<Is...>, meta::quote<readable_types_>>>, meta::list<concepts::Readable::common_reference_t<Is>...>>;
            
            template <typename MapFn, typename ReduceFn>
            using iter_map_reduce_fn_ = meta::compose<meta::uncurry<meta::on<ReduceFn, meta::uncurry<MapFn>>>, meta::quote<iter_args_lists_>>;
        }
        
        template <typename C, typename ... Is>
        using IndirectFunction = meta::and_<meta::strict_and<Readable<Is>...>, meta::lazy::invoke<detail::iter_map_reduce_fn_<meta::bind_front<meta::quote<Function>, C>, meta::quote<meta::strict_and>>, Is...>, meta::lazy::invoke<detail::iter_map_reduce_fn_<meta::bind_front<meta::quote<concepts::Function::result_t>, C>, meta::quote<CommonReference>>, Is...>>;
        
        template <typename C, typename ... Is>
        using IndirectPredicate = meta::and_<meta::strict_and<Readable<Is>...>, meta::lazy::invoke<detail::iter_map_reduce_fn_<meta::bind_front<meta::quote<Predicate>, C>, meta::quote<meta::strict_and>>, Is...>>;
        
        template <typename C, typename I0, typename I1 = I0>
        using IndirectRelation = meta::and_<meta::strict_and<Readable<I0>, Readable<I1>>, meta::lazy::invoke<detail::iter_map_reduce_fn_<meta::bind_front<meta::quote<Relation>, C>, meta::quote<meta::strict_and>>, I0, I1>>;
        
        template <typename C, typename ... Is>
        using IndirectCallable = IndirectFunction<function_type<C>, Is...>;
        
        template <typename C, typename ... Is>
        using IndirectCallablePredicate = IndirectPredicate<function_type<C>, Is...>;
        
        template <typename C, typename I0, typename I1 = I0>
        using IndirectCallableRelation = IndirectRelation<function_type<C>, I0, I1>;
        
        namespace detail
        {
            template <typename I, typename Proj>
            struct projected_readable
            {
                using value_type = decay_t<concepts::Callable::result_t<Proj&, concepts::Readable::value_t<I>>>;
                
                using reference = concepts::Callable::result_t<Proj&, concepts::Readable::reference_t<I>>;
                
                reference operator*() const;
            };
        }
        
        template <typename I, typename Proj>
        using projected = meta::if_<IndirectCallable<Proj, I>, detail::projected_readable<I, Proj>>;
        
        template <typename I, typename V = concepts::Readable::value_t<I>>
        using Permutable = meta::strict_and<ForwardIterator<I>, IndirectlySwappable<I, I>, IndirectlyMovableStorable<I, I>>;
        
        template <typename I0, typename I1, typename Out, typename C = ordered_less, typename P0 = ident, typename P1 = ident>
        using Mergeable = meta::strict_and<InputIterator<I0>, InputIterator<I1>, WeaklyIncrementable<Out>, IndirectCallableRelation<C, projected<I0, P0>, projected<I1, P1>>, IndirectlyCopyable<I0, Out>, IndirectlyCopyable<I1, Out>>;
        
        template <typename I0, typename I1, typename Out, typename C = ordered_less, typename P0 = ident, typename P1 = ident>
        using MoveMergeable = meta::strict_and<InputIterator<I0>, InputIterator<I1>, WeaklyIncrementable<Out>, IndirectCallableRelation<C, projected<I0, P0>, projected<I1, P1>>, IndirectlyMovable<I0, Out>, IndirectlyMovable<I1, Out>>;
        
        template <typename I, typename C = ordered_less, typename P = ident>
        using Sortable = meta::strict_and<ForwardIterator<I>, IndirectCallableRelation<C, projected<I, P>, projected<I, P>>, Permutable<I>>;
        
        template <typename I, typename V2, typename C = ordered_less, typename P = ident>
        using BinarySearchable = meta::strict_and<ForwardIterator<I>, IndirectCallableRelation<C, projected<I, P>, V2 const*>>;
        
        template <typename I1, typename I2, typename C = equal_to, typename P1 = ident, typename P2 = ident>
        using AsymmetricallyComparable = meta::strict_and<InputIterator<I1>, InputIterator<I2>, IndirectCallablePredicate<C, projected<I1, P1>, projected<I2, P2>>>;
        
        template <typename I1, typename I2, typename C = equal_to, typename P1 = ident, typename P2 = ident>
        using Comparable = meta::strict_and<AsymmetricallyComparable<I1, I2, C, P1, P2>, IndirectCallableRelation<C, projected<I1, P1>, projected<I2, P2>>>;
        
        template <typename S, typename I>
        using sized_sentinel_concept = concepts::most_refined<meta::list<concepts::SizedSentinel, concepts::Sentinel>, S, I>;
        
        template <typename S, typename I>
        using sized_sentinel_concept_t = meta::_t<sized_sentinel_concept<S, I>>;
    }
}

namespace ranges
{
    inline namespace v3{}
}

Class ranges::v3::input_iterator_tag

struct input_iterator_tag{};

@{


Function template ranges::v3::detail::upgrade_iterator_category_<T>

template <typename T>
T upgrade_iterator_category_(T*, void*);

/////////////////////////////////////////////////////////////////////////////////////


Function template ranges::v3::detail::downgrade_iterator_category_<T, B>

template <typename T, typename B>
meta::nil_ downgrade_iterator_category_(T*, void*, B);

/////////////////////////////////////////////////////////////////////////////////////


Class template ranges::v3::iterator_category<T>

template <typename T, typename>
struct iterator_category{};

@{


Alias template ranges::v3::iterator_concept<T>

template <typename T>
using iterator_concept = concepts::most_refined<meta::list<concepts::RandomAccessIterator, concepts::BidirectionalIterator, concepts::ForwardIterator, concepts::InputIterator>, T>;

/////////////////////////////////////////////////////////////////////////////////////////


Alias template ranges::v3::Permutable<I, V>

template <typename I, typename V = concepts::Readable::value_t<I>>
using Permutable = meta::strict_and<ForwardIterator<I>, IndirectlySwappable<I, I>, IndirectlyMovableStorable<I, I>>;

/////////////////////////////////////////////////////////////////////////////////////////