1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2009, 2011 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 ov_tree_map_/ov_tree_map_.hpp 38 * Contains an implementation class for ov_tree. 39 */ 40 41 #include <map> 42 #include <set> 43 #include <ext/pb_ds/exception.hpp> 44 #include <ext/pb_ds/tree_policy.hpp> 45 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 46 #include <ext/pb_ds/detail/types_traits.hpp> 47 #include <ext/pb_ds/detail/type_utils.hpp> 48 #include <ext/pb_ds/detail/tree_trace_base.hpp> 49 #ifdef _GLIBCXX_DEBUG 50 #include <ext/pb_ds/detail/debug_map_base.hpp> 51 #endif 52 #include <utility> 53 #include <functional> 54 #include <algorithm> 55 #include <vector> 56 #include <assert.h> 57 #include <debug/debug.h> 58 59 namespace __gnu_pbds 60 { 61 namespace detail 62 { 63 #ifdef PB_DS_DATA_TRUE_INDICATOR 64 #define PB_DS_OV_TREE_NAME ov_tree_map 65 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_map 66 #endif 67 68 #ifdef PB_DS_DATA_FALSE_INDICATOR 69 #define PB_DS_OV_TREE_NAME ov_tree_set 70 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_set 71 #endif 72 73 #define PB_DS_CLASS_T_DEC \ 74 template<typename Key, typename Mapped, typename Cmp_Fn, \ 75 typename Node_And_It_Traits, typename _Alloc> 76 77 #define PB_DS_CLASS_C_DEC \ 78 PB_DS_OV_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 79 80 #define PB_DS_OV_TREE_TRAITS_BASE \ 81 types_traits<Key, Mapped, _Alloc, false> 82 83 #ifdef _GLIBCXX_DEBUG 84 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 85 debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \ 86 typename _Alloc::template rebind<Key>::other::const_reference> 87 #endif 88 89 #ifdef PB_DS_TREE_TRACE 90 #define PB_DS_TREE_TRACE_BASE_C_DEC \ 91 tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \ 92 typename Node_And_It_Traits::node_iterator, \ 93 Cmp_Fn, false, _Alloc> 94 #endif 95 96 #ifndef PB_DS_CHECK_KEY_EXISTS 97 # error Missing definition 98 #endif 99 100 /** 101 * @brief Ordered-vector tree associative-container. 102 * @ingroup branch-detail 103 */ 104 template<typename Key, typename Mapped, typename Cmp_Fn, 105 typename Node_And_It_Traits, typename _Alloc> 106 class PB_DS_OV_TREE_NAME : 107 #ifdef _GLIBCXX_DEBUG 108 protected PB_DS_DEBUG_MAP_BASE_C_DEC, 109 #endif 110 #ifdef PB_DS_TREE_TRACE 111 public PB_DS_TREE_TRACE_BASE_C_DEC, 112 #endif 113 public Cmp_Fn, 114 public Node_And_It_Traits::node_update, 115 public PB_DS_OV_TREE_TRAITS_BASE 116 { 117 private: 118 typedef PB_DS_OV_TREE_TRAITS_BASE traits_base; 119 typedef Node_And_It_Traits traits_type; 120 121 typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type; 122 123 typedef typename _Alloc::template rebind<non_const_value_type>::other value_allocator; 124 typedef typename value_allocator::pointer value_vector; 125 126 #ifdef _GLIBCXX_DEBUG 127 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 128 #endif 129 130 #ifdef PB_DS_TREE_TRACE 131 typedef PB_DS_TREE_TRACE_BASE_C_DEC trace_base; 132 #endif 133 134 typedef typename traits_base::pointer mapped_pointer_; 135 typedef typename traits_base::const_pointer mapped_const_pointer_; 136 137 typedef typename traits_type::metadata_type metadata_type; 138 139 typedef typename _Alloc::template rebind<metadata_type>::other metadata_allocator; 140 typedef typename metadata_allocator::pointer metadata_pointer; 141 typedef typename metadata_allocator::const_reference metadata_const_reference; 142 typedef typename metadata_allocator::reference metadata_reference; 143 144 typedef typename traits_type::null_node_update_pointer 145 null_node_update_pointer; 146 147 public: 148 typedef ov_tree_tag container_category; 149 typedef _Alloc allocator_type; 150 typedef typename _Alloc::size_type size_type; 151 typedef typename _Alloc::difference_type difference_type; 152 typedef Cmp_Fn cmp_fn; 153 154 typedef typename traits_base::key_type key_type; 155 typedef typename traits_base::key_pointer key_pointer; 156 typedef typename traits_base::key_const_pointer key_const_pointer; 157 typedef typename traits_base::key_reference key_reference; 158 typedef typename traits_base::key_const_reference key_const_reference; 159 typedef typename traits_base::mapped_type mapped_type; 160 typedef typename traits_base::mapped_pointer mapped_pointer; 161 typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 162 typedef typename traits_base::mapped_reference mapped_reference; 163 typedef typename traits_base::mapped_const_reference mapped_const_reference; 164 typedef typename traits_base::value_type value_type; 165 typedef typename traits_base::pointer pointer; 166 typedef typename traits_base::const_pointer const_pointer; 167 typedef typename traits_base::reference reference; 168 typedef typename traits_base::const_reference const_reference; 169 170 typedef const_pointer point_const_iterator; 171 #ifdef PB_DS_DATA_TRUE_INDICATOR 172 typedef pointer point_iterator; 173 #else 174 typedef point_const_iterator point_iterator; 175 #endif 176 177 typedef point_iterator iterator; 178 typedef point_const_iterator const_iterator; 179 180 /// Conditional destructor. 181 template<typename Size_Type> 182 class cond_dtor 183 { 184 public: 185 cond_dtor(value_vector a_vec, iterator& r_last_it, 186 Size_Type total_size) 187 : m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size), 188 m_no_action(false) 189 { } 190 191 ~cond_dtor() 192 { 193 if (m_no_action) 194 return; 195 iterator it = m_a_vec; 196 while (it != m_r_last_it) 197 { 198 it->~value_type(); 199 ++it; 200 } 201 202 if (m_max_size > 0) 203 value_allocator().deallocate(m_a_vec, m_max_size); 204 } 205 206 inline void 207 set_no_action() 208 { m_no_action = true; } 209 210 protected: 211 value_vector m_a_vec; 212 iterator& m_r_last_it; 213 const Size_Type m_max_size; 214 bool m_no_action; 215 }; 216 217 typedef typename traits_type::node_update node_update; 218 typedef typename traits_type::node_iterator node_iterator; 219 typedef typename traits_type::node_const_iterator node_const_iterator; 220 221 222 PB_DS_OV_TREE_NAME(); 223 224 PB_DS_OV_TREE_NAME(const Cmp_Fn&); 225 226 PB_DS_OV_TREE_NAME(const Cmp_Fn&, const node_update&); 227 228 PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC&); 229 230 ~PB_DS_OV_TREE_NAME(); 231 232 void 233 swap(PB_DS_CLASS_C_DEC&); 234 235 template<typename It> 236 void 237 copy_from_range(It, It); 238 239 inline size_type 240 max_size() const; 241 242 inline bool 243 empty() const; 244 245 inline size_type 246 size() const; 247 248 Cmp_Fn& 249 get_cmp_fn(); 250 251 const Cmp_Fn& 252 get_cmp_fn() const; 253 254 inline mapped_reference 255 operator[](key_const_reference r_key) 256 { 257 #ifdef PB_DS_DATA_TRUE_INDICATOR 258 PB_DS_ASSERT_VALID((*this)) 259 point_iterator it = lower_bound(r_key); 260 if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) 261 { 262 PB_DS_CHECK_KEY_EXISTS(r_key) 263 PB_DS_ASSERT_VALID((*this)) 264 return it->second; 265 } 266 return insert_new_val(it, std::make_pair(r_key, mapped_type()))->second; 267 #else 268 insert(r_key); 269 return traits_base::s_null_type; 270 #endif 271 } 272 273 inline std::pair<point_iterator, bool> 274 insert(const_reference r_value) 275 { 276 PB_DS_ASSERT_VALID((*this)) 277 key_const_reference r_key = PB_DS_V2F(r_value); 278 point_iterator it = lower_bound(r_key); 279 280 if (it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) 281 { 282 PB_DS_ASSERT_VALID((*this)) 283 PB_DS_CHECK_KEY_EXISTS(r_key) 284 return std::make_pair(it, false); 285 } 286 287 return std::make_pair(insert_new_val(it, r_value), true); 288 } 289 290 inline point_iterator 291 lower_bound(key_const_reference r_key) 292 { 293 pointer it = m_a_values; 294 pointer e_it = m_a_values + m_size; 295 while (it != e_it) 296 { 297 pointer mid_it = it + ((e_it - it) >> 1); 298 if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key)) 299 it = ++mid_it; 300 else 301 e_it = mid_it; 302 } 303 return it; 304 } 305 306 inline point_const_iterator 307 lower_bound(key_const_reference r_key) const 308 { return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); } 309 310 inline point_iterator 311 upper_bound(key_const_reference r_key) 312 { 313 iterator pot_it = lower_bound(r_key); 314 if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) 315 { 316 PB_DS_CHECK_KEY_EXISTS(r_key) 317 return ++pot_it; 318 } 319 320 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 321 return pot_it; 322 } 323 324 inline point_const_iterator 325 upper_bound(key_const_reference r_key) const 326 { return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); } 327 328 inline point_iterator 329 find(key_const_reference r_key) 330 { 331 PB_DS_ASSERT_VALID((*this)) 332 iterator pot_it = lower_bound(r_key); 333 if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) 334 { 335 PB_DS_CHECK_KEY_EXISTS(r_key) 336 return pot_it; 337 } 338 339 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 340 return end(); 341 } 342 343 inline point_const_iterator 344 find(key_const_reference r_key) const 345 { return (const_cast<PB_DS_CLASS_C_DEC&>(*this).find(r_key)); } 346 347 bool 348 erase(key_const_reference); 349 350 template<typename Pred> 351 inline size_type 352 erase_if(Pred); 353 354 inline iterator 355 erase(iterator it) 356 { return erase_imp<iterator>(it); } 357 358 void 359 clear(); 360 361 void 362 join(PB_DS_CLASS_C_DEC&); 363 364 void 365 split(key_const_reference, PB_DS_CLASS_C_DEC&); 366 367 inline iterator 368 begin() 369 { return m_a_values; } 370 371 inline const_iterator 372 begin() const 373 { return m_a_values; } 374 375 inline iterator 376 end() 377 { return m_end_it; } 378 379 inline const_iterator 380 end() const 381 { return m_end_it; } 382 383 /// Returns a const node_iterator corresponding to the node at the 384 /// root of the tree. 385 inline node_const_iterator 386 node_begin() const; 387 388 /// Returns a node_iterator corresponding to the node at the 389 /// root of the tree. 390 inline node_iterator 391 node_begin(); 392 393 /// Returns a const node_iterator corresponding to a node just 394 /// after a leaf of the tree. 395 inline node_const_iterator 396 node_end() const; 397 398 /// Returns a node_iterator corresponding to a node just 399 /// after a leaf of the tree. 400 inline node_iterator 401 node_end(); 402 403 private: 404 405 inline void 406 update(node_iterator, null_node_update_pointer); 407 408 template<typename Node_Update> 409 void 410 update(node_iterator, Node_Update*); 411 412 void 413 reallocate_metadata(null_node_update_pointer, size_type); 414 415 template<typename Node_Update_> 416 void 417 reallocate_metadata(Node_Update_*, size_type); 418 419 template<typename It> 420 void 421 copy_from_ordered_range(It, It); 422 423 void 424 value_swap(PB_DS_CLASS_C_DEC&); 425 426 template<typename It> 427 void 428 copy_from_ordered_range(It, It, It, It); 429 430 template<typename Ptr> 431 inline static Ptr 432 mid_pointer(Ptr p_begin, Ptr p_end) 433 { 434 _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin); 435 return (p_begin + (p_end - p_begin) / 2); 436 } 437 438 inline iterator 439 insert_new_val(iterator it, const_reference r_value) 440 { 441 #ifdef PB_DS_REGRESSION 442 typename _Alloc::group_adjustor adjust(m_size); 443 #endif 444 445 PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_value)) 446 447 value_vector a_values = s_value_alloc.allocate(m_size + 1); 448 449 iterator source_it = begin(); 450 iterator source_end_it = end(); 451 iterator target_it = a_values; 452 iterator ret_it; 453 454 cond_dtor<size_type> cd(a_values, target_it, m_size + 1); 455 while (source_it != it) 456 { 457 new (const_cast<void*>(static_cast<const void*>(target_it))) 458 value_type(*source_it++); 459 ++target_it; 460 } 461 462 new (const_cast<void*>(static_cast<const void*>(ret_it = target_it))) 463 value_type(r_value); 464 ++target_it; 465 466 while (source_it != source_end_it) 467 { 468 new (const_cast<void*>(static_cast<const void*>(target_it))) 469 value_type(*source_it++); 470 ++target_it; 471 } 472 473 reallocate_metadata((node_update*)this, m_size + 1); 474 cd.set_no_action(); 475 if (m_size != 0) 476 { 477 cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); 478 } 479 480 ++m_size; 481 m_a_values = a_values; 482 m_end_it = m_a_values + m_size; 483 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value))); 484 update(node_begin(), (node_update* )this); 485 PB_DS_ASSERT_VALID((*this)) 486 return ret_it; 487 } 488 489 #ifdef _GLIBCXX_DEBUG 490 void 491 assert_valid(const char*, int) const; 492 493 void 494 assert_iterators(const char*, int) const; 495 #endif 496 497 template<typename It> 498 It 499 erase_imp(It); 500 501 inline node_const_iterator 502 PB_DS_node_begin_imp() const; 503 504 inline node_const_iterator 505 PB_DS_node_end_imp() const; 506 507 inline node_iterator 508 PB_DS_node_begin_imp(); 509 510 inline node_iterator 511 PB_DS_node_end_imp(); 512 513 private: 514 static value_allocator s_value_alloc; 515 static metadata_allocator s_metadata_alloc; 516 517 value_vector m_a_values; 518 metadata_pointer m_a_metadata; 519 iterator m_end_it; 520 size_type m_size; 521 }; 522 523 #include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp> 524 #include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp> 525 #include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp> 526 #include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp> 527 #include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp> 528 #include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp> 529 #include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp> 530 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 531 532 #undef PB_DS_CLASS_C_DEC 533 #undef PB_DS_CLASS_T_DEC 534 #undef PB_DS_OV_TREE_NAME 535 #undef PB_DS_OV_TREE_TRAITS_BASE 536 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 537 #ifdef PB_DS_TREE_TRACE 538 #undef PB_DS_TREE_TRACE_BASE_C_DEC 539 #endif 540 #undef PB_DS_CONST_NODE_ITERATOR_NAME 541 } // namespace detail 542 } // namespace __gnu_pbds 543