1// -*- C++ -*-
2
3// Copyright (C) 2005-2014 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
48namespace __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