Fn cmp_fn; typedef Allocator allocator; public: binary_heap_(); binary_heap_(const Cmp_Fn& r_cmp_fn); binary_heap_(const PB_DS_CLASS_C_DEC& other); void swap(PB_DS_CLASS_C_DEC& other); ~binary_heap_(); inline bool empty() const; inline size_type size() const; inline size_type max_size() const; Cmp_Fn& get_cmp_fn(); const Cmp_Fn& get_cmp_fn() const; inline point_iterator push(const_reference r_val); void modify(point_iterator it, const_reference r_new_val); inline const_reference top() const; inline void pop(); inline void erase(point_iterator it); template typename PB_DS_CLASS_C_DEC::size_type erase_if(Pred pred); inline static void erase_at(entry_pointer a_entries, size_type size, false_type); inline static void erase_at(entry_pointer a_entries, size_type size, true_type); inline iterator begin(); inline const_iterator begin() const; inline iterator end(); inline const_iterator end() const; void clear(); template void split(Pred pred, PB_DS_CLASS_C_DEC& other); void join(PB_DS_CLASS_C_DEC& other); #ifdef PB_DS_BINARY_HEAP_TRACE_ void trace() const; #endif protected: template void copy_from_range(It first_it, It last_it); private: void value_swap(PB_DS_CLASS_C_DEC& other); inline void insert_value(const_reference r_val, false_type); inline void insert_value(value_type val, true_type); inline void insert_entry(entry e); inline void resize_for_insert_if_needed(); inline void swap_value_imp(entry_pointer p_e, value_type new_val, true_type); inline void swap_value_imp(entry_pointer p_e, const_reference r_new_val, false_type); void fix(entry_pointer p_e); inline const_reference top_imp(true_type) const; inline const_reference top_imp(false_type) const; inline static size_type left_child(size_type i); inline static size_type right_child(size_type i); inline static size_type parent(size_type i); inline void resize_for_erase_if_needed(); template size_type partition(Pred pred); #ifdef _GLIBCXX_DEBUG void assert_valid() const; #endif #ifdef PB_DS_BINARY_HEAP_TRACE_ void trace_entry(const entry& r_e, false_type) const; void trace_entry(const entry& r_e, true_type) const; #endif private: static entry_allocator s_entry_allocator; static value_allocator s_value_allocator; static no_throw_copies_t s_no_throw_copies_ind; size_type m_size; size_type m_actual_size; entry_pointer m_a_entries; }; #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_ENTRY_CMP_DEC #undef PB_DS_RESIZE_POLICY_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 resize_policy.hpp * Contains an implementation class for a binary_heap. */ #ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP #define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC template #define PB_DS_CLASS_C_DEC resize_policy template class resize_policy { public: typedef Size_Type size_type; enum { min_size = 16 }; public: inline resize_policy(); inline void swap(PB_DS_CLASS_C_DEC& other); inline bool resize_needed_for_grow(size_type size) const; inline bool resize_needed_for_shrink(size_type size) const; inline bool grow_needed(size_type size) const; inline bool shrink_needed(size_type size) const; inline size_type get_new_size_for_grow() const; inline size_type get_new_size_for_shrink() const; size_type get_new_size_for_arbitrary(size_type size) const; inline void notify_grow_resize(); inline void notify_shrink_resize(); void notify_arbitrary(size_type actual_size); #ifdef _GLIBCXX_DEBUG void assert_valid() const; #endif #ifdef PB_DS_BINARY_HEAP_TRACE_ void trace() const; #endif private: enum { ratio = 8, factor = 2 }; private: size_type m_next_shrink_size; size_type m_next_grow_size; }; PB_DS_CLASS_T_DEC inline PB_DS_CLASS_C_DEC:: resize_policy() : m_next_shrink_size(0), m_next_grow_size(min_size) { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { std::swap(m_next_shrink_size, other.m_next_shrink_size); std::swap(m_next_grow_size, other.m_next_grow_size); } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: resize_needed_for_grow(size_type size) const { _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size); return size == m_next_grow_size; } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: resize_needed_for_shrink(size_type size) const { _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size); return size == m_next_shrink_size; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: get_new_size_for_grow() const { return m_next_grow_size* factor; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: get_new_size_for_shrink() const { const size_type half_size = m_next_grow_size / factor; return std::max(static_cast(min_size), half_size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: get_new_size_for_arbitrary(size_type size) const { size_type ret = min_size; while (ret < size) ret *= factor; return ret; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_grow_resize() { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size); m_next_grow_size *= factor; m_next_shrink_size = m_next_grow_size / ratio; _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_shrink_resize() { _GLIBCXX_DEBUG_ONLY(assert_valid();) m_next_shrink_size /= factor; if (m_next_shrink_size == 1) m_next_shrink_size = 0; m_next_grow_size = std::max(m_next_grow_size / factor, static_cast(min_size)); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_arbitrary(size_type actual_size) { m_next_grow_size = actual_size; m_next_shrink_size = m_next_grow_size / ratio; _GLIBCXX_DEBUG_ONLY(assert_valid();) } #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { _GLIBCXX_DEBUG_ASSERT(m_next_shrink_size == 0 || m_next_shrink_size* ratio == m_next_grow_size); _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size); } #endif #ifdef PB_DS_BINARY_HEAP_TRACE_ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: trace() const { std::cerr << "shrink = " << m_next_shrink_size << " grow = " << m_next_grow_size << std::endl; } #endif #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_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 policy_access_fn_imps.hpp * Contains an implementation class for a binary_heap. */ PB_DS_CLASS_T_DEC Cmp_Fn& PB_DS_CLASS_C_DEC:: get_cmp_fn() { return (*this); } PB_DS_CLASS_T_DEC const Cmp_Fn& PB_DS_CLASS_C_DEC:: get_cmp_fn() const { return (*this); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file find_fn_imps.hpp * Contains an implementation class for a binary_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(!empty()); return top_imp(s_no_throw_copies_ind); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reference PB_DS_CLASS_C_DEC:: top_imp(true_type) const { return* m_a_entries; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reference PB_DS_CLASS_C_DEC:: top_imp(false_type) const { return** m_a_entries; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: left_child(size_type i) { return i* 2 + 1; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: right_child(size_type i) { return i* 2 + 2; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: parent(size_type i) { return (i - 1) / 2; } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file constructors_destructor_fn_imps.hpp * Contains an implementation class for binary_heap_. */ PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::entry_allocator PB_DS_CLASS_C_DEC::s_entry_allocator; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::value_allocator PB_DS_CLASS_C_DEC::s_value_allocator; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::no_throw_copies_t PB_DS_CLASS_C_DEC::s_no_throw_copies_ind; PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: copy_from_range(It first_it, It last_it) { while (first_it != last_it) { insert_value(*first_it, s_no_throw_copies_ind); ++first_it; } std::make_heap(m_a_entries, m_a_entries + m_size, static_cast(*this)); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: binary_heap_() : m_size(0), m_actual_size(resize_policy::min_size), m_a_entries(s_entry_allocator.allocate(m_actual_size)) { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: binary_heap_(const Cmp_Fn& r_cmp_fn) : entry_cmp(r_cmp_fn), m_size(0), m_actual_size(resize_policy::min_size), m_a_entries(s_entry_allocator.allocate(m_actual_size)) { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: binary_heap_(const PB_DS_CLASS_C_DEC& other) : entry_cmp(other), resize_policy(other), m_size(0), m_actual_size(other.m_actual_size), m_a_entries(s_entry_allocator.allocate(m_actual_size)) { _GLIBCXX_DEBUG_ONLY(other.assert_valid();) _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries); const_iterator first_it = other.begin(); const_iterator last_it = other.end(); try { while (first_it != last_it) { insert_value(*first_it, s_no_throw_copies_ind); ++first_it; } } catch(...) { for (size_type i = 0; i < m_size; ++i) erase_at(m_a_entries, i, s_no_throw_copies_ind); s_entry_allocator.deallocate(m_a_entries, m_actual_size); __throw_exception_again; } _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries); value_swap(other); std::swap((entry_cmp& )(*this), (entry_cmp& )other); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: value_swap(PB_DS_CLASS_C_DEC& other) { std::swap(m_a_entries, other.m_a_entries); std::swap(m_size, other.m_size); std::swap(m_actual_size, other.m_actual_size); static_cast(this)->swap(other); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~binary_heap_() { for (size_type i = 0; i < m_size; ++i) erase_at(m_a_entries, i, s_no_throw_copies_ind); s_entry_allocator.deallocate(m_a_entries, m_actual_size); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file debug_fn_imps.hpp * Contains an implementation class for a binary_heap. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { #ifdef PB_DS_REGRESSION s_entry_allocator.check_allocated(m_a_entries, m_actual_size); #endif resize_policy::assert_valid(); _GLIBCXX_DEBUG_ASSERT(m_size <= m_actual_size); for (size_type i = 0; i < m_size; ++i) { #ifdef PB_DS_REGRESSION s_value_allocator.check_allocated(m_a_entries[i], 1); #endif if (left_child(i) < m_size) _GLIBCXX_DEBUG_ASSERT(!entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child(i)])); _GLIBCXX_DEBUG_ASSERT(parent(left_child(i)) == i); if (right_child(i) < m_size) _GLIBCXX_DEBUG_ASSERT(!entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child(i)])); _GLIBCXX_DEBUG_ASSERT(parent(right_child(i)) == i); } } #endif // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file erase_fn_imps.hpp * Contains an implementation class for a binary_heap. */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear() { for (size_type i = 0; i < m_size; ++i) erase_at(m_a_entries, i, s_no_throw_copies_ind); try { const size_type actual_size = resize_policy::get_new_size_for_arbitrary(0); entry_pointer a_entries = s_entry_allocator.allocate(actual_size); resize_policy::notify_arbitrary(actual_size); s_entry_allocator.deallocate(m_a_entries, m_actual_size); m_actual_size = actual_size; m_a_entries = a_entries; } catch(...) { } m_size = 0; _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: erase_at(entry_pointer a_entries, size_type i, false_type) { a_entries[i]->~value_type(); s_value_allocator.deallocate(a_entries[i], 1); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: erase_at(entry_pointer, size_type, true_type) { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: pop() { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ASSERT(!empty()); erase_at(m_a_entries, 0, s_no_throw_copies_ind); std::pop_heap(m_a_entries, m_a_entries + m_size, static_cast(*this)); resize_for_erase_if_needed(); _GLIBCXX_DEBUG_ASSERT(m_size > 0); --m_size; _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();) typedef typename entry_pred< value_type, Pred, simple_value, Allocator>::type pred_t; const size_type left = partition(pred_t(pred)); _GLIBCXX_DEBUG_ASSERT(m_size >= left); const size_type ersd = m_size - left; for (size_type i = left; i < m_size; ++i) erase_at(m_a_entries, i, s_no_throw_copies_ind); try { const size_type actual_size = resize_policy::get_new_size_for_arbitrary(left); entry_pointer a_entries = s_entry_allocator.allocate(actual_size); std::copy(m_a_entries, m_a_entries + left, a_entries); s_entry_allocator.deallocate(m_a_entries, m_actual_size); m_actual_size = actual_size; resize_policy::notify_arbitrary(m_actual_size); } catch(...) { }; m_size = left; std::make_heap(m_a_entries, m_a_entries + m_size, static_cast(*this)); _GLIBCXX_DEBUG_ONLY(assert_valid();) return ersd; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: erase(point_iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ASSERT(!empty()); const size_type fix_pos = it.m_p_e - m_a_entries; std::swap(*it.m_p_e, m_a_entries[m_size - 1]); erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); resize_for_erase_if_needed(); _GLIBCXX_DEBUG_ASSERT(m_size > 0); --m_size; _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size); if (fix_pos != m_size) fix(m_a_entries + fix_pos); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: resize_for_erase_if_needed() { if (!resize_policy::resize_needed_for_shrink(m_size)) return; try { const size_type new_actual_size = resize_policy::get_new_size_for_shrink(); entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size); resize_policy::notify_shrink_resize(); _GLIBCXX_DEBUG_ASSERT(m_size > 0); std::copy(m_a_entries, m_a_entries + m_size - 1, a_new_entries); s_entry_allocator.deallocate(m_a_entries, m_actual_size); m_actual_size = new_actual_size; m_a_entries = a_new_entries; } catch(...) { } } PB_DS_CLASS_T_DEC template typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: partition(Pred pred) { size_type left = 0; size_type right = m_size - 1; while (right + 1 != left) { _GLIBCXX_DEBUG_ASSERT(left <= m_size); if (!pred(m_a_entries[left])) ++left; else if (pred(m_a_entries[right])) --right; else { _GLIBCXX_DEBUG_ASSERT(left < right); std::swap(m_a_entries[left], m_a_entries[right]); ++left; --right; } } return left; } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file iterators_fn_imps.hpp * Contains an implementation class for a binary_heap. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: begin() { return (iterator(m_a_entries)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: begin() const { return (const_iterator(m_a_entries)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: end() { return (iterator(m_a_entries + m_size)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end() const { return (const_iterator(m_a_entries + m_size)); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file const_point_iterator.hpp * Contains an iterator class returned by the table's const find and insert * methods. */ #ifndef PB_DS_BINARY_HEAP_CONST_FIND_ITERATOR_HPP #define PB_DS_BINARY_HEAP_CONST_FIND_ITERATOR_HPP #include #include namespace __gnu_pbds { namespace detail { // Const point-type iterator. template class binary_heap_const_point_iterator_ { protected: typedef typename Allocator::template rebind::other::pointer entry_pointer; public: // Category. typedef trivial_iterator_tag iterator_category; // Difference type. typedef trivial_iterator_difference_type difference_type; // Iterator's value type. typedef Value_Type value_type; // Iterator's pointer type. typedef typename Allocator::template rebind::other::pointer pointer; // Iterator's const pointer type. typedef typename Allocator::template rebind::other::const_pointer const_pointer; // Iterator's reference type. typedef typename Allocator::template rebind::other::reference reference; // Iterator's const reference type. typedef typename Allocator::template rebind::other::const_reference const_reference; inline binary_heap_const_point_iterator_(entry_pointer p_e) : m_p_e(p_e) { } // Default constructor. inline binary_heap_const_point_iterator_() : m_p_e(NULL) { } // Copy constructor. inline binary_heap_const_point_iterator_(const binary_heap_const_point_iterator_& other) : m_p_e(other.m_p_e) { } // Access. inline const_pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(m_p_e != NULL); return to_ptr(integral_constant()); } // Access. inline const_reference operator*() const { _GLIBCXX_DEBUG_ASSERT(m_p_e != NULL); return *to_ptr(integral_constant()); } // Compares content to a different iterator object. inline bool operator==(const binary_heap_const_point_iterator_& other) const { return m_p_e == other.m_p_e; } // Compares content (negatively) to a different iterator object. inline bool operator!=(const binary_heap_const_point_iterator_& other) const { return m_p_e != other.m_p_e; } private: inline const_pointer to_ptr(true_type) const { return m_p_e; } inline const_pointer to_ptr(false_type) const { return *m_p_e; } public: entry_pointer m_p_e; }; } // 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_iterator.hpp * Contains an iterator class returned by the table's const find and insert * methods. */ #ifndef PB_DS_BINARY_HEAP_CONST_ITERATOR_HPP #define PB_DS_BINARY_HEAP_CONST_ITERATOR_HPP #include #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_C_DEC \ binary_heap_const_iterator_ #define PB_DS_BASE_C_DEC \ binary_heap_const_point_iterator_ // Const point-type iterator. template class binary_heap_const_iterator_ : public PB_DS_BASE_C_DEC { private: typedef typename PB_DS_BASE_C_DEC::entry_pointer entry_pointer; typedef PB_DS_BASE_C_DEC base_type; public: // Category. typedef std::forward_iterator_tag iterator_category; // Difference type. typedef typename Allocator::difference_type difference_type; // Iterator's value type. typedef typename base_type::value_type value_type; // Iterator's pointer type. typedef typename base_type::pointer pointer; // Iterator's const pointer type. typedef typename base_type::const_pointer const_pointer; // Iterator's reference type. typedef typename base_type::reference reference; // Iterator's const reference type. typedef typename base_type::const_reference const_reference; public: inline binary_heap_const_iterator_(entry_pointer p_e) : base_type(p_e) { } // Default constructor. inline binary_heap_const_iterator_() { } // Copy constructor. inline binary_heap_const_iterator_(const PB_DS_CLASS_C_DEC& other) : base_type(other) { } // Compares content to a different iterator object. inline bool operator==(const PB_DS_CLASS_C_DEC& other) const { return base_type::m_p_e == other.m_p_e; } // Compares content (negatively) to a different iterator object. inline bool operator!=(const PB_DS_CLASS_C_DEC& other) const { return base_type::m_p_e != other.m_p_e; } inline PB_DS_CLASS_C_DEC& operator++() { _GLIBCXX_DEBUG_ASSERT(base_type::m_p_e != NULL); inc(); return *this; } inline PB_DS_CLASS_C_DEC operator++(int) { PB_DS_CLASS_C_DEC ret_it(base_type::m_p_e); operator++(); return ret_it; } private: void inc() { ++base_type::m_p_e; } }; #undef PB_DS_CLASS_C_DEC #undef PB_DS_BASE_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 entry_pred.hpp * Contains an implementation class for a binary_heap. */ #ifndef PB_DS_BINARY_HEAP_ENTRY_PRED_HPP #define PB_DS_BINARY_HEAP_ENTRY_PRED_HPP namespace __gnu_pbds { namespace detail { template struct entry_pred { typedef Pred type; }; template struct entry_pred< Value_Type, Pred, false, Allocator> { public: typedef typename Allocator::template rebind< Value_Type>::other::const_pointer entry; struct type : public Pred { public: inline type() { } inline type(const Pred& other) : Pred(other) { } inline bool operator()(entry p_v) const { return Pred::operator()(*p_v); } }; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_BINARY_HEAP_ENTRY_PRED_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 entry_cmp.hpp * Contains an implementation class for a binary_heap. */ #ifndef PB_DS_BINARY_HEAP_ENTRY_CMP_HPP #define PB_DS_BINARY_HEAP_ENTRY_CMP_HPP namespace __gnu_pbds { namespace detail { template struct entry_cmp { typedef Cmp_Fn type; }; template struct entry_cmp< Value_Type, Cmp_Fn, false, Allocator> { public: typedef typename Allocator::template rebind< Value_Type>::other::const_pointer entry; struct type : public Cmp_Fn { public: inline type() { } inline type(const Cmp_Fn& other) : Cmp_Fn(other) { } inline bool operator()(entry p_lhs, entry p_rhs) const { return Cmp_Fn::operator()(*p_lhs, * p_rhs); } }; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_BINARY_HEAP_ENTRY_CMP_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 types_traits.hpp * Contains a traits class of types used by containers. */ #ifndef PB_DS_TYPES_TRAITS_HPP #define PB_DS_TYPES_TRAITS_HPP #include #include #include namespace __gnu_pbds { namespace detail { template struct vt_base_selector { typedef value_type_base type; }; template struct types_traits : public vt_base_selector::type { typedef typename Alloc::template rebind::other key_allocator; typedef typename key_allocator::value_type key_type; typedef typename key_allocator::pointer key_pointer; typedef typename key_allocator::const_pointer const_key_pointer; typedef typename key_allocator::reference key_reference; typedef typename key_allocator::const_reference const_key_reference; typedef typename Alloc::size_type size_type; // Extra value (used when the extra value is stored with each value). typedef std::pair comp_hash; typedef integral_constant store_extra; store_extra m_store_extra_indicator; typedef typename no_throw_copies::indicator no_throw_copies; no_throw_copies m_no_throw_copies_indicator; }; } // 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 cond_dealtor.hpp * Contains a conditional deallocator. */ #ifndef PB_DS_COND_DEALTOR_HPP #define PB_DS_COND_DEALTOR_HPP namespace __gnu_pbds { namespace detail { #define PB_DS_COND_DEALTOR_CLASS_T_DEC \ template #define PB_DS_COND_DEALTOR_CLASS_C_DEC \ cond_dealtor< \ Entry, \ Allocator> template class cond_dealtor { public: typedef typename Allocator::template rebind::other entry_allocator; typedef typename entry_allocator::pointer entry_pointer; public: inline cond_dealtor(entry_pointer p_e); inline ~cond_dealtor(); inline void set_no_action(); private: entry_pointer m_p_e; bool m_no_action_destructor; static entry_allocator s_alloc; }; PB_DS_COND_DEALTOR_CLASS_T_DEC typename PB_DS_COND_DEALTOR_CLASS_C_DEC::entry_allocator PB_DS_COND_DEALTOR_CLASS_C_DEC::s_alloc; PB_DS_COND_DEALTOR_CLASS_T_DEC inline PB_DS_COND_DEALTOR_CLASS_C_DEC:: cond_dealtor(entry_pointer p_e) : m_p_e(p_e), m_no_action_destructor(false) { } PB_DS_COND_DEALTOR_CLASS_T_DEC inline void PB_DS_COND_DEALTOR_CLASS_C_DEC:: set_no_action() { m_no_action_destructor = true; } PB_DS_COND_DEALTOR_CLASS_T_DEC inline PB_DS_COND_DEALTOR_CLASS_C_DEC:: ~cond_dealtor() { if (m_no_action_destructor) return; s_alloc.deallocate(m_p_e, 1); } #undef PB_DS_COND_DEALTOR_CLASS_T_DEC #undef PB_DS_COND_DEALTOR_CLASS_C_DEC } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_COND_DEALTOR_HPP �.X..� split_join_fn_imps.hpp� rc_binomial_heap_.hpp�insert_fn_imps.hpp�trace_fn_imps.hpp�,#constructors_destructor_fn_imps.hpp�debug_fn_imps.hpp�erase_fn_imps.hpp�rc.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 split_join_fn_imps.hpp * Contains an implementation for rc_binomial_heap_. */ PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: split(Pred pred, PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) make_binomial_heap(); other.make_binomial_heap(); base_type::split(pred, other); base_type::find_max(); other.find_max(); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: join(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) make_binomial_heap(); other.make_binomial_heap(); base_type::join(other); base_type::find_max(); other.find_max(); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) } // -*- 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