id_pointer(p_begin_metadata, base_type::m_p_metadata))); } // Returns the node reference associated with the right node. inline ov_tree_node_it_ get_r_child() const { if (base_type::m_p_value == base_type::m_p_end_value) return (this_type(base_type::m_p_end_value, base_type::m_p_end_value, base_type::m_p_end_value)); const_metadata_pointer p_end_metadata = base_type::m_p_metadata + (base_type::m_p_end_value - base_type::m_p_value); return (this_type(base_type::mid_pointer(base_type::m_p_value + 1, base_type::m_p_end_value), base_type::m_p_value + 1, base_type::m_p_end_value,(base_type::m_p_metadata == NULL)? NULL : base_type::mid_pointer(base_type::m_p_metadata + 1, p_end_metadata))); } }; #undef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC #undef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC } // namespace detail } // namespace __gnu_pbds #endif // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file insert_fn_imps.hpp * Contains an implementation class for ov_tree_. */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: reallocate_metadata(null_node_update_pointer, size_type) { } PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: reallocate_metadata(Node_Update_* , size_type new_size) { metadata_pointer a_new_metadata_vec =(new_size == 0) ? NULL : s_metadata_alloc.allocate(new_size); if (m_a_metadata != NULL) { for (size_type i = 0; i < m_size; ++i) m_a_metadata[i].~metadata_type(); s_metadata_alloc.deallocate(m_a_metadata, m_size); } std::swap(m_a_metadata, a_new_metadata_vec); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file ov_tree_map_.hpp * Contains an implementation class for ov_tree_. */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_OV_TREE_CLASS_NAME ov_tree_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_OV_TREE_CLASS_NAME ov_tree_no_data_ #endif #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_const_node_iterator_data_ #else #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_const_node_iterator_no_data_ #endif #define PB_DS_CLASS_C_DEC \ PB_DS_OV_TREE_CLASS_NAME #define PB_DS_TYPES_TRAITS_C_DEC \ types_traits #ifdef _GLIBCXX_DEBUG #define PB_DS_DEBUG_MAP_BASE_C_DEC \ debug_map_base, \ typename Allocator::template rebind::other::const_reference> #endif #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_V2F(X) (X).first #define PB_DS_V2S(X) (X).second #define PB_DS_EP2VP(X)& ((X)->m_value) #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_V2F(X) (X) #define PB_DS_V2S(X) Mapped_Data() #define PB_DS_EP2VP(X)& ((X)->m_value.first) #endif #ifdef PB_DS_TREE_TRACE #define PB_DS_TREE_TRACE_BASE_C_DEC \ tree_trace_base #endif // Ordered-vector tree associative-container. template class PB_DS_OV_TREE_CLASS_NAME : #ifdef _GLIBCXX_DEBUG protected PB_DS_DEBUG_MAP_BASE_C_DEC, #endif #ifdef PB_DS_TREE_TRACE public PB_DS_TREE_TRACE_BASE_C_DEC, #endif public Cmp_Fn, public Node_And_It_Traits::node_update, public PB_DS_TYPES_TRAITS_C_DEC { private: typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; typedef typename remove_const::type non_const_value_type; typedef typename Allocator::template rebind::other value_allocator; typedef typename value_allocator::pointer value_vector; typedef Cmp_Fn cmp_fn_base; #ifdef _GLIBCXX_DEBUG typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; #endif typedef typename traits_base::pointer mapped_pointer_; typedef typename traits_base::const_pointer const_mapped_pointer_; typedef typename Node_And_It_Traits::metadata_type metadata_type; typedef typename Allocator::template rebind::other metadata_allocator; typedef typename metadata_allocator::pointer metadata_pointer; typedef typename metadata_allocator::const_reference const_metadata_reference; typedef typename metadata_allocator::reference metadata_reference; typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer; public: typedef Allocator allocator; typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; typedef Cmp_Fn cmp_fn; typedef typename Node_And_It_Traits::node_update node_update; typedef typename traits_base::key_type key_type; typedef typename traits_base::key_pointer key_pointer; typedef typename traits_base::const_key_pointer const_key_pointer; typedef typename traits_base::key_reference key_reference; typedef typename traits_base::const_key_reference const_key_reference; typedef typename traits_base::mapped_type mapped_type; typedef typename traits_base::mapped_pointer mapped_pointer; typedef typename traits_base::const_mapped_pointer const_mapped_pointer; typedef typename traits_base::mapped_reference mapped_reference; typedef typename traits_base::const_mapped_reference const_mapped_reference; typedef typename traits_base::value_type value_type; typedef typename traits_base::pointer pointer; typedef typename traits_base::const_pointer const_pointer; typedef typename traits_base::reference reference; typedef typename traits_base::const_reference const_reference; typedef const_pointer const_point_iterator; #ifdef PB_DS_DATA_TRUE_INDICATOR typedef pointer point_iterator; #else typedef const_point_iterator point_iterator; #endif typedef const_point_iterator const_iterator; typedef point_iterator iterator; #include typedef typename Node_And_It_Traits::const_node_iterator const_node_iterator; typedef typename Node_And_It_Traits::node_iterator node_iterator; public: PB_DS_OV_TREE_CLASS_NAME(); PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn&); PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn&, const node_update&); PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC&); ~PB_DS_OV_TREE_CLASS_NAME(); void swap(PB_DS_CLASS_C_DEC&); template void copy_from_range(It, It); inline size_type max_size() const; inline bool empty() const; inline size_type size() const; Cmp_Fn& get_cmp_fn(); const Cmp_Fn& get_cmp_fn() const; inline mapped_reference operator[](const_key_reference r_key) { #ifdef PB_DS_DATA_TRUE_INDICATOR _GLIBCXX_DEBUG_ONLY(assert_valid();) point_iterator it = lower_bound(r_key); if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); _GLIBCXX_DEBUG_ONLY(assert_valid();) return it->second; } _GLIBCXX_DEBUG_ONLY(assert_valid();) return (insert_new_val(it, std::make_pair(r_key, mapped_type()))->second); #else insert(r_key); return traits_base::s_null_mapped; #endif } inline std::pair insert(const_reference r_value) { _GLIBCXX_DEBUG_ONLY(assert_valid();) const_key_reference r_key = PB_DS_V2F(r_value); point_iterator it = lower_bound(r_key); if (it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it))) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); return std::make_pair(it, false); } _GLIBCXX_DEBUG_ONLY(assert_valid();) return std::make_pair(insert_new_val(it, r_value), true); } inline point_iterator lower_bound(const_key_reference r_key) { pointer it = m_a_values; pointer e_it = m_a_values + m_size; while (it != e_it) { pointer mid_it = it + ((e_it - it) >> 1); if (cmp_fn_base::operator()(PB_DS_V2F(*mid_it), r_key)) it = ++mid_it; else e_it = mid_it; } return it; } inline const_point_iterator lower_bound(const_key_reference r_key) const { return const_cast(*this).lower_bound(r_key); } inline point_iterator upper_bound(const_key_reference r_key) { iterator pot_it = lower_bound(r_key); if (pot_it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); return ++pot_it; } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); return pot_it; } inline const_point_iterator upper_bound(const_key_reference r_key) const { return const_cast(*this).upper_bound(r_key); } inline point_iterator find(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) iterator pot_it = lower_bound(r_key); if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it))) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); return pot_it; } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); return end(); } inline const_point_iterator find(const_key_reference r_key) const { return (const_cast(*this).find(r_key)); } bool erase(const_key_reference); template inline size_type erase_if(Pred); inline iterator erase(iterator it) { return erase_imp(it); } void clear(); void join(PB_DS_CLASS_C_DEC&); void split(const_key_reference, PB_DS_CLASS_C_DEC&); inline iterator begin() { return m_a_values; } inline const_iterator begin() const { return m_a_values; } inline iterator end() { return m_end_it; } inline const_iterator end() const { return m_end_it; } inline const_node_iterator node_begin() const; inline const_node_iterator node_end() const; inline node_iterator node_begin(); inline node_iterator node_end(); private: inline void update(node_iterator /*it*/, null_node_update_pointer); template void update(node_iterator, Node_Update*); void reallocate_metadata(null_node_update_pointer, size_type); template void reallocate_metadata(Node_Update_*, size_type); template void copy_from_ordered_range(It, It); void value_swap(PB_DS_CLASS_C_DEC&); template void copy_from_ordered_range(It, It, It, It); template inline static Ptr mid_pointer(Ptr p_begin, Ptr p_end) { _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin); return (p_begin + (p_end - p_begin) / 2); } inline iterator insert_new_val(itera‘2’2“2tor it, const_reference r_value) { _GLIBCXX_DEBUG_ONLY(assert_valid();) #ifdef PB_DS_REGRESSION typename Allocator::group_throw_prob_adjustor adjust(m_size); #endif _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(PB_DS_V2F(r_value))); value_vector a_values = s_value_alloc.allocate(m_size + 1); iterator source_it = begin(); iterator source_end_it = end(); iterator target_it = a_values; iterator ret_it; cond_dtor cd(a_values, target_it, m_size + 1); while (source_it != it) { new (const_cast(static_cast(target_it))) value_type(*source_it++); ++target_it; } new (const_cast(static_cast(ret_it = target_it))) value_type(r_value); ++target_it; while (source_it != source_end_it) { new (const_cast(static_cast(target_it))) value_type(*source_it++); ++target_it; } reallocate_metadata((node_update* )this, m_size + 1); cd.set_no_action(); if (m_size != 0) { cond_dtor cd1(m_a_values, m_end_it, m_size); } ++m_size; m_a_values = a_values; m_end_it = m_a_values + m_size; _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value))); update(node_begin(), (node_update* )this); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) return ret_it; } #ifdef _GLIBCXX_DEBUG void assert_valid() const; void assert_iterators() const; #endif template It erase_imp(It it); inline const_node_iterator PB_DS_node_begin_imp() const; inline const_node_iterator PB_DS_node_end_imp() const; inline node_iterator PB_DS_node_begin_imp(); inline node_iterator PB_DS_node_end_imp(); private: static value_allocator s_value_alloc; static metadata_allocator s_metadata_alloc; value_vector m_a_values; metadata_pointer m_a_metadata; iterator m_end_it; size_type m_size; }; #include #include #include #include #include #include #include #include #undef PB_DS_CLASS_C_DEC #undef PB_DS_CLASS_T_DEC #undef PB_DS_OV_TREE_CLASS_NAME #undef PB_DS_TYPES_TRAITS_C_DEC #undef PB_DS_DEBUG_MAP_BASE_C_DEC #ifdef PB_DS_TREE_TRACE #undef PB_DS_TREE_TRACE_BASE_C_DEC #endif #undef PB_DS_V2F #undef PB_DS_EP2VP #undef PB_DS_V2S #undef PB_DS_CONST_NODE_ITERATOR_NAME } // namespace detail } // namespace __gnu_pbds // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file cond_dtor.hpp * Contains a conditional destructor */ template class cond_dtor { public: cond_dtor(value_vector a_vec, iterator& r_last_it, Size_Type total_size) : m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size), m_no_action(false) { } ~cond_dtor() { if (m_no_action) return; iterator it = m_a_vec; while (it != m_r_last_it) { it->~value_type(); ++it; } if (m_max_size > 0) value_allocator().deallocate(m_a_vec, m_max_size); } inline void set_no_action() { m_no_action = true; } protected: value_vector m_a_vec; iterator& m_r_last_it; const Size_Type m_max_size; bool m_no_action; }; // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file info_fn_imps.hpp * Contains an implementation class for ov_tree_. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const { _GLIBCXX_DEBUG_ONLY(assert_valid();) return m_size; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const { return s_value_alloc.max_size(); } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const { return size() == 0; } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file policy_access_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC Cmp_Fn& PB_DS_CLASS_C_DEC:: get_cmp_fn() { return *this; } PB_DS_CLASS_T_DEC const Cmp_Fn& PB_DS_CLASS_C_DEC:: get_cmp_fn() const { return *this; } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file constructors_destructor_fn_imps.hpp * Contains an implementation class for ov_tree_. */ PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::value_allocator PB_DS_CLASS_C_DEC::s_value_alloc; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::metadata_allocator PB_DS_CLASS_C_DEC::s_metadata_alloc; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_OV_TREE_CLASS_NAME() : m_a_values(NULL), m_a_metadata(NULL), m_end_it(NULL), m_size(0) { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn) : cmp_fn_base(r_cmp_fn), m_a_values(NULL), m_a_metadata(NULL), m_end_it(NULL), m_size(0) { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) : cmp_fn_base(r_cmp_fn), node_update(r_node_update), m_a_values(NULL), m_a_metadata(NULL), m_end_it(NULL), m_size(0) { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : #ifdef _GLIBCXX_DEBUG debug_base(other), #endif #ifdef PB_DS_TREE_TRACE PB_DS_TREE_TRACE_BASE_C_DEC(other), #endif cmp_fn_base(other), node_update(other), m_a_values(NULL), m_a_metadata(NULL), m_end_it(NULL), m_size(0) { copy_from_ordered_range(other.begin(), other.end()); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } PB_DS_CLASS_T_DEC template inline void PB_DS_CLASS_C_DEC:: copy_from_range(It first_it, It last_it) { #ifdef PB_DS_DATA_TRUE_INDICATOR typedef std::map< key_type, mapped_type, Cmp_Fn, typename Allocator::template rebind< value_type>::other> map_type; #else typedef std::set< key_type, Cmp_Fn, typename Allocator::template rebind< Key>::other> map_type; #endif map_type m(first_it, last_it); copy_from_ordered_range(m.begin(), m.end()); } PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: copy_from_ordered_range(It first_it, It last_it) { const size_type len = std::distance(first_it, last_it); if (len == 0) return; value_vector a_values = s_value_alloc.allocate(len); iterator target_it = a_values; It source_it = first_it; It source_end_it = last_it; cond_dtor cd(a_values, target_it, len); while (source_it != source_end_it) { new (const_cast(static_cast(target_it))) value_type(*source_it++); ++target_it; } reallocate_metadata((node_update* )this, len); cd.set_no_action(); m_a_values = a_values; m_size = len; m_end_it = m_a_values + m_size; update(PB_DS_node_begin_imp(), (node_update* )this); #ifdef _GLIBCXX_DEBUG const_iterator dbg_it = m_a_values; while (dbg_it != m_end_it) { debug_base::insert_new(PB_DS_V2F(*dbg_it)); dbg_it++; } PB_DS_CLASS_C_DEC::assert_valid(); #endif } PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: copy_from_ordered_range(It first_it, It last_it, It other_first_it, It other_last_it) { clear(); const size_type len = std::distance(first_it, last_it) + std::distance(other_first_it, other_last_it); value_vector a_values = s_value_alloc.allocate(len); iterator target_it = a_values; It source_it = first_it; It source_end_it = last_it; cond_dtor cd(a_values, target_it, len); while (source_it != source_end_it) { new (const_cast(static_cast(target_it))) value_type(*source_it++); ++target_it; } source_it = other_first_it; source_end_it = other_last_it; while (source_it != source_end_it) { new (const_cast(static_cast(target_it))) value_type(*source_it++); ++target_it; } reallocate_metadata((node_update* )this, len); cd.set_no_action(); m_a_values = a_values; m_size = len; m_end_it = m_a_values + m_size; update(PB_DS_node_begin_imp(), (node_update* )this); #ifdef _GLIBCXX_DEBUG const_iterator dbg_it = m_a_values; while (dbg_it != m_end_it) { debug_base::insert_new(PB_DS_V2F(*dbg_it)); dbg_it++; } PB_DS_CLASS_C_DEC::assert_valid(); #endif } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) value_swap(other); std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: value_swap(PB_DS_CLASS_C_DEC& other) { std::swap(m_a_values, other.m_a_values); std::swap(m_a_metadata, other.m_a_metadata); std::swap(m_size, other.m_size); std::swap(m_end_it, other.m_end_it); _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~PB_DS_OV_TREE_CLASS_NAME() { _GLIBCXX_DEBUG_ONLY(assert_valid();) cond_dtor cd(m_a_values, m_end_it, m_size); reallocate_metadata((node_update* )this, 0); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: update(node_iterator /*it*/, null_node_update_pointer) { } PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: update(node_iterator nd_it, Node_Update* p_update) { const_node_iterator end_it = PB_DS_node_end_imp(); if (nd_it == end_it) return; update(nd_it.get_l_child(), p_update); update(nd_it.get_r_child(), p_update); node_update::operator()(nd_it, end_it); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file debug_fn_imps.hpp * Contains an implementation class for ov_tree_. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { std::cout << "av1" << std::endl; if (m_a_values == NULL || m_end_it == NULL || m_size == 0) _GLIBCXX_DEBUG_ASSERT(m_a_values == NULL && m_end_it == NULL && m_size == 0); std::cout << "av2" << std::endl; assert_iterators(); std::cout << "av3" << std::endl; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_iterators() const { debug_base::check_size(m_size); size_type iterated_num = 0; const_iterator prev_it = end(); _GLIBCXX_DEBUG_ASSERT( m_end_it == m_a_values + m_size); for (const_iterator it = begin(); it != end(); ++it) { ++iterated_num; _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(PB_DS_V2F(*it));) _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)) == it); const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it)); --upper_bound_it; _GLIBCXX_DEBUG_ASSERT(upper_bound_it == it); if (prev_it != end()) _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*prev_it), PB_DS_V2F(*it))); prev_it = it; } _GLIBCXX_DEBUG_ASSERT(iterated_num == m_size); } #endif // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file erase_fn_imps.hpp * Contains an implementation class for ov_tree_. */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear() { _GLIBCXX_DEBUG_ONLY(assert_valid();) if (m_size == 0) { _GLIBCXX_DEBUG_ONLY(assert_valid();) return; } else { reallocate_metadata((node_update* )this, 0); cond_dtor cd(m_a_values, m_end_it, m_size); } _GLIBCXX_DEBUG_ONLY(debug_base::clear();) m_a_values = NULL; m_size = 0; m_end_it = m_a_values; _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC template inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { _GLIBCXX_DEBUG_ONLY(assert_valid();) #ifdef PB_DS_REGRESSION typename Allocator::group_throw_prob_adjustor adjust(m_size); #endif size_type new_size = 0; size_type num_val_ersd = 0; iterator source_it = m_a_values; for (source_it = begin(); source_it != m_end_it; ++source_it) if (!pred(*source_it)) ++new_size; else ++num_val_ersd; if (new_size == 0) { clear(); return num_val_ersd; } value_vector a_new_values = s_value_alloc.allocate(new_size); iterator target_it = a_new_values; cond_dtor cd(a_new_values, target_it, new_size); _GLIBCXX_DEBUG_ONLY(debug_base::clear()); for (source_it = begin(); source_it != m_end_it; ++source_it) { if (!pred(*source_it)) { new (const_cast(static_cast(target_it))) value_type(*source_it); _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(*source_it))); ++target_it; } } reallocate_metadata((node_update* )this, new_size); cd.set_no_action(); { cond_dtor cd1(m_a_values, m_end_it, m_size); } m_a_values = a_new_values; m_size = new_size; m_end_it = target_it; update(node_begin(), (node_update* )this); _GLIBCXX_DEBUG_ONLY(assert_valid();) return num_val_ersd; } PB_DS_CLASS_T_DEC template It PB_DS_CLASS_C_DEC:: erase_imp(It it) { _GLIBCXX_DEBUG_ONLY(assert_valid();) if (it == end()) return end(); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::check_key_exists(PB_DS_V2F(*it));) #ifdef PB_DS_REGRESSION typename Allocator::group_throw_prob_adjustor adjust(m_size); #endif _GLIBCXX_DEBUG_ASSERT(m_size > 0); value_vector a_values = s_value_alloc.allocate(m_size - 1); iterator source_it = begin(); iterator source_end_it = end(); iterator target_it = a_values; iterator ret_it = end(); cond_dtor cd(a_values, target_it, m_size - 1); _GLIBCXX_DEBUG_ONLY(size_type cnt = 0;) while (source_it != source_end_it) { if (source_it != it) { _GLIBCXX_DEBUG_ONLY(++cnt;) _GLIBCXX_DEBUG_ASSERT(cnt != m_size); new (const_cast(static_cast(target_it))) value_type(*source_it); ++target_it; } else ret_it = target_it; ++source_it; } _GLIBCXX_DEBUG_ASSERT(m_size > 0); reallocate_metadata((node_update* )this, m_size - 1); cd.set_no_action(); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::erase_existing(PB_DS_V2F(*it));) { cond_dtor cd1(m_a_values, m_end_it, m_size); } m_a_values = a_values; --m_size; m_end_it = m_a_values + m_size; update(node_begin(), (node_update* )this); _GLIBCXX_DEBUG_ONLY(assert_valid();) return It(ret_it); } PB_DS_CLASS_T_DEC bool PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { point_iterator it = find(r_key); if (it == end()) return false; erase(it); return true; } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file traits.hpp * Contains an implementation class for ov_tree_. */ #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP #define PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP #include namespace __gnu_pbds { namespace detail { template class Node_Update, class Allocator> struct tree_traits< Key, Mapped, Cmp_Fn, Node_Update, ov_tree_tag, Allocator> { private: typedef typename types_traits< Key, Mapped, Allocator, false>::value_type value_type; public: typedef typename tree_node_metadata_selector< Key, Mapped, Cmp_Fn, Node_Update, Allocator>::type metadata_type; typedef ov_tree_node_const_it_< value_type, metadata_type, Allocator> const_node_iterator; typedef ov_tree_node_it_< value_type, metadata_type, Allocator> node_iterator; typedef Node_Update< const_node_iterator, node_iterator, Cmp_Fn, Allocator> node_update; typedef __gnu_pbds::null_tree_node_update< const_node_iterator, node_iterator, Cmp_Fn, Allocator>* null_node_update_pointer; }; template class Node_Update, class Allocator> struct tree_traits< Key, null_mapped_type, Cmp_Fn, Node_Update, ov_tree_tag, Allocator> { private: typedef typename types_traits< Key, null_mapped_type, Allocator, false>::value_type value_type; public: typedef typename tree_node_metadata_selector< Key, null_mapped_type, Cmp_Fn, Node_Update, Allocator>::type metadata_type; typedef ov_tree_node_const_it_< value_type, metadata_type, Allocator> const_node_iterator; typedef const_node_iterator node_iterator; typedef Node_Update< const_node_iterator, const_node_iterator, Cmp_Fn, Allocator> node_update; typedef __gnu_pbds::null_tree_node_update< const_node_iterator, node_iterator, Cmp_Fn, Allocator>* null_node_update_pointer; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file iterators_fn_imps.hpp * Contains an implementation class for ov_tree_. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_begin() const { return PB_DS_node_begin_imp(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_end() const { return PB_DS_node_end_imp(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_begin() { return PB_DS_node_begin_imp(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_end() { return PB_DS_node_end_imp(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: PB_DS_node_begin_imp() const { return const_node_iterator(const_cast(mid_pointer(begin(), end())), const_cast(begin()), const_cast(end()),(m_a_metadata == NULL)? NULL : mid_pointer(m_a_metadata, m_a_metadata + m_size)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: PB_DS_node_end_imp() const { return const_node_iterator(end(), end(), end(), (m_a_metadata == NULL) ? NULL : m_a_metadata + m_size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: PB_DS_node_begin_imp() { return node_iterator(mid_pointer(begin(), end()), begin(), end(), (m_a_metadata == NULL) ? NULL : mid_pointer(m_a_metadata, m_a_metadata + m_size)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: PB_DS_node_end_imp() { return node_iterator(end(), end(), end(),(m_a_metadata == NULL) ? NULL : m_a_metadata + m_size); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file priority_queue_base_dispatch.hpp * Contains an pqiative container dispatching base. */ #ifndef PB_DS_PRIORITY_QUEUE_BASE_DS_DISPATCHER_HPP #define PB_DS_PRIORITY_QUEUE_BASE_DS_DISPATCHER_HPP #include #include #include #include #include namespace __gnu_pbds { namespace detail { template struct priority_queue_base_dispatch; template struct priority_queue_base_dispatch { typedef pairing_heap_< Value_Type, Cmp_Fn, Allocator> type; }; template struct priority_queue_base_dispatch { typedef binomial_heap_< Value_Type, Cmp_Fn, Allocator> type; }; template struct priority_queue_base_dispatch { typedef rc_binomial_heap_< Value_Type, Cmp_Fn, Allocator> type; }; template struct priority_queue_base_dispatch { typedef binary_heap_< Value_Type, Cmp_Fn, Allocator> type; }; template struct priority_queue_base_dispatch { typedef thin_heap_< Value_Type, Cmp_Fn, Allocator> type; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_PRIORITY_QUEUE_BASE_DS_DISPATCHER_HPP ‚ .X ..ƒ$basic_tree_policy_base.hpp„ traits.hpp…°null_node_metadata.hpp// -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file basic_tree_policy_base.hpp * Contains a base class for tree_like policies. */ #ifndef PB_DS_TREE_LIKE_POLICY_BASE_HPP #define PB_DS_TREE_LIKE_POLICY_BASE_HPP namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_C_DEC \ basic_tree_policy_base< \ Const_Node_Iterator, \ Node_Iterator, \ Allocator> template struct basic_tree_policy_base { protected: typedef typename Node_Iterator::value_type it_type; typedef typename std::iterator_traits< it_type>::value_type value_type; typedef typename value_type::first_type key_type; typedef typename Allocator::template rebind< typename remove_const< key_type>::type>::other::const_reference const_key_reference; typedef typename Allocator::template rebind< typename remove_const< value_type>::type>::other::const_reference const_reference; typedef typename Allocator::template rebind< typename remove_const< value_type>::type>: