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 for thin_heap_. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reference PB_DS_CLASS_C_DEC:: top() const { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL); return m_p_max->m_value; } // -*- 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 for thin_heap_. */ 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) push(*(first_it++)); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: thin_heap_() : m_p_max(NULL) { initialize(); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: thin_heap_(const Cmp_Fn& r_cmp_fn) : PB_DS_BASE_C_DEC(r_cmp_fn), m_p_max(NULL) { initialize(); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: thin_heap_(const PB_DS_CLASS_C_DEC& other) : PB_DS_BASE_C_DEC(other) { initialize(); m_p_max = base_type::m_p_root; for (node_pointer p_nd = base_type::m_p_root; p_nd != NULL; p_nd = p_nd->m_p_next_sibling) if (Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value)) m_p_max = p_nd; _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();) base_type::swap(other); std::swap(m_p_max, other.m_p_max); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~thin_heap_() { } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: initialize() { std::fill(m_a_aux, m_a_aux + max_rank, static_cast(NULL)); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file debug_fn_imps.hpp * Contains an implementation for thin_heap_. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { base_type::assert_valid(); assert_node_consistent(base_type::m_p_root, true); assert_max(); assert_aux_null(); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_aux_null() const { for (size_type i = 0; i < max_rank; ++i) _GLIBCXX_DEBUG_ASSERT(m_a_aux[i] == NULL); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_max() const { if (m_p_max == NULL) { _GLIBCXX_DEBUG_ASSERT(base_type::empty()); return; } _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); _GLIBCXX_DEBUG_ASSERT(base_type::parent(m_p_max) == NULL); _GLIBCXX_DEBUG_ASSERT(m_p_max->m_p_prev_or_parent == NULL); for (const_iterator it = base_type::begin(); it != base_type::end(); ++it) _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(m_p_max->m_value, it.m_p_nd->m_value)); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_node_consistent(const_node_pointer p_nd, bool root) const { base_type::assert_node_consistent(p_nd, root); if (p_nd == NULL) return; assert_node_consistent(p_nd->m_p_next_sibling, root); assert_node_consistent(p_nd->m_p_l_child, false); if (!root) { if (p_nd->m_metadata == 0) _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_next_sibling == NULL); else _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata + 1); } if (p_nd->m_p_l_child != NULL) _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child->m_metadata + 1 == base_type::degree(p_nd)); const bool unmarked_valid =(p_nd->m_p_l_child == NULL&& p_nd->m_metadata == 0) ||(p_nd->m_p_l_child != NULL&& p_nd->m_metadata == p_nd->m_p_l_child->m_metadata + 1); const bool marked_valid =(p_nd->m_p_l_child == NULL&& p_nd->m_metadata == 1) ||(p_nd->m_p_l_child != NULL&& p_nd->m_metadata == p_nd->m_p_l_child->m_metadata + 2); _GLIBCXX_DEBUG_ASSERT(unmarked_valid || marked_valid); if (root) _GLIBCXX_DEBUG_ASSERT(unmarked_valid); } #endif // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file erase_fn_imps.hpp * Contains an implementation for thin_heap_. */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: pop() { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL); node_pointer p_nd = m_p_max; remove_max_node(); base_type::actual_erase_node(p_nd); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: remove_max_node() { to_aux_except_max(); make_from_aux(); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: to_aux_except_max() { node_pointer p_add = base_type::m_p_root; while (p_add != m_p_max) { node_pointer p_next_add = p_add->m_p_next_sibling; add_to_aux(p_add); p_add = p_next_add; } p_add = m_p_max->m_p_l_child; while (p_add != NULL) { node_pointer p_next_add = p_add->m_p_next_sibling; p_add->m_metadata = p_add->m_p_l_child == NULL? 0 : p_add->m_p_l_child->m_metadata + 1; add_to_aux(p_add); p_add = p_next_add; } p_add = m_p_max->m_p_next_sibling; while (p_add != NULL) { node_pointer p_next_add = p_add->m_p_next_sibling; add_to_aux(p_add); p_add = p_next_add; } } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: add_to_aux(node_pointer p_nd) { size_type r = p_nd->m_metadata; while (m_a_aux[r] != NULL) { _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound()); if (Cmp_Fn::operator()(m_a_aux[r]->m_value, p_nd->m_value)) make_child_of(m_a_aux[r], p_nd); else { make_child_of(p_nd, m_a_aux[r]); p_nd = m_a_aux[r]; } m_a_aux[r] = NULL; ++r; } _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound()); m_a_aux[r] = p_nd; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: make_child_of(node_pointer p_nd, node_pointer p_new_parent) { _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_new_parent->m_metadata); _GLIBCXX_DEBUG_ASSERT(m_a_aux[p_nd->m_metadata] == p_nd || m_a_aux[p_nd->m_metadata] == p_new_parent); ++p_new_parent->m_metadata; base_type::make_child_of(p_nd, p_new_parent); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: make_from_aux() { base_type::m_p_root = m_p_max = NULL; const size_type rnk_bnd = rank_bound(); size_type i = 0; while (i < rnk_bnd) { if (m_a_aux[i] != NULL) { make_root_and_link(m_a_aux[i]); m_a_aux[i] = NULL; } ++i; } _GLIBCXX_DEBUG_ONLY(assert_aux_null();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: remove_node(node_pointer p_nd) { node_pointer p_parent = p_nd; while (base_type::parent(p_parent) != NULL) p_parent = base_type::parent(p_parent); base_type::bubble_to_top(p_nd); m_p_max = p_nd; node_pointer p_fix = base_type::m_p_root; while (p_fix != NULL&& p_fix->m_p_next_sibling != p_parent) p_fix = p_fix->m_p_next_sibling; if (p_fix != NULL) p_fix->m_p_next_sibling = p_nd; remove_max_node(); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: clear() { base_type::clear(); m_p_max = NULL; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: erase(point_iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); node_pointer p_nd = it.m_p_nd; remove_node(p_nd); base_type::actual_erase_node(p_nd); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC template typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { _GLIBCXX_DEBUG_ONLY(assert_valid();) if (base_type::empty()) { _GLIBCXX_DEBUG_ONLY(assert_valid();) return 0; } base_type::to_linked_list(); node_pointer p_out = base_type::prune(pred); size_type ersd = 0; while (p_out != NULL) { ++ersd; node_pointer p_next = p_out->m_p_next_sibling; base_type::actual_erase_node(p_out); p_out = p_next; } node_pointer p_cur = base_type::m_p_root; m_p_max = base_type::m_p_root = NULL; while (p_cur != NULL) { node_pointer p_next = p_cur->m_p_next_sibling; make_root_and_link(p_cur); p_cur = p_next; } _GLIBCXX_DEBUG_ONLY(assert_valid();) return ersd; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: rank_bound() { const std::size_t* const p_upper = std::upper_bound( g_a_rank_bounds, g_a_rank_bounds + num_distinct_rank_bounds, base_type::m_size); if (p_upper == g_a_rank_bounds + num_distinct_rank_bounds) return max_rank; return (p_upper - g_a_rank_bounds); } // -*- 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 thin_heap_.hpp * Contains an implementation class for a thin heap. */ #ifndef PB_DS_THIN_HEAP_HPP #define PB_DS_THIN_HEAP_HPP /* * Thin heaps. * Tarjan and Kaplan. */ #include #include #include #include #include #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ thin_heap_ #ifdef _GLIBCXX_DEBUG #define PB_DS_BASE_C_DEC \ left_child_next_sibling_heap_ #else #define PB_DS_BASE_C_DEC \ left_child_next_sibling_heap_ #endif /** * class description = "t|-|i|\| h34p"> **/ template class thin_heap_ : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; protected: typedef typename base_type::node node; typedef typename base_type::node_pointer node_pointer; typedef typename base_type::const_node_pointer const_node_pointer; public: typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; typedef Value_Type value_type; typedef typename Allocator::template rebind< value_type>::other::pointer pointer; typedef typename Allocator::template rebind< value_type>::other::const_pointer const_pointer; typedef typename Allocator::template rebind< value_type>::other::reference reference; typedef typename Allocator::template rebind< value_type>::other::const_reference const_reference; typedef typename PB_DS_BASE_C_DEC::const_point_iterator const_point_iterator; typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator; typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator; typedef typename PB_DS_BASE_C_DEC::iterator iterator; typedef Cmp_Fn cmp_fn; typedef Allocator allocator; public: inline point_iterator push(const_reference r_val); void modify(point_iterator it, const_reference r_new_val); inline const_reference top() const; void pop(); void erase(point_iterator it); inline void clear(); template size_type erase_if(Pred pred); template void split(Pred pred, PB_DS_CLASS_C_DEC& other); void join(PB_DS_CLASS_C_DEC& other); protected: thin_heap_(); thin_heap_(const Cmp_Fn& r_cmp_fn); thin_heap_(const PB_DS_CLASS_C_DEC& other); void swap(PB_DS_CLASS_C_DEC& other); ~thin_heap_(); template void copy_from_range(It first_it, It last_it); #ifdef _GLIBCXX_DEBUG void assert_valid() const; void assert_max() const; #endif #ifdef PB_DS_THIN_HEAP_TRACE_ void trace() const; #endif private: enum { max_rank = (sizeof(size_type) << 4) + 2 }; private: void initialize(); inline void update_max(node_pointer p_nd); inline void fix(node_pointer p_nd); inline void fix_root(node_pointer p_y); inline void fix_sibling_rank_1_unmarked(node_pointer p_y); inline void fix_sibling_rank_1_marked(node_pointer p_y); inline void fix_sibling_general_unmarked(node_pointer p_y); inline void fix_sibling_general_marked(node_pointer p_y); inline void fix_child(node_pointer p_y); inline static void make_root(node_pointer p_nd); inline void make_root_and_link(node_pointer p_nd); inline void remove_max_node(); void to_aux_except_max(); inline void add_to_aux(node_pointer p_nd); inline void make_from_aux(); inline size_type rank_bound(); inline void make_child_of(node_pointer p_nd, node_pointer p_new_parent); inline void remove_node(node_pointer p_nd); inline node_pointer join(node_pointer p_lhs, node_pointer p_rhs) const; #ifdef _GLIBCXX_DEBUG void assert_node_consistent(const_node_pointer p_nd, bool root) const; void assert_aux_null() const; #endif private: node_pointer m_p_max; node_pointer m_a_aux[max_rank]; }; enum { num_distinct_rank_bounds = 48 }; // Taken from the SGI implementation; acknowledged in the docs. static const std::size_t g_a_rank_bounds[num_distinct_rank_bounds] = { /* Dealing cards... */ /* 0 */ 0ul, /* 1 */ 1ul, /* 2 */ 1ul, /* 3 */ 2ul, /* 4 */ 4ul, /* 5 */ 6ul, /* 6 */ 11ul, /* 7 */ 17ul, /* 8 */ 29ul, /* 9 */ 46ul, /* 10 */ 76ul, /* 11 */ 122ul, /* 12 */ 199ul, /* 13 */ 321ul, /* 14 */ 521ul, /* 15 */ 842ul, /* 16 */ 1364ul, /* 17 */ 2206ul, /* 18 */ 3571ul, /* 19 */ 5777ul, /* 20 */ 9349ul, /* 21 */ 15126ul, /* 22 */ 24476ul, /* 23 */ 39602ul, /* 24 */ 64079ul, /* 25 */ 103681ul, /* 26 */ 167761ul, /* 27 */ 271442ul, /* 28 */ 439204ul, /* 29 */ 710646ul, /* 30 */ 1149851ul, /* 31 */ 1860497ul, /* 32 */ 3010349ul, /* 33 */ 4870846ul, /* 34 */ 7881196ul, /* 35 */ 12752042ul, /* 36 */ 20633239ul, /* 37 */ 33385282ul, /* 38 */ 54018521ul, /* 39 */ 87403803ul, /* 40 */ 141422324ul, /* 41 */ 228826127ul, /* 42 */ 370248451ul, /* 43 */ 599074578ul, /* 44 */ 969323029ul, /* 45 */ 1568397607ul, /* 46 */ 2537720636ul, /* 47 */ 4106118243ul /* Pot's good, let's play */ }; #include #include #include #include #include #include #include #undef PB_DS_CLASS_C_DEC #undef PB_DS_CLASS_T_DEC #undef PB_DS_BASE_C_DEC } // namespace detail } // namespace __gnu_pbds #endif  .X ..,!prefix_search_node_update_imp.hpp,#string_trie_e_access_traits_imp.hpp$node_metadata_selector.hpp order_statistics_imp.hpp (sample_trie_e_access_traits.hpp!trie_policy_base.hpp" null_node_update_imp.hpp#èsample_trie_node_update.hpp// -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file prefix_search_node_update_imp.hpp * Contains an implementation of prefix_search_node_update. */ PB_DS_CLASS_T_DEC std::pair< typename PB_DS_CLASS_C_DEC::const_iterator, typename PB_DS_CLASS_C_DEC::const_iterator> PB_DS_CLASS_C_DEC:: prefix_range(const_key_reference r_key) const { const e_access_traits& r_traits = get_e_access_traits(); return (prefix_range( r_traits.begin(r_key), r_traits.end(r_key))); } PB_DS_CLASS_T_DEC std::pair< typename PB_DS_CLASS_C_DEC::iterator, typename PB_DS_CLASS_C_DEC::iterator> PB_DS_CLASS_C_DEC:: prefix_range(const_key_reference r_key) { return (prefix_range( get_e_access_traits().begin(r_key), get_e_access_traits().end(r_key))); } PB_DS_CLASS_T_DEC std::pair< typename PB_DS_CLASS_C_DEC::const_iterator, typename PB_DS_CLASS_C_DEC::const_iterator> PB_DS_CLASS_C_DEC:: prefix_range(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) const { const std::pair non_const_ret = const_cast(this)->prefix_range(b, e); return (std::make_pair( const_iterator(non_const_ret.first), const_iterator(non_const_ret.second))); } PB_DS_CLASS_T_DEC std::pair< typename PB_DS_CLASS_C_DEC::iterator, typename PB_DS_CLASS_C_DEC::iterator> PB_DS_CLASS_C_DEC:: prefix_range(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) { Node_Iterator nd_it = node_begin(); Node_Iterator end_nd_it = node_end(); const e_access_traits& r_traits = get_e_access_traits(); const size_type given_range_length = std::distance(b, e); while (true) { if (nd_it == end_nd_it) return (std::make_pair(end(), end())); const size_type common_range_length = PB_DS_BASE_C_DEC::common_prefix_len(nd_it, b, e, r_traits); if (common_range_length >= given_range_length) { iterator ret_b = leftmost_it(nd_it); iterator ret_e = rightmost_it(nd_it); return (std::make_pair(ret_b, ++ret_e)); } nd_it = next_child(nd_it, b, e, end_nd_it, r_traits); } } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: next_child(node_iterator nd_it, typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e, node_iterator end_nd_it, const e_access_traits& r_traits) { const size_type num_children = nd_it.num_children(); node_iterator ret = end_nd_it; size_type max_length = 0; for (size_type i = 0; i < num_children; ++i) { node_iterator pot = nd_it.get_child(i); const size_type common_range_length = PB_DS_BASE_C_DEC::common_prefix_len( pot, b, e, r_traits); if (common_range_length > max_length) { ret = pot; max_length = common_range_length; } } return (ret); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: operator()(node_iterator /*nd_it*/, const_node_iterator /*end_nd_it*/) const { } // -*- 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 string_trie_e_access_traits_imp.hpp * Contains a policy for extracting character positions from * a string for a vector-based PATRICIA tree */ PB_DS_CLASS_T_DEC detail::integral_constant PB_DS_CLASS_C_DEC::s_rev_ind; PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: e_pos(e_type e) { return (static_cast(e - min_e_val)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: begin(const_key_reference r_key) { return (begin_imp(r_key, s_rev_ind)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end(const_key_reference r_key) { return (end_imp(r_key, s_rev_ind)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: begin_imp(const_key_reference r_key, detail::false_type) { return (r_key.begin()); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: begin_imp(const_key_reference r_key, detail::true_type) { return (r_key.rbegin()); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end_imp(const_key_reference r_key, detail::false_type) { return (r_key.end()); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end_imp(const_key_reference r_key, detail::true_type) { return (r_key.rend()); } // -*- 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_selector.hpp * Contains an implementation class for tries. */ #ifndef PB_DS_TRIE_NODE_METADATA_SELECTOR_HPP #define PB_DS_TRIE_NODE_METADATA_SELECTOR_HPP #include #include namespace __gnu_pbds { namespace detail { template struct trie_metadata_helper { typedef typename Node_Update::metadata_type type; }; template struct trie_metadata_helper< Node_Update, true> { typedef null_node_metadata type; }; template class Node_Update, class Allocator> struct trie_node_metadata_selector { private: typedef dumconst_node_iterator< Key, Data, Allocator> dumconst_node_it; enum { null_update = is_same< Node_Update< dumconst_node_it, dumconst_node_it, Cmp_Fn, Allocator>, null_trie_node_update< dumconst_node_it, dumconst_node_it, Cmp_Fn, Allocator> >::value }; public: typedef typename trie_metadata_helper< Node_Update< dumconst_node_it, dumconst_node_it, Cmp_Fn, Allocator>, null_update>::type type; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_TRIE_NODE_METADATA_SELECTOR_HPP // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file order_statistics_imp.hpp * Contains forward declarations for order_statistics_key */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: find_by_order(size_type order) { if (empty()) return (end()); ++order; node_iterator nd_it = node_begin(); node_iterator end_nd_it = node_end(); while (true) { if (order > nd_it.get_metadata()) return (++base_type::rightmost_it(nd_it)); const size_type num_children = nd_it.num_children(); if (num_children == 0) return (*nd_it); for (size_type i = 0; i < num_children; ++i) { node_iterator child_nd_it = nd_it.get_child(i); if (order <= child_nd_it.get_metadata()) { i = num_children; nd_it = child_nd_it; } else order -= child_nd_it.get_metadata(); } } } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: find_by_order(size_type order) const { return (const_cast(this)->find_by_order(order)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: order_of_key(const_key_reference r_key) const { const E_Access_Traits& r_traits = const_cast(this)->get_e_access_traits(); return (order_of_prefix( r_traits.begin(r_key), r_traits.end(r_key))); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: order_of_prefix(typename e_access_traits::const_iterator b, typename e_access_traits::const_iterator e) const { if (empty()) return (0); const E_Access_Traits& r_traits = const_cast(this)->get_e_access_traits(); const_node_iterator nd_it = node_begin(); const_node_iterator end_nd_it = node_end(); size_type ord = 0; while (true) { const size_type num_children = nd_it.num_children(); if (num_children == 0) { const_key_reference r_key = base_type::extract_key(*(*nd_it)); typename e_access_traits::const_iterator key_b = r_traits.begin(r_key); typename e_access_traits::const_iterator key_e = r_traits.end(r_key); return ((base_type::less( key_b, key_e, b, e, r_traits))? ord + 1 : ord); } const_node_iterator next_nd_it = end_nd_it; size_type i = num_children - 1; do { const_node_iterator child_nd_it = nd_it.get_child(i); if (next_nd_it != end_nd_it) ord += child_nd_it.get_metadata(); else if (!base_type::less( b, e, child_nd_it.valid_prefix().first, child_nd_it.valid_prefix().second, r_traits)) next_nd_it = child_nd_it; } while (i-- > 0); if (next_nd_it == end_nd_it) return (ord); nd_it = next_nd_it; } } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: operator()(node_iterator nd_it, const_node_iterator /*end_nd_it*/) const { const size_type num_children = nd_it.num_children(); size_type children_rank = 0; for (size_type i = 0; i < num_children; ++i) children_rank += nd_it.get_child(i).get_metadata(); const_cast(nd_it.get_metadata()) =(num_children == 0)? 1 : children_rank; } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~trie_order_statistics_node_update() { } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file sample_trie_e_access_traits.hpp * Contains a sample probe policy. */ #ifndef PB_DS_SAMPLE_TRIE_E_ACCESS_TRAITS_HPP #define PB_DS_SAMPLE_TRIE_E_ACCESS_TRAITS_HPP // A sample trie element-access traits. class sample_trie_e_access_traits { public: // Size type. typedef size_t size_type; // Key type. typedef std::string key_type; // Const key reference type. typedef typename Allocator::template rebind< key_type>::other::const_reference const_key_reference; // Element const iterator type. typedef std::string::const_iterator const_iterator; // Element type. typedef char e_type; enum { max_size = 4 }; public: // Returns a const_iterator to the first element of r_key. inline static const_iterator begin(const_key_reference r_key); // Returns a const_iterator to the after-last element of r_key. inline static const_iterator end(const_key_reference r_key); // Maps an element to a position. inline static size_type e_pos(e_type e); }; #endif // #ifndef PB_DS_SAMPLE_TRIE_E_ACCESS_TRAITS_HPP // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file trie_policy_base.hpp * Contains an implementation of trie_policy_base. */ #ifndef PB_DS_TRIE_POLICY_BASE_HPP #define PB_DS_TRIE_POLICY_BASE_HPP #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template< \ class Const_Node_Iterator, \ class Node_Iterator, \ class E_Access_Traits, \ typename Allocator> #define PB_DS_CLASS_C_DEC \ trie_policy_base< \ Const_Node_Iterator, \ Node_Iterator, \ E_Access_Traits, \ Allocator> #define PB_DS_BASE_C_DEC \ basic_tree_policy_base< \ Const_Node_Iterator, \ Node_Iterator, \ Allocator> template class trie_policy_base : public PB_DS_BASE_C_DEC { public: typedef E_Access_Traits e_access_traits; typedef Allocator allocator; typedef typename allocator::size_type size_type; typedef null_node_metadata metadata_type; typedef Const_Node_Iterator const_node_iterator; typedef Node_Iterator node_iterator; typedef typename const_node_iterator::value_type const_iterator; typedef typename node_iterator::value_type iterator; public: typedef typename PB_DS_BASE_C_DEC::key_type key_type; typedef typename PB_DS_BASE_C_DEC::const_key_reference const_key_reference; protected: virtual const_iterator end() const = 0; virtual iterator end() = 0; virtual const_node_iterator node_begin() const = 0; virtual node_iterator node_begin() = 0; virtual const_node_iterator node_end() const = 0; virtual node_iterator node_end() = 0; virtual const e_access_traits& get_e_access_traits() const = 0; private: typedef std::pair< typename e_access_traits::const_iterator, typename e_access_traits::const_iterator> prefix_range_t; typedef PB_DS_BASE_C_DEC base_type; protected: static size_type common_prefix_len(node_iterator nd_it, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits); static iterator leftmost_it(node_iterator nd_it); static iterator rightmost_it(node_iterator nd_it); static bool less(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits); }; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: common_prefix_len(node_iterator nd_it, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits) { prefix_range_t pref_range = nd_it.valid_prefix(); typename e_access_traits::const_iterator b_l = pref_range.first; typename e_access_traits::const_iterator e_l = pref_range.second; const size_type range_length_l = std::distance(b_l, e_l); const size_type range_length_r = std::distance(b_r, e_r); if (range_length_r < range_length_l) { std::swap(b_l, b_r); std::swap(e_l, e_r); } size_type ret = 0; while (b_l != e_l) { if (r_traits.e_pos(*b_l) != r_traits.e_pos(*b_r)) return (ret); ++ret; ++b_l; ++b_r; } return (ret); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: leftmost_it(node_iterator nd_it) { if (nd_it.num_children() == 0) return (*nd_it); return (leftmost_it(nd_it.get_child(0))); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: rightmost_it(node_iterator nd_it) { const size_type num_children = nd_it.num_children(); if (num_children == 0) return (*nd_it); return (rightmost_it(nd_it.get_child(num_children - 1))); } PB_DS_CLASS_T_DEC bool PB_DS_CLASS_C_DEC:: less(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits) { while (b_l != e_l) { if (b_r == e_r) return (false); size_type l_pos = r_traits.e_pos(*b_l); size_type r_pos = r_traits.e_pos(*b_r); if (l_pos != r_pos) return (l_pos < r_pos); ++b_l; ++b_r; } return (b_r != e_r); } #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_BASE_C_DEC } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_TRIE_POLICY_BASE_HPP // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file null_node_update_imp.hpp * Contains an implementation of null_node_update. */ PB_DS_CLASS_T_DEC template inline void PB_DS_CLASS_C_DEC:: swap(null_trie_node_update< Const_Node_Iterator_, Node_Iterator_, E_Access_Traits_, Allocator_>& /*other*/) { } // -*- 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 sample_trie_node_update.hpp * Contains a samle node update functor. */ #ifndef PB_DS_SAMPLE_TRIE_NODE_UPDATOR_HPP #define PB_DS_SAMPLE_TRIE_NODE_UPDATOR_HPP // A sample node updator. template class sample_trie_node_update { public: // Metadata type. typedef size_t metadata_type; protected: // Default constructor. sample_trie_node_update(); // Updates the rank of a node through a node_iterator node_it; end_nd_it is the end node iterator. inline void operator()(node_iterator node_it, const_node_iterator end_nd_it) const; }; #endif // #ifndef PB_DS_SAMPLE_TRIE_NODE_UPDATOR_HPP $ .X ..% split_join_fn_imps.hpp&insert_fn_imps.hpp'find_fn_imps.hpp(,#constructors_destructor_fn_imps.hpp)debug_fn_imps.hpp*erase_fn_imps.hpp+0pairing_heap_.hpp// -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or