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