fdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { if (m_p_head->m_p_parent != NULL) m_p_head->m_p_parent->assert_valid(this); assert_iterators(); assert_reverse_iterators(); if (m_p_head->m_p_parent == NULL) { _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_min == m_p_head); _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_max == m_p_head); _GLIBCXX_DEBUG_ASSERT(empty()); return; } _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_min->m_type == pat_trie_leaf_node_type); _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_max->m_type == pat_trie_leaf_node_type); _GLIBCXX_DEBUG_ASSERT(!empty()); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_iterators() const { size_type calc_size = 0; for (const_iterator it = begin(); it != end(); ++it) { ++calc_size; debug_base::check_key_exists(PB_DS_V2F(*it)); _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)) == it); _GLIBCXX_DEBUG_ASSERT(--upper_bound(PB_DS_V2F(*it)) == it); } _GLIBCXX_DEBUG_ASSERT(calc_size == m_size); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_reverse_iterators() const { size_type calc_size = 0; for (const_reverse_iterator it = rbegin(); it != rend(); ++it) { ++calc_size; const_node_pointer p_nd = const_cast(this)->find_imp(PB_DS_V2F(*it)); _GLIBCXX_DEBUG_ASSERT(p_nd == it.m_p_nd); } _GLIBCXX_DEBUG_ASSERT(calc_size == m_size); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: recursive_count_leafs(const_node_pointer p_nd) { if (p_nd == NULL) return (0); if (p_nd->m_type == pat_trie_leaf_node_type) return (1); _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); size_type ret = 0; for (typename internal_node::const_iterator it = static_cast(p_nd)->begin(); it != static_cast(p_nd)->end(); ++it) ret += recursive_count_leafs(*it); return ret; } #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 node_metadata_base.hpp * Contains an internal PB_DS_BASE_C_DEC for a patricia tree. */ #ifndef PB_DS_PAT_TRIE_NODE_METADATA_BASE_HPP #define PB_DS_PAT_TRIE_NODE_METADATA_BASE_HPP #include namespace __gnu_pbds { namespace detail { template struct pat_trie_node_metadata_base { public: typedef Metadata metadata_type; typedef typename Allocator::template rebind< metadata_type>::other::const_reference const_metadata_reference; public: inline const_metadata_reference get_metadata() const { return (m_metadata); } public: metadata_type m_metadata; }; template struct pat_trie_node_metadata_base< null_node_metadata, Allocator> { public: typedef null_node_metadata metadata_type; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_PAT_TRIE_NODE_BASE_HPP // -*- C++ -*- // Copyright (C) 2005, 2006, 2007 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 pat_trie_.hpp * Contains an implementation class for a patricia tree. */ /** * This implementation loosely borrows ideas from: * 1) "Fast Mergeable Integer Maps", Okasaki, Gill 1998 * 2) "Ptset: Sets of integers implemented as Patricia trees", * Jean-Christophe Filliatr, 2000 **/ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef _GLIBCXX_DEBUG #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 pat_trie_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_CLASS_NAME pat_trie_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 >, 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 /** * class description = PATRICIA trie implementation."> **/ template class PB_DS_CLASS_NAME : #ifdef _GLIBCXX_DEBUG public PB_DS_DEBUG_MAP_BASE_C_DEC, #endif public Node_And_It_Traits::synth_e_access_traits, public Node_And_It_Traits::node_update, public PB_DS_TYPES_TRAITS_C_DEC { private: typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; typedef typename Node_And_It_Traits::synth_e_access_traits synth_e_access_traits; typedef typename Allocator::template rebind::other::const_pointer const_e_access_traits_pointer; typedef typename synth_e_access_traits::const_iterator const_e_iterator; typedef typename Node_And_It_Traits::node node; typedef typename Allocator::template rebind::other::const_pointer const_node_pointer; typedef typename Allocator::template rebind::other::pointer node_pointer; typedef typename Node_And_It_Traits::head head; typedef typename Allocator::template rebind::other head_allocator; typedef typename head_allocator::pointer head_pointer; typedef typename Node_And_It_Traits::leaf leaf; typedef typename Allocator::template rebind::other leaf_allocator; typedef typename leaf_allocator::const_pointer const_leaf_pointer; typedef typename leaf_allocator::pointer leaf_pointer; typedef typename Node_And_It_Traits::internal_node internal_node; typedef typename Allocator::template rebind::other internal_node_allocator; typedef typename internal_node_allocator::const_pointer const_internal_node_pointer; typedef typename internal_node_allocator::pointer internal_node_pointer; #include #ifdef _GLIBCXX_DEBUG typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; #endif #include typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer; public: typedef pat_trie_tag container_category; typedef Allocator allocator; typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; typedef typename traits_base::key_type key_type; typedef typename traits_base::key_pointer key_pointer; typedef typename traits_base::const_key_pointer const_key_pointer; typedef typename traits_base::key_reference key_reference; typedef typename traits_base::const_key_reference const_key_reference; typedef typename traits_base::mapped_type mapped_type; typedef typename traits_base::mapped_pointer mapped_pointer; typedef typename traits_base::const_mapped_pointer const_mapped_pointer; typedef typename traits_base::mapped_reference mapped_reference; typedef typename traits_base::const_mapped_reference const_mapped_reference; typedef typename traits_base::value_type value_type; typedef typename traits_base::pointer pointer; typedef typename traits_base::const_pointer const_pointer; typedef typename traits_base::reference reference; typedef typename traits_base::const_reference const_reference; typedef typename Node_And_It_Traits::const_iterator const_point_iterator; typedef typename Node_And_It_Traits::iterator point_iterator; typedef const_point_iterator const_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 typename Node_And_It_Traits::e_access_traits e_access_traits; typedef typename Node_And_It_Traits::node_update node_update; PB_DS_CLASS_NAME(); PB_DS_CLASS_NAME(const e_access_traits&); PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); void swap(PB_DS_CLASS_C_DEC&); ~PB_DS_CLASS_NAME(); inline bool empty() const; inline size_type size() const; inline size_type max_size() const; e_access_traits& get_e_access_traits(); const e_access_traits& get_e_access_traits() const; node_update& get_node_update(); const node_update& get_node_update() const; inline std::pair insert(const_reference); inline mapped_reference operator[](const_key_reference r_key) { #ifdef PB_DS_DATA_TRUE_INDICATOR return insert(std::make_pair(r_key, mapped_type())).first->second; #else insert(r_key); return traits_base::s_null_mapped; #endif } inline point_iterator find(const_key_reference); inline const_point_iterator find(const_key_reference) const; inline point_iterator lower_bound(const_key_reference); inline const_point_iterator lower_bound(const_key_reference) const; inline point_iterator upper_bound(const_key_reference); inline const_point_iterator upper_bound(const_key_reference) const; void clear(); inline bool erase(const_key_reference); inline const_iterator erase(const_iterator); #ifdef PB_DS_DATA_TRUE_INDICATOR inline iterator erase(iterator); #endif inline const_reverse_iterator erase(const_reverse_iterator); #ifdef PB_DS_DATA_TRUE_INDICATOR inline reverse_iterator erase(reverse_iterator); #endif template inline size_type erase_if(Pred); void join(PB_DS_CLASS_C_DEC&); void split(const_key_reference, PB_DS_CLASS_C_DEC&); 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(); #ifdef PB_DS_PAT_TRIE_TRACE_ void trace() const; #endif protected: template void copy_from_range(It, It); void value_swap(PB_DS_CLASS_C_DEC&); node_pointer recursive_copy_node(const_node_pointer); private: void initialize(); inline void apply_update(node_pointer, null_node_update_pointer); template inline void apply_update(node_pointer, Node_Update_*); bool join_prep(PB_DS_CLASS_C_DEC&, split_join_branch_bag&); void rec_join_prep(const_node_pointer, const_node_pointer, split_join_branch_bag&); void rec_join_prep(const_leaf_pointer, const_leaf_pointer, split_join_branch_bag&); void rec_join_prep(const_leaf_pointer, const_internal_node_pointer, split_join_branch_bag&); void rec_join_prep(const_internal_node_pointer, const_leaf_pointer, split_join_branch_bag&); void rec_join_prep(const_internal_node_pointer, const_internal_node_pointer, split_join_branch_bag&); node_pointer rec_join(node_pointer, node_pointer, size_type, split_join_branch_bag&); node_pointer rec_join(leaf_pointer, leaf_pointer, split_join_branch_bag&); node_pointer rec_join(leaf_pointer, internal_node_pointer, size_type, split_join_branch_bag&); node_pointer rec_join(internal_node_pointer, leaf_pointer, size_type, split_join_branch_bag&); node_pointer rec_join(internal_node_pointer, internal_node_pointer, split_join_branch_bag&); size_type keys_diff_ind(typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_Ò4Ó4Ô4Õ4access_traits::const_iterator, typename e_access_traits::const_iterator); internal_node_pointer insert_branch(node_pointer, node_pointer, split_join_branch_bag&); void update_min_max_for_inserted_leaf(leaf_pointer); void erase_leaf(leaf_pointer); inline void actual_erase_leaf(leaf_pointer); void clear_imp(node_pointer); void erase_fixup(internal_node_pointer); void update_min_max_for_erased_leaf(leaf_pointer); static inline const_e_iterator pref_begin(const_node_pointer); static inline const_e_iterator pref_end(const_node_pointer); inline node_pointer find_imp(const_key_reference); inline node_pointer lower_bound_imp(const_key_reference); inline node_pointer upper_bound_imp(const_key_reference); inline static const_leaf_pointer leftmost_descendant(const_node_pointer); inline static leaf_pointer leftmost_descendant(node_pointer); inline static const_leaf_pointer rightmost_descendant(const_node_pointer); inline static leaf_pointer rightmost_descendant(node_pointer); #ifdef _GLIBCXX_DEBUG void assert_valid() const; void assert_iterators() const; void assert_reverse_iterators() const; static size_type recursive_count_leafs(const_node_pointer); #endif #ifdef PB_DS_PAT_TRIE_TRACE_ static void trace_node(const_node_pointer, size_type); template static void trace_node_metadata(const_node_pointer, type_to_type); static void trace_node_metadata(const_node_pointer, type_to_type); #endif leaf_pointer split_prep(const_key_reference, PB_DS_CLASS_C_DEC&, split_join_branch_bag&); node_pointer rec_split(node_pointer, const_e_iterator, const_e_iterator, PB_DS_CLASS_C_DEC&, split_join_branch_bag&); void split_insert_branch(size_type, const_e_iterator, typename internal_node::iterator, size_type, split_join_branch_bag&); static head_allocator s_head_allocator; static internal_node_allocator s_internal_node_allocator; static leaf_allocator s_leaf_allocator; head_pointer m_p_head; size_type m_size; }; #include #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 #undef PB_DS_V2F #undef PB_DS_EP2VP #undef PB_DS_V2S } // namespace detail } // namespace __gnu_pbds // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file erase_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { node_pointer p_nd = find_imp(r_key); if (p_nd == NULL || p_nd->m_type == pat_trie_internal_node_type) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); return false; } _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); if (!synth_e_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast(p_nd)->value()), r_key)) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); return false; } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); erase_leaf(static_cast(p_nd)); _GLIBCXX_DEBUG_ONLY(assert_valid();) return true; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: erase_fixup(internal_node_pointer p_nd) { _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1); if (std::distance(p_nd->begin(), p_nd->end()) == 1) { node_pointer p_parent = p_nd->m_p_parent; if (p_parent == m_p_head) m_p_head->m_p_parent =* p_nd->begin(); else { _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); node_pointer p_new_child =* p_nd->begin(); static_cast(p_parent)->replace_child( p_new_child, pref_begin(p_new_child), pref_end(p_new_child), this); } (*p_nd->begin())->m_p_parent = p_nd->m_p_parent; p_nd->~internal_node(); s_internal_node_allocator.deallocate(p_nd, 1); if (p_parent == m_p_head) return; _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); p_nd = static_cast(p_parent); } while (true) { _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1); p_nd->update_prefixes(this); apply_update(p_nd, (node_update* )this); _GLIBCXX_DEBUG_ONLY(p_nd->assert_valid(this);) if (p_nd->m_p_parent->m_type == pat_trie_head_node_type) return; _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type == pat_trie_internal_node_type); p_nd = static_cast(p_nd->m_p_parent); } } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: actual_erase_leaf(leaf_pointer p_l) { _GLIBCXX_DEBUG_ASSERT(m_size > 0); --m_size; _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_l->value()))); p_l->~leaf(); s_leaf_allocator.deallocate(p_l, 1); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear() { _GLIBCXX_DEBUG_ONLY(assert_valid();) if (empty()) return; clear_imp(m_p_head->m_p_parent); m_size = 0; initialize(); _GLIBCXX_DEBUG_ONLY(debug_base::clear();) _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear_imp(node_pointer p_nd) { if (p_nd->m_type == pat_trie_internal_node_type) { _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); for (typename internal_node::iterator it = static_cast(p_nd)->begin(); it != static_cast(p_nd)->end(); ++it) { node_pointer p_child =* it; clear_imp(p_child); } s_internal_node_allocator.deallocate(static_cast(p_nd), 1); return; } _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); static_cast(p_nd)->~leaf(); s_leaf_allocator.deallocate(static_cast(p_nd), 1); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: erase(const_iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it == end()) return it; const_iterator ret_it = it; ++ret_it; _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); erase_leaf(static_cast(it.m_p_nd)); _GLIBCXX_DEBUG_ONLY(assert_valid()); return ret_it; } #ifdef PB_DS_DATA_TRUE_INDICATOR PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: erase(iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it == end()) return it; iterator ret_it = it; ++ret_it; _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); erase_leaf(static_cast(it.m_p_nd)); _GLIBCXX_DEBUG_ONLY(assert_valid()); return ret_it; } #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator PB_DS_CLASS_C_DEC:: erase(const_reverse_iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it.m_p_nd == m_p_head) return it; const_reverse_iterator ret_it = it; ++ret_it; _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); erase_leaf(static_cast(it.m_p_nd)); _GLIBCXX_DEBUG_ONLY(assert_valid()); return ret_it; } #ifdef PB_DS_DATA_TRUE_INDICATOR PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::reverse_iterator PB_DS_CLASS_C_DEC:: erase(reverse_iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it.m_p_nd == m_p_head) return it; reverse_iterator ret_it = it; ++ret_it; _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); erase_leaf(static_cast(it.m_p_nd)); _GLIBCXX_DEBUG_ONLY(assert_valid()); return ret_it; } #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR PB_DS_CLASS_T_DEC template inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { size_type num_ersd = 0; _GLIBCXX_DEBUG_ONLY(assert_valid();) iterator it = begin(); while (it != end()) { _GLIBCXX_DEBUG_ONLY(assert_valid();) if (pred(*it)) { ++num_ersd; it = erase(it); } else ++it; } _GLIBCXX_DEBUG_ONLY(assert_valid();) return num_ersd; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: erase_leaf(leaf_pointer p_l) { update_min_max_for_erased_leaf(p_l); if (p_l->m_p_parent->m_type == pat_trie_head_node_type) { _GLIBCXX_DEBUG_ASSERT(size() == 1); clear(); return; } _GLIBCXX_DEBUG_ASSERT(size() > 1); _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type == pat_trie_internal_node_type); internal_node_pointer p_parent = static_cast(p_l->m_p_parent); p_parent->remove_child(p_l); erase_fixup(p_parent); actual_erase_leaf(p_l); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: update_min_max_for_erased_leaf(leaf_pointer p_l) { if (m_size == 1) { m_p_head->m_p_min = m_p_head; m_p_head->m_p_max = m_p_head; return; } if (p_l == static_cast(m_p_head->m_p_min)) { iterator it(p_l); ++it; m_p_head->m_p_min = it.m_p_nd; return; } if (p_l == static_cast(m_p_head->m_p_max)) { iterator it(p_l); --it; m_p_head->m_p_max = it.m_p_nd; } } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file traits.hpp * Contains an implementation class for pat_trie_. */ #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP #define PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP #include #include #include #include #include #include #include namespace __gnu_pbds { namespace detail { template class Node_Update, class Allocator> struct trie_traits< Key, Mapped, E_Access_Traits, Node_Update, pat_trie_tag, Allocator> { private: typedef types_traits< Key, Mapped, Allocator, false> type_traits; public: typedef typename trie_node_metadata_selector< Key, Mapped, E_Access_Traits, Node_Update, Allocator>::type metadata_type; typedef E_Access_Traits e_access_traits; typedef __gnu_pbds::detail::synth_e_access_traits< type_traits, false, e_access_traits> synth_e_access_traits; typedef pat_trie_node_base< type_traits, synth_e_access_traits, metadata_type, Allocator> node; typedef pat_trie_leaf< type_traits, synth_e_access_traits, metadata_type, Allocator> leaf; typedef pat_trie_head< type_traits, synth_e_access_traits, metadata_type, Allocator> head; typedef pat_trie_internal_node< type_traits, synth_e_access_traits, metadata_type, Allocator> internal_node; typedef pat_trie_const_it_< type_traits, node, leaf, head, internal_node, true, Allocator> const_iterator; typedef pat_trie_it_< type_traits, node, leaf, head, internal_node, true, Allocator> iterator; typedef pat_trie_const_it_< type_traits, node, leaf, head, internal_node, false, Allocator> const_reverse_iterator; typedef pat_trie_it_< type_traits, node, leaf, head, internal_node, false, Allocator> reverse_iterator; typedef pat_trie_const_node_it_< node, leaf, head, internal_node, const_iterator, iterator, synth_e_access_traits, Allocator> const_node_iterator; typedef pat_trie_node_it_< node, leaf, head, internal_node, const_iterator, iterator, synth_e_access_traits, Allocator> node_iterator; typedef Node_Update< const_node_iterator, node_iterator, E_Access_Traits, Allocator> node_update; typedef __gnu_pbds::null_trie_node_update< const_node_iterator, node_iterator, E_Access_Traits, Allocator>* null_node_update_pointer; }; template class Node_Update, class Allocator> struct trie_traits< Key, null_mapped_type, E_Access_Traits, Node_Update, pat_trie_tag, Allocator> { private: typedef types_traits< Key, null_mapped_type, Allocator, false> type_traits; public: typedef typename trie_node_metadata_selector< Key, null_mapped_type, E_Access_Traits, Node_Update, Allocator>::type metadata_type; typedef E_Access_Traits e_access_traits; typedef __gnu_pbds::detail::synth_e_access_traits< type_traits, true, e_access_traits> synth_e_access_traits; typedef pat_trie_node_base< type_traits, synth_e_access_traits, metadata_type, Allocator> node; typedef pat_trie_leaf< type_traits, synth_e_access_traits, metadata_type, Allocator> leaf; typedef pat_trie_head< type_traits, synth_e_access_traits, metadata_type, Allocator> head; typedef pat_trie_internal_node< type_traits, synth_e_access_traits, metadata_type, Allocator> internal_node; typedef pat_trie_const_it_< type_traits, node, leaf, head, internal_node, true, Allocator> const_iterator; typedef const_iterator iterator; typedef pat_trie_const_it_< type_traits, node, leaf, head, internal_node, false, Allocator> const_reverse_iterator; typedef const_reverse_iterator reverse_iterator; typedef pat_trie_const_node_it_< node, leaf, head, internal_node, const_iterator, iterator, synth_e_access_traits, Allocator> const_node_iterator; typedef const_node_iterator node_iterator; typedef Node_Update< const_node_iterator, node_iterator, E_Access_Traits, Allocator> node_update; typedef __gnu_pbds::null_trie_node_update< const_node_iterator, const_node_iterator, E_Access_Traits, Allocator>* null_node_update_pointer; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP // -*- C++ -*- // Copyright (C) 2005, 2006, 2007 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 internal_node.hpp * Contains an internal PB_DS_BASE_C_DEC for a patricia tree. */ #ifndef PB_DS_PAT_TRIE_INTERNAL_NODE_HPP #define PB_DS_PAT_TRIE_INTERNAL_NODE_HPP #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ pat_trie_internal_node #define PB_DS_BASE_C_DEC \ pat_trie_node_base #define PB_DS_LEAF_C_DEC \ pat_trie_leaf template struct pat_trie_internal_node : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; typedef Type_Traits type_traits; typedef typename type_traits::value_type value_type; typedef typename Allocator::size_type size_type; typedef E_Access_Traits e_access_traits; typedef typename e_access_traits::const_iterator const_e_iterator; typedef typename Allocator::template rebind::other access_rebind; typedef typename access_rebind::const_pointer const_e_access_traits_pointer; typedef typename Allocator::template rebind::other base_rebind; typedef typename base_rebind::pointer node_pointer; typedef typename base_rebind::const_pointer const_node_pointer; typedef PB_DS_LEAF_C_DEC leaf; typedef typename Allocator::template rebind::other leaf_rebind; typedef typename leaf_rebind::pointer leaf_pointer; typedef typename leaf_rebind::const_pointer const_leaf_pointer; typedef typename Allocator::template rebind::other internal_node_rebind; typedef typename internal_node_rebind::pointer internal_node_pointer; typedef typename internal_node_rebind::const_pointer const_internal_node_pointer; #ifdef _GLIBCXX_DEBUG typedef typename base_type::subtree_debug_info subtree_debug_info; virtual subtree_debug_info assert_valid_imp(const_e_access_traits_pointer) const; #endif inline size_type get_pref_pos(const_e_iterator, const_e_iterator, const_e_access_traits_pointer) const; public: typedef typename Allocator::template rebind::other node_pointer_rebind; typedef typename node_pointer_rebind::pointer node_pointer_pointer; typedef typename node_pointer_rebind::reference node_pointer_reference; enum { arr_size = E_Access_Traits::max_size + 1 }; PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2); #include #include pat_trie_internal_node(size_type, const const_e_iterator); void update_prefixes(const_e_access_traits_pointer); const_iterator begin() const; iterator begin(); const_iterator end() const; iterator end(); inline node_pointer get_child_node(const_e_iterator, const_e_iterator, const_e_access_traits_pointer); inline const_node_pointer get_child_node(const_e_iterator, const_e_iterator, const_e_access_traits_pointer) const; inline iterator get_child_it(const_e_iterator, const_e_iterator, const_e_access_traits_pointer); inline node_pointer get_lower_bound_child_node(const_e_iterator, const_e_iterator, size_type, const_e_access_traits_pointer); inline node_pointer add_child(node_pointer, const_e_iterator, const_e_iterator, const_e_access_traits_pointer); inline const_node_pointer get_join_child(const_node_pointer, const_e_access_traits_pointer) const; inline node_pointer get_join_child(node_pointer, const_e_access_traits_pointer); void remove_child(node_pointer p_nd); iterator remove_child(iterator it); void replace_child(node_pointer, const_e_iterator, const_e_iterator, const_e_access_traits_pointer); inline const_e_iterator pref_b_it() const; inline const_e_iterator pref_e_it() const; inline size_type get_e_ind() const; bool should_be_mine(const_e_iterator, const_e_iterator, size_type, const_e_access_traits_pointer) const; leaf_pointer leftmost_descendant(); const_leaf_pointer leftmost_descendant() const; leaf_pointer rightmost_descendant(); const_leaf_pointer rightmost_descendant() const; #ifdef _GLIBCXX_DEBUG size_type e_ind() const; #endif private: pat_trie_internal_node(const pat_trie_internal_node&); size_type get_begin_pos() const; const size_type m_e_ind; const_e_iterator m_pref_b_it; const_e_iterator m_pref_e_it; node_pointer m_a_p_children[arr_size]; static leaf_rebind s_leaf_alloc; static internal_node_rebind s_internal_node_alloc; }; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::leaf_rebind PB_DS_CLASS_C_DEC::s_leaf_alloc; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::internal_node_rebind PB_DS_CLASS_C_DEC::s_internal_node_alloc; PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: get_pref_pos(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) const { if (static_cast(std::distance(b_it, e_it)) <= m_e_ind) return 0; std::advance(b_it, m_e_ind); return 1 + p_traits->e_pos(*b_it); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: pat_trie_internal_node(size_type len, const const_e_iterator it) : PB_DS_BASE_C_DEC(pat_trie_internal_node_type), m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it) { std::advance(m_pref_e_it, m_e_ind); std::fill(m_a_p_children, m_a_p_children + arr_size, static_cast(NULL)); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: update_prefixes(const_e_access_traits_pointer p_traits) { node_pointer p_first = *begin(); if (p_first->m_type == pat_trie_leaf_node_type) { const_leaf_pointer p = static_cast(p_first); m_pref_b_it = p_traits->begin(e_access_traits::extract_key(p->value())); } else { _GLIBCXX_DEBUG_ASSERT(p_first->m_type == pat_trie_internal_node_type); m_pref_b_it = static_cast(p_first)->pref_b_it(); } m_pref_e_it = m_pref_b_it; std::advance(m_pref_e_it, m_e_ind); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: begin() const { typedef node_pointer_pointer pointer_type; pointer_type p = const_cast(m_a_p_children); return const_iterator(p + get_begin_pos(), p + arr_size); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: begin() { return iterator(m_a_p_children + get_begin_pos(), m_a_p_children + arr_size); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end() const { typedef node_pointer_pointer pointer_type; pointer_type p = const_cast(m_a_p_children) + arr_size; return const_iterator(p, p); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: end() { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: get_child_node(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) { const size_type i = get_pref_pos(b_it, e_it, p_traits); _GLIBCXX_DEBUG_ASSERT(i < arr_size); return m_a_p_children[i]; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: get_child_it(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) { const size_type i = get_pref_pos(b_it, e_it, p_traits); _GLIBCXX_DEBUG_ASSERT(i < arr_size); _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != NULL); return iterator(m_a_p_children + i, m_a_p_children + i); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_pointer PB_DS_CLASS_C_DEC:: get_child_node(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) const { return const_cast(get_child_node(b_it, e_it, p_traits)); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: get_lower_bound_child_node(const_e_iterator b_it, const_e_iterator e_it, size_type checked_ind, const_e_access_traits_pointer p_traits) { if (!should_be_mine(b_it, e_it, checked_ind, p_traits)) { if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, m_pref_e_it, true)) return leftmost_descendant(); return rightmost_descendant(); } size_type i = get_pref_pos(b_it, e_it, p_traits); _GLIBCXX_DEBUG_ASSERT(i < arr_size); if (m_a_p_children[i] != NULL) return m_a_p_children[i]; while (++i < arr_size) if (m_a_p_children[i] != NULL) { if (m_a_p_children[i]->m_type == pat_trie_leaf_node_type) return m_a_p_children[i]; _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i]->m_type == pat_trie_internal_node_type); return static_cast(m_a_p_children[i])->leftmost_descendant(); } return rightmost_descendant(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: add_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) { const size_type i = get_pref_pos(b_it, e_it, p_traits); _GLIBCXX_DEBUG_ASSERT(i < arr_size); if (m_a_p_children[i] == NULL) { m_a_p_children[i] = p_nd; p_ndô4õ4ö4÷4ø4ù4ú4->m_p_parent = this; return p_nd; } return m_a_p_children[i]; } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::const_node_pointer PB_DS_CLASS_C_DEC:: get_join_child(const_node_pointer p_nd, const_e_access_traits_pointer p_traits) const { node_pointer p = const_cast(p_nd); return const_cast(this)->get_join_child(p, p_traits); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits) { size_type i; const_e_iterator b_it; const_e_iterator e_it; if (p_nd->m_type == pat_trie_leaf_node_type) { typename Type_Traits::const_key_reference r_key = e_access_traits::extract_key(static_cast(p_nd)->value()); b_it = p_traits->begin(r_key); e_it = p_traits->end(r_key); } else { b_it = static_cast(p_nd)->pref_b_it(); e_it = static_cast(p_nd)->pref_e_it(); } i = get_pref_pos(b_it, e_it, p_traits); _GLIBCXX_DEBUG_ASSERT(i < arr_size); return m_a_p_children[i]; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: remove_child(node_pointer p_nd) { size_type i = 0; for (; i < arr_size; ++i) if (m_a_p_children[i] == p_nd) { m_a_p_children[i] = NULL; return; } _GLIBCXX_DEBUG_ASSERT(i != arr_size); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: remove_child(iterator it) { iterator ret = it; ++ret; * it.m_p_p_cur = NULL; return ret; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: replace_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) { const size_type i = get_pref_pos(b_it, e_it, p_traits); _GLIBCXX_DEBUG_ASSERT(i < arr_size); m_a_p_children[i] = p_nd; p_nd->m_p_parent = this; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_e_iterator PB_DS_CLASS_C_DEC:: pref_b_it() const { return m_pref_b_it; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_e_iterator PB_DS_CLASS_C_DEC:: pref_e_it() const { return m_pref_e_it; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: get_e_ind() const { return m_e_ind; } PB_DS_CLASS_T_DEC bool PB_DS_CLASS_C_DEC:: should_be_mine(const_e_iterator b_it, const_e_iterator e_it, size_type checked_ind, const_e_access_traits_pointer p_traits) const { if (m_e_ind == 0) return true; const size_type num_es = std::distance(b_it, e_it); if (num_es < m_e_ind) return false; const_e_iterator key_b_it = b_it; std::advance(key_b_it, checked_ind); const_e_iterator key_e_it = b_it; std::advance(key_e_it, m_e_ind); const_e_iterator value_b_it = m_pref_b_it; std::advance(value_b_it, checked_ind); const_e_iterator value_e_it = m_pref_b_it; std::advance(value_e_it, m_e_ind); return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it, value_e_it); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::leaf_pointer PB_DS_CLASS_C_DEC:: leftmost_descendant() { node_pointer p_pot =* begin(); if (p_pot->m_type == pat_trie_leaf_node_type) return (static_cast(p_pot)); _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); return static_cast(p_pot)->leftmost_descendant(); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::const_leaf_pointer PB_DS_CLASS_C_DEC:: leftmost_descendant() const { return const_cast(this)->leftmost_descendant(); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::leaf_pointer PB_DS_CLASS_C_DEC:: rightmost_descendant() { const size_type num_children = std::distance(begin(), end()); _GLIBCXX_DEBUG_ASSERT(num_children >= 2); iterator it = begin(); std::advance(it, num_children - 1); node_pointer p_pot =* it; if (p_pot->m_type == pat_trie_leaf_node_type) return static_cast(p_pot); _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); return static_cast(p_pot)->rightmost_descendant(); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::const_leaf_pointer PB_DS_CLASS_C_DEC:: rightmost_descendant() const { return const_cast(this)->rightmost_descendant(); } #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: e_ind() const { return m_e_ind; } #endif PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: get_begin_pos() const { size_type i; for (i = 0; i < arr_size && m_a_p_children[i] == NULL; ++i) ; return i; } #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_internal_node_type); _GLIBCXX_DEBUG_ASSERT(static_cast(std::distance(pref_b_it(), pref_e_it())) == m_e_ind); _GLIBCXX_DEBUG_ASSERT(std::distance(begin(), end()) >= 2); for (typename pat_trie_internal_node::const_iterator it = begin(); it != end(); ++it) { const_node_pointer p_nd =* it; _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent == this); subtree_debug_info child_ret = p_nd->assert_valid_imp(p_traits); _GLIBCXX_DEBUG_ASSERT(static_cast(std::distance(child_ret.first, child_ret.second)) >= m_e_ind); _GLIBCXX_DEBUG_ASSERT(should_be_mine(child_ret.first, child_ret.second, 0, p_traits)); _GLIBCXX_DEBUG_ASSERT(get_pref_pos(child_ret.first, child_ret.second, p_traits) == static_cast(it.m_p_p_cur - m_a_p_children)); } return std::make_pair(pref_b_it(), pref_e_it()); } #endif #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_BASE_C_DEC #undef PB_DS_LEAF_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 const_child_iterator.hpp * Contains a const_iterator for a patricia tree. */ struct const_iterator { public: typedef std::forward_iterator_tag iterator_category; typedef typename Allocator::difference_type difference_type; typedef node_pointer value_type; typedef node_pointer_pointer pointer; typedef node_pointer_reference reference; public: inline const_iterator(node_pointer_pointer p_p_cur = NULL, node_pointer_pointer p_p_end = NULL) : m_p_p_cur(p_p_cur), m_p_p_end(p_p_end) { } inline bool operator==(const const_iterator& other) const { return m_p_p_cur == other.m_p_p_cur; } inline bool operator!=(const const_iterator& other) const { return m_p_p_cur != other.m_p_p_cur; } inline const_iterator& operator++() { do ++m_p_p_cur; while (m_p_p_cur != m_p_p_end&& * m_p_p_cur == NULL); return *this; } inline const_iterator operator++(int) { const_iterator ret_it(*this); operator++(); return ret_it; } const node_pointer_pointer operator->() const { _GLIBCXX_DEBUG_ONLY(assert_referencible();) return (m_p_p_cur); } const_node_pointer operator*() const { _GLIBCXX_DEBUG_ONLY(assert_referencible();) return (*m_p_p_cur); } protected: #ifdef _GLIBCXX_DEBUG void assert_referencible() const { _GLIBCXX_DEBUG_ASSERT(m_p_p_cur != m_p_p_end&& * m_p_p_cur != NULL); } #endif public: node_pointer_pointer m_p_p_cur; node_pointer_pointer m_p_p_end; }; // -*- 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