libstdc++
ov_tree_map_/node_iterators.hpp
Go to the documentation of this file.
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 
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>
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 
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:
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