111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2005-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the terms 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the GNU General Public License as published by the Free Software 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Foundation; either version 3, or (at your option) any later 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, but 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Permission to use, copy, modify, sell, and distribute this software 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// is hereby granted without fee, provided that the above copyright 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// notice appears in all copies, and that both that copyright notice 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// and this permission notice appear in supporting documentation. None 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the above authors, nor IBM Haifa Research Laboratories, make any 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// representation about the suitability of this software for any 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// purpose. It is provided "as is" without express or implied 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// warranty. 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @file ov_tree_map_/ov_tree_map_.hpp 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Contains an implementation class for ov_tree. 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <map> 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <set> 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/exception.hpp> 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/tree_policy.hpp> 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/types_traits.hpp> 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/type_utils.hpp> 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/tree_trace_base.hpp> 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/debug_map_base.hpp> 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <utility> 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <functional> 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <algorithm> 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <vector> 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <assert.h> 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <debug/debug.h> 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_pbds 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert namespace detail 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_OV_TREE_NAME ov_tree_map 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_map 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_FALSE_INDICATOR 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_OV_TREE_NAME ov_tree_set 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_node_const_iterator_set 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CLASS_T_DEC \ 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key, typename Mapped, typename Cmp_Fn, \ 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename Node_And_It_Traits, typename _Alloc> 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CLASS_C_DEC \ 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_OV_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_OV_TREE_TRAITS_BASE \ 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert types_traits<Key, Mapped, _Alloc, false> 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_DEBUG_MAP_BASE_C_DEC \ 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \ 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Alloc::template rebind<Key>::other::const_reference> 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_TREE_TRACE 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_TREE_TRACE_BASE_C_DEC \ 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \ 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename Node_And_It_Traits::node_iterator, \ 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Cmp_Fn, false, _Alloc> 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef PB_DS_CHECK_KEY_EXISTS 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# error Missing definition 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Ordered-vector tree associative-container. 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @ingroup branch-detail 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key, typename Mapped, typename Cmp_Fn, 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename Node_And_It_Traits, typename _Alloc> 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class PB_DS_OV_TREE_NAME : 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected PB_DS_DEBUG_MAP_BASE_C_DEC, 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_TREE_TRACE 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public PB_DS_TREE_TRACE_BASE_C_DEC, 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public Cmp_Fn, 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public Node_And_It_Traits::node_update, 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public PB_DS_OV_TREE_TRAITS_BASE 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef PB_DS_OV_TREE_TRAITS_BASE traits_base; 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef Node_And_It_Traits traits_type; 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type; 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::template rebind<non_const_value_type>::other value_allocator; 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename value_allocator::pointer value_vector; 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_TREE_TRACE 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef PB_DS_TREE_TRACE_BASE_C_DEC trace_base; 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::pointer mapped_pointer_; 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::const_pointer mapped_const_pointer_; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::metadata_type metadata_type; 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::template rebind<metadata_type>::other metadata_allocator; 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename metadata_allocator::pointer metadata_pointer; 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename metadata_allocator::const_reference metadata_const_reference; 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename metadata_allocator::reference metadata_reference; 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::null_node_update_pointer 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert null_node_update_pointer; 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef ov_tree_tag container_category; 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Alloc allocator_type; 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::size_type size_type; 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::difference_type difference_type; 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef Cmp_Fn cmp_fn; 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_type key_type; 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_pointer key_pointer; 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_const_pointer key_const_pointer; 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_reference key_reference; 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_const_reference key_const_reference; 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_type mapped_type; 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_pointer mapped_pointer; 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_reference mapped_reference; 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_const_reference mapped_const_reference; 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::value_type value_type; 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::pointer pointer; 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::const_pointer const_pointer; 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::reference reference; 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::const_reference const_reference; 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef const_pointer point_const_iterator; 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef pointer point_iterator; 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef point_const_iterator point_iterator; 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef point_iterator iterator; 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef point_const_iterator const_iterator; 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Conditional destructor. 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Size_Type> 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class cond_dtor 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert cond_dtor(value_vector a_vec, iterator& r_last_it, 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Size_Type total_size) 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size), 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert m_no_action(false) 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { } 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~cond_dtor() 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (m_no_action) 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator it = m_a_vec; 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (it != m_r_last_it) 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert it->~value_type(); 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++it; 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (m_max_size > 0) 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_allocator().deallocate(m_a_vec, m_max_size); 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set_no_action() 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { m_no_action = true; } 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected: 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_vector m_a_vec; 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator& m_r_last_it; 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const Size_Type m_max_size; 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool m_no_action; 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node_update node_update; 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node_iterator node_iterator; 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node_const_iterator node_const_iterator; 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_OV_TREE_NAME(); 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_OV_TREE_NAME(const Cmp_Fn&); 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_OV_TREE_NAME(const Cmp_Fn&, const node_update&); 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC&); 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~PB_DS_OV_TREE_NAME(); 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert swap(PB_DS_CLASS_C_DEC&); 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename It> 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert copy_from_range(It, It); 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_type 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert max_size() const; 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert empty() const; 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_type 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size() const; 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Cmp_Fn& 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_cmp_fn(); 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const Cmp_Fn& 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_cmp_fn() const; 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline mapped_reference 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator[](key_const_reference r_key) 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_ASSERT_VALID((*this)) 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert point_iterator it = lower_bound(r_key); 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_CHECK_KEY_EXISTS(r_key) 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_ASSERT_VALID((*this)) 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return it->second; 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return insert_new_val(it, std::make_pair(r_key, mapped_type()))->second; 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(r_key); 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return traits_base::s_null_type; 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline std::pair<point_iterator, bool> 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(const_reference r_value) 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 27611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_ASSERT_VALID((*this)) 27711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert key_const_reference r_key = PB_DS_V2F(r_value); 27811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert point_iterator it = lower_bound(r_key); 27911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) 28111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 28211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_ASSERT_VALID((*this)) 28311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_CHECK_KEY_EXISTS(r_key) 28411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(it, false); 28511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 28611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(insert_new_val(it, r_value), true); 28811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 28911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 29111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert lower_bound(key_const_reference r_key) 29211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 29311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pointer it = m_a_values; 29411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pointer e_it = m_a_values + m_size; 29511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (it != e_it) 29611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 29711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pointer mid_it = it + ((e_it - it) >> 1); 29811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key)) 29911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert it = ++mid_it; 30011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 30111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert e_it = mid_it; 30211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 30311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return it; 30411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 30511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 30711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert lower_bound(key_const_reference r_key) const 30811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); } 30911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 31111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert upper_bound(key_const_reference r_key) 31211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 31311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator pot_it = lower_bound(r_key); 31411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) 31511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 31611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_CHECK_KEY_EXISTS(r_key) 31711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return ++pot_it; 31811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 31911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 32111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return pot_it; 32211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 32311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 32511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert upper_bound(key_const_reference r_key) const 32611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); } 32711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 32911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(key_const_reference r_key) 33011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 33111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_ASSERT_VALID((*this)) 33211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator pot_it = lower_bound(r_key); 33311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) 33411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 33511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_CHECK_KEY_EXISTS(r_key) 33611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return pot_it; 33711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 33811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 34011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return end(); 34111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 34211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 34411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(key_const_reference r_key) const 34511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return (const_cast<PB_DS_CLASS_C_DEC&>(*this).find(r_key)); } 34611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 34811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(key_const_reference); 34911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Pred> 35111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_type 35211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase_if(Pred); 35311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 35511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(iterator it) 35611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return erase_imp<iterator>(it); } 35711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 35911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear(); 36011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 36211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert join(PB_DS_CLASS_C_DEC&); 36311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 36511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert split(key_const_reference, PB_DS_CLASS_C_DEC&); 36611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 36811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin() 36911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return m_a_values; } 37011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_iterator 37211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin() const 37311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return m_a_values; } 37411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 37611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end() 37711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return m_end_it; } 37811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_iterator 38011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end() const 38111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return m_end_it; } 38211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a const node_iterator corresponding to the node at the 38411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// root of the tree. 38511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_const_iterator 38611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_begin() const; 38711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a node_iterator corresponding to the node at the 38911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// root of the tree. 39011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_iterator 39111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_begin(); 39211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a const node_iterator corresponding to a node just 39411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// after a leaf of the tree. 39511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_const_iterator 39611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_end() const; 39711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a node_iterator corresponding to a node just 39911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// after a leaf of the tree. 40011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_iterator 40111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_end(); 40211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 40411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 40611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert update(node_iterator, null_node_update_pointer); 40711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Node_Update> 40911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 41011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert update(node_iterator, Node_Update*); 41111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 41311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert reallocate_metadata(null_node_update_pointer, size_type); 41411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Node_Update_> 41611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 41711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert reallocate_metadata(Node_Update_*, size_type); 41811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename It> 42011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 42111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert copy_from_ordered_range(It, It); 42211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 42411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_swap(PB_DS_CLASS_C_DEC&); 42511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename It> 42711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 42811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert copy_from_ordered_range(It, It, It, It); 42911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 43011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Ptr> 43111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline static Ptr 43211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert mid_pointer(Ptr p_begin, Ptr p_end) 43311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 43411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin); 43511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return (p_begin + (p_end - p_begin) / 2); 43611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 43711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 43811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 43911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert_new_val(iterator it, const_reference r_value) 44011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 44111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_REGRESSION 44211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Alloc::group_adjustor adjust(m_size); 44311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 44411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 44511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_value)) 44611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 44711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_vector a_values = s_value_alloc.allocate(m_size + 1); 44811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 44911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator source_it = begin(); 45011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator source_end_it = end(); 45111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator target_it = a_values; 45211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator ret_it; 45311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert cond_dtor<size_type> cd(a_values, target_it, m_size + 1); 45511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (source_it != it) 45611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 45711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert new (const_cast<void*>(static_cast<const void*>(target_it))) 45811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_type(*source_it++); 45911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++target_it; 46011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 46111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 46211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert new (const_cast<void*>(static_cast<const void*>(ret_it = target_it))) 46311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_type(r_value); 46411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++target_it; 46511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 46611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (source_it != source_end_it) 46711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 46811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert new (const_cast<void*>(static_cast<const void*>(target_it))) 46911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_type(*source_it++); 47011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++target_it; 47111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 47211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 47311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert reallocate_metadata((node_update*)this, m_size + 1); 47411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert cd.set_no_action(); 47511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (m_size != 0) 47611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 47711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); 47811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 47911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 48011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++m_size; 48111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert m_a_values = a_values; 48211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert m_end_it = m_a_values + m_size; 48311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value))); 48411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert update(node_begin(), (node_update* )this); 48511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_ASSERT_VALID((*this)) 48611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return ret_it; 48711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 48811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 48911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 49011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 49111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_valid(const char*, int) const; 49211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 49311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 49411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_iterators(const char*, int) const; 49511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 49611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 49711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename It> 49811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert It 49911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase_imp(It); 50011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 50111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_const_iterator 50211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_node_begin_imp() const; 50311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 50411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_const_iterator 50511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_node_end_imp() const; 50611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 50711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_iterator 50811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_node_begin_imp(); 50911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_iterator 51111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_node_end_imp(); 51211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 51411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static value_allocator s_value_alloc; 51511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static metadata_allocator s_metadata_alloc; 51611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_vector m_a_values; 51811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert metadata_pointer m_a_metadata; 51911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterator m_end_it; 52011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type m_size; 52111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 52211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 52311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp> 52411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp> 52511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp> 52611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp> 52711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp> 52811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp> 52911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp> 53011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 53111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 53211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_CLASS_C_DEC 53311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_CLASS_T_DEC 53411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_OV_TREE_NAME 53511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_OV_TREE_TRAITS_BASE 53611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_DEBUG_MAP_BASE_C_DEC 53711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_TREE_TRACE 53811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_TREE_TRACE_BASE_C_DEC 53911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 54011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_CONST_NODE_ITERATOR_NAME 54111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } // namespace detail 54211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace __gnu_pbds 543