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 update_fn_imps.hpp * Contains an implementation class for pat_trie_. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: apply_update(node_pointer /*p_nd*/, null_node_update_pointer) { } 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, this), const_node_iterator(NULL, 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 leaf.hpp * Contains a pat_trie_leaf for a patricia tree. */ #ifndef PB_DS_PAT_TRIE_LEAF_HPP #define PB_DS_PAT_TRIE_LEAF_HPP #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template< \ class Type_Traits, \ class E_Access_Traits, \ class Metadata, \ class Allocator> #define PB_DS_CLASS_C_DEC \ pat_trie_leaf< \ Type_Traits, \ E_Access_Traits, \ Metadata, \ Allocator> #define PB_DS_BASE_C_DEC \ pat_trie_node_base< \ Type_Traits, \ E_Access_Traits, \ Metadata, \ Allocator> #define PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC \ pat_trie_subtree_debug_info< \ Type_Traits, \ E_Access_Traits, \ Allocator> template struct pat_trie_leaf : public PB_DS_BASE_C_DEC { private: typedef typename Type_Traits::value_type value_type; typedef typename Type_Traits::const_reference const_reference; typedef typename Type_Traits::reference reference; typedef typename Allocator::template rebind< E_Access_Traits>::other::const_pointer const_e_access_traits_pointer; #ifdef _GLIBCXX_DEBUG typedef typename PB_DS_BASE_C_DEC::subtree_debug_info subtree_debug_info; #endif typedef PB_DS_BASE_C_DEC base_type; public: pat_trie_leaf(const_reference r_val); inline reference value(); inline const_reference value() const; #ifdef _GLIBCXX_DEBUG virtual subtree_debug_info assert_valid_imp(const_e_access_traits_pointer p_traits) const; virtual ~pat_trie_leaf(); #endif private: pat_trie_leaf(const PB_DS_CLASS_C_DEC& other); value_type m_value; }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: pat_trie_leaf(const_reference r_val) : PB_DS_BASE_C_DEC(pat_trie_leaf_node_type), m_value(r_val) { } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::reference PB_DS_CLASS_C_DEC:: value() { return m_value; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reference PB_DS_CLASS_C_DEC:: value() const { return m_value; } #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::subtree_debug_info PB_DS_CLASS_C_DEC:: assert_valid_imp(const_e_access_traits_pointer p_traits) const { _GLIBCXX_DEBUG_ASSERT(base_type::m_type == pat_trie_leaf_node_type); subtree_debug_info ret; const_reference r_val = value(); return std::make_pair(p_traits->begin(p_traits->extract_key(r_val)), p_traits->end(p_traits->extract_key(r_val))); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~pat_trie_leaf() { } #endif #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_BASE_C_DEC #undef PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_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 info_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const { return (m_size == 0); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const { 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_internal_node_allocator.max_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 trace_fn_imps.hpp * Contains an implementation class for pat_trie_. */ #ifdef PB_DS_PAT_TRIE_TRACE_ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: trace() const { std::cerr << std::endl; if (m_p_head->m_p_parent == NULL) return; trace_node(m_p_head->m_p_parent, 0); std::cerr << std::endl; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: trace_node(const_node_pointer p_nd, size_type level) { for (size_type i = 0; i < level; ++i) std::cerr << ' '; std::cerr << p_nd << " "; std::cerr << ((p_nd->m_type == pat_trie_leaf_node_type) ? "l " : "i "); trace_node_metadata(p_nd, type_to_type()); typename e_access_traits::const_iterator el_it = pref_begin(p_nd); while (el_it != pref_end(p_nd)) { std::cerr <<* el_it; ++el_it; } if (p_nd->m_type == pat_trie_leaf_node_type) { std::cerr << std::endl; return; } const_internal_node_pointer p_internal = static_cast(p_nd); std::cerr << " " << static_cast(p_internal->get_e_ind()) << std::endl; const size_type num_children = std::distance(p_internal->begin(), p_internal->end()); for (size_type child_i = 0; child_i < num_children; ++child_i) { typename internal_node::const_iterator child_it = p_internal->begin(); std::advance(child_it, num_children - child_i - 1); trace_node(*child_it, level + 1); } } PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: trace_node_metadata(const_node_pointer p_nd, type_to_type) { std::cerr << "(" << static_cast(p_nd->get_metadata()) << ") "; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: trace_node_metadata(const_node_pointer, type_to_type) { } #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 policy_access_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::e_access_traits& PB_DS_CLASS_C_DEC:: get_e_access_traits() { return *this; } PB_DS_CLASS_T_DEC const typename PB_DS_CLASS_C_DEC::e_access_traits& PB_DS_CLASS_C_DEC:: get_e_access_traits() const { return *this; } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_update& PB_DS_CLASS_C_DEC:: get_node_update() { return *this; } PB_DS_CLASS_T_DEC const typename PB_DS_CLASS_C_DEC::node_update& PB_DS_CLASS_C_DEC:: get_node_update() 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 synth_e_access_traits.hpp * Contains an implementation class for a patricia tree. */ #ifndef PB_DS_SYNTH_E_ACCESS_TRAITS_HPP #define PB_DS_SYNTH_E_ACCESS_TRAITS_HPP #include namespace __gnu_pbds { namespace detail { #define PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC \ template #define PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC \ synth_e_access_traits< \ Type_Traits, \ Set, \ E_Access_Traits> template struct synth_e_access_traits : public E_Access_Traits { private: typedef E_Access_Traits base_type; typedef Type_Traits type_traits; typedef typename type_traits::const_key_reference const_key_reference; typedef typename type_traits::const_reference const_reference; public: synth_e_access_traits(); synth_e_access_traits(const E_Access_Traits& r_traits); inline bool equal_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after = true) const; bool equal_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const; bool cmp_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after = false) const; bool cmp_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const; inline static const_key_reference extract_key(const_reference r_val); #ifdef _GLIBCXX_DEBUG bool operator()(const_key_reference r_lhs, const_key_reference r_rhs); #endif private: inline static const_key_reference extract_key(const_reference r_val, true_type); inline static const_key_reference extract_key(const_reference r_val, false_type); private: static integral_constant s_set_ind; }; PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC integral_constant PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::s_set_ind; PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: synth_e_access_traits() { } PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: synth_e_access_traits(const E_Access_Traits& r_traits) : E_Access_Traits(r_traits) { } PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC inline bool PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: equal_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after /*= false */) const { while (b_l != e_l) { if (b_r == e_r) return (false); if (base_type::e_pos(*b_l) != base_type::e_pos(*b_r)) return (false); ++b_l; ++b_r; } return (!compare_after || b_r == e_r); } PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC bool PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: equal_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const { return (equal_prefixes(base_type::begin(r_lhs_key), base_type::end(r_lhs_key), base_type::begin(r_rhs_key), base_type::end(r_rhs_key), true)); } PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC bool PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: cmp_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after /* = false*/) const { while (b_l != e_l) { if (b_r == e_r) return (false); const typename base_type::size_type l_pos = base_type::e_pos(*b_l); const typename base_type::size_type r_pos = base_type::e_pos(*b_r); if (l_pos != r_pos) return (l_pos < r_pos); ++b_l; ++b_r; } if (!compare_after) return (false); return (b_r != e_r); } PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC bool PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: cmp_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const { return (cmp_prefixes(base_type::begin(r_lhs_key), base_type::end(r_lhs_key), base_type::begin(r_rhs_key), base_type::end(r_rhs_key), true)); } PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: extract_key(const_reference r_val) { return (extract_key(r_val, s_set_ind)); } PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: extract_key(const_reference r_val, true_type) { return (r_val); } PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: extract_key(const_reference r_val, false_type) { return (r_val.first); } #ifdef _GLIBCXX_DEBUG PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC bool PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: operator()(const_key_reference r_lhs, const_key_reference r_rhs) { return (cmp_keys(r_lhs, r_rhs)); } #endif #undef PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC #undef PB_DS_SYNTH_E_ACCESS_TRAITS_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 split_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();); _GLIBCXX_DEBUG_ONLY(other.assert_valid();); split_join_branch_bag bag; leaf_pointer p_split_lf = split_prep(r_key, other, bag); if (p_split_lf == NULL) { _GLIBCXX_DEBUG_ASSERT(bag.empty()); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) return; } _GLIBCXX_DEBUG_ASSERT(!bag.empty()); other.clear(); m_p_head->m_p_parent = rec_split(m_p_head->m_p_parent, pref_begin(p_split_lf), pref_end(p_split_lf), other, bag); m_p_head->m_p_parent->m_p_parent = m_p_head; other.m_p_head->m_p_max = m_p_head->m_p_max; m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); other.m_p_head->m_p_min = other.leftmost_descendant(other.m_p_head->m_p_parent); other.m_size = std::distance(other.PB_DS_CLASS_C_DEC::begin(), other.PB_DS_CLASS_C_DEC::end()); m_size -= other.m_size; _GLIBCXX_DEBUG_ONLY(assert_valid();); _GLIBCXX_DEBUG_ONLY(other.assert_valid();); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::leaf_pointer PB_DS_CLASS_C_DEC:: split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) { _GLIBCXX_DEBUG_ASSERT(r_bag.empty()); if (m_size == 0) { other.clear(); _GLIBCXX_DEBUG_ONLY(assert_valid();); _GLIBCXX_DEBUG_ONLY(other.assert_valid();); return (NULL); } if (synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(static_cast(m_p_head->m_p_min)->value()))) { other.clear(); value_swap(other); _GLIBCXX_DEBUG_ONLY(assert_valid();); _GLIBCXX_DEBUG_ONLY(other.assert_valid();); return (NULL); } if (!synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(static_cast(m_p_head->m_p_max)->value()))) { _GLIBCXX_DEBUG_ONLY(assert_valid();); _GLIBCXX_DEBUG_ONLY(other.assert_valid();); return (NULL); } iterator it = lower_bound(r_key); if (!synth_e_access_traits::equal_keys(PB_DS_V2F(*it), r_key)) --it; node_pointer p_nd = it.m_p_nd; _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); leaf_pointer p_ret_l = static_cast(p_nd); while (p_nd->m_type != pat_trie_head_node_type) { r_bag.add_branch(); p_nd = p_nd->m_p_parent; } _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(synth_e_access_traits& )(*this), other);) return (p_ret_l); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: rec_split(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) { if (p_nd->m_type == pat_trie_leaf_node_type) { _GLIBCXX_DEBUG_ASSERT(other.m_p_head->m_p_parent == NULL); return (p_nd); } _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); internal_node_pointer p_internal_nd = static_cast(p_nd); node_pointer p_child_ret = rec_split(p_internal_nd->get_child_node(b_it, e_it, this), b_it, e_it, other, r_bag); _GLIBCXX_DEBUG_ONLY(p_child_ret->assert_valid(this);) p_internal_nd->replace_child(p_child_ret, b_it, e_it, this); apply_update(p_internal_nd, (node_update* )this); typename internal_node::iterator child_it = p_internal_nd->get_child_it(b_it, e_it, this); const size_type lhs_num_children = std::distance(p_internal_nd->begin(), child_it) + 1; _GLIBCXX_DEBUG_ASSERT(lhs_num_children > 0); size_type rhs_num_children = std::distance(p_internal_nd->begin(), p_internal_nd->end()) - lhs_num_children; if (rhs_num_children == 0) { apply_update(p_internal_nd, (node_update* )this); return (p_internal_nd); } ++child_it; other.split_insert_branch(p_internal_nd->get_e_ind(), b_it, child_it, rhs_num_children, r_bag); child_it = p_internal_nd->get_child_it(b_it, e_it, this); ++child_it; while (rhs_num_children != 0) { child_it = p_internal_nd->remove_child(child_it); --rhs_num_children; } apply_update(p_internal_nd, (node_update* )this); _GLIBCXX_DEBUG_ASSERT(std::distance(p_internal_nd->begin(), p_internal_nd->end()) >= 1); if (std::distance(p_internal_nd->begin(), p_internal_nd->end()) > 1) { p_internal_nd->update_prefixes(this); _GLIBCXX_DEBUG_ONLY(p_internal_nd->assert_valid(this);) apply_update(p_internal_nd, (node_update* )this); return (p_internal_nd); } node_pointer p_ret =* p_internal_nd->begin(); p_internal_nd->~internal_node(); s_internal_node_allocator.deallocate(p_internal_nd, 1); apply_update(p_ret, (node_update* )this); return (p_ret); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: split_insert_branch(size_type e_ind, const_e_iterator b_it, typename internal_node::iterator child_b_it, size_type num_children, split_join_branch_bag& r_bag) { #ifdef _GLIBCXX_DEBUG if (m_p_head->m_p_parent != NULL) m_p_head->m_p_parent->assert_valid(this); #endif const size_type total_num_children =((m_p_head->m_p_parent == NULL)? 0 : 1) + num_children; if (total_num_children == 0) { _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == NULL); return; } if (total_num_children == 1) { if (m_p_head->m_p_parent != NULL) { _GLIBCXX_DEBUG_ONLY(m_p_head->m_p_parent->assert_valid(this);) return; } _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == NULL); m_p_head->m_p_parent =* child_b_it; m_p_head->m_p_parent->m_p_parent = m_p_head; apply_update(m_p_head->m_p_parent, (node_update* )this); _GLIBCXX_DEBUG_ONLY(m_p_head->m_p_parent->assert_valid(this);) return; } _GLIBCXX_DEBUG_ASSERT(total_num_children > 1); internal_node_pointer p_new_root = r_bag.get_branch(); new (p_new_root) internal_node(e_ind, b_it); size_type num_inserted = 0; while (num_inserted++ < num_children) { _GLIBCXX_DEBUG_ONLY((*child_b_it)->assert_valid(this);) p_new_root->add_child(*child_b_it, pref_begin(*child_b_it), pref_end(*child_b_it), this); ++child_b_it; } if (m_p_head->m_p_parent != NULL) p_new_root->add_child(m_p_head->m_p_parent, pref_begin(m_p_head->m_p_parent), pref_end(m_p_head->m_p_parent), this); m_p_head->m_p_parent = p_new_root; p_new_root->m_p_parent = m_p_head; apply_update(m_p_head->m_p_parent, (node_update* )this); _GLIBCXX_DEBUG_ONLY(m_p_head->m_p_parent->assert_valid(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 find_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::point_iterator PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) node_pointer p_nd = find_imp(r_key); if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) return end(); } if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast(p_nd)->value()), r_key)) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); return iterator(p_nd); } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) return end(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_point_iterator PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) const { _GLIBCXX_DEBUG_ONLY(assert_valid();) const_node_pointer p_nd = const_cast(this)->find_imp(r_key); if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) return end(); } if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast(p_nd)->value()), r_key)) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); return const_iterator(const_cast(p_nd)); } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) return end(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: find_imp(const_key_reference r_key) { if (empty()) return (NULL); typename synth_e_access_traits::const_iterator b_it = synth_e_access_traits::begin(r_key); typename synth_e_access_traits::const_iterator e_it = synth_e_access_traits::end(r_key); node_pointer p_nd = m_p_head->m_p_parent; _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); while (p_nd->m_type != pat_trie_leaf_node_type) { _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); node_pointer p_next_nd = static_cast(p_nd)->get_child_node(b_it, e_it, this); if (p_next_nd == NULL) return p_nd; p_nd = p_next_nd; } return p_nd; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: lower_bound_imp(const_key_reference r_key) { if (empty()) return (m_p_head); node_pointer p_nd = m_p_head->m_p_parent; _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); typename PB_DS_CLASS_C_DEC::const_e_iterator b_it = synth_e_access_traits::begin(r_key); typename PB_DS_CLASS_C_DEC::const_e_iterator e_it = synth_e_access_traits::end(r_key); size_type checked_ind = 0; while (true) { if (p_nd->m_type == pat_trie_leaf_node_type) { if (!synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast(p_nd)->value()), r_key)) return p_nd; iterator it(p_nd); ++it; return it.m_p_nd; } _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); const size_type new_checked_ind = static_cast(p_nd)->get_e_ind(); p_nd = static_cast(p_nd)->get_lower_bound_child_node( b_it, e_it, checked_ind, this); checked_ind = new_checked_ind; } } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::point_iterator PB_DS_CLASS_C_DEC:: lower_bound(const_key_reference r_key) { return point_iterator(lower_bound_imp(r_key)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_point_iterator PB_DS_CLASS_C_DEC:: lower_bound(const_key_reference r_key) const { return const_point_iterator(const_cast(this)->lower_bound_imp(r_key)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::point_iterator PB_DS_CLASS_C_DEC:: upper_bound(const_key_reference r_key) { point_iterator l_bound_it = lower_bound(r_key); _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), r_key)); if (l_bound_it == end() || synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) return l_bound_it; return ++l_bound_it; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_point_iterator PB_DS_CLASS_C_DEC:: upper_bound(const_key_reference r_key) const { const_point_iterator l_bound_it = lower_bound(r_key); _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), r_key)); if (l_bound_it == end() || synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) return l_bound_it; return ++l_bound_it; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_e_iterator PB_DS_CLASS_C_DEC:: pref_begin(const_node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) return (synth_e_access_traits::begin(PB_DS_V2F(static_cast(p_nd)->value()))); _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); return static_cast(p_nd)->pref_b_it(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_e_iterator PB_DS_CLASS_C_DEC:: pref_end(const_node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) return (synth_e_access_traits::end(PB_DS_V2F(static_cast(p_nd)->value()))); _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); return static_cast(p_nd)->pref_e_it(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer PB_DS_CLASS_C_DEC:: leftmost_descendant(const_node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) return static_cast(p_nd); return static_cast(p_nd)->leftmost_descendant(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::leaf_pointer PB_DS_CLASS_C_DEC:: leftmost_descendant(node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) return static_cast(p_nd); return static_cast(p_nd)->leftmost_descendant(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer PB_DS_CLASS_C_DEC:: rightmost_descendant(const_node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) return static_cast(p_nd); return static_cast(p_nd)->rightmost_descendant(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::leaf_pointer PB_DS_CLASS_C_DEC:: rightmost_descendant(node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) return static_cast(p_nd); return static_cast(p_nd)->rightmost_descendant(); } // -*- 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 bin_search_tree_. */ PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::head_allocator PB_DS_CLASS_C_DEC::s_head_allocator; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::internal_node_allocator PB_DS_CLASS_C_DEC::s_internal_node_allocator; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::leaf_allocator PB_DS_CLASS_C_DEC::s_leaf_allocator; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME() : m_p_head(s_head_allocator.allocate(1)), m_size(0) { initialize(); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const e_access_traits& r_e_access_traits) : synth_e_access_traits(r_e_access_traits), m_p_head(s_head_allocator.allocate(1)), m_size(0) { initialize(); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : #ifdef _GLIBCXX_DEBUG debug_base(other), #endif synth_e_access_traits(other), node_update(other), m_p_head(s_head_allocator.allocate(1)), m_size(0) { initialize(); m_size = other.m_size; _GLIBCXX_DEBUG_ONLY(other.assert_valid();) if (other.m_p_head->m_p_parent == NULL) { _GLIBCXX_DEBUG_ONLY(assert_valid();) return; } try { m_p_head->m_p_parent = recursive_copy_node(other.m_p_head->m_p_parent); } catch(...) { s_head_allocator.deallocate(m_p_head, 1); __throw_exception_again; } m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent); m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); m_p_head->m_p_parent->m_p_parent = m_p_head; _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) value_swap(other); std::swap((e_access_traits& )(*this), (e_access_traits& )other); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: value_swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) std::swap(m_p_head, other.m_p_head); std::swap(m_size, other.m_size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~PB_DS_CLASS_NAME() { clear(); s_head_allocator.deallocate(m_p_head, 1); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: initialize() { new (m_p_head) head(); m_p_head->m_p_parent = NULL; m_p_head->m_p_min = m_p_head; m_p_head->m_p_max = m_p_head; m_size = 0; } PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: copy_from_range(It first_it, It last_it) { while (first_it != last_it) insert(*(first_it++)); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: recursive_copy_node(const_node_pointer p_other_nd) { _GLIBCXX_DEBUG_ASSERT(p_other_nd != NULL); if (p_other_nd->m_type == pat_trie_leaf_node_type) { const_leaf_pointer p_other_leaf = static_cast(p_other_nd); leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); cond_dealtor cond(p_new_lf); new (p_new_lf) leaf(p_other_leaf->value()); apply_update(p_new_lf, (node_update* )this); cond.set_no_action_dtor(); return (p_new_lf); } _GLIBCXX_DEBUG_ASSERT(p_other_nd->m_type == pat_trie_internal_node_type); node_pointer a_p_children[internal_node::arr_size]; size_type child_i = 0; const_internal_node_pointer p_other_internal_nd = static_cast(p_other_nd); typename internal_node::const_iterator child_it = p_other_internal_nd->begin(); internal_node_pointer p_ret; try { while (child_it != p_other_internal_nd->end()) a_p_children[child_i++] = recursive_copy_node(*(child_it++)); p_ret = s_internal_node_allocator.allocate(1); } catch(...) { while (child_i-- > 0) clear_imp(a_p_children[child_i]); __throw_exception_again; } new (p_ret) internal_node(p_other_internal_nd->get_e_ind(), pref_begin(a_p_children[0])); --child_i; _GLIBCXX_DEBUG_ASSERT(child_i > 1); do p_ret->add_child(a_p_children[child_i], pref_begin(a_p_children[child_i]), pref_end(a_p_children[child_i]), this); while (child_i-- > 0); apply_update(p_ret, (node_update* )this); return p_ret; } // -*- 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 point_iterators.hpp * Contains an implementation class for bin_search_tree_. */ #ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP #define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP #include namespace __gnu_pbds { namespace detail { #define PB_DS_CONST_IT_C_DEC \ pat_trie_const_it_< \ Type_Traits, \ Node, \ Leaf, \ Head, \ Internal_Node, \ Is_Forward_Iterator, \ Allocator> #define PB_DS_CONST_ODIR_IT_C_DEC \ pat_trie_const_it_< \ Type_Traits, \ Node, \ Leaf, \ Head, \ Internal_Node, \ !Is_Forward_Iterator, \ Allocator> #define PB_DS_IT_C_DEC \ pat_trie_it_< \ Type_Traits, \ Node, \ Leaf, \ Head, \ Internal_Node, \ Is_Forward_Iterator, \ Allocator> #define PB_DS_ODIR_IT_C_DEC \ pat_trie_it_< \ Type_Traits, \ Node, \ Leaf, \ Head, \ Internal_Node, \ !Is_Forward_Iterator, \ Allocator> // Const iterator. template class pat_trie_const_it_ { private: typedef typename Allocator::template rebind< Node>::other::pointer node_pointer; typedef typename Allocator::template rebind< Leaf>::other::const_pointer const_leaf_pointer; typedef typename Allocator::template rebind< Leaf>::other::pointer leaf_pointer; typedef typename Allocator::template rebind< Head>::other::pointer head_pointer; typedef typename Allocator::template rebind< Internal_Node>::other::pointer internal_node_pointer; public: typedef std::bidirectional_iterator_tag iterator_category; typedef typename Allocator::difference_type difference_type; typedef typename Type_Traits::value_type value_type; typedef typename Type_Traits::pointer pointer; typedef typename Type_Traits::const_pointer const_pointer; typedef typename Type_Traits::reference reference; typedef typename Type_Traits::const_reference const_reference; public: inline pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd) { } inline pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other) : m_p_nd(other.m_p_nd) { } inline PB_DS_CONST_IT_C_DEC& operator=(const PB_DS_CONST_IT_C_DEC& other) { m_p_nd = other.m_p_nd; return *this; } inline PB_DS_CONST_IT_C_DEC& operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other) { m_p_nd = other.m_p_nd; return *this; } inline const_pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type); return &static_cast(m_p_nd)->value(); } inline const_reference operator*() const { _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type); return static_cast(m_p_nd)->value(); } inline bool operator==(const PB_DS_CONST_IT_C_DEC& other) const { return (m_p_nd == other.m_p_nd); } inline bool operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const { return (m_p_nd == other.m_p_nd); } inline bool operator!=(const PB_DS_CONST_IT_C_DEC& other) const { return (m_p_nd != other.m_p_nd); } inline bool operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const { return (m_p_nd != other.m_p_nd); } inline PB_DS_CONST_IT_C_DEC& operator++() { inc(integral_constant()); return *this; } inline PB_DS_CONST_IT_C_DEC operator++(int) { PB_DS_CONST_IT_C_DEC ret_it(m_p_nd); operator++(); return ret_it; } inline PB_DS_CONST_IT_C_DEC& operator--() { dec(integral_constant()); return *this; } inline PB_DS_CONST_IT_C_DEC operator--(int) { PB_DS_CONST_IT_C_DEC ret_it(m_p_nd); operator--(); return ret_it; } protected: inline void inc(false_type) { dec(true_type()); } void inc(true_type) { if (m_p_nd->m_type == pat_trie_head_node_type) { m_p_nd = static_cast(m_p_nd)->m_p_min; return; } node_pointer p_y = m_p_nd->m_p_parent; while (p_y->m_type != pat_trie_head_node_type && get_larger_sibling(m_p_nd) == NULL) { m_p_nd = p_y; p_y = p_y->m_p_parent; } if (p_y->m_type == pat_trie_head_node_type) { m_p_nd = p_y; return; } m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd)); } inline void dec(false_type) { inc(true_type()); } void dec(true_type) { if (m_p_nd->m_type == pat_trie_head_node_type) { m_p_nd = static_cast(m_p_nd)->m_p_max; return; } node_pointer p_y = m_p_nd->m_p_parent; while (p_y->m_type != pat_trie_head_node_type && get_smaller_sibling(m_p_nd) == NULL) { m_p_nd = p_y; p_y = p_y->m_p_parent; } if (p_y->m_type == pat_trie_head_node_type) { m_p_nd = p_y; return; } m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd)); } inline static node_pointer get_larger_sibling(node_pointer p_nd) { internal_node_pointer p_parent = static_cast(p_nd->m_p_parent); typename Internal_Node::iterator it = p_parent->begin(); while (*it != p_nd) ++it; typename Internal_Node::iterator next_it = it; ++next_it; return ((next_it == p_parent->end())? NULL :* next_it); } inline static node_pointer get_smaller_sibling(node_pointer p_nd) { internal_node_pointer p_parent = static_cast(p_nd->m_p_parent); typename Internal_Node::iterator it = p_parent->begin(); if (*it == p_nd) return (NULL); typename Internal_Node::iterator prev_it; do { prev_it = it; ++it; if (*it == p_nd) return (*prev_it); } while (true); _GLIBCXX_DEBUG_ASSERT(false); return (NULL); } inline static leaf_pointer leftmost_descendant(node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) return static_cast(p_nd); return static_cast(p_nd)->leftmost_descendant(); } inline static leaf_pointer rightmost_descendant(node_pointer p_nd) { if (p_nd->m_type == pat_trie_leaf_node_type) return static_cast(p_nd); return static_cast(p_nd)->rightmost_descendant(); } public: node_pointer m_p_nd; }; // Iterator. template class pat_trie_it_ : public PB_DS_CONST_IT_C_DEC { private: typedef typename Allocator::template rebind< Node>::other::pointer node_pointer; typedef typename Allocator::template rebind< Leaf>::other::const_pointer const_leaf_pointer; typedef typename Allocator::template rebind< Leaf>::other::pointer leaf_pointer; typedef typename Allocator::template rebind< Head>::other::pointer head_pointer; typedef typename Allocator::template rebind< Internal_Node>::other::pointer internal_node_pointer; public: typedef typename Type_Traits::value_type value_type; typedef typename Type_Traits::const_pointer const_pointer; typedef typename Type_Traits::pointer pointer; typedef typename Type_Traits::const_reference const_reference; typedef typename Type_Traits::reference reference; inline pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd) { } inline pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd) { } inline PB_DS_IT_C_DEC& operator=(const PB_DS_IT_C_DEC& other) { base_it_type::m_p_nd = other.m_p_nd; return *this; } inline PB_DS_IT_C_DEC& operator=(const PB_DS_ODIR_IT_C_DEC& other) { base_it_type::m_p_nd = other.m_p_nd; return *this; } inline pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type); return &static_cast(base_it_type::m_p_nd)->value(); } inline reference operator*() const { _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type); return static_cast(base_it_type::m_p_nd)->value(); } inline PB_DS_IT_C_DEC& operator++() { PB_DS_CONST_IT_C_DEC:: operator++(); return *this; } inline PB_DS_IT_C_DEC operator++(int) { PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd); operator++(); return ret_it; } inline PB_DS_IT_C_DEC& operator--() { PB_DS_CONST_IT_C_DEC::operator--(); return *this; } inline PB_DS_IT_C_DEC operator--(int) { PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd); operator--(); return ret_it; } protected: typedef PB_DS_CONST_IT_C_DEC base_it_type; friend class PB_DS_CLASS_C_DEC; }; #undef PB_DS_CONST_IT_C_DEC #undef PB_DS_CONST_ODIR_IT_C_DEC #undef PB_DS_IT_C_DEC #undef PB_DS_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 pat_trie_. */ #i