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