diff options
Diffstat (limited to 'boost/geometry/index/rtree.hpp')
| -rw-r--r-- | boost/geometry/index/rtree.hpp | 341 |
1 files changed, 304 insertions, 37 deletions
diff --git a/boost/geometry/index/rtree.hpp b/boost/geometry/index/rtree.hpp index 9d5d57d059..84c4da8a2a 100644 --- a/boost/geometry/index/rtree.hpp +++ b/boost/geometry/index/rtree.hpp @@ -59,6 +59,7 @@ #include <boost/geometry/index/detail/algorithms/is_valid.hpp> #include <boost/geometry/index/detail/rtree/visitors/insert.hpp> +#include <boost/geometry/index/detail/rtree/visitors/iterator.hpp> #include <boost/geometry/index/detail/rtree/visitors/remove.hpp> #include <boost/geometry/index/detail/rtree/visitors/copy.hpp> #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp> @@ -78,6 +79,7 @@ #include <boost/geometry/index/detail/rtree/utilities/view.hpp> +#include <boost/geometry/index/detail/rtree/iterators.hpp> #include <boost/geometry/index/detail/rtree/query_iterators.hpp> #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL @@ -220,8 +222,17 @@ public: /*! \brief Unsigned integral type used by the container. */ typedef typename allocators_type::size_type size_type; - /*! \brief Type of const query iterator. */ - typedef index::detail::rtree::iterators::query_iterator<value_type, allocators_type> const_query_iterator; + /*! \brief Type of const iterator, category ForwardIterator. */ + typedef index::detail::rtree::iterators::iterator + < + value_type, options_type, translator_type, box_type, allocators_type + > const_iterator; + + /*! \brief Type of const query iterator, category ForwardIterator. */ + typedef index::detail::rtree::iterators::query_iterator + < + value_type, allocators_type + > const_query_iterator; public: @@ -766,6 +777,27 @@ public: tree.query(bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result)); // return 5 elements nearest to pt and elements are intersecting box tree.query(bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result)); + + // For each found value do_something (it is a type of function object) + tree.query(bgi::intersects(box), + boost::make_function_output_iterator(do_something())); + + // For each value stored in the rtree do_something + // always_true is a type of function object always returning true + tree.query(bgi::satisfies(always_true()), + boost::make_function_output_iterator(do_something())); + + // C++11 (lambda expression) + tree.query(bgi::intersects(box), + boost::make_function_output_iterator([](value_type const& val){ + // do something + })); + + // C++14 (generic lambda expression) + tree.query(bgi::intersects(box), + boost::make_function_output_iterator([](auto const& val){ + // do something + })); \endverbatim \par Throws @@ -774,7 +806,7 @@ public: \warning Only one \c nearest() perdicate may be passed to the query. Passing more of them results in compile-time error. - + \param predicates Predicates. \param out_it The output iterator, e.g. generated by std::back_inserter(). @@ -794,11 +826,11 @@ public: } /*! - \brief Returns the query iterator pointing at the begin of the query range. + \brief Returns a query iterator pointing at the begin of the query range. + + This method returns an iterator which may be used to perform iterative queries. + For the information about predicates which may be passed to this method see query(). - This method returns the iterator which may be used to perform iterative queries. For the information - about the predicates which may be passed to this method see query(). - \par Example \verbatim for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ; @@ -808,12 +840,29 @@ public: if ( has_enough_nearest_values() ) break; } + + // C++11 (auto) + for ( auto it = tree.qbegin(bgi::nearest(pt, 3)) ; it != tree.qend() ; ++it ) + { + // do something with value + } + + // C++14 (generic lambda expression) + std::for_each(tree.qbegin(bgi::nearest(pt, 3)), tree.qend(), [](auto const& val){ + // do something with value + }); \endverbatim + \par Iterator category + ForwardIterator + \par Throws If predicates copy throws. If allocation throws. + \warning + The modification of the rtree may invalidate the iterators. + \param predicates Predicates. \return The iterator pointing at the begin of the query range. @@ -825,10 +874,10 @@ public: } /*! - \brief Returns the query iterator pointing at the end of the query range. + \brief Returns a query iterator pointing at the end of the query range. + + This method returns an iterator which may be used to check if the query has ended. - This method returns the iterator which may be used to check if the query has ended. - \par Example \verbatim for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ; @@ -838,10 +887,27 @@ public: if ( has_enough_nearest_values() ) break; } + + // C++11 (auto) + for ( auto it = tree.qbegin(bgi::nearest(pt, 3)) ; it != tree.qend() ; ++it ) + { + // do something with value + } + + // C++14 (generic lambda expression) + std::for_each(tree.qbegin(bgi::nearest(pt, 3)), tree.qend(), [](auto const& val){ + // do something with value + }); \endverbatim + \par Iterator category + ForwardIterator + \par Throws Nothing + + \warning + The modification of the rtree may invalidate the iterators. \return The iterator pointing at the end of the query range. */ @@ -854,10 +920,10 @@ public: private: #endif /*! - \brief Returns the query iterator pointing at the begin of the query range. + \brief Returns a query iterator pointing at the begin of the query range. - This method returns the iterator which may be used to perform iterative queries. For the information - about the predicates which may be passed to this method see query(). + This method returns an iterator which may be used to perform iterative queries. + For the information about predicates which may be passed to this method see query(). The type of the returned iterator depends on the type of passed Predicates but the iterator of this type may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator @@ -867,16 +933,24 @@ private: \par Example \verbatim // Store the result in the container using std::copy() - it requires both iterators of the same type - std::copy(tree.qbegin(bgi::intersects(box)), tree.qend(bgi::intersects(box)), std::back_inserter(result)); + std::copy(tree.qbegin_(bgi::intersects(box)), tree.qend_(bgi::intersects(box)), std::back_inserter(result)); // Store the result in the container using std::copy() and type-erased iterators - Rtree::const_query_iterator first = tree.qbegin(bgi::intersects(box)); - Rtree::const_query_iterator last = tree.qend(); + Rtree::const_query_iterator first = tree.qbegin_(bgi::intersects(box)); + Rtree::const_query_iterator last = tree.qend_(); std::copy(first, last, std::back_inserter(result)); // Boost.Typeof typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter; - for ( Iter it = tree.qbegin(bgi::nearest(pt, 10000)) ; it != tree.qend() ; ++it ) + for ( Iter it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it ) + { + // do something with value + if ( has_enough_nearest_values() ) + break; + } + + // C++11 (auto) + for ( auto it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it ) { // do something with value if ( has_enough_nearest_values() ) @@ -884,10 +958,16 @@ private: } \endverbatim + \par Iterator category + ForwardIterator + \par Throws If predicates copy throws. If allocation throws. + \warning + The modification of the rtree may invalidate the iterators. + \param predicates Predicates. \return The iterator pointing at the begin of the query range. @@ -937,12 +1017,18 @@ private: \par Example \verbatim // Store the result in the container using std::copy() - it requires both iterators of the same type - std::copy(tree.qbegin(bgi::intersects(box)), tree.qend(bgi::intersects(box)), std::back_inserter(result)); + std::copy(tree.qbegin_(bgi::intersects(box)), tree.qend_(bgi::intersects(box)), std::back_inserter(result)); \endverbatim + \par Iterator category + ForwardIterator + \par Throws If predicates copy throws. + \warning + The modification of the rtree may invalidate the iterators. + \param predicates Predicates. \return The iterator pointing at the end of the query range. @@ -989,13 +1075,21 @@ private: \par Example \verbatim // Store the result in the container using std::copy() and type-erased iterators - Rtree::const_query_iterator first = tree.qbegin(bgi::intersects(box)); - Rtree::const_query_iterator last = tree.qend(); + Rtree::const_query_iterator first = tree.qbegin_(bgi::intersects(box)); + Rtree::const_query_iterator last = tree.qend_(); std::copy(first, last, std::back_inserter(result)); // Boost.Typeof typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter; - for ( Iter it = tree.qbegin(bgi::nearest(pt, 10000)) ; it != tree.qend() ; ++it ) + for ( Iter it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it ) + { + // do something with value + if ( has_enough_nearest_values() ) + break; + } + + // C++11 (auto) + for ( auto it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it ) { // do something with value if ( has_enough_nearest_values() ) @@ -1003,8 +1097,14 @@ private: } \endverbatim + \par Iterator category + ForwardIterator + \par Throws Nothing + + \warning + The modification of the rtree may invalidate the iterators. \return The iterator pointing at the end of the query range. */ @@ -1017,6 +1117,88 @@ private: public: /*! + \brief Returns the iterator pointing at the begin of the rtree values range. + + This method returns the iterator which may be used to iterate over all values + stored in the rtree. + + \par Example + \verbatim + // Copy all values into the vector + std::copy(tree.begin(), tree.end(), std::back_inserter(vec)); + + for ( Rtree::const_iterator it = tree.begin() ; it != tree.end() ; ++it ) + { + // do something with value + } + + // C++11 (auto) + for ( auto it = tree.begin() ; it != tree.end() ; ++it ) + { + // do something with value + } + + // C++14 (generic lambda expression) + std::for_each(tree.begin(), tree.end(), [](auto const& val){ + // do something with value + }) + \endverbatim + + \par Iterator category + ForwardIterator + + \par Throws + If allocation throws. + + \warning + The modification of the rtree may invalidate the iterators. + + \return The iterator pointing at the begin of the range. + */ + const_iterator begin() const + { + if ( !m_members.root ) + return const_iterator(); + + return const_iterator(m_members.root); + } + + /*! + \brief Returns the iterator pointing at the end of the rtree values range. + + This method returns the iterator which may be compared with the iterator returned by begin() + in order to check if the iteration has ended. + + \par Example + \verbatim + for ( Rtree::const_iterator it = tree.begin() ; it != tree.end() ; ++it ) + { + // do something with value + } + + // C++11 (lambda expression) + std::for_each(tree.begin(), tree.end(), [](value_type const& val){ + // do something with value + }) + \endverbatim + + \par Iterator category + ForwardIterator + + \par Throws + Nothing. + + \warning + The modification of the rtree may invalidate the iterators. + + \return The iterator pointing at the end of the range. + */ + const_iterator end() const + { + return const_iterator(); + } + + /*! \brief Returns the number of stored values. \return The number of stored values. @@ -1763,6 +1945,10 @@ bgi::query(tree, bgi::intersects(poly) && !bgi::within(box), std::back_inserter( bgi::query(tree, bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result)); // return 5 elements nearest to pt and elements are intersecting box bgi::query(tree, bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result)); + +// For each found value do_something (it is a type of function object) +tree.query(bgi::intersects(box), + boost::make_function_output_iterator(do_something())); \endverbatim \par Throws @@ -1797,20 +1983,19 @@ about the predicates which may be passed to this method see query(). \par Example \verbatim - -for ( Rtree::const_query_iterator it = qbegin(tree, bgi::nearest(pt, 10000)) ; - it != qend(tree) ; ++it ) -{ - // do something with value - if ( has_enough_nearest_values() ) - break; -} +std::for_each(bgi::qbegin(tree, bgi::nearest(pt, 3)), bgi::qend(tree), do_something()); \endverbatim +\par Iterator category +ForwardIterator + \par Throws If predicates copy throws. If allocation throws. +\warning +The modification of the rtree may invalidate the iterators. + \ingroup rtree_functions \param tree The rtree. @@ -1834,19 +2019,18 @@ This method returns the iterator which may be used to check if the query has end \par Example \verbatim - -for ( Rtree::const_query_iterator it = qbegin(tree, bgi::nearest(pt, 10000)) ; - it != qend(tree) ; ++it ) -{ - // do something with value - if ( has_enough_nearest_values() ) - break; -} +std::for_each(bgi::qbegin(tree, bgi::nearest(pt, 3)), bgi::qend(tree), do_something()); \endverbatim +\par Iterator category +ForwardIterator + \par Throws Nothing +\warning +The modification of the rtree may invalidate the iterators. + \ingroup rtree_functions \return The iterator pointing at the end of the query range. @@ -1859,6 +2043,72 @@ qend(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree) } /*! +\brief Returns the iterator pointing at the begin of the rtree values range. + +This method returns the iterator which may be used to iterate over all values +stored in the rtree. + +\par Example +\verbatim +std::for_each(bgi::begin(tree), bgi::end(tree), do_something()); +// the same as +std::for_each(boost::begin(tree), boost::end(tree), do_something()); +\endverbatim + +\par Iterator category +ForwardIterator + +\par Throws +If allocation throws. + +\warning +The modification of the rtree may invalidate the iterators. + +\ingroup rtree_functions + +\return The iterator pointing at the begin of the range. +*/ +template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline +typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator +begin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree) +{ + return tree.begin(); +} + +/*! +\brief Returns the iterator pointing at the end of the rtree values range. + +This method returns the iterator which may be compared with the iterator returned by begin() +in order to check if the iteration has ended. + +\par Example +\verbatim +std::for_each(bgi::begin(tree), bgi::end(tree), do_something()); +// the same as +std::for_each(boost::begin(tree), boost::end(tree), do_something()); +\endverbatim + +\par Iterator category +ForwardIterator + +\par Throws +Nothing. + +\warning +The modification of the rtree may invalidate the iterators. + +\ingroup rtree_functions + +\return The iterator pointing at the end of the range. +*/ +template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline +typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator +end(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree) +{ + return tree.end(); +} + +/*! \brief Remove all values from the index. It calls \c rtree::clear(). @@ -1944,6 +2194,23 @@ inline void swap(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & }}} // namespace boost::geometry::index +// Boost.Range adaptation +namespace boost { + +template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> +struct range_mutable_iterator + < + boost::geometry::index::rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> + > +{ + typedef typename boost::geometry::index::rtree + < + Value, Parameters, IndexableGetter, EqualTo, Allocator + >::const_iterator type; +}; + +} // namespace boost + // TODO: don't include the implementation at the end of the file #include <boost/geometry/algorithms/detail/comparable_distance/implementation.hpp> |