1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2007, 2009, 2010 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10 
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 // General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26 
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
34 // warranty.
35 
36 /**
37  * @file ov_tree_map_/node_iterators.hpp
38  * Contains an implementation class for ov_tree_.
39  */
40 
41 #ifndef PB_DS_OV_TREE_NODE_ITERATORS_HPP
42 #define PB_DS_OV_TREE_NODE_ITERATORS_HPP
43 
44 #include <ext/pb_ds/tag_and_trait.hpp>
45 #include <ext/pb_ds/detail/type_utils.hpp>
46 #include <debug/debug.h>
47 
48 namespace __gnu_pbds
49 {
50   namespace detail
51   {
52 #define PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC	\
53     ov_tree_node_const_it_<Value_Type, Metadata_Type, _Alloc>
54 
55     /// Const node reference.
56     template<typename Value_Type, typename Metadata_Type, typename _Alloc>
57     class ov_tree_node_const_it_
58     {
59 
60     protected:
61       typedef
62       typename _Alloc::template rebind<
63       Value_Type>::other::pointer
64       pointer;
65 
66       typedef
67       typename _Alloc::template rebind<
68 	Value_Type>::other::const_pointer
69       const_pointer;
70 
71       typedef
72       typename _Alloc::template rebind<
73 	Metadata_Type>::other::const_pointer
74       const_metadata_pointer;
75 
76       typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC this_type;
77 
78     protected:
79 
80       template<typename Ptr>
81       inline static Ptr
82       mid_pointer(Ptr p_begin, Ptr p_end)
83       {
84 	_GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
85 	return (p_begin + (p_end - p_begin) / 2);
86       }
87 
88     public:
89 
90       typedef trivial_iterator_tag iterator_category;
91 
92       typedef trivial_iterator_difference_type difference_type;
93 
94       typedef
95       typename _Alloc::template rebind<
96 	Value_Type>::other::const_pointer
97       value_type;
98 
99       typedef
100       typename _Alloc::template rebind<
101 	typename remove_const<
102 	Value_Type>::type>::other::const_pointer
103       reference;
104 
105       typedef
106       typename _Alloc::template rebind<
107 	typename remove_const<
108 	Value_Type>::type>::other::const_pointer
109       const_reference;
110 
111       typedef Metadata_Type metadata_type;
112 
113       typedef
114       typename _Alloc::template rebind<
115 	metadata_type>::other::const_reference
116       metadata_const_reference;
117 
118     public:
119       inline
120       ov_tree_node_const_it_(const_pointer p_nd = 0,  const_pointer p_begin_nd = 0,  const_pointer p_end_nd = 0,  const_metadata_pointer p_metadata = 0) : m_p_value(const_cast<pointer>(p_nd)), m_p_begin_value(const_cast<pointer>(p_begin_nd)), m_p_end_value(const_cast<pointer>(p_end_nd)), m_p_metadata(p_metadata)
121       { }
122 
123       inline const_reference
124       operator*() const
125       { return m_p_value; }
126 
127       inline metadata_const_reference
128       get_metadata() const
129       {
130 	enum
131 	  {
132 	    has_metadata = !is_same<Metadata_Type, null_type>::value
133 	  };
134 
135 	PB_DS_STATIC_ASSERT(should_have_metadata, has_metadata);
136 	_GLIBCXX_DEBUG_ASSERT(m_p_metadata != 0);
137 	return *m_p_metadata;
138       }
139 
140       /// Returns the node iterator associated with the left node.
141       inline this_type
142       get_l_child() const
143       {
144 	if (m_p_begin_value == m_p_value)
145 	  return (this_type(m_p_begin_value, m_p_begin_value, m_p_begin_value));
146 
147 	const_metadata_pointer p_begin_metadata =
148 	  m_p_metadata - (m_p_value - m_p_begin_value);
149 
150 	return (this_type(mid_pointer(m_p_begin_value, m_p_value),
151 			  m_p_begin_value,
152 			  m_p_value,
153 			  mid_pointer(p_begin_metadata, m_p_metadata)));
154       }
155 
156       /// Returns the node iterator associated with the right node.
157       inline this_type
158       get_r_child() const
159       {
160 	if (m_p_value == m_p_end_value)
161 	  return (this_type(m_p_end_value, m_p_end_value, m_p_end_value));
162 
163 	const_metadata_pointer p_end_metadata =
164 	  m_p_metadata + (m_p_end_value - m_p_value);
165 
166 	return (this_type(mid_pointer(m_p_value + 1, m_p_end_value),
167 			  m_p_value + 1,
168 			  m_p_end_value,(m_p_metadata == 0) ?
169 			  0 : mid_pointer(m_p_metadata + 1, p_end_metadata)));
170       }
171 
172       inline bool
173       operator==(const this_type& other) const
174       {
175 	const bool is_end = m_p_begin_value == m_p_end_value;
176 	const bool is_other_end = other.m_p_begin_value == other.m_p_end_value;
177 
178 	if (is_end)
179 	  return (is_other_end);
180 
181 	if (is_other_end)
182 	  return (is_end);
183 
184 	return m_p_value == other.m_p_value;
185       }
186 
187       inline bool
188       operator!=(const this_type& other) const
189       { return !operator==(other); }
190 
191     public:
192       pointer m_p_value;
193       pointer m_p_begin_value;
194       pointer m_p_end_value;
195 
196       const_metadata_pointer m_p_metadata;
197     };
198 
199 #define PB_DS_OV_TREE_NODE_ITERATOR_C_DEC \
200     ov_tree_node_it_<Value_Type, Metadata_Type, _Alloc>
201 
202     /// Node reference.
203     template<typename Value_Type, typename Metadata_Type, typename _Alloc>
204     class ov_tree_node_it_ : public PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
205     {
206     private:
207       typedef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC this_type;
208 
209       typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC base_type;
210 
211       typedef typename base_type::pointer pointer;
212 
213       typedef typename base_type::const_pointer const_pointer;
214 
215       typedef
216       typename base_type::const_metadata_pointer
217       const_metadata_pointer;
218 
219     public:
220       typedef trivial_iterator_tag iterator_category;
221 
222       typedef trivial_iterator_difference_type difference_type;
223 
224       typedef
225       typename _Alloc::template rebind<
226 	Value_Type>::other::pointer
227       value_type;
228 
229       typedef
230       typename _Alloc::template rebind<
231 	typename remove_const<
232 	Value_Type>::type>::other::pointer
233       reference;
234 
235       typedef
236       typename _Alloc::template rebind<
237 	typename remove_const<
238 	Value_Type>::type>::other::pointer
239       const_reference;
240 
241       inline
242       ov_tree_node_it_(const_pointer p_nd = 0,  const_pointer p_begin_nd = 0,  const_pointer p_end_nd = 0,  const_metadata_pointer p_metadata = 0) : base_type(p_nd,  p_begin_nd,  p_end_nd,  p_metadata)
243       { }
244 
245       /// Access.
246       inline reference
247       operator*() const
248       { return reference(base_type::m_p_value); }
249 
250       /// Returns the node reference associated with the left node.
251       inline ov_tree_node_it_
252       get_l_child() const
253       {
254 	if (base_type::m_p_begin_value == base_type::m_p_value)
255 	  return (this_type(base_type::m_p_begin_value,  base_type::m_p_begin_value,  base_type::m_p_begin_value));
256 
257 	const_metadata_pointer p_begin_metadata =
258 	  base_type::m_p_metadata - (base_type::m_p_value - base_type::m_p_begin_value);
259 
260 	return (this_type(base_type::mid_pointer(base_type::m_p_begin_value, base_type::m_p_value),
261 			  base_type::m_p_begin_value,
262 			  base_type::m_p_value,
263 			  base_type::mid_pointer(p_begin_metadata, base_type::m_p_metadata)));
264       }
265 
266       /// Returns the node reference associated with the right node.
267       inline ov_tree_node_it_
268       get_r_child() const
269       {
270 	if (base_type::m_p_value == base_type::m_p_end_value)
271 	  return this_type(base_type::m_p_end_value, base_type::m_p_end_value,
272 			   base_type::m_p_end_value);
273 
274 	const_metadata_pointer p_end_metadata =
275 	  base_type::m_p_metadata + (base_type::m_p_end_value - base_type::m_p_value);
276 
277 	return (this_type(base_type::mid_pointer(base_type::m_p_value + 1, base_type::m_p_end_value),
278 			  base_type::m_p_value + 1,
279 			  base_type::m_p_end_value,(base_type::m_p_metadata == 0)?
280 			  0 : base_type::mid_pointer(base_type::m_p_metadata + 1, p_end_metadata)));
281       }
282 
283     };
284 
285 #undef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC
286 #undef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
287 
288 } // namespace detail
289 } // namespace __gnu_pbds
290 
291 #endif
292