ator->() const { _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL); return &base_it_type::m_p_nd->m_value; } inline typename PB_DS_TREE_CONST_IT_C_DEC::reference operator*() const { _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL); return base_it_type::m_p_nd->m_value; } inline PB_DS_TREE_IT_C_DEC& operator++() { PB_DS_TREE_CONST_IT_C_DEC:: operator++(); return *this; } inline PB_DS_TREE_IT_C_DEC operator++(int) { PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); operator++(); return ret_it; } inline PB_DS_TREE_IT_C_DEC& operator--() { PB_DS_TREE_CONST_IT_C_DEC:: operator--(); return *this; } inline PB_DS_TREE_IT_C_DEC operator--(int) { PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); operator--(); return ret_it; } protected: typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type; }; #undef PB_DS_TREE_CONST_IT_C_DEC #undef PB_DS_TREE_CONST_ODIR_IT_C_DEC #undef PB_DS_TREE_IT_C_DEC #undef PB_DS_TREE_ODIR_IT_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 debug_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { structure_only_assert_valid(); assert_consistent_with_debug_base(); assert_size(); assert_iterators(); if (m_p_head->m_p_parent == NULL) { _GLIBCXX_DEBUG_ASSERT(m_size == 0); } else { _GLIBCXX_DEBUG_ASSERT(m_size > 0); } } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: structure_only_assert_valid() const { _GLIBCXX_DEBUG_ASSERT(m_p_head != NULL); if (m_p_head->m_p_parent == NULL) { _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head); _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head); } else { _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent->m_p_parent == m_p_head); _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left != m_p_head); _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right != m_p_head); } if (m_p_head->m_p_parent != NULL) assert_node_consistent(m_p_head->m_p_parent); assert_min(); assert_max(); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_node_consistent(const node_pointer p_nd) const { assert_node_consistent_(p_nd); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_consistent_t PB_DS_CLASS_C_DEC:: assert_node_consistent_(const node_pointer p_nd) const { if (p_nd == NULL) return (std::make_pair((const_pointer)NULL,(const_pointer)NULL)); assert_node_consistent_with_left(p_nd); assert_node_consistent_with_right(p_nd); const std::pair l_range = assert_node_consistent_(p_nd->m_p_left); if (l_range.second != NULL) _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*l_range.second), PB_DS_V2F(p_nd->m_value))); const std::pair r_range = assert_node_consistent_(p_nd->m_p_right); if (r_range.first != NULL) _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), PB_DS_V2F(*r_range.first))); return (std::make_pair((l_range.first != NULL)? l_range.first :& p_nd->m_value,(r_range.second != NULL)? r_range.second :& p_nd->m_value)); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_node_consistent_with_left(const node_pointer p_nd) const { if (p_nd->m_p_left == NULL) return; _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left->m_p_parent == p_nd); _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), PB_DS_V2F(p_nd->m_p_left->m_value))); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_node_consistent_with_right(const node_pointer p_nd) const { if (p_nd->m_p_right == NULL) return; _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right->m_p_parent == p_nd); _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_p_right->m_value), PB_DS_V2F(p_nd->m_value))); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_min() const { assert_min_imp(m_p_head->m_p_parent); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_min_imp(const node_pointer p_nd) const { if (p_nd == NULL) { _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head); return; } if (p_nd->m_p_left == NULL) { _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_left); return; } assert_min_imp(p_nd->m_p_left); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_max() const { assert_max_imp(m_p_head->m_p_parent); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_max_imp(const node_pointer p_nd) const { if (p_nd == NULL) { _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head); return; } if (p_nd->m_p_right == NULL) { _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_right); return; } assert_max_imp(p_nd->m_p_right); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_iterators() const { size_type iterated_num = 0; const_iterator prev_it = end(); for (const_iterator it = begin(); it != end(); ++it) { ++iterated_num; _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)).m_p_nd == it.m_p_nd); const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it)); --upper_bound_it; _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == it.m_p_nd); 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); size_type reverse_iterated_num = 0; const_reverse_iterator reverse_prev_it = rend(); for (const_reverse_iterator reverse_it = rbegin(); reverse_it != rend(); ++reverse_it) { ++reverse_iterated_num; _GLIBCXX_DEBUG_ASSERT(lower_bound( PB_DS_V2F(*reverse_it)).m_p_nd == reverse_it.m_p_nd); const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*reverse_it)); --upper_bound_it; _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == reverse_it.m_p_nd); if (reverse_prev_it != rend()) _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(*reverse_prev_it), PB_DS_V2F(*reverse_it))); reverse_prev_it = reverse_it; } _GLIBCXX_DEBUG_ASSERT(reverse_iterated_num == m_size); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_consistent_with_debug_base() const { debug_base::check_size(m_size); assert_consistent_with_debug_base(m_p_head->m_p_parent); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_consistent_with_debug_base(const node_pointer p_nd) const { if (p_nd == NULL) return; debug_base::check_key_exists(PB_DS_V2F(p_nd->m_value)); assert_consistent_with_debug_base(p_nd->m_p_left); assert_consistent_with_debug_base(p_nd->m_p_right); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_size() const { _GLIBCXX_DEBUG_ASSERT(recursive_count(m_p_head->m_p_parent) == 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 cond_key_dtor_entry_dealtor.hpp * Contains a binary tree container conditional deallocator */ class bin_seach_tree_cond_key_dtor_entry_dealtor_ { public: inline bin_seach_tree_cond_key_dtor_entry_dealtor_(node_pointer p_nd) : m_p_nd(p_nd), m_no_action_dtor(false), m_key_destruct(false) { } inline void set_no_action_dtor() { m_no_action_dtor = true; } inline void set_key_destruct() { m_key_destruct = true; } inline ~bin_seach_tree_cond_key_dtor_entry_dealtor_() { if (m_no_action_dtor) return; if (m_key_destruct) m_p_nd->m_value.first.~Key(); bin_tree_base::s_alloc.deallocate(m_p_nd, 1); } protected: node_pointer m_p_nd; bool m_no_action_dtor; bool m_key_destruct; }; // -*- 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 bin_search_tree_. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: actual_erase_node(node_pointer p_z) { _GLIBCXX_DEBUG_ASSERT(m_size > 0); --m_size; _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value))); p_z->~node(); s_node_allocator.deallocate(p_z, 1); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: update_min_max_for_erased_node(node_pointer p_z) { if (m_size == 1) { m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; return; } if (m_p_head->m_p_left == p_z) { iterator it(p_z); ++it; m_p_head->m_p_left = it.m_p_nd; } else if (m_p_head->m_p_right == p_z) { iterator it(p_z); --it; m_p_head->m_p_right = it.m_p_nd; } } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear() { _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) clear_imp(m_p_head->m_p_parent); m_size = 0; initialize(); _GLIBCXX_DEBUG_ONLY(debug_base::clear();) _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear_imp(node_pointer p_nd) { if (p_nd == NULL) return; clear_imp(p_nd->m_p_left); clear_imp(p_nd->m_p_right); p_nd->~node(); s_node_allocator.deallocate(p_nd, 1); } // -*- 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 for bin_search_tree_. */ #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP #define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP #include #include namespace __gnu_pbds { namespace detail { template class Node_Update, class Node, class Allocator> struct bin_search_tree_traits { private: typedef types_traits< Key, Mapped, Allocator, false> type_traits; public: typedef Node node; typedef bin_search_tree_const_it_< typename Allocator::template rebind< node>::other::pointer, typename type_traits::value_type, typename type_traits::pointer, typename type_traits::const_pointer, typename type_traits::reference, typename type_traits::const_reference, true, Allocator> const_point_iterator; typedef bin_search_tree_it_< typename Allocator::template rebind< node>::other::pointer, typename type_traits::value_type, typename type_traits::pointer, typename type_traits::const_pointer, typename type_traits::reference, typename type_traits::const_reference, true, Allocator> point_iterator; typedef bin_search_tree_const_it_< typename Allocator::template rebind< node>::other::pointer, typename type_traits::value_type, typename type_traits::pointer, typename type_traits::const_pointer, typename type_traits::reference, typename type_traits::const_reference, false, Allocator> const_reverse_iterator; typedef bin_search_tree_it_< typename Allocator::template rebind< node>::other::pointer, typename type_traits::value_type, typename type_traits::pointer, typename type_traits::const_pointer, typename type_traits::reference, typename type_traits::const_reference, false, Allocator> reverse_iterator; typedef bin_search_tree_const_node_it_< Node, const_point_iterator, point_iterator, Allocator> const_node_iterator; typedef bin_search_tree_node_it_< Node, const_point_iterator, point_iterator, 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 Node, class Allocator> struct bin_search_tree_traits< Key, null_mapped_type, Cmp_Fn, Node_Update, Node, Allocator> { private: typedef types_traits< Key, null_mapped_type, Allocator, false> type_traits; public: typedef Node node; typedef bin_search_tree_const_it_< typename Allocator::template rebind< node>::other::pointer, typename type_traits::value_type, typename type_traits::pointer, typename type_traits::const_pointer, typename type_traits::reference, typename type_traits::const_reference, true, Allocator> const_point_iterator; typedef const_point_iterator point_iterator; typedef bin_search_tree_const_it_< typename Allocator::template rebind< node>::other::pointer, typename type_traits::value_type, typename type_traits::pointer, typename type_traits::const_pointer, typename type_traits::reference, typename type_traits::const_reference, false, Allocator> const_reverse_iterator; typedef const_reverse_iterator reverse_iterator; typedef bin_search_tree_const_node_it_< Node, const_point_iterator, point_iterator, Allocator> const_node_iterator; typedef const_node_iterator 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; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_BIN_SEARCH_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 bin_search_tree_. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: begin() { return (iterator(m_p_head->m_p_left)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: begin() const { return (const_iterator(m_p_head->m_p_left)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: end() { return (iterator(m_p_head)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end() const { return (const_iterator(m_p_head)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator PB_DS_CLASS_C_DEC:: rbegin() const { return (const_reverse_iterator(m_p_head->m_p_right)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::reverse_iterator PB_DS_CLASS_C_DEC:: rbegin() { return (reverse_iterator(m_p_head->m_p_right)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::reverse_iterator PB_DS_CLASS_C_DEC:: rend() { return (reverse_iterator(m_p_head)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator PB_DS_CLASS_C_DEC:: rend() const { return (const_reverse_iterator(m_p_head)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_begin() const { return (const_node_iterator(m_p_head->m_p_parent)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_begin() { return (node_iterator(m_p_head->m_p_parent)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_end() const { return (const_node_iterator(NULL)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_end() { return (node_iterator(NULL)); } // -*- 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 rotate_fn_imps.hpp * Contains imps for rotating nodes. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: rotate_left(node_pointer p_x) { node_pointer p_y = p_x->m_p_right; p_x->m_p_right = p_y->m_p_left; if (p_y->m_p_left != NULL) p_y->m_p_left->m_p_parent = p_x; p_y->m_p_parent = p_x->m_p_parent; if (p_x == m_p_head->m_p_parent) m_p_head->m_p_parent = p_y; else if (p_x == p_x->m_p_parent->m_p_left) p_x->m_p_parent->m_p_left = p_y; else p_x->m_p_parent->m_p_right = p_y; p_y->m_p_left = p_x; p_x->m_p_parent = p_y; _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) apply_update(p_x, (node_update* )this); apply_update(p_x->m_p_parent, (node_update* )this); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: rotate_right(node_pointer p_x) { node_pointer p_y = p_x->m_p_left; p_x->m_p_left = p_y->m_p_right; if (p_y->m_p_right != NULL) p_y->m_p_right->m_p_parent = p_x; p_y->m_p_parent = p_x->m_p_parent; if (p_x == m_p_head->m_p_parent) m_p_head->m_p_parent = p_y; else if (p_x == p_x->m_p_parent->m_p_right) p_x->m_p_parent->m_p_right = p_y; else p_x->m_p_parent->m_p_left = p_y; p_y->m_p_right = p_x; p_x->m_p_parent = p_y; _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) apply_update(p_x, (node_update* )this); apply_update(p_x->m_p_parent, (node_update* )this); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: rotate_parent(node_pointer p_nd) { node_pointer p_parent = p_nd->m_p_parent; if (p_nd == p_parent->m_p_left) rotate_right(p_parent); else rotate_left(p_parent); _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_parent = p_nd); _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == p_parent || p_nd->m_p_right == p_parent); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: apply_update(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/) { } PB_DS_CLASS_T_DEC template inline void PB_DS_CLASS_C_DEC:: apply_update(node_pointer p_nd, Node_Update_* /*p_update*/) { node_update::operator()( node_iterator(p_nd), const_node_iterator(static_cast(NULL))); } PB_DS_CLASS_T_DEC template inline void PB_DS_CLASS_C_DEC:: update_to_top(node_pointer p_nd, Node_Update_* p_update) { while (p_nd != m_p_head) { apply_update(p_nd, p_update); p_nd = p_nd->m_p_parent; } } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: update_to_top(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/) { } // -*- 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 r_erase_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: actual_erase_node(node_pointer p_z) { _GLIBCXX_DEBUG_ASSERT(m_size > 0); --m_size; _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value))); p_z->~node(); s_node_allocator.deallocate(p_z, 1); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: update_min_max_for_erased_node(node_pointer p_z) { if (m_size == 1) { m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; return; } if (m_p_head->m_p_left == p_z) { iterator it(p_z); ++it; m_p_head->m_p_left = it.m_p_nd; } else if (m_p_head->m_p_right == p_z) { iterator it(p_z); --it; m_p_head->m_p_right = it.m_p_nd; } } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear() { _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) clear_imp(m_p_head->m_p_parent); m_size = 0; initialize(); _GLIBCXX_DEBUG_ONLY(debug_base::clear();) _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear_imp(node_pointer p_nd) { if (p_nd == NULL) return; clear_imp(p_nd->m_p_left); clear_imp(p_nd->m_p_right); p_nd->~Node(); s_node_allocator.deallocate(p_nd, 1); } // -*- 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 bin_search_tree_.hpp * Contains an implementation class for bin_search_tree_. */ /* * This implementation uses an idea from the SGI STL (using a "header" node * which is needed for efficient iteration). */ #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_CLASS_NAME \ bin_search_tree_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_CLASS_NAME \ bin_search_tree_no_data_ #endif #define PB_DS_CLASS_C_DEC \ PB_DS_CLASS_NAME< \ Key, \ Mapped, \ Cmp_Fn, \ Node_And_It_Traits, \ Allocator> #define PB_DS_TYPES_TRAITS_C_DEC \ types_traits< \ Key, \ Mapped, \ Allocator, \ false> #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< \ typename Node_And_It_Traits::const_node_iterator, \ typename Node_And_It_Traits::node_iterator, \ Cmp_Fn, \ true, \ Allocator> #endif /** * class description = "8i|\|4ree $34rc|-| 7r33 74813."> **/ template class PB_DS_CLASS_NAME : #ifdef _GLIBCXX_DEBUG public 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 PB_DS_TYPES_TRAITS_C_DEC, public Node_And_It_Traits::node_update { protected: typedef typename Allocator::template rebind< typename Node_And_It_Traits::node>::other node_allocator; typedef typename node_allocator::value_type node; typedef typename node_allocator::pointer node_pointer; typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer; private: typedef cond_dealtor< node, Allocator> cond_dealtor_t; #ifdef _GLIBCXX_DEBUG typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; #endif public: typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type; typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer; typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer const_key_pointer; typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference; typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference const_key_reference; #ifdef PB_DS_DATA_TRUE_INDICATOR typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type; typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer mapped_pointer; typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer const_mapped_pointer; typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference mapped_reference; typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference const_mapped_reference; #endif typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type; typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer; typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer; typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference; typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_reference const_reference; typedef typename Node_And_It_Traits::const_point_iterator const_point_iterator; typedef const_point_iterator const_iterator; typedef typename Node_And_It_Traits::point_iterator point_iterator; typedef point_iterator iterator; typedef typename Node_And_It_Traits::const_reverse_iterator const_reverse_iterator; typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator; typedef typename Node_And_It_Traits::const_node_iterator const_node_iterator; typedef typename Node_And_It_Traits::node_iterator node_iterator; typedef Cmp_Fn cmp_fn; typedef Allocator allocator; typedef typename Node_And_It_Traits::node_update node_update; public: PB_DS_CLASS_NAME(); PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn); PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update); PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); void swap(PB_DS_CLASS_C_DEC& other); ~PB_DS_CLASS_NAME(); inline bool empty() const; inline size_type size() const; inline size_type max_size() const; Cmp_Fn& get_cmp_fn(); const Cmp_Fn& get_cmp_fn() const; inline point_iterator lower_bound(const_key_reference r_key); inline const_point_iterator lower_bound(const_key_reference r_key) const; inline point_iterator upper_bound(const_key_reference r_key); inline const_point_iterator upper_bound(const_key_reference r_key) const; inline point_iterator find(const_key_reference r_key); inline const_point_iterator find(const_key_reference r_key) const; inline iterator begin(); inline const_iterator begin() const; inline iterator end(); inline const_iterator end() const; inline reverse_iterator rbegin(); inline const_reverse_iterator rbegin() const; inline reverse_iterator rend(); inline const_reverse_iterator rend() const; inline const_node_iterator node_begin() const; inline node_iterator node_begin(); inline const_node_iterator node_end() const; inline node_iterator node_end(); void clear(); protected: void value_swap(PB_DS_CLASS_C_DEC& other); void initialize_min_max(); inline iterator insert_imp_empty(const_reference r_value); inline iterator insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd); inline node_pointer get_new_node_for_leaf_insert(const_reference r_val, false_type); inline node_pointer get_new_node_for_leaf_insert(const_reference r_val, true_type); inline void actual_erase_node(node_pointer p_nd); inline std::pair erase(node_pointer p_nd); inline void update_min_max_for_erased_node(node_pointer p_nd); static void clear_imp(node_pointer p_nd); inline std::pair< point_iterator, bool> insert_leaf(const_reference r_value); inline void rotate_left(node_pointer p_x); inline void rotate_right(node_pointer p_y); inline void rotate_parent(node_pointer p_nd); inline void apply_update(node_pointer p_nd, null_node_update_pointer); template inline void apply_update(node_pointer p_nd, Node_Update_* p_update); inline void update_to_top(node_pointer p_nd, null_node_update_pointer); template inline void update_to_top(node_pointer p_nd, Node_Update_* p_update); bool join_prep(PB_DS_CLASS_C_DEC& other); void join_finish(PB_DS_CLASS_C_DEC& other); bool split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other); void split_finish(PB_DS_CLASS_C_DEC& other); size_type recursive_count(node_pointer p_nd) const; #ifdef _GLIBCXX_DEBUG void assert_valid() const; void structure_only_assert_valid() const; void assert_node_consistent(const node_pointer p_nd) const; #endif private: #ifdef _GLIBCXX_DEBUG void assert_iterators() const; void assert_consistent_with_debug_base() const; void assert_node_consistent_with_left(const node_pointer p_nd) const; void assert_node_consistent_with_right(const node_pointer p_nd) const; void assert_consistent_with_debug_base(const node_pointer p_nd) const; void assert_min() const; void assert_min_imp(const node_pointer p_nd) const; void assert_max() const; void assert_max_imp(const node_pointer p_nd) const; void assert_size() const; typedef std::pair< const_pointer, const_pointer> node_consistent_t; node_consistent_t assert_node_consistent_(const node_pointer p_nd) const; #endif void initialize(); node_pointer recursive_copy_node(const node_pointer p_nd); protected: node_pointer m_p_head; size_type m_size; static node_allocator s_node_allocator; }; #include #include #include #include #include #include #include #include #include #include #undef PB_DS_CLASS_C_DEC #undef PB_DS_CLASS_T_DEC #undef PB_DS_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 } // namespace detail } // namespace __gnu_pbds Z .X ..[insert_fn_imps.hpp\ lu_map_.hpp]info_fn_imps.hpp^trace_fn_imps.hpp_find_fn_imps.hpp` entry_metadata_base.hppadebug_fn_imps.hppberase_fn_imps.hppc iterators_fn_imps.hppdô"constructor_destructor_fn_imps.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 insert_fn_imps.hpp * Contains implementations of lu_map_. */ PB_DS_CLASS_T_DEC inline std::pair< typename PB_DS_CLASS_C_DEC::point_iterator, bool> PB_DS_CLASS_C_DEC:: insert(const_reference r_val) { _GLIBCXX_DEBUG_ONLY(assert_valid();) entry_pointer p_l = find_imp(PB_DS_V2F(r_val)); if (p_l != NULL) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(PB_DS_V2F(r_val));) return std::make_pair(point_iterator(&p_l->m_value), false); } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(PB_DS_V2F(r_val));) p_l = allocate_new_entry(r_val, traits_base::m_no_throw_copies_indicator); p_l->m_p_next = m_p_l; m_p_l = p_l; _GLIBCXX_DEBUG_ONLY(assert_valid();) return std::make_pair(point_iterator(&p_l->m_value), true); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::entry_pointer PB_DS_CLASS_C_DEC:: allocate_new_entry(const_reference r_val, false_type) { entry_pointer p_l = s_entry_allocator.allocate(1); cond_dealtor_t cond(p_l); new (const_cast(static_cast(&p_l->m_value))) value_type(r_val); cond.set_no_action(); _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) init_entry_metadata(p_l, s_metadata_type_indicator); return p_l; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::entry_pointer PB_DS_CLASS_C_DEC:: allocate_new_entry(const_reference r_val, true_type) { entry_pointer p_l = s_entry_allocator.allocate(1); new (&p_l->m_value) value_type(r_val); _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) init_entry_metadata(p_l, s_metadata_type_indicator); return p_l; } PB_DS_CLASS_T_DEC template inline void PB_DS_CLASS_C_DEC:: init_entry_metadata(entry_pointer p_l, type_to_type) { new (&p_l->m_update_metadata) Metadata(s_update_policy()); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: init_entry_metadata(entry_pointer, type_to_type) { } // -*- 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 lu_map_.hpp * Contains a list update map. */ #include #include #include #include #include #include #include #ifdef _GLIBCXX_DEBUG #include #endif #ifdef PB_DS_LU_MAP_TRACE_ #include #endif #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_CLASS_NAME lu_map_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_CLASS_NAME lu_map_no_data_ #endif #define PB_DS_CLASS_C_DEC \ PB_DS_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::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 /* Skip to the lu, my darling. */ // list-based (with updates) associative container. template class PB_DS_CLASS_NAME : #ifdef _GLIBCXX_DEBUG protected PB_DS_DEBUG_MAP_BASE_C_DEC, #endif public PB_DS_TYPES_TRAITS_C_DEC { private: typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; struct entry : public lu_map_entry_metadata_base { typename traits_base::value_type m_value; typename Allocator::template rebind::other::pointer m_p_next; }; typedef typename Allocator::template rebind::other entry_allocator; typedef typename entry_allocator::pointer entry_pointer; typedef typename entry_allocator::const_pointer const_entry_pointer; typedef typename entry_allocator::reference entry_reference; typedef typename entry_allocator::const_reference const_entry_reference; typedef typename Allocator::template rebind::other entry_pointer_allocator; typedef typename entry_pointer_allocator::pointer entry_pointer_array; 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_; #define PB_DS_GEN_POS entry_pointer #include #include #include #include #undef PB_DS_GEN_POS #ifdef _GLIBCXX_DEBUG typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; #endif typedef cond_dealtor cond_dealtor_t; public: typedef Allocator allocator; typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; typedef Eq_Fn eq_fn; typedef Update_Policy update_policy; typedef typename Update_Policy::metadata_type update_metadata; 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; #ifdef PB_DS_DATA_TRUE_INDICATOR typedef point_iterator_ point_iterator; #endif #ifdef PB_DS_DATA_FALSE_INDICATOR typedef const_point_iterator_ point_iterator; #endif typedef const_point_iterator_ const_point_iterator; #ifdef PB_DS_DATA_TRUE_INDICATOR typedef iterator_ iterator; #endif #ifdef PB_DS_DATA_FALSE_INDICATOR typedef const_iterator_ iterator; #endif typedef const_iterator_ const_iterator; public: PB_DS_CLASS_NAME(); PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); virtual ~PB_DS_CLASS_NAME(); template PB_DS_CLASS_NAME(It first_it, It last_it); void swap(PB_DS_CLASS_C_DEC&); inline size_type size() const; inline size_type max_size() const; inline bool empty() const; inline mapped_reference operator[](const_key_reference r_key) { #ifdef PB_DS_DATA_TRUE_INDICATOR _GLIBCXX_DEBUG_ONLY(assert_valid();) return insert(std::make_pair(r_key, mapped_type())).first->second; #else insert(r_key); return traits_base::s_null_mapped; #endif } inline std::pair insert(const_reference); inline point_iterator find(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) entry_pointer p_e = find_imp(r_key); return point_iterator(p_e == NULL ? NULL: &p_e->m_value); } inline const_point_iterator find(c