]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
56 | void unspecified_bool_type_func() const {} | |
57 | typedef void (tree_iterator::*unspecified_bool_type)() const; | |
92f5a8d4 TL |
58 | class nat; |
59 | typedef typename | |
60 | detail::if_c< IsConst | |
61 | , tree_iterator<value_traits, false> | |
62 | , nat>::type nonconst_iterator; | |
7c673cae FG |
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 | ||
71 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator() | |
72 | {} | |
73 | ||
1e59de90 | 74 | BOOST_INTRUSIVE_FORCEINLINE explicit tree_iterator(node_ptr nodeptr, const_value_traits_ptr traits_ptr) |
7c673cae FG |
75 | : members_(nodeptr, traits_ptr) |
76 | {} | |
77 | ||
92f5a8d4 | 78 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator(const tree_iterator &other) |
7c673cae FG |
79 | : members_(other.pointed_node(), other.get_value_traits()) |
80 | {} | |
81 | ||
92f5a8d4 TL |
82 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator(const nonconst_iterator &other) |
83 | : members_(other.pointed_node(), other.get_value_traits()) | |
84 | {} | |
85 | ||
86 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(const tree_iterator &other) | |
87 | { members_.nodeptr_ = other.members_.nodeptr_; return *this; } | |
7c673cae | 88 | |
1e59de90 | 89 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(node_ptr nodeptr) |
92f5a8d4 TL |
90 | { members_.nodeptr_ = nodeptr; return *this; } |
91 | ||
92 | BOOST_INTRUSIVE_FORCEINLINE node_ptr pointed_node() const | |
93 | { return members_.nodeptr_; } | |
7c673cae FG |
94 | |
95 | public: | |
92f5a8d4 | 96 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator& operator++() |
7c673cae FG |
97 | { |
98 | members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); | |
92f5a8d4 | 99 | return *this; |
7c673cae FG |
100 | } |
101 | ||
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 | ||
92f5a8d4 | 109 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator& operator--() |
7c673cae FG |
110 | { |
111 | members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); | |
92f5a8d4 | 112 | return *this; |
7c673cae FG |
113 | } |
114 | ||
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 | ||
122 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator& go_left() | |
123 | { | |
124 | members_.nodeptr_ = node_traits::get_left(members_.nodeptr_); | |
92f5a8d4 | 125 | return *this; |
7c673cae FG |
126 | } |
127 | ||
128 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator& go_right() | |
129 | { | |
130 | members_.nodeptr_ = node_traits::get_right(members_.nodeptr_); | |
92f5a8d4 | 131 | return *this; |
7c673cae FG |
132 | } |
133 | ||
134 | BOOST_INTRUSIVE_FORCEINLINE tree_iterator& go_parent() | |
135 | { | |
136 | members_.nodeptr_ = node_traits::get_parent(members_.nodeptr_); | |
92f5a8d4 | 137 | return *this; |
7c673cae FG |
138 | } |
139 | ||
140 | BOOST_INTRUSIVE_FORCEINLINE operator unspecified_bool_type() const | |
141 | { return members_.nodeptr_ ? &tree_iterator::unspecified_bool_type_func : 0; } | |
142 | ||
143 | BOOST_INTRUSIVE_FORCEINLINE bool operator! () const | |
144 | { return !members_.nodeptr_; } | |
145 | ||
146 | BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const tree_iterator& l, const tree_iterator& r) | |
147 | { return l.pointed_node() == r.pointed_node(); } | |
148 | ||
149 | BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const tree_iterator& l, const tree_iterator& r) | |
150 | { return !(l == r); } | |
151 | ||
152 | BOOST_INTRUSIVE_FORCEINLINE reference operator*() const | |
153 | { return *operator->(); } | |
154 | ||
155 | BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const | |
156 | { return this->operator_arrow(detail::bool_<stateful_value_traits>()); } | |
157 | ||
158 | BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr get_value_traits() const | |
159 | { return members_.get_ptr(); } | |
160 | ||
161 | 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 | ||
166 | tree_iterator<value_traits, false> unconst() const | |
167 | { return tree_iterator<value_traits, false>(this->pointed_node(), this->get_value_traits()); } | |
168 | ||
169 | private: | |
170 | BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::false_) const | |
171 | { return ValueTraits::to_value_ptr(members_.nodeptr_); } | |
172 | ||
173 | 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 |