libstdc++
bin_search_tree_.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2020 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 
55 namespace __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::true_type
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:75
std::false_type
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:78
std::end
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
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::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