ceph/src/boost/libs/geometry/include/boost/geometry/index/detail/rtree/visitors/iterator.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree iterator visitor implementation
   4 //
   5 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
   6 //
   7 // Use, modification and distribution is subject to the Boost Software License,
   8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   9 // http://www.boost.org/LICENSE_1_0.txt)
  10
  11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
  13
  14 namespace boost { namespace geometry { namespace index {
  15
  16 namespace detail { namespace rtree { namespace visitors {
  17
  18 template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
  19 class iterator
  20     : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
  21 {
  22 public:
  23     typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
  24     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
  25     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
  26
  27     typedef typename Allocators::size_type size_type;
  28     typedef typename Allocators::const_reference const_reference;
  29     typedef typename Allocators::node_pointer node_pointer;
  30
  31     typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
  32     typedef typename rtree::elements_type<leaf>::type leaf_elements;
  33     typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator;
  34
  35     inline iterator()
  36         : m_values(NULL)
  37         , m_current()
  38     {}
  39
  40     inline void operator()(internal_node const& n)
  41     {
  42         typedef typename rtree::elements_type<internal_node>::type elements_type;
  43         elements_type const& elements = rtree::elements(n);
  44
  45         m_internal_stack.push_back(std::make_pair(elements.begin(), elements.end()));
  46     }
  47
  48     inline void operator()(leaf const& n)
  49     {
  50         m_values = ::boost::addressof(rtree::elements(n));
  51         m_current = rtree::elements(n).begin();
  52     }
  53
  54     const_reference dereference() const
  55     {
  56         BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable");
  57         return *m_current;
  58     }
  59
  60     void initialize(node_pointer root)
  61     {
  62         rtree::apply_visitor(*this, *root);
  63         search_value();
  64     }
  65
  66     void increment()
  67     {
  68         ++m_current;
  69         search_value();
  70     }
  71
  72     void search_value()
  73     {
  74         for (;;)
  75         {
  76             // if leaf is choosen, move to the next value in leaf
  77             if ( m_values )
  78             {
  79                 // there are more values in the current leaf
  80                 if ( m_current != m_values->end() )
  81                 {
  82                     return;
  83                 }
  84                 // no more values, clear current leaf
  85                 else
  86                 {
  87                     m_values = 0;
  88                 }
  89             }
  90             // if leaf isn't choosen, move to the next leaf
  91             else
  92             {
  93                 // return if there is no more nodes to traverse
  94                 if ( m_internal_stack.empty() )
  95                     return;
  96
  97                 // no more children in current node, remove it from stack
  98                 if ( m_internal_stack.back().first == m_internal_stack.back().second )
  99                 {
 100                     m_internal_stack.pop_back();
 101                     continue;
 102                 }
 103
 104                 internal_iterator it = m_internal_stack.back().first;
 105                 ++m_internal_stack.back().first;
 106
 107                 // push the next node to the stack
 108                 rtree::apply_visitor(*this, *(it->second));
 109             }
 110         }
 111     }
 112
 113     bool is_end() const
 114     {
 115         return 0 == m_values;
 116     }
 117
 118     friend bool operator==(iterator const& l, iterator const& r)
 119     {
 120         return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current );
 121     }
 122
 123 private:
 124
 125     std::vector< std::pair<internal_iterator, internal_iterator> > m_internal_stack;
 126     const leaf_elements * m_values;
 127     leaf_iterator m_current;
 128 };
 129
 130 }}} // namespace detail::rtree::visitors
 131
 132 }}} // namespace boost::geometry::index
 133
 134 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP