libstdc++
bin_search_tree_.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2021 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 bin_search_tree_/bin_search_tree_.hpp
38 * Contains an implementation class for binary search tree.
39 */
40
41#include <ext/pb_ds/exception.hpp>
42#include <ext/pb_ds/tree_policy.hpp>
43#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
44#include <ext/pb_ds/detail/types_traits.hpp>
45#include <ext/pb_ds/detail/cond_dealtor.hpp>
46#include <ext/pb_ds/detail/type_utils.hpp>
47#include <ext/pb_ds/detail/tree_trace_base.hpp>
48#ifdef _GLIBCXX_DEBUG
49#include <ext/pb_ds/detail/debug_map_base.hpp>
50#endif
51#include <utility>
52#include <functional>
53#include <debug/debug.h>
54
55namespace __gnu_pbds
56{
57 namespace detail
58 {
59#ifdef PB_DS_DATA_TRUE_INDICATOR
60#define PB_DS_BIN_TREE_NAME bin_search_tree_map
61#endif
62
63#ifdef PB_DS_DATA_FALSE_INDICATOR
64#define PB_DS_BIN_TREE_NAME bin_search_tree_set
65#endif
66
67#define PB_DS_CLASS_T_DEC \
68 template<typename Key, typename Mapped, typename Cmp_Fn, \
69 typename Node_And_It_Traits, typename _Alloc>
70
71#define PB_DS_CLASS_C_DEC \
72 PB_DS_BIN_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
73
74#define PB_DS_BIN_TREE_TRAITS_BASE \
75 types_traits<Key, Mapped, _Alloc, false>
76
77#ifdef _GLIBCXX_DEBUG
78#define PB_DS_DEBUG_MAP_BASE_C_DEC \
79 debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
80 typename rebind_traits<_Alloc, Key>::const_reference>
81#endif
82
83#ifdef PB_DS_TREE_TRACE
84#define PB_DS_TREE_TRACE_BASE_C_DEC \
85 tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \
86 typename Node_And_It_Traits::node_iterator, \
87 Cmp_Fn, true, _Alloc>
88#endif
89
90
91 /*
92 * @brief Binary search tree (BST).
93 *
94 * This implementation uses an idea from the SGI STL (using a @a
95 * header node which is needed for efficient iteration).
96 */
97 template<typename Key, typename Mapped, typename Cmp_Fn,
98 typename Node_And_It_Traits, typename _Alloc>
99 class PB_DS_BIN_TREE_NAME :
100#ifdef _GLIBCXX_DEBUG
101 public PB_DS_DEBUG_MAP_BASE_C_DEC,
102#endif
103#ifdef PB_DS_TREE_TRACE
104 public PB_DS_TREE_TRACE_BASE_C_DEC,
105#endif
106 public Cmp_Fn,
107 public PB_DS_BIN_TREE_TRAITS_BASE,
108 public Node_And_It_Traits::node_update
109 {
110 typedef Node_And_It_Traits traits_type;
111 typedef rebind_traits<_Alloc, typename traits_type::node>
112 node_alloc_traits;
113
114 protected:
115 typedef PB_DS_BIN_TREE_TRAITS_BASE traits_base;
116
117 typedef
118 typename node_alloc_traits::allocator_type node_allocator;
119
120 typedef typename node_alloc_traits::value_type node;
121 typedef typename node_alloc_traits::pointer node_pointer;
122
123 typedef typename traits_type::null_node_update_pointer
124 null_node_update_pointer;
125
126 private:
127 typedef cond_dealtor<node, _Alloc> cond_dealtor_t;
128
129#ifdef _GLIBCXX_DEBUG
130 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
131#endif
132
133 public:
134 typedef typename _Alloc::size_type size_type;
135 typedef typename _Alloc::difference_type difference_type;
136 typedef typename traits_base::key_type key_type;
137 typedef typename traits_base::key_pointer key_pointer;
138 typedef typename traits_base::key_const_pointer key_const_pointer;
139 typedef typename traits_base::key_reference key_reference;
140 typedef typename traits_base::key_const_reference key_const_reference;
141
142#ifdef PB_DS_DATA_TRUE_INDICATOR
143 typedef typename traits_base::mapped_type mapped_type;
144 typedef typename traits_base::mapped_pointer mapped_pointer;
145 typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
146 typedef typename traits_base::mapped_reference mapped_reference;
147 typedef typename traits_base::mapped_const_reference mapped_const_reference;
148#endif
149
150 typedef typename traits_base::value_type value_type;
151 typedef typename traits_base::pointer pointer;
152 typedef typename traits_base::const_pointer const_pointer;
153 typedef typename traits_base::reference reference;
154 typedef typename traits_base::const_reference const_reference;
155 typedef typename traits_type::point_const_iterator point_const_iterator;
156
157 typedef point_const_iterator const_iterator;
158 typedef typename traits_type::point_iterator point_iterator;
159 typedef point_iterator iterator;
160
161 typedef typename traits_type::const_reverse_iterator const_reverse_iterator;
162
163 typedef typename traits_type::reverse_iterator reverse_iterator;
164 typedef typename traits_type::node_const_iterator node_const_iterator;
165 typedef typename traits_type::node_iterator node_iterator;
166 typedef typename traits_type::node_update node_update;
167
168 typedef Cmp_Fn cmp_fn;
169 typedef _Alloc allocator_type;
170
171 PB_DS_BIN_TREE_NAME();
172
173 PB_DS_BIN_TREE_NAME(const Cmp_Fn&);
174
175 PB_DS_BIN_TREE_NAME(const Cmp_Fn&, const node_update&);
176
177 PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC&);
178
179 void
180 swap(PB_DS_CLASS_C_DEC&);
181
182 ~PB_DS_BIN_TREE_NAME();
183
184 inline bool
185 empty() const;
186
187 inline size_type
188 size() const;
189
190 inline size_type
191 max_size() const;
192
193 Cmp_Fn&
194 get_cmp_fn();
195
196 const Cmp_Fn&
197 get_cmp_fn() const;
198
199 inline point_iterator
200 lower_bound(key_const_reference);
201
202 inline point_const_iterator
203 lower_bound(key_const_reference) const;
204
205 inline point_iterator
206 upper_bound(key_const_reference);
207
208 inline point_const_iterator
209 upper_bound(key_const_reference) const;
210
211 inline point_iterator
212 find(key_const_reference);
213
214 inline point_const_iterator
215 find(key_const_reference) const;
216
217 inline iterator
218 begin();
219
220 inline const_iterator
221 begin() const;
222
223 inline iterator
224 end();
225
226 inline const_iterator
227 end() const;
228
229 inline reverse_iterator
230 rbegin();
231
232 inline const_reverse_iterator
233 rbegin() const;
234
235 inline reverse_iterator
236 rend();
237
238 inline const_reverse_iterator
239 rend() const;
240
241 /// Returns a const node_iterator corresponding to the node at the
242 /// root of the tree.
243 inline node_const_iterator
244 node_begin() const;
245
246 /// Returns a node_iterator corresponding to the node at the
247 /// root of the tree.
248 inline node_iterator
249 node_begin();
250
251 /// Returns a const node_iterator corresponding to a node just
252 /// after a leaf of the tree.
253 inline node_const_iterator
254 node_end() const;
255
256 /// Returns a node_iterator corresponding to a node just
257 /// after a leaf of the tree.
258 inline node_iterator
259 node_end();
260
261 void
262 clear();
263
264 protected:
265 void
266 value_swap(PB_DS_CLASS_C_DEC&);
267
268 void
269 initialize_min_max();
270
271 inline iterator
272 insert_imp_empty(const_reference);
273
274 inline iterator
275 insert_leaf_new(const_reference, node_pointer, bool);
276
277 inline node_pointer
278 get_new_node_for_leaf_insert(const_reference, false_type);
279
280 inline node_pointer
281 get_new_node_for_leaf_insert(const_reference, true_type);
282
283 inline void
284 actual_erase_node(node_pointer);
285
286 inline std::pair<node_pointer, bool>
287 erase(node_pointer);
288
289 inline void
290 update_min_max_for_erased_node(node_pointer);
291
292 static void
293 clear_imp(node_pointer);
294
295 inline std::pair<point_iterator, bool>
296 insert_leaf(const_reference);
297
298 inline void
299 rotate_left(node_pointer);
300
301 inline void
302 rotate_right(node_pointer);
303
304 inline void
305 rotate_parent(node_pointer);
306
307 inline void
308 apply_update(node_pointer, null_node_update_pointer);
309
310 template<typename Node_Update_>
311 inline void
312 apply_update(node_pointer, Node_Update_*);
313
314 inline void
315 update_to_top(node_pointer, null_node_update_pointer);
316
317 template<typename Node_Update_>
318 inline void
319 update_to_top(node_pointer, Node_Update_*);
320
321 bool
322 join_prep(PB_DS_CLASS_C_DEC&);
323
324 void
325 join_finish(PB_DS_CLASS_C_DEC&);
326
327 bool
328 split_prep(key_const_reference, PB_DS_CLASS_C_DEC&);
329
330 void
331 split_finish(PB_DS_CLASS_C_DEC&);
332
333 size_type
334 recursive_count(node_pointer) const;
335
336#ifdef _GLIBCXX_DEBUG
337 void
338 assert_valid(const char*, int) const;
339
340 void
341 structure_only_assert_valid(const char*, int) const;
342
343 void
344 assert_node_consistent(const node_pointer, const char*, int) const;
345#endif
346
347 private:
348#ifdef _GLIBCXX_DEBUG
349 void
350 assert_iterators(const char*, int) const;
351
352 void
353 assert_consistent_with_debug_base(const char*, int) const;
354
355 void
356 assert_node_consistent_with_left(const node_pointer,
357 const char*, int) const;
358
359 void
360 assert_node_consistent_with_right(const node_pointer,
361 const char*, int) const;
362
363 void
364 assert_consistent_with_debug_base(const node_pointer,
365 const char*, int) const;
366
367 void
368 assert_min(const char*, int) const;
369
370 void
371 assert_min_imp(const node_pointer, const char*, int) const;
372
373 void
374 assert_max(const char*, int) const;
375
376 void
377 assert_max_imp(const node_pointer, const char*, int) const;
378
379 void
380 assert_size(const char*, int) const;
381
382 typedef std::pair<const_pointer, const_pointer> node_consistent_t;
383
384 node_consistent_t
385 assert_node_consistent_(const node_pointer, const char*, int) const;
386#endif
387
388 void
389 initialize();
390
391 node_pointer
392 recursive_copy_node(const node_pointer);
393
394 protected:
395 node_pointer m_p_head;
396 size_type m_size;
397 static node_allocator s_node_allocator;
398 };
399
400#define PB_DS_STRUCT_ONLY_ASSERT_VALID(X) \
401 _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);)
402
403#define PB_DS_ASSERT_NODE_CONSISTENT(_Node) \
404 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, __FILE__, __LINE__);)
405
406#include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
407#include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp>
408#include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
409#include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
410#include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
411#include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
412#include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
413#include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
414#include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp>
415#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
416
417#undef PB_DS_ASSERT_NODE_CONSISTENT
418#undef PB_DS_STRUCT_ONLY_ASSERT_VALID
419#undef PB_DS_CLASS_C_DEC
420#undef PB_DS_CLASS_T_DEC
421#undef PB_DS_BIN_TREE_NAME
422#undef PB_DS_BIN_TREE_TRAITS_BASE
423#undef PB_DS_DEBUG_MAP_BASE_C_DEC
424
425#ifdef PB_DS_TREE_TRACE
426#undef PB_DS_TREE_TRACE_BASE_C_DEC
427#endif
428 } // namespace detail
429} // namespace __gnu_pbds
std::swap
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:428
std::end
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1239
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1217
std::rend
constexpr auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
Definition: range_access.h:161
std::empty
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:263
std::size
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:245
std::rbegin
constexpr auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
Definition: range_access.h:141
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition: assoc_container.hpp:52
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213