1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2007-2013 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // See http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 13 #ifndef BOOST_INTRUSIVE_TREE_ITERATOR_HPP 14 #define BOOST_INTRUSIVE_TREE_ITERATOR_HPP 15 16 #ifndef BOOST_CONFIG_HPP 17 # include <boost/config.hpp> 18 #endif 19 20 #if defined(BOOST_HAS_PRAGMA_ONCE) 21 # pragma once 22 #endif 23 24 #include <boost/intrusive/detail/config_begin.hpp> 25 #include <boost/intrusive/detail/workaround.hpp> 26 #include <boost/intrusive/detail/std_fwd.hpp> 27 #include <boost/intrusive/detail/iiterator.hpp> 28 #include <boost/intrusive/detail/bstree_algorithms_base.hpp> 29 30 namespace boost { 31 namespace intrusive { 32 33 ///////////////////////////////////////////////////////////////////////////// 34 // // 35 // Implementation of the tree iterator // 36 // // 37 ///////////////////////////////////////////////////////////////////////////// 38 39 // tree_iterator provides some basic functions for a 40 // node oriented bidirectional iterator: 41 template<class ValueTraits, bool IsConst> 42 class tree_iterator 43 { 44 private: 45 typedef iiterator< ValueTraits, IsConst 46 , std::bidirectional_iterator_tag> types_t; 47 typedef typename types_t::value_traits value_traits; 48 typedef typename types_t::node_traits node_traits; 49 typedef typename types_t::node node; 50 typedef typename types_t::node_ptr node_ptr; 51 typedef typename types_t::const_value_traits_ptr const_value_traits_ptr; 52 typedef bstree_algorithms_base<node_traits> node_algorithms; 53 54 static const bool stateful_value_traits = types_t::stateful_value_traits; 55 unspecified_bool_type_func() const56 void unspecified_bool_type_func() const {} 57 typedef void (tree_iterator::*unspecified_bool_type)() const; 58 59 public: 60 typedef typename types_t::iterator_type::difference_type difference_type; 61 typedef typename types_t::iterator_type::value_type value_type; 62 typedef typename types_t::iterator_type::pointer pointer; 63 typedef typename types_t::iterator_type::reference reference; 64 typedef typename types_t::iterator_type::iterator_category iterator_category; 65 tree_iterator()66 BOOST_INTRUSIVE_FORCEINLINE tree_iterator() 67 {} 68 tree_iterator(const node_ptr & nodeptr,const const_value_traits_ptr & traits_ptr)69 BOOST_INTRUSIVE_FORCEINLINE explicit tree_iterator(const node_ptr & nodeptr, const const_value_traits_ptr &traits_ptr) 70 : members_(nodeptr, traits_ptr) 71 {} 72 tree_iterator(tree_iterator<value_traits,false> const & other)73 BOOST_INTRUSIVE_FORCEINLINE tree_iterator(tree_iterator<value_traits, false> const& other) 74 : members_(other.pointed_node(), other.get_value_traits()) 75 {} 76 pointed_node() const77 BOOST_INTRUSIVE_FORCEINLINE const node_ptr &pointed_node() const 78 { return members_.nodeptr_; } 79 operator =(const node_ptr & nodeptr)80 BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(const node_ptr &nodeptr) 81 { members_.nodeptr_ = nodeptr; return static_cast<tree_iterator&>(*this); } 82 83 public: operator ++()84 tree_iterator& operator++() 85 { 86 members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); 87 return static_cast<tree_iterator&> (*this); 88 } 89 operator ++(int)90 tree_iterator operator++(int) 91 { 92 tree_iterator result (*this); 93 members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); 94 return result; 95 } 96 operator --()97 tree_iterator& operator--() 98 { 99 members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); 100 return static_cast<tree_iterator&> (*this); 101 } 102 operator --(int)103 tree_iterator operator--(int) 104 { 105 tree_iterator result (*this); 106 members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); 107 return result; 108 } 109 go_left()110 BOOST_INTRUSIVE_FORCEINLINE tree_iterator& go_left() 111 { 112 members_.nodeptr_ = node_traits::get_left(members_.nodeptr_); 113 return static_cast<tree_iterator&> (*this); 114 } 115 go_right()116 BOOST_INTRUSIVE_FORCEINLINE tree_iterator& go_right() 117 { 118 members_.nodeptr_ = node_traits::get_right(members_.nodeptr_); 119 return static_cast<tree_iterator&> (*this); 120 } 121 go_parent()122 BOOST_INTRUSIVE_FORCEINLINE tree_iterator& go_parent() 123 { 124 members_.nodeptr_ = node_traits::get_parent(members_.nodeptr_); 125 return static_cast<tree_iterator&> (*this); 126 } 127 operator unspecified_bool_type() const128 BOOST_INTRUSIVE_FORCEINLINE operator unspecified_bool_type() const 129 { return members_.nodeptr_ ? &tree_iterator::unspecified_bool_type_func : 0; } 130 operator !() const131 BOOST_INTRUSIVE_FORCEINLINE bool operator! () const 132 { return !members_.nodeptr_; } 133 operator ==(const tree_iterator & l,const tree_iterator & r)134 BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const tree_iterator& l, const tree_iterator& r) 135 { return l.pointed_node() == r.pointed_node(); } 136 operator !=(const tree_iterator & l,const tree_iterator & r)137 BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const tree_iterator& l, const tree_iterator& r) 138 { return !(l == r); } 139 operator *() const140 BOOST_INTRUSIVE_FORCEINLINE reference operator*() const 141 { return *operator->(); } 142 operator ->() const143 BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const 144 { return this->operator_arrow(detail::bool_<stateful_value_traits>()); } 145 get_value_traits() const146 BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr get_value_traits() const 147 { return members_.get_ptr(); } 148 end_iterator_from_it() const149 tree_iterator end_iterator_from_it() const 150 { 151 return tree_iterator(node_algorithms::get_header(this->pointed_node()), this->get_value_traits()); 152 } 153 unconst() const154 tree_iterator<value_traits, false> unconst() const 155 { return tree_iterator<value_traits, false>(this->pointed_node(), this->get_value_traits()); } 156 157 private: operator_arrow(detail::false_) const158 BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::false_) const 159 { return ValueTraits::to_value_ptr(members_.nodeptr_); } 160 operator_arrow(detail::true_) const161 BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::true_) const 162 { return this->get_value_traits()->to_value_ptr(members_.nodeptr_); } 163 164 iiterator_members<node_ptr, const_value_traits_ptr, stateful_value_traits> members_; 165 }; 166 167 } //namespace intrusive 168 } //namespace boost 169 170 #include <boost/intrusive/detail/config_end.hpp> 171 172 #endif //BOOST_INTRUSIVE_TREE_ITERATOR_HPP 173