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