Chris@102: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@102: 
Chris@102: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@102: 
Chris@102: // This file was modified by Oracle on 2013, 2014, 2015.
Chris@102: // Modifications copyright (c) 2013-2015 Oracle and/or its affiliates.
Chris@102: 
Chris@102: // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
Chris@102: 
Chris@102: // Use, modification and distribution is subject to the Boost Software License,
Chris@102: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@102: // http://www.boost.org/LICENSE_1_0.txt)
Chris@102: 
Chris@102: #ifndef BOOST_GEOMETRY_UTIL_RANGE_HPP
Chris@102: #define BOOST_GEOMETRY_UTIL_RANGE_HPP
Chris@102: 
Chris@102: #include <algorithm>
Chris@102: 
Chris@102: #include <boost/assert.hpp>
Chris@102: #include <boost/concept_check.hpp>
Chris@102: #include <boost/config.hpp>
Chris@102: #include <boost/range/concepts.hpp>
Chris@102: #include <boost/range/begin.hpp>
Chris@102: #include <boost/range/end.hpp>
Chris@102: #include <boost/range/empty.hpp>
Chris@102: #include <boost/range/size.hpp>
Chris@102: #include <boost/type_traits/is_convertible.hpp>
Chris@102: 
Chris@102: #include <boost/geometry/core/mutable_range.hpp>
Chris@102: 
Chris@102: namespace boost { namespace geometry { namespace range {
Chris@102: 
Chris@102: namespace detail {
Chris@102: 
Chris@102: // NOTE: For SinglePassRanges pos could iterate over all elements until the i-th element was met.
Chris@102: 
Chris@102: template <typename RandomAccessRange>
Chris@102: struct pos
Chris@102: {
Chris@102:     typedef typename boost::range_iterator<RandomAccessRange>::type iterator;
Chris@102:     typedef typename boost::range_size<RandomAccessRange>::type size_type;
Chris@102:     typedef typename boost::range_difference<RandomAccessRange>::type difference_type;
Chris@102: 
Chris@102:     static inline iterator apply(RandomAccessRange & rng, size_type i)
Chris@102:     {
Chris@102:         BOOST_RANGE_CONCEPT_ASSERT(( boost::RandomAccessRangeConcept<RandomAccessRange> ));
Chris@102:         return boost::begin(rng) + static_cast<difference_type>(i);
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: } // namespace detail
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently return an iterator of a RandomAccessRange.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename RandomAccessRange>
Chris@102: inline typename boost::range_iterator<RandomAccessRange const>::type
Chris@102: pos(RandomAccessRange const& rng,
Chris@102:     typename boost::range_size<RandomAccessRange const>::type i)
Chris@102: {
Chris@102:     BOOST_ASSERT(i <= boost::size(rng));
Chris@102:     return detail::pos<RandomAccessRange const>::apply(rng, i);
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently return an iterator of a RandomAccessRange.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename RandomAccessRange>
Chris@102: inline typename boost::range_iterator<RandomAccessRange>::type
Chris@102: pos(RandomAccessRange & rng,
Chris@102:     typename boost::range_size<RandomAccessRange>::type i)
Chris@102: {
Chris@102:     BOOST_ASSERT(i <= boost::size(rng));
Chris@102:     return detail::pos<RandomAccessRange>::apply(rng, i);
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently return an element of a RandomAccessRange.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename RandomAccessRange>
Chris@102: inline typename boost::range_reference<RandomAccessRange const>::type
Chris@102: at(RandomAccessRange const& rng,
Chris@102:    typename boost::range_size<RandomAccessRange const>::type i)
Chris@102: {
Chris@102:     BOOST_ASSERT(i < boost::size(rng));
Chris@102:     return * detail::pos<RandomAccessRange const>::apply(rng, i);
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently return an element of a RandomAccessRange.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename RandomAccessRange>
Chris@102: inline typename boost::range_reference<RandomAccessRange>::type
Chris@102: at(RandomAccessRange & rng,
Chris@102:    typename boost::range_size<RandomAccessRange>::type i)
Chris@102: {
Chris@102:     BOOST_ASSERT(i < boost::size(rng));
Chris@102:     return * detail::pos<RandomAccessRange>::apply(rng, i);
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently return the front element of a Range.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline typename boost::range_reference<Range const>::type
Chris@102: front(Range const& rng)
Chris@102: {
Chris@102:     BOOST_ASSERT(!boost::empty(rng));
Chris@102:     return *boost::begin(rng);
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently return the front element of a Range.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline typename boost::range_reference<Range>::type
Chris@102: front(Range & rng)
Chris@102: {
Chris@102:     BOOST_ASSERT(!boost::empty(rng));
Chris@102:     return *boost::begin(rng);
Chris@102: }
Chris@102: 
Chris@102: // NOTE: For SinglePassRanges back() could iterate over all elements until the last element is met.
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently return the back element of a BidirectionalRange.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename BidirectionalRange>
Chris@102: inline typename boost::range_reference<BidirectionalRange const>::type
Chris@102: back(BidirectionalRange const& rng)
Chris@102: {
Chris@102:     BOOST_RANGE_CONCEPT_ASSERT(( boost::BidirectionalRangeConcept<BidirectionalRange const> ));
Chris@102:     BOOST_ASSERT(!boost::empty(rng));
Chris@102:     return *(boost::rbegin(rng));
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently return the back element of a BidirectionalRange.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename BidirectionalRange>
Chris@102: inline typename boost::range_reference<BidirectionalRange>::type
Chris@102: back(BidirectionalRange & rng)
Chris@102: {
Chris@102:     BOOST_RANGE_CONCEPT_ASSERT((boost::BidirectionalRangeConcept<BidirectionalRange>));
Chris@102:     BOOST_ASSERT(!boost::empty(rng));
Chris@102:     return *(boost::rbegin(rng));
Chris@102: }
Chris@102: 
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently clear a mutable range.
Chris@102:        It uses traits::clear<>.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline void clear(Range & rng)
Chris@102: {
Chris@102:     // NOTE: this trait is probably not needed since it could be implemented using resize()
Chris@102:     geometry::traits::clear<Range>::apply(rng);
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently insert a new element at the end of a mutable range.
Chris@102:        It uses boost::geometry::traits::push_back<>.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline void push_back(Range & rng,
Chris@102:                       typename boost::range_value<Range>::type const& value)
Chris@102: {
Chris@102:     geometry::traits::push_back<Range>::apply(rng, value);
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently resize a mutable range.
Chris@102:        It uses boost::geometry::traits::resize<>.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline void resize(Range & rng,
Chris@102:                    typename boost::range_size<Range>::type new_size)
Chris@102: {
Chris@102:     geometry::traits::resize<Range>::apply(rng, new_size);
Chris@102: }
Chris@102: 
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently remove an element from the back of a mutable range.
Chris@102:        It uses resize().
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline void pop_back(Range & rng)
Chris@102: {
Chris@102:     BOOST_ASSERT(!boost::empty(rng));
Chris@102:     range::resize(rng, boost::size(rng) - 1);
Chris@102: }
Chris@102: 
Chris@102: namespace detail {
Chris@102: 
Chris@102: #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@102: 
Chris@102: template <typename It,
Chris@102:           typename OutIt,
Chris@102:           bool UseMove = boost::is_convertible
Chris@102:                             <
Chris@102:                                 typename std::iterator_traits<It>::value_type &&,
Chris@102:                                 typename std::iterator_traits<OutIt>::value_type
Chris@102:                             >::value>
Chris@102: struct copy_or_move_impl
Chris@102: {
Chris@102:     static inline OutIt apply(It first, It last, OutIt out)
Chris@102:     {
Chris@102:         return std::move(first, last, out);
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: template <typename It, typename OutIt>
Chris@102: struct copy_or_move_impl<It, OutIt, false>
Chris@102: {
Chris@102:     static inline OutIt apply(It first, It last, OutIt out)
Chris@102:     {
Chris@102:         return std::copy(first, last, out);
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: template <typename It, typename OutIt>
Chris@102: inline OutIt copy_or_move(It first, It last, OutIt out)
Chris@102: {
Chris@102:     return copy_or_move_impl<It, OutIt>::apply(first, last, out);
Chris@102: }
Chris@102: 
Chris@102: #else
Chris@102: 
Chris@102: template <typename It, typename OutIt>
Chris@102: inline OutIt copy_or_move(It first, It last, OutIt out)
Chris@102: {
Chris@102:     return std::copy(first, last, out);
Chris@102: }
Chris@102: 
Chris@102: #endif
Chris@102: 
Chris@102: } // namespace detail
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently remove an element from a mutable range.
Chris@102:        It uses std::copy() and resize(). Version taking mutable iterators.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline typename boost::range_iterator<Range>::type
Chris@102: erase(Range & rng,
Chris@102:       typename boost::range_iterator<Range>::type it)
Chris@102: {
Chris@102:     BOOST_ASSERT(!boost::empty(rng));
Chris@102:     BOOST_ASSERT(it != boost::end(rng));
Chris@102: 
Chris@102:     typename boost::range_difference<Range>::type const
Chris@102:         d = std::distance(boost::begin(rng), it);
Chris@102: 
Chris@102:     typename boost::range_iterator<Range>::type
Chris@102:         next = it;
Chris@102:     ++next;
Chris@102: 
Chris@102:     detail::copy_or_move(next, boost::end(rng), it);
Chris@102:     range::resize(rng, boost::size(rng) - 1);
Chris@102: 
Chris@102:     // NOTE: In general this should be sufficient:
Chris@102:     //    return it;
Chris@102:     // But in MSVC using the returned iterator causes
Chris@102:     // assertion failures when iterator debugging is enabled
Chris@102:     // Furthermore the code below should work in the case if resize()
Chris@102:     // invalidates iterators when the container is resized down.
Chris@102:     return boost::begin(rng) + d;
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently remove an element from a mutable range.
Chris@102:        It uses std::copy() and resize(). Version taking non-mutable iterators.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline typename boost::range_iterator<Range>::type
Chris@102: erase(Range & rng,
Chris@102:       typename boost::range_iterator<Range const>::type cit)
Chris@102: {
Chris@102:     BOOST_RANGE_CONCEPT_ASSERT(( boost::RandomAccessRangeConcept<Range> ));
Chris@102: 
Chris@102:     typename boost::range_iterator<Range>::type
Chris@102:         it = boost::begin(rng)
Chris@102:                 + std::distance(boost::const_begin(rng), cit);
Chris@102: 
Chris@102:     return erase(rng, it);
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently remove a range of elements from a mutable range.
Chris@102:        It uses std::copy() and resize(). Version taking mutable iterators.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline typename boost::range_iterator<Range>::type
Chris@102: erase(Range & rng,
Chris@102:       typename boost::range_iterator<Range>::type first,
Chris@102:       typename boost::range_iterator<Range>::type last)
Chris@102: {
Chris@102:     typename boost::range_difference<Range>::type const
Chris@102:         diff = std::distance(first, last);
Chris@102:     BOOST_ASSERT(diff >= 0);
Chris@102: 
Chris@102:     std::size_t const count = static_cast<std::size_t>(diff);
Chris@102:     BOOST_ASSERT(count <= boost::size(rng));
Chris@102:     
Chris@102:     if ( count > 0 )
Chris@102:     {
Chris@102:         typename boost::range_difference<Range>::type const
Chris@102:             d = std::distance(boost::begin(rng), first);
Chris@102: 
Chris@102:         detail::copy_or_move(last, boost::end(rng), first);
Chris@102:         range::resize(rng, boost::size(rng) - count);
Chris@102: 
Chris@102:         // NOTE: In general this should be sufficient:
Chris@102:         //    return first;
Chris@102:         // But in MSVC using the returned iterator causes
Chris@102:         // assertion failures when iterator debugging is enabled
Chris@102:         // Furthermore the code below should work in the case if resize()
Chris@102:         // invalidates iterators when the container is resized down.
Chris@102:         return boost::begin(rng) + d;
Chris@102:     }
Chris@102: 
Chris@102:     return first;
Chris@102: }
Chris@102: 
Chris@102: /*!
Chris@102: \brief Short utility to conveniently remove a range of elements from a mutable range.
Chris@102:        It uses std::copy() and resize(). Version taking non-mutable iterators.
Chris@102: \ingroup utility
Chris@102: */
Chris@102: template <typename Range>
Chris@102: inline typename boost::range_iterator<Range>::type
Chris@102: erase(Range & rng,
Chris@102:       typename boost::range_iterator<Range const>::type cfirst,
Chris@102:       typename boost::range_iterator<Range const>::type clast)
Chris@102: {
Chris@102:     BOOST_RANGE_CONCEPT_ASSERT(( boost::RandomAccessRangeConcept<Range> ));
Chris@102: 
Chris@102:     typename boost::range_iterator<Range>::type
Chris@102:         first = boost::begin(rng)
Chris@102:                     + std::distance(boost::const_begin(rng), cfirst);
Chris@102:     typename boost::range_iterator<Range>::type
Chris@102:         last = boost::begin(rng)
Chris@102:                     + std::distance(boost::const_begin(rng), clast);
Chris@102: 
Chris@102:     return erase(rng, first, last);
Chris@102: }
Chris@102: 
Chris@102: }}} // namespace boost::geometry::range
Chris@102: 
Chris@102: #endif // BOOST_GEOMETRY_UTIL_RANGE_HPP