1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file ov_tree_map_.hpp 44169691Skan * Contains an implementation class for ov_tree_. 45169691Skan */ 46169691Skan 47169691Skan#include <map> 48169691Skan#include <set> 49169691Skan#include <ext/pb_ds/tree_policy.hpp> 50169691Skan#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 51169691Skan#include <ext/pb_ds/detail/types_traits.hpp> 52169691Skan#include <ext/pb_ds/detail/map_debug_base.hpp> 53169691Skan#include <ext/pb_ds/detail/type_utils.hpp> 54169691Skan#include <ext/pb_ds/exception.hpp> 55169691Skan#include <ext/pb_ds/detail/tree_trace_base.hpp> 56169691Skan#include <utility> 57169691Skan#include <functional> 58169691Skan#include <algorithm> 59169691Skan#include <vector> 60169691Skan#include <assert.h> 61169691Skan#include <debug/debug.h> 62169691Skan 63169691Skannamespace pb_ds 64169691Skan{ 65169691Skan namespace detail 66169691Skan { 67169691Skan#define PB_DS_CLASS_T_DEC \ 68169691Skan template<typename Key, typename Mapped, class Cmp_Fn, \ 69169691Skan class Node_And_It_Traits, class Allocator> 70169691Skan 71169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 72169691Skan#define PB_DS_OV_TREE_CLASS_NAME ov_tree_data_ 73169691Skan#endif 74169691Skan 75169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 76169691Skan#define PB_DS_OV_TREE_CLASS_NAME ov_tree_no_data_ 77169691Skan#endif 78169691Skan 79169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 80169691Skan#define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_const_node_iterator_data_ 81169691Skan#else 82169691Skan#define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_const_node_iterator_no_data_ 83169691Skan#endif 84169691Skan 85169691Skan#define PB_DS_CLASS_C_DEC \ 86169691Skan PB_DS_OV_TREE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator> 87169691Skan 88169691Skan#define PB_DS_TYPES_TRAITS_C_DEC \ 89169691Skan types_traits<Key, Mapped, Allocator, false> 90169691Skan 91169691Skan#ifdef _GLIBCXX_DEBUG 92169691Skan#define PB_DS_MAP_DEBUG_BASE_C_DEC \ 93169691Skan map_debug_base<Key, eq_by_less<Key, Cmp_Fn>, \ 94169691Skan typename Allocator::template rebind<Key>::other::const_reference> 95169691Skan#endif 96169691Skan 97169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 98169691Skan#define PB_DS_V2F(X) (X).first 99169691Skan#define PB_DS_V2S(X) (X).second 100169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value) 101169691Skan#endif 102169691Skan 103169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 104169691Skan#define PB_DS_V2F(X) (X) 105169691Skan#define PB_DS_V2S(X) Mapped_Data() 106169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value.first) 107169691Skan#endif 108169691Skan 109169691Skan#ifdef PB_DS_TREE_TRACE 110169691Skan#define PB_DS_TREE_TRACE_BASE_C_DEC \ 111169691Skan tree_trace_base<typename Node_And_It_Traits::const_node_iterator, \ 112169691Skan typename Node_And_It_Traits::node_iterator, \ 113169691Skan Cmp_Fn, false, Allocator> 114169691Skan#endif 115169691Skan 116169691Skan // Ordered-vector tree associative-container. 117169691Skan template<typename Key, typename Mapped, class Cmp_Fn, 118169691Skan class Node_And_It_Traits, class Allocator> 119169691Skan class PB_DS_OV_TREE_CLASS_NAME : 120169691Skan#ifdef _GLIBCXX_DEBUG 121169691Skan protected PB_DS_MAP_DEBUG_BASE_C_DEC, 122169691Skan#endif 123169691Skan#ifdef PB_DS_TREE_TRACE 124169691Skan public PB_DS_TREE_TRACE_BASE_C_DEC, 125169691Skan#endif 126169691Skan public Cmp_Fn, 127169691Skan public Node_And_It_Traits::node_update, 128169691Skan public PB_DS_TYPES_TRAITS_C_DEC 129169691Skan { 130169691Skan private: 131169691Skan typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 132169691Skan 133169691Skan typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type; 134169691Skan 135169691Skan typedef typename Allocator::template rebind<non_const_value_type>::other value_allocator; 136169691Skan typedef typename value_allocator::pointer value_vector; 137169691Skan 138169691Skan 139169691Skan typedef Cmp_Fn cmp_fn_base; 140169691Skan 141169691Skan#ifdef _GLIBCXX_DEBUG 142169691Skan typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base; 143169691Skan#endif 144169691Skan 145169691Skan typedef typename traits_base::pointer mapped_pointer_; 146169691Skan typedef typename traits_base::const_pointer const_mapped_pointer_; 147169691Skan 148169691Skan typedef typename Node_And_It_Traits::metadata_type metadata_type; 149169691Skan 150169691Skan typedef typename Allocator::template rebind<metadata_type>::other metadata_allocator; 151169691Skan typedef typename metadata_allocator::pointer metadata_pointer; 152169691Skan typedef typename metadata_allocator::const_reference const_metadata_reference; 153169691Skan typedef typename metadata_allocator::reference metadata_reference; 154169691Skan 155169691Skan typedef 156169691Skan typename Node_And_It_Traits::null_node_update_pointer 157169691Skan null_node_update_pointer; 158169691Skan 159169691Skan public: 160169691Skan 161169691Skan typedef Allocator allocator; 162169691Skan typedef typename Allocator::size_type size_type; 163169691Skan typedef typename Allocator::difference_type difference_type; 164169691Skan 165169691Skan typedef Cmp_Fn cmp_fn; 166169691Skan 167169691Skan typedef typename Node_And_It_Traits::node_update node_update; 168169691Skan 169169691Skan typedef typename traits_base::key_type key_type; 170169691Skan typedef typename traits_base::key_pointer key_pointer; 171169691Skan typedef typename traits_base::const_key_pointer const_key_pointer; 172169691Skan typedef typename traits_base::key_reference key_reference; 173169691Skan typedef typename traits_base::const_key_reference const_key_reference; 174169691Skan typedef typename traits_base::mapped_type mapped_type; 175169691Skan typedef typename traits_base::mapped_pointer mapped_pointer; 176169691Skan typedef typename traits_base::const_mapped_pointer const_mapped_pointer; 177169691Skan typedef typename traits_base::mapped_reference mapped_reference; 178169691Skan typedef typename traits_base::const_mapped_reference const_mapped_reference; 179169691Skan typedef typename traits_base::value_type value_type; 180169691Skan typedef typename traits_base::pointer pointer; 181169691Skan typedef typename traits_base::const_pointer const_pointer; 182169691Skan typedef typename traits_base::reference reference; 183169691Skan typedef typename traits_base::const_reference const_reference; 184169691Skan 185169691Skan typedef const_pointer const_point_iterator; 186169691Skan 187169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 188169691Skan typedef pointer point_iterator; 189169691Skan#else 190169691Skan typedef const_point_iterator point_iterator; 191169691Skan#endif 192169691Skan 193169691Skan typedef const_point_iterator const_iterator; 194169691Skan 195169691Skan typedef point_iterator iterator; 196169691Skan 197169691Skan#include <ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp> 198169691Skan 199169691Skan typedef 200169691Skan typename Node_And_It_Traits::const_node_iterator 201169691Skan const_node_iterator; 202169691Skan 203169691Skan typedef typename Node_And_It_Traits::node_iterator node_iterator; 204169691Skan 205169691Skan public: 206169691Skan 207169691Skan PB_DS_OV_TREE_CLASS_NAME(); 208169691Skan 209169691Skan PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn&); 210169691Skan 211169691Skan PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn&, const node_update&); 212169691Skan 213169691Skan PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 214169691Skan 215169691Skan ~PB_DS_OV_TREE_CLASS_NAME(); 216169691Skan 217169691Skan void 218169691Skan swap(PB_DS_CLASS_C_DEC&); 219169691Skan 220169691Skan template<typename It> 221169691Skan void 222169691Skan copy_from_range(It, It); 223169691Skan 224169691Skan inline size_type 225169691Skan max_size() const; 226169691Skan 227169691Skan inline bool 228169691Skan empty() const; 229169691Skan 230169691Skan inline size_type 231169691Skan size() const; 232169691Skan 233169691Skan Cmp_Fn& 234169691Skan get_cmp_fn(); 235169691Skan 236169691Skan const Cmp_Fn& 237169691Skan get_cmp_fn() const; 238169691Skan 239169691Skan inline mapped_reference 240169691Skan operator[](const_key_reference r_key) 241169691Skan { 242169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 243169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 244169691Skan point_iterator it = lower_bound(r_key); 245169691Skan if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) 246169691Skan { 247169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 248169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 249169691Skan return it->second; 250169691Skan } 251169691Skan 252169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 253169691Skan return (insert_new_val(it, std::make_pair(r_key, mapped_type()))->second); 254169691Skan#else 255169691Skan insert(r_key); 256169691Skan return traits_base::s_null_mapped; 257169691Skan#endif 258169691Skan } 259169691Skan 260169691Skan inline std::pair<point_iterator, bool> 261169691Skan insert(const_reference r_value) 262169691Skan { 263169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 264169691Skan const_key_reference r_key = PB_DS_V2F(r_value); 265169691Skan point_iterator it = lower_bound(r_key); 266169691Skan 267169691Skan if (it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) 268169691Skan { 269169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 270169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 271169691Skan return std::make_pair(it, false); 272169691Skan } 273169691Skan 274169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 275169691Skan return std::make_pair(insert_new_val(it, r_value), true); 276169691Skan } 277169691Skan 278169691Skan inline point_iterator 279169691Skan lower_bound(const_key_reference r_key) 280169691Skan { 281169691Skan pointer it = m_a_values; 282169691Skan pointer e_it = m_a_values + m_size; 283169691Skan while (it != e_it) 284169691Skan { 285169691Skan pointer mid_it = it + ((e_it - it) >> 1); 286169691Skan if (cmp_fn_base::operator()(PB_DS_V2F(*mid_it), r_key)) 287169691Skan it = ++mid_it; 288169691Skan else 289169691Skan e_it = mid_it; 290169691Skan } 291169691Skan return it; 292169691Skan } 293169691Skan 294169691Skan inline const_point_iterator 295169691Skan lower_bound(const_key_reference r_key) const 296169691Skan { return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); } 297169691Skan 298169691Skan inline point_iterator 299169691Skan upper_bound(const_key_reference r_key) 300169691Skan { 301169691Skan iterator pot_it = lower_bound(r_key); 302169691Skan if (pot_it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) 303169691Skan { 304169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 305169691Skan return ++pot_it; 306169691Skan } 307169691Skan 308169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); 309169691Skan return pot_it; 310169691Skan } 311169691Skan 312169691Skan inline const_point_iterator 313169691Skan upper_bound(const_key_reference r_key) const 314169691Skan { return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); } 315169691Skan 316169691Skan inline point_iterator 317169691Skan find(const_key_reference r_key) 318169691Skan { 319169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 320169691Skan iterator pot_it = lower_bound(r_key); 321169691Skan if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) 322169691Skan { 323169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 324169691Skan return pot_it; 325169691Skan } 326169691Skan 327169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); 328169691Skan return end(); 329169691Skan } 330169691Skan 331169691Skan inline const_point_iterator 332169691Skan find(const_key_reference r_key) const 333169691Skan { return (const_cast<PB_DS_CLASS_C_DEC& >(*this).find(r_key)); } 334169691Skan 335169691Skan bool 336169691Skan erase(const_key_reference); 337169691Skan 338169691Skan template<typename Pred> 339169691Skan inline size_type 340169691Skan erase_if(Pred); 341169691Skan 342169691Skan inline iterator 343169691Skan erase(iterator it) 344169691Skan { return erase_imp<iterator>(it); } 345169691Skan 346169691Skan void 347169691Skan clear(); 348169691Skan 349169691Skan void 350169691Skan join(PB_DS_CLASS_C_DEC&); 351169691Skan 352169691Skan void 353169691Skan split(const_key_reference, PB_DS_CLASS_C_DEC&); 354169691Skan 355169691Skan inline iterator 356169691Skan begin() 357169691Skan { return m_a_values; } 358169691Skan 359169691Skan inline const_iterator 360169691Skan begin() const 361169691Skan { return m_a_values; } 362169691Skan 363169691Skan inline iterator 364169691Skan end() 365169691Skan { return m_end_it; } 366169691Skan 367169691Skan inline const_iterator 368169691Skan end() const 369169691Skan { return m_end_it; } 370169691Skan 371169691Skan inline const_node_iterator 372169691Skan node_begin() const; 373169691Skan 374169691Skan inline const_node_iterator 375169691Skan node_end() const; 376169691Skan 377169691Skan inline node_iterator 378169691Skan node_begin(); 379169691Skan 380169691Skan inline node_iterator 381169691Skan node_end(); 382169691Skan 383169691Skan private: 384169691Skan 385169691Skan inline void 386169691Skan update(node_iterator /*it*/, null_node_update_pointer); 387169691Skan 388169691Skan template<typename Node_Update> 389169691Skan void 390169691Skan update(node_iterator, Node_Update*); 391169691Skan 392169691Skan void 393169691Skan reallocate_metadata(null_node_update_pointer, size_type); 394169691Skan 395169691Skan template<typename Node_Update_> 396169691Skan void 397169691Skan reallocate_metadata(Node_Update_*, size_type); 398169691Skan 399169691Skan template<typename It> 400169691Skan void 401169691Skan copy_from_ordered_range(It, It); 402169691Skan 403169691Skan void 404169691Skan value_swap(PB_DS_CLASS_C_DEC&); 405169691Skan 406169691Skan template<typename It> 407169691Skan void 408169691Skan copy_from_ordered_range(It, It, It, It); 409169691Skan 410169691Skan template<typename Ptr> 411169691Skan inline static Ptr 412169691Skan mid_pointer(Ptr p_begin, Ptr p_end) 413169691Skan { 414169691Skan _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin); 415169691Skan return (p_begin + (p_end - p_begin) / 2); 416169691Skan } 417169691Skan 418169691Skan inline iterator 419169691Skan insert_new_val(iterator it, const_reference r_value) 420169691Skan { 421169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 422169691Skan#ifdef PB_DS_REGRESSION 423169691Skan typename Allocator::group_throw_prob_adjustor adjust(m_size); 424169691Skan#endif 425169691Skan 426169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(PB_DS_V2F(r_value))); 427169691Skan 428169691Skan value_vector a_values = s_value_alloc.allocate(m_size + 1); 429169691Skan 430169691Skan iterator source_it = begin(); 431169691Skan iterator source_end_it = end(); 432169691Skan iterator target_it = a_values; 433169691Skan iterator ret_it; 434169691Skan 435169691Skan cond_dtor<size_type> cd(a_values, target_it, m_size + 1); 436169691Skan while (source_it != it) 437169691Skan { 438169691Skan new (const_cast<void* >(static_cast<const void* >(target_it))) 439169691Skan value_type(*source_it++); 440169691Skan ++target_it; 441169691Skan } 442169691Skan 443169691Skan new (const_cast<void* >(static_cast<const void* >(ret_it = target_it))) 444169691Skan value_type(r_value); 445169691Skan ++target_it; 446169691Skan 447169691Skan while (source_it != source_end_it) 448169691Skan { 449169691Skan new (const_cast<void* >(static_cast<const void* >(target_it))) 450169691Skan value_type(*source_it++); 451169691Skan ++target_it; 452169691Skan } 453169691Skan 454169691Skan reallocate_metadata((node_update* )this, m_size + 1); 455169691Skan cd.set_no_action(); 456169691Skan if (m_size != 0) 457169691Skan { 458169691Skan cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); 459169691Skan } 460169691Skan 461169691Skan ++m_size; 462169691Skan m_a_values = a_values; 463169691Skan m_end_it = m_a_values + m_size; 464169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_value))); 465169691Skan update(node_begin(), (node_update* )this); 466169691Skan _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) 467169691Skan return ret_it; 468169691Skan } 469169691Skan 470169691Skan#ifdef _GLIBCXX_DEBUG 471169691Skan void 472169691Skan assert_valid() const; 473169691Skan 474169691Skan void 475169691Skan assert_iterators() const; 476169691Skan#endif 477169691Skan 478169691Skan template<typename It> 479169691Skan It 480169691Skan erase_imp(It it); 481169691Skan 482169691Skan inline const_node_iterator 483169691Skan PB_DS_node_begin_imp() const; 484169691Skan 485169691Skan inline const_node_iterator 486169691Skan PB_DS_node_end_imp() const; 487169691Skan 488169691Skan inline node_iterator 489169691Skan PB_DS_node_begin_imp(); 490169691Skan 491169691Skan inline node_iterator 492169691Skan PB_DS_node_end_imp(); 493169691Skan 494169691Skan private: 495169691Skan static value_allocator s_value_alloc; 496169691Skan static metadata_allocator s_metadata_alloc; 497169691Skan 498169691Skan value_vector m_a_values; 499169691Skan metadata_pointer m_a_metadata; 500169691Skan iterator m_end_it; 501169691Skan size_type m_size; 502169691Skan }; 503169691Skan 504169691Skan#include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp> 505169691Skan#include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp> 506169691Skan#include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp> 507169691Skan#include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp> 508169691Skan#include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp> 509169691Skan#include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp> 510169691Skan#include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp> 511169691Skan#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 512169691Skan 513169691Skan#undef PB_DS_CLASS_C_DEC 514169691Skan#undef PB_DS_CLASS_T_DEC 515169691Skan#undef PB_DS_OV_TREE_CLASS_NAME 516169691Skan#undef PB_DS_TYPES_TRAITS_C_DEC 517169691Skan#undef PB_DS_MAP_DEBUG_BASE_C_DEC 518169691Skan#ifdef PB_DS_TREE_TRACE 519169691Skan#undef PB_DS_TREE_TRACE_BASE_C_DEC 520169691Skan#endif 521169691Skan 522169691Skan#undef PB_DS_V2F 523169691Skan#undef PB_DS_EP2VP 524169691Skan#undef PB_DS_V2S 525169691Skan#undef PB_DS_CONST_NODE_ITERATOR_NAME 526169691Skan 527169691Skan } // namespace detail 528169691Skan} // namespace pb_ds 529