3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
33 // Permission to use, copy, modify, sell, and distribute this software
34 // is hereby granted without fee, provided that the above copyright
35 // notice appears in all copies, and that both that copyright notice
36 // and this permission notice appear in supporting documentation. None
37 // of the above authors, nor IBM Haifa Research Laboratories, make any
38 // representation about the suitability of this software for any
39 // purpose. It is provided "as is" without express or implied
43 * @file bin_search_tree_.hpp
44 * Contains an implementation class for bin_search_tree_.
47 * This implementation uses an idea from the SGI STL (using a "header" node
48 * which is needed for efficient iteration).
51 #include <ext/pb_ds/exception.hpp>
52 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
53 #include <ext/pb_ds/detail/types_traits.hpp>
54 #include <ext/pb_ds/detail/map_debug_base.hpp>
55 #include <ext/pb_ds/tree_policy.hpp>
56 #include <ext/pb_ds/detail/cond_dealtor.hpp>
57 #include <ext/pb_ds/detail/type_utils.hpp>
58 #include <ext/pb_ds/detail/tree_trace_base.hpp>
61 #include <debug/debug.h>
68 #define PB_DS_CLASS_T_DEC \
69 template<typename Key, typename Mapped, class Cmp_Fn, \
70 class Node_And_It_Traits, class Allocator>
72 #ifdef PB_DS_DATA_TRUE_INDICATOR
73 #define PB_DS_CLASS_NAME \
77 #ifdef PB_DS_DATA_FALSE_INDICATOR
78 #define PB_DS_CLASS_NAME \
79 bin_search_tree_no_data_
82 #define PB_DS_CLASS_C_DEC \
90 #define PB_DS_TYPES_TRAITS_C_DEC \
98 #define PB_DS_MAP_DEBUG_BASE_C_DEC \
99 map_debug_base<Key, eq_by_less<Key, Cmp_Fn>, \
100 typename Allocator::template rebind<Key>::other::const_reference>
103 #ifdef PB_DS_DATA_TRUE_INDICATOR
104 #define PB_DS_V2F(X) (X).first
105 #define PB_DS_V2S(X) (X).second
106 #define PB_DS_EP2VP(X)& ((X)->m_value)
109 #ifdef PB_DS_DATA_FALSE_INDICATOR
110 #define PB_DS_V2F(X) (X)
111 #define PB_DS_V2S(X) Mapped_Data()
112 #define PB_DS_EP2VP(X)& ((X)->m_value.first)
115 #ifdef PB_DS_TREE_TRACE
116 #define PB_DS_TREE_TRACE_BASE_C_DEC \
118 typename Node_And_It_Traits::const_node_iterator, \
119 typename Node_And_It_Traits::node_iterator, \
126 * class description = "8i|\|4ree $34rc|-| 7r33 74813.">
128 template<typename Key,
131 class Node_And_It_Traits,
133 class PB_DS_CLASS_NAME :
134 #ifdef _GLIBCXX_DEBUG
135 public PB_DS_MAP_DEBUG_BASE_C_DEC,
137 #ifdef PB_DS_TREE_TRACE
138 public PB_DS_TREE_TRACE_BASE_C_DEC,
141 public PB_DS_TYPES_TRAITS_C_DEC,
142 public Node_And_It_Traits::node_update
147 typename Allocator::template rebind<
148 typename Node_And_It_Traits::node>::other
151 typedef typename node_allocator::value_type node;
153 typedef typename node_allocator::pointer node_pointer;
155 typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
158 typename Node_And_It_Traits::null_node_update_pointer
159 null_node_update_pointer;
162 typedef cond_dealtor< node, Allocator> cond_dealtor_t;
164 #ifdef _GLIBCXX_DEBUG
165 typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
170 typedef typename Allocator::size_type size_type;
172 typedef typename Allocator::difference_type difference_type;
174 typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
176 typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
179 typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
182 typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
185 typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
188 #ifdef PB_DS_DATA_TRUE_INDICATOR
189 typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
192 typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
196 typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
197 const_mapped_pointer;
200 typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
204 typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
205 const_mapped_reference;
208 typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
210 typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
212 typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
214 typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
217 typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
221 typename Node_And_It_Traits::const_point_iterator
222 const_point_iterator;
224 typedef const_point_iterator const_iterator;
226 typedef typename Node_And_It_Traits::point_iterator point_iterator;
228 typedef point_iterator iterator;
231 typename Node_And_It_Traits::const_reverse_iterator
232 const_reverse_iterator;
234 typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
237 typename Node_And_It_Traits::const_node_iterator
240 typedef typename Node_And_It_Traits::node_iterator node_iterator;
242 typedef Cmp_Fn cmp_fn;
244 typedef Allocator allocator;
246 typedef typename Node_And_It_Traits::node_update node_update;
252 PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
254 PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update);
256 PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
259 swap(PB_DS_CLASS_C_DEC& other);
278 inline point_iterator
279 lower_bound(const_key_reference r_key);
281 inline const_point_iterator
282 lower_bound(const_key_reference r_key) const;
284 inline point_iterator
285 upper_bound(const_key_reference r_key);
287 inline const_point_iterator
288 upper_bound(const_key_reference r_key) const;
290 inline point_iterator
291 find(const_key_reference r_key);
293 inline const_point_iterator
294 find(const_key_reference r_key) const;
299 inline const_iterator
305 inline const_iterator
308 inline reverse_iterator
311 inline const_reverse_iterator
314 inline reverse_iterator
317 inline const_reverse_iterator
320 inline const_node_iterator
326 inline const_node_iterator
338 value_swap(PB_DS_CLASS_C_DEC& other);
341 initialize_min_max();
344 insert_imp_empty(const_reference r_value);
347 insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd);
350 get_new_node_for_leaf_insert(const_reference r_val, false_type);
353 get_new_node_for_leaf_insert(const_reference r_val, true_type);
356 actual_erase_node(node_pointer p_nd);
358 inline std::pair<node_pointer, bool>
359 erase(node_pointer p_nd);
362 update_min_max_for_erased_node(node_pointer p_nd);
365 clear_imp(node_pointer p_nd);
370 insert_leaf(const_reference r_value);
373 rotate_left(node_pointer p_x);
376 rotate_right(node_pointer p_y);
379 rotate_parent(node_pointer p_nd);
382 apply_update(node_pointer p_nd, null_node_update_pointer);
384 template<typename Node_Update_>
386 apply_update(node_pointer p_nd, Node_Update_* p_update);
389 update_to_top(node_pointer p_nd, null_node_update_pointer);
391 template<typename Node_Update_>
393 update_to_top(node_pointer p_nd, Node_Update_* p_update);
396 join_prep(PB_DS_CLASS_C_DEC& other);
399 join_finish(PB_DS_CLASS_C_DEC& other);
402 split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
405 split_finish(PB_DS_CLASS_C_DEC& other);
408 recursive_count(node_pointer p_nd) const;
410 #ifdef _GLIBCXX_DEBUG
412 assert_valid() const;
415 structure_only_assert_valid() const;
418 assert_node_consistent(const node_pointer p_nd) const;
422 #ifdef _GLIBCXX_DEBUG
424 assert_iterators() const;
427 assert_consistent_with_debug_base() const;
430 assert_node_consistent_with_left(const node_pointer p_nd) const;
433 assert_node_consistent_with_right(const node_pointer p_nd) const;
436 assert_consistent_with_debug_base(const node_pointer p_nd) const;
442 assert_min_imp(const node_pointer p_nd) const;
448 assert_max_imp(const node_pointer p_nd) const;
453 typedef std::pair< const_pointer, const_pointer> node_consistent_t;
456 assert_node_consistent_(const node_pointer p_nd) const;
463 recursive_copy_node(const node_pointer p_nd);
466 node_pointer m_p_head;
470 static node_allocator s_node_allocator;
473 #include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
474 #include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp>
475 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
476 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
477 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
478 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
479 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
480 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
481 #include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp>
482 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
484 #undef PB_DS_CLASS_C_DEC
486 #undef PB_DS_CLASS_T_DEC
488 #undef PB_DS_CLASS_NAME
490 #undef PB_DS_TYPES_TRAITS_C_DEC
492 #undef PB_DS_MAP_DEBUG_BASE_C_DEC
494 #ifdef PB_DS_TREE_TRACE
495 #undef PB_DS_TREE_TRACE_BASE_C_DEC
502 } // namespace detail