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 class nat; 59 typedef typename 60 detail::if_c< IsConst 61 , tree_iterator<value_traits, false> 62 , nat>::type nonconst_iterator; 63 64 public: 65 typedef typename types_t::iterator_type::difference_type difference_type; 66 typedef typename types_t::iterator_type::value_type value_type; 67 typedef typename types_t::iterator_type::pointer pointer; 68 typedef typename types_t::iterator_type::reference reference; 69 typedef typename types_t::iterator_type::iterator_category iterator_category; 70 tree_iterator()71 BOOST_INTRUSIVE_FORCEINLINE tree_iterator() 72 {} 73 tree_iterator(const node_ptr & nodeptr,const const_value_traits_ptr & traits_ptr)74 BOOST_INTRUSIVE_FORCEINLINE explicit tree_iterator(const node_ptr & nodeptr, const const_value_traits_ptr &traits_ptr) 75 : members_(nodeptr, traits_ptr) 76 {} 77 tree_iterator(const tree_iterator & other)78 BOOST_INTRUSIVE_FORCEINLINE tree_iterator(const tree_iterator &other) 79 : members_(other.pointed_node(), other.get_value_traits()) 80 {} 81 tree_iterator(const nonconst_iterator & other)82 BOOST_INTRUSIVE_FORCEINLINE tree_iterator(const nonconst_iterator &other) 83 : members_(other.pointed_node(), other.get_value_traits()) 84 {} 85 operator =(const tree_iterator & other)86 BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(const tree_iterator &other) 87 { members_.nodeptr_ = other.members_.nodeptr_; return *this; } 88 operator =(const node_ptr & nodeptr)89 BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(const node_ptr &nodeptr) 90 { members_.nodeptr_ = nodeptr; return *this; } 91 pointed_node() const92 BOOST_INTRUSIVE_FORCEINLINE node_ptr pointed_node() const 93 { return members_.nodeptr_; } 94 95 public: operator ++()96 BOOST_INTRUSIVE_FORCEINLINE tree_iterator& operator++() 97 { 98 members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); 99 return *this; 100 } 101 operator ++(int)102 tree_iterator operator++(int) 103 { 104 tree_iterator result (*this); 105 members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); 106 return result; 107 } 108 operator --()109 BOOST_INTRUSIVE_FORCEINLINE tree_iterator& operator--() 110 { 111 members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); 112 return *this; 113 } 114 operator --(int)115 tree_iterator operator--(int) 116 { 117 tree_iterator result (*this); 118 members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); 119 return result; 120 } 121 go_left()122 BOOST_INTRUSIVE_FORCEINLINE tree_iterator& go_left() 123 { 124 members_.nodeptr_ = node_traits::get_left(members_.nodeptr_); 125 return *this; 126 } 127 go_right()128 BOOST_INTRUSIVE_FORCEINLINE tree_iterator& go_right() 129 { 130 members_.nodeptr_ = node_traits::get_right(members_.nodeptr_); 131 return *this; 132 } 133 go_parent()134 BOOST_INTRUSIVE_FORCEINLINE tree_iterator& go_parent() 135 { 136 members_.nodeptr_ = node_traits::get_parent(members_.nodeptr_); 137 return *this; 138 } 139 operator unspecified_bool_type() const140 BOOST_INTRUSIVE_FORCEINLINE operator unspecified_bool_type() const 141 { return members_.nodeptr_ ? &tree_iterator::unspecified_bool_type_func : 0; } 142 operator !() const143 BOOST_INTRUSIVE_FORCEINLINE bool operator! () const 144 { return !members_.nodeptr_; } 145 operator ==(const tree_iterator & l,const tree_iterator & r)146 BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const tree_iterator& l, const tree_iterator& r) 147 { return l.pointed_node() == r.pointed_node(); } 148 operator !=(const tree_iterator & l,const tree_iterator & r)149 BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const tree_iterator& l, const tree_iterator& r) 150 { return !(l == r); } 151 operator *() const152 BOOST_INTRUSIVE_FORCEINLINE reference operator*() const 153 { return *operator->(); } 154 operator ->() const155 BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const 156 { return this->operator_arrow(detail::bool_<stateful_value_traits>()); } 157 get_value_traits() const158 BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr get_value_traits() const 159 { return members_.get_ptr(); } 160 end_iterator_from_it() const161 tree_iterator end_iterator_from_it() const 162 { 163 return tree_iterator(node_algorithms::get_header(this->pointed_node()), this->get_value_traits()); 164 } 165 unconst() const166 tree_iterator<value_traits, false> unconst() const 167 { return tree_iterator<value_traits, false>(this->pointed_node(), this->get_value_traits()); } 168 169 private: operator_arrow(detail::false_) const170 BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::false_) const 171 { return ValueTraits::to_value_ptr(members_.nodeptr_); } 172 operator_arrow(detail::true_) const173 BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::true_) const 174 { return this->get_value_traits()->to_value_ptr(members_.nodeptr_); } 175 176 iiterator_members<node_ptr, const_value_traits_ptr, stateful_value_traits> members_; 177 }; 178 179 } //namespace intrusive 180 } //namespace boost 181 182 #include <boost/intrusive/detail/config_end.hpp> 183 184 #endif //BOOST_INTRUSIVE_TREE_ITERATOR_HPP 185