3 // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
37 * @file bin_search_tree_.hpp
38 * Contains an implementation class for bin_search_tree_.
41 * This implementation uses an idea from the SGI STL (using a @a header node
42 * which is needed for efficient iteration).
45 #include <ext/pb_ds/exception.hpp>
46 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
47 #include <ext/pb_ds/detail/types_traits.hpp>
48 #include <ext/pb_ds/detail/debug_map_base.hpp>
49 #include <ext/pb_ds/tree_policy.hpp>
50 #include <ext/pb_ds/detail/cond_dealtor.hpp>
51 #include <ext/pb_ds/detail/type_utils.hpp>
52 #include <ext/pb_ds/detail/tree_trace_base.hpp>
55 #include <debug/debug.h>
62 #define PB_DS_CLASS_T_DEC \
63 template<typename Key, typename Mapped, class Cmp_Fn, \
64 class Node_And_It_Traits, class Allocator>
66 #ifdef PB_DS_DATA_TRUE_INDICATOR
67 #define PB_DS_CLASS_NAME \
71 #ifdef PB_DS_DATA_FALSE_INDICATOR
72 #define PB_DS_CLASS_NAME \
73 bin_search_tree_no_data_
76 #define PB_DS_CLASS_C_DEC \
84 #define PB_DS_TYPES_TRAITS_C_DEC \
92 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
93 debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
94 typename Allocator::template rebind<Key>::other::const_reference>
97 #ifdef PB_DS_DATA_TRUE_INDICATOR
98 #define PB_DS_V2F(X) (X).first
99 #define PB_DS_V2S(X) (X).second
100 #define PB_DS_EP2VP(X)& ((X)->m_value)
103 #ifdef PB_DS_DATA_FALSE_INDICATOR
104 #define PB_DS_V2F(X) (X)
105 #define PB_DS_V2S(X) Mapped_Data()
106 #define PB_DS_EP2VP(X)& ((X)->m_value.first)
109 #ifdef PB_DS_TREE_TRACE
110 #define PB_DS_TREE_TRACE_BASE_C_DEC \
112 typename Node_And_It_Traits::const_node_iterator, \
113 typename Node_And_It_Traits::node_iterator, \
120 * class description = "8i|\|4ree $34rc|-| 7r33 74813.">
122 template<typename Key
,
125 class Node_And_It_Traits
,
127 class PB_DS_CLASS_NAME
:
128 #ifdef _GLIBCXX_DEBUG
129 public PB_DS_DEBUG_MAP_BASE_C_DEC
,
131 #ifdef PB_DS_TREE_TRACE
132 public PB_DS_TREE_TRACE_BASE_C_DEC
,
135 public PB_DS_TYPES_TRAITS_C_DEC
,
136 public Node_And_It_Traits::node_update
141 typename
Allocator::template rebind
<
142 typename
Node_And_It_Traits::node
>::other
145 typedef typename
node_allocator::value_type node
;
147 typedef typename
node_allocator::pointer node_pointer
;
149 typedef PB_DS_TYPES_TRAITS_C_DEC traits_base
;
152 typename
Node_And_It_Traits::null_node_update_pointer
153 null_node_update_pointer
;
156 typedef cond_dealtor
< node
, Allocator
> cond_dealtor_t
;
158 #ifdef _GLIBCXX_DEBUG
159 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base
;
164 typedef typename
Allocator::size_type size_type
;
166 typedef typename
Allocator::difference_type difference_type
;
168 typedef typename
PB_DS_TYPES_TRAITS_C_DEC::key_type key_type
;
170 typedef typename
PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer
;
173 typename
PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
176 typedef typename
PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference
;
179 typename
PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
182 #ifdef PB_DS_DATA_TRUE_INDICATOR
183 typedef typename
PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type
;
186 typename
PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
190 typename
PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
191 const_mapped_pointer
;
194 typename
PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
198 typename
PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
199 const_mapped_reference
;
202 typedef typename
PB_DS_TYPES_TRAITS_C_DEC::value_type value_type
;
204 typedef typename
PB_DS_TYPES_TRAITS_C_DEC::pointer pointer
;
206 typedef typename
PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer
;
208 typedef typename
PB_DS_TYPES_TRAITS_C_DEC::reference reference
;
211 typename
PB_DS_TYPES_TRAITS_C_DEC::const_reference
215 typename
Node_And_It_Traits::const_point_iterator
216 const_point_iterator
;
218 typedef const_point_iterator const_iterator
;
220 typedef typename
Node_And_It_Traits::point_iterator point_iterator
;
222 typedef point_iterator iterator
;
225 typename
Node_And_It_Traits::const_reverse_iterator
226 const_reverse_iterator
;
228 typedef typename
Node_And_It_Traits::reverse_iterator reverse_iterator
;
231 typename
Node_And_It_Traits::const_node_iterator
234 typedef typename
Node_And_It_Traits::node_iterator node_iterator
;
236 typedef Cmp_Fn cmp_fn
;
238 typedef Allocator allocator_type
;
240 typedef typename
Node_And_It_Traits::node_update node_update
;
246 PB_DS_CLASS_NAME(const Cmp_Fn
& r_cmp_fn
);
248 PB_DS_CLASS_NAME(const Cmp_Fn
& r_cmp_fn
, const node_update
& r_update
);
250 PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC
& other
);
253 swap(PB_DS_CLASS_C_DEC
& other
);
272 inline point_iterator
273 lower_bound(const_key_reference r_key
);
275 inline const_point_iterator
276 lower_bound(const_key_reference r_key
) const;
278 inline point_iterator
279 upper_bound(const_key_reference r_key
);
281 inline const_point_iterator
282 upper_bound(const_key_reference r_key
) const;
284 inline point_iterator
285 find(const_key_reference r_key
);
287 inline const_point_iterator
288 find(const_key_reference r_key
) const;
293 inline const_iterator
299 inline const_iterator
302 inline reverse_iterator
305 inline const_reverse_iterator
308 inline reverse_iterator
311 inline const_reverse_iterator
314 inline const_node_iterator
320 inline const_node_iterator
332 value_swap(PB_DS_CLASS_C_DEC
& other
);
335 initialize_min_max();
338 insert_imp_empty(const_reference r_value
);
341 insert_leaf_new(const_reference r_value
, node_pointer p_nd
, bool left_nd
);
344 get_new_node_for_leaf_insert(const_reference r_val
, false_type
);
347 get_new_node_for_leaf_insert(const_reference r_val
, true_type
);
350 actual_erase_node(node_pointer p_nd
);
352 inline std::pair
<node_pointer
, bool>
353 erase(node_pointer p_nd
);
356 update_min_max_for_erased_node(node_pointer p_nd
);
359 clear_imp(node_pointer p_nd
);
364 insert_leaf(const_reference r_value
);
367 rotate_left(node_pointer p_x
);
370 rotate_right(node_pointer p_y
);
373 rotate_parent(node_pointer p_nd
);
376 apply_update(node_pointer p_nd
, null_node_update_pointer
);
378 template<typename Node_Update_
>
380 apply_update(node_pointer p_nd
, Node_Update_
* p_update
);
383 update_to_top(node_pointer p_nd
, null_node_update_pointer
);
385 template<typename Node_Update_
>
387 update_to_top(node_pointer p_nd
, Node_Update_
* p_update
);
390 join_prep(PB_DS_CLASS_C_DEC
& other
);
393 join_finish(PB_DS_CLASS_C_DEC
& other
);
396 split_prep(const_key_reference r_key
, PB_DS_CLASS_C_DEC
& other
);
399 split_finish(PB_DS_CLASS_C_DEC
& other
);
402 recursive_count(node_pointer p_nd
) const;
404 #ifdef _GLIBCXX_DEBUG
406 assert_valid() const;
409 structure_only_assert_valid() const;
412 assert_node_consistent(const node_pointer p_nd
) const;
416 #ifdef _GLIBCXX_DEBUG
418 assert_iterators() const;
421 assert_consistent_with_debug_base() const;
424 assert_node_consistent_with_left(const node_pointer p_nd
) const;
427 assert_node_consistent_with_right(const node_pointer p_nd
) const;
430 assert_consistent_with_debug_base(const node_pointer p_nd
) const;
436 assert_min_imp(const node_pointer p_nd
) const;
442 assert_max_imp(const node_pointer p_nd
) const;
447 typedef std::pair
< const_pointer
, const_pointer
> node_consistent_t
;
450 assert_node_consistent_(const node_pointer p_nd
) const;
457 recursive_copy_node(const node_pointer p_nd
);
460 node_pointer m_p_head
;
464 static node_allocator s_node_allocator
;
467 #include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
468 #include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp>
469 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
470 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
471 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
472 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
473 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
474 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
475 #include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp>
476 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
478 #undef PB_DS_CLASS_C_DEC
480 #undef PB_DS_CLASS_T_DEC
482 #undef PB_DS_CLASS_NAME
484 #undef PB_DS_TYPES_TRAITS_C_DEC
486 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
488 #ifdef PB_DS_TREE_TRACE
489 #undef PB_DS_TREE_TRACE_BASE_C_DEC
496 } // namespace detail
497 } // namespace __gnu_pbds