]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2005, 2006 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 2, 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 | // 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. | |
20 | ||
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 | |
29 | // Public License. | |
30 | ||
31 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
32 | ||
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 | |
40 | // warranty. | |
41 | ||
42 | /** | |
43 | * @file bin_search_tree_.hpp | |
44 | * Contains an implementation class for bin_search_tree_. | |
45 | */ | |
46 | /* | |
47 | * This implementation uses an idea from the SGI STL (using a "header" node | |
48 | * which is needed for efficient iteration). | |
49 | */ | |
50 | ||
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> | |
551fe1a2 | 54 | #include <ext/pb_ds/detail/debug_map_base.hpp> |
4569a895 AT |
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> | |
59 | #include <utility> | |
60 | #include <functional> | |
47bea7b8 | 61 | #include <debug/debug.h> |
4569a895 AT |
62 | |
63 | namespace pb_ds | |
64 | { | |
65 | namespace detail | |
66 | { | |
67 | ||
4569a895 | 68 | #define PB_DS_CLASS_T_DEC \ |
47bea7b8 BK |
69 | template<typename Key, typename Mapped, class Cmp_Fn, \ |
70 | class Node_And_It_Traits, class Allocator> | |
4569a895 AT |
71 | |
72 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
73 | #define PB_DS_CLASS_NAME \ | |
74 | bin_search_tree_data_ | |
47bea7b8 | 75 | #endif |
4569a895 AT |
76 | |
77 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
78 | #define PB_DS_CLASS_NAME \ | |
79 | bin_search_tree_no_data_ | |
47bea7b8 | 80 | #endif |
4569a895 AT |
81 | |
82 | #define PB_DS_CLASS_C_DEC \ | |
83 | PB_DS_CLASS_NAME< \ | |
84 | Key, \ | |
85 | Mapped, \ | |
86 | Cmp_Fn, \ | |
87 | Node_And_It_Traits, \ | |
88 | Allocator> | |
89 | ||
90 | #define PB_DS_TYPES_TRAITS_C_DEC \ | |
91 | types_traits< \ | |
92 | Key, \ | |
93 | Mapped, \ | |
94 | Allocator, \ | |
95 | false> | |
96 | ||
47bea7b8 | 97 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 BK |
98 | #define PB_DS_DEBUG_MAP_BASE_C_DEC \ |
99 | debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \ | |
47bea7b8 BK |
100 | typename Allocator::template rebind<Key>::other::const_reference> |
101 | #endif | |
4569a895 AT |
102 | |
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) | |
47bea7b8 | 107 | #endif |
4569a895 AT |
108 | |
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) | |
47bea7b8 | 113 | #endif |
4569a895 AT |
114 | |
115 | #ifdef PB_DS_TREE_TRACE | |
116 | #define PB_DS_TREE_TRACE_BASE_C_DEC \ | |
117 | tree_trace_base< \ | |
118 | typename Node_And_It_Traits::const_node_iterator, \ | |
119 | typename Node_And_It_Traits::node_iterator, \ | |
120 | Cmp_Fn, \ | |
121 | true, \ | |
122 | Allocator> | |
47bea7b8 | 123 | #endif |
4569a895 AT |
124 | |
125 | /** | |
126 | * class description = "8i|\|4ree $34rc|-| 7r33 74813."> | |
127 | **/ | |
128 | template<typename Key, | |
129 | typename Mapped, | |
130 | class Cmp_Fn, | |
131 | class Node_And_It_Traits, | |
132 | class Allocator> | |
133 | class PB_DS_CLASS_NAME : | |
47bea7b8 | 134 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 | 135 | public PB_DS_DEBUG_MAP_BASE_C_DEC, |
47bea7b8 | 136 | #endif |
4569a895 AT |
137 | #ifdef PB_DS_TREE_TRACE |
138 | public PB_DS_TREE_TRACE_BASE_C_DEC, | |
47bea7b8 | 139 | #endif |
4569a895 AT |
140 | public Cmp_Fn, |
141 | public PB_DS_TYPES_TRAITS_C_DEC, | |
142 | public Node_And_It_Traits::node_update | |
143 | { | |
144 | ||
145 | protected: | |
146 | typedef | |
147 | typename Allocator::template rebind< | |
148 | typename Node_And_It_Traits::node>::other | |
149 | node_allocator; | |
150 | ||
151 | typedef typename node_allocator::value_type node; | |
152 | ||
153 | typedef typename node_allocator::pointer node_pointer; | |
154 | ||
155 | typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; | |
156 | ||
157 | typedef | |
158 | typename Node_And_It_Traits::null_node_update_pointer | |
159 | null_node_update_pointer; | |
160 | ||
161 | private: | |
162 | typedef cond_dealtor< node, Allocator> cond_dealtor_t; | |
163 | ||
47bea7b8 | 164 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 | 165 | typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; |
47bea7b8 | 166 | #endif |
4569a895 AT |
167 | |
168 | public: | |
169 | ||
170 | typedef typename Allocator::size_type size_type; | |
171 | ||
172 | typedef typename Allocator::difference_type difference_type; | |
173 | ||
174 | typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type; | |
175 | ||
176 | typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer; | |
177 | ||
178 | typedef | |
179 | typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer | |
180 | const_key_pointer; | |
181 | ||
182 | typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference; | |
183 | ||
184 | typedef | |
185 | typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference | |
186 | const_key_reference; | |
187 | ||
188 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
4569a895 AT |
189 | typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type; |
190 | ||
191 | typedef | |
192 | typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer | |
193 | mapped_pointer; | |
194 | ||
195 | typedef | |
196 | typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer | |
197 | const_mapped_pointer; | |
198 | ||
199 | typedef | |
200 | typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference | |
201 | mapped_reference; | |
202 | ||
203 | typedef | |
204 | typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference | |
205 | const_mapped_reference; | |
47bea7b8 | 206 | #endif |
4569a895 AT |
207 | |
208 | typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type; | |
209 | ||
210 | typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer; | |
211 | ||
212 | typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer; | |
213 | ||
214 | typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference; | |
215 | ||
216 | typedef | |
217 | typename PB_DS_TYPES_TRAITS_C_DEC::const_reference | |
218 | const_reference; | |
219 | ||
220 | typedef | |
221 | typename Node_And_It_Traits::const_point_iterator | |
222 | const_point_iterator; | |
223 | ||
224 | typedef const_point_iterator const_iterator; | |
225 | ||
226 | typedef typename Node_And_It_Traits::point_iterator point_iterator; | |
227 | ||
228 | typedef point_iterator iterator; | |
229 | ||
230 | typedef | |
231 | typename Node_And_It_Traits::const_reverse_iterator | |
232 | const_reverse_iterator; | |
233 | ||
234 | typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator; | |
235 | ||
236 | typedef | |
237 | typename Node_And_It_Traits::const_node_iterator | |
238 | const_node_iterator; | |
239 | ||
240 | typedef typename Node_And_It_Traits::node_iterator node_iterator; | |
241 | ||
242 | typedef Cmp_Fn cmp_fn; | |
243 | ||
244 | typedef Allocator allocator; | |
245 | ||
246 | typedef typename Node_And_It_Traits::node_update node_update; | |
247 | ||
248 | public: | |
249 | ||
250 | PB_DS_CLASS_NAME(); | |
251 | ||
252 | PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn); | |
253 | ||
254 | PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update); | |
255 | ||
256 | PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); | |
257 | ||
258 | void | |
259 | swap(PB_DS_CLASS_C_DEC& other); | |
260 | ||
261 | ~PB_DS_CLASS_NAME(); | |
262 | ||
263 | inline bool | |
264 | empty() const; | |
265 | ||
266 | inline size_type | |
267 | size() const; | |
268 | ||
269 | inline size_type | |
270 | max_size() const; | |
271 | ||
272 | Cmp_Fn& | |
273 | get_cmp_fn(); | |
274 | ||
275 | const Cmp_Fn& | |
276 | get_cmp_fn() const; | |
277 | ||
278 | inline point_iterator | |
279 | lower_bound(const_key_reference r_key); | |
280 | ||
281 | inline const_point_iterator | |
282 | lower_bound(const_key_reference r_key) const; | |
283 | ||
284 | inline point_iterator | |
285 | upper_bound(const_key_reference r_key); | |
286 | ||
287 | inline const_point_iterator | |
288 | upper_bound(const_key_reference r_key) const; | |
289 | ||
290 | inline point_iterator | |
291 | find(const_key_reference r_key); | |
292 | ||
293 | inline const_point_iterator | |
294 | find(const_key_reference r_key) const; | |
295 | ||
296 | inline iterator | |
297 | begin(); | |
298 | ||
299 | inline const_iterator | |
300 | begin() const; | |
301 | ||
302 | inline iterator | |
303 | end(); | |
304 | ||
305 | inline const_iterator | |
306 | end() const; | |
307 | ||
308 | inline reverse_iterator | |
309 | rbegin(); | |
310 | ||
311 | inline const_reverse_iterator | |
312 | rbegin() const; | |
313 | ||
314 | inline reverse_iterator | |
315 | rend(); | |
316 | ||
317 | inline const_reverse_iterator | |
318 | rend() const; | |
319 | ||
320 | inline const_node_iterator | |
321 | node_begin() const; | |
322 | ||
323 | inline node_iterator | |
324 | node_begin(); | |
325 | ||
326 | inline const_node_iterator | |
327 | node_end() const; | |
328 | ||
329 | inline node_iterator | |
330 | node_end(); | |
331 | ||
332 | void | |
333 | clear(); | |
334 | ||
335 | protected: | |
336 | ||
337 | void | |
338 | value_swap(PB_DS_CLASS_C_DEC& other); | |
339 | ||
340 | void | |
341 | initialize_min_max(); | |
342 | ||
343 | inline iterator | |
344 | insert_imp_empty(const_reference r_value); | |
345 | ||
346 | inline iterator | |
347 | insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd); | |
348 | ||
349 | inline node_pointer | |
350 | get_new_node_for_leaf_insert(const_reference r_val, false_type); | |
351 | ||
352 | inline node_pointer | |
353 | get_new_node_for_leaf_insert(const_reference r_val, true_type); | |
354 | ||
355 | inline void | |
356 | actual_erase_node(node_pointer p_nd); | |
357 | ||
358 | inline std::pair<node_pointer, bool> | |
359 | erase(node_pointer p_nd); | |
360 | ||
361 | inline void | |
362 | update_min_max_for_erased_node(node_pointer p_nd); | |
363 | ||
364 | static void | |
365 | clear_imp(node_pointer p_nd); | |
366 | ||
367 | inline std::pair< | |
368 | point_iterator, | |
369 | bool> | |
370 | insert_leaf(const_reference r_value); | |
371 | ||
372 | inline void | |
373 | rotate_left(node_pointer p_x); | |
374 | ||
375 | inline void | |
376 | rotate_right(node_pointer p_y); | |
377 | ||
378 | inline void | |
379 | rotate_parent(node_pointer p_nd); | |
380 | ||
381 | inline void | |
382 | apply_update(node_pointer p_nd, null_node_update_pointer); | |
383 | ||
384 | template<typename Node_Update_> | |
385 | inline void | |
386 | apply_update(node_pointer p_nd, Node_Update_* p_update); | |
387 | ||
388 | inline void | |
389 | update_to_top(node_pointer p_nd, null_node_update_pointer); | |
390 | ||
391 | template<typename Node_Update_> | |
392 | inline void | |
393 | update_to_top(node_pointer p_nd, Node_Update_* p_update); | |
394 | ||
395 | bool | |
396 | join_prep(PB_DS_CLASS_C_DEC& other); | |
397 | ||
398 | void | |
399 | join_finish(PB_DS_CLASS_C_DEC& other); | |
400 | ||
401 | bool | |
402 | split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other); | |
403 | ||
404 | void | |
405 | split_finish(PB_DS_CLASS_C_DEC& other); | |
406 | ||
407 | size_type | |
408 | recursive_count(node_pointer p_nd) const; | |
409 | ||
47bea7b8 | 410 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
411 | void |
412 | assert_valid() const; | |
413 | ||
414 | void | |
415 | structure_only_assert_valid() const; | |
416 | ||
417 | void | |
418 | assert_node_consistent(const node_pointer p_nd) const; | |
47bea7b8 | 419 | #endif |
4569a895 AT |
420 | |
421 | private: | |
47bea7b8 | 422 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
423 | void |
424 | assert_iterators() const; | |
425 | ||
426 | void | |
427 | assert_consistent_with_debug_base() const; | |
428 | ||
429 | void | |
430 | assert_node_consistent_with_left(const node_pointer p_nd) const; | |
431 | ||
432 | void | |
433 | assert_node_consistent_with_right(const node_pointer p_nd) const; | |
434 | ||
435 | void | |
436 | assert_consistent_with_debug_base(const node_pointer p_nd) const; | |
437 | ||
438 | void | |
439 | assert_min() const; | |
440 | ||
441 | void | |
442 | assert_min_imp(const node_pointer p_nd) const; | |
443 | ||
444 | void | |
445 | assert_max() const; | |
446 | ||
447 | void | |
448 | assert_max_imp(const node_pointer p_nd) const; | |
449 | ||
450 | void | |
451 | assert_size() const; | |
452 | ||
453 | typedef std::pair< const_pointer, const_pointer> node_consistent_t; | |
454 | ||
455 | node_consistent_t | |
456 | assert_node_consistent_(const node_pointer p_nd) const; | |
47bea7b8 | 457 | #endif |
4569a895 AT |
458 | |
459 | void | |
460 | initialize(); | |
461 | ||
462 | node_pointer | |
463 | recursive_copy_node(const node_pointer p_nd); | |
464 | ||
465 | protected: | |
466 | node_pointer m_p_head; | |
467 | ||
468 | size_type m_size; | |
469 | ||
470 | static node_allocator s_node_allocator; | |
471 | }; | |
472 | ||
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> | |
483 | ||
484 | #undef PB_DS_CLASS_C_DEC | |
485 | ||
486 | #undef PB_DS_CLASS_T_DEC | |
487 | ||
488 | #undef PB_DS_CLASS_NAME | |
489 | ||
490 | #undef PB_DS_TYPES_TRAITS_C_DEC | |
491 | ||
551fe1a2 | 492 | #undef PB_DS_DEBUG_MAP_BASE_C_DEC |
4569a895 AT |
493 | |
494 | #ifdef PB_DS_TREE_TRACE | |
495 | #undef PB_DS_TREE_TRACE_BASE_C_DEC | |
47bea7b8 | 496 | #endif |
4569a895 AT |
497 | |
498 | #undef PB_DS_V2F | |
499 | #undef PB_DS_EP2VP | |
500 | #undef PB_DS_V2S | |
501 | ||
4569a895 AT |
502 | } // namespace detail |
503 | } // namespace pb_ds |