diff options
Diffstat (limited to 'gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_')
16 files changed, 2133 insertions, 0 deletions
diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp new file mode 100644 index 0000000..2d6842d --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp @@ -0,0 +1,352 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/binary_heap_.hpp + * Contains an implementation class for a binary heap. + */ + +#ifndef PB_DS_BINARY_HEAP_HPP +#define PB_DS_BINARY_HEAP_HPP + +#include <queue> +#include <algorithm> +#include <ext/pb_ds/detail/cond_dealtor.hpp> +#include <ext/pb_ds/detail/cond_dealtor.hpp> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <ext/pb_ds/detail/binary_heap_/entry_cmp.hpp> +#include <ext/pb_ds/detail/binary_heap_/entry_pred.hpp> +#include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp> +#include <ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp> +#include <ext/pb_ds/detail/binary_heap_/const_iterator.hpp> +#ifdef PB_DS_BINARY_HEAP_TRACE_ +#include <iostream> +#endif +#include <ext/pb_ds/detail/type_utils.hpp> +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { +#define PB_DS_CLASS_T_DEC \ + template<typename Value_Type, typename Cmp_Fn, typename _Alloc> + +#define PB_DS_CLASS_C_DEC \ + binary_heap<Value_Type, Cmp_Fn, _Alloc> + +#define PB_DS_ENTRY_CMP_DEC \ + entry_cmp<Value_Type, Cmp_Fn, _Alloc, is_simple<Value_Type>::value>::type + +#define PB_DS_RESIZE_POLICY_DEC \ + __gnu_pbds::detail::resize_policy<typename _Alloc::size_type> + + /** + * Binary heaps composed of resize and compare policies. + * + * @ingroup heap-detail + * + * Based on CLRS. + */ + template<typename Value_Type, typename Cmp_Fn, typename _Alloc> + class binary_heap + : public PB_DS_ENTRY_CMP_DEC, public PB_DS_RESIZE_POLICY_DEC + { + public: + typedef Value_Type value_type; + typedef Cmp_Fn cmp_fn; + typedef _Alloc allocator_type; + typedef typename _Alloc::size_type size_type; + typedef typename _Alloc::difference_type difference_type; + typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp; + typedef PB_DS_RESIZE_POLICY_DEC resize_policy; + typedef cond_dealtor<value_type, _Alloc> cond_dealtor_t; + + private: + enum + { + simple_value = is_simple<value_type>::value + }; + + typedef integral_constant<int, simple_value> no_throw_copies_t; + + typedef typename _Alloc::template rebind<value_type> __rebind_v; + typedef typename __rebind_v::other value_allocator; + + public: + typedef typename value_allocator::pointer pointer; + typedef typename value_allocator::const_pointer const_pointer; + typedef typename value_allocator::reference reference; + typedef typename value_allocator::const_reference const_reference; + + typedef typename __conditional_type<simple_value, + value_type, pointer>::__type + entry; + + typedef typename _Alloc::template rebind<entry>::other + entry_allocator; + + typedef typename entry_allocator::pointer entry_pointer; + + typedef binary_heap_point_const_iterator_<value_type, entry, + simple_value, _Alloc> + point_const_iterator; + + typedef point_const_iterator point_iterator; + + typedef binary_heap_const_iterator_<value_type, entry, + simple_value, _Alloc> + const_iterator; + + typedef const_iterator iterator; + + + binary_heap(); + + binary_heap(const cmp_fn&); + + binary_heap(const binary_heap&); + + void + swap(binary_heap&); + + ~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); + + void + modify(point_iterator, const_reference); + + inline const_reference + top() const; + + inline void + pop(); + + inline void + erase(point_iterator); + + template<typename Pred> + size_type + erase_if(Pred); + + inline void + erase_at(entry_pointer, size_type, false_type); + + inline void + erase_at(entry_pointer, size_type, true_type); + + inline iterator + begin(); + + inline const_iterator + begin() const; + + inline iterator + end(); + + inline const_iterator + end() const; + + void + clear(); + + template<typename Pred> + void + split(Pred, binary_heap&); + + void + join(binary_heap&); + +#ifdef PB_DS_BINARY_HEAP_TRACE_ + void + trace() const; +#endif + + protected: + template<typename It> + void + copy_from_range(It, It); + + private: + void + value_swap(binary_heap&); + + inline void + insert_value(const_reference, false_type); + + inline void + insert_value(value_type, true_type); + + inline void + resize_for_insert_if_needed(); + + inline void + swap_value_imp(entry_pointer, value_type, true_type); + + inline void + swap_value_imp(entry_pointer, const_reference, false_type); + + void + fix(entry_pointer); + + inline const_reference + top_imp(true_type) const; + + inline const_reference + top_imp(false_type) const; + + inline static size_type + left_child(size_type); + + inline static size_type + right_child(size_type); + + inline static size_type + parent(size_type); + + inline void + resize_for_erase_if_needed(); + + template<typename Pred> + size_type + partition(Pred); + + void + make_heap() + { + const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); + entry_pointer end = m_a_entries + m_size; + std::make_heap(m_a_entries, end, m_cmp); + _GLIBCXX_DEBUG_ASSERT(is_heap()); + } + + void + push_heap() + { + if (!is_heap()) + make_heap(); + else + { + const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); + entry_pointer end = m_a_entries + m_size; + std::push_heap(m_a_entries, end, m_cmp); + } + } + + void + pop_heap() + { + const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); + entry_pointer end = m_a_entries + m_size; + std::pop_heap(m_a_entries, end, m_cmp); + } + + bool + is_heap() + { + const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); + entry_pointer end = m_a_entries + m_size; + bool p = std::__is_heap(m_a_entries, end, m_cmp); + return p; + } + +#ifdef _GLIBCXX_DEBUG + void + assert_valid(const char*, int) const; +#endif + +#ifdef PB_DS_BINARY_HEAP_TRACE_ + void + trace_entry(const entry&, false_type) const; + + void + trace_entry(const entry&, true_type) const; +#endif + + 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; + }; + +#define PB_DS_ASSERT_VALID(X) \ + _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);) + +#define PB_DS_DEBUG_VERIFY(_Cond) \ + _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \ + _M_message(#_Cond" assertion from %1;:%2;") \ + ._M_string(__FILE__)._M_integer(__LINE__) \ + ,__file,__line) + +#include <ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp> +#include <ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp> +#include <ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp> +#include <ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp> +#include <ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp> +#include <ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp> +#include <ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp> +#include <ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp> +#include <ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp> +#include <ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp> + +#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 diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp new file mode 100644 index 0000000..0f41db0 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp @@ -0,0 +1,139 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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 <ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp> +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { +#define PB_DS_BIN_HEAP_CIT_BASE \ + binary_heap_point_const_iterator_<Value_Type, Entry, Simple, _Alloc> + + /// Const point-type iterator. + template<typename Value_Type, + typename Entry, + bool Simple, + typename _Alloc> + class binary_heap_const_iterator_ : public PB_DS_BIN_HEAP_CIT_BASE + { + private: + typedef PB_DS_BIN_HEAP_CIT_BASE base_type; + typedef typename base_type::entry_pointer entry_pointer; + + public: + /// Category. + typedef std::forward_iterator_tag iterator_category; + + /// Difference type. + typedef typename _Alloc::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; + + 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 binary_heap_const_iterator_& other) + : base_type(other) + { } + + /// Compares content to a different iterator object. + inline bool + operator==(const binary_heap_const_iterator_& other) const + { return base_type::m_p_e == other.m_p_e; } + + /// Compares content (negatively) to a different iterator object. + inline bool + operator!=(const binary_heap_const_iterator_& other) const + { return base_type::m_p_e != other.m_p_e; } + + inline binary_heap_const_iterator_& + operator++() + { + _GLIBCXX_DEBUG_ASSERT(base_type::m_p_e != 0); + inc(); + return *this; + } + + inline binary_heap_const_iterator_ + operator++(int) + { + binary_heap_const_iterator_ ret_it(base_type::m_p_e); + operator++(); + return ret_it; + } + + private: + void + inc() + { ++base_type::m_p_e; } + }; + +#undef PB_DS_BIN_HEAP_CIT_BASE + } // namespace detail +} // namespace __gnu_pbds + +#endif diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp new file mode 100644 index 0000000..b3aef0e --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp @@ -0,0 +1,139 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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<typename It> +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; + } + make_heap(); + PB_DS_ASSERT_VALID((*this)) +} + +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)) +{ PB_DS_ASSERT_VALID((*this)) } + +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)) +{ PB_DS_ASSERT_VALID((*this)) } + +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)) +{ + PB_DS_ASSERT_VALID(other) + _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries); + + __try + { + copy_from_range(other.begin(), other.end()); + } + __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; + } + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +swap(PB_DS_CLASS_C_DEC& other) +{ + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries); + value_swap(other); + std::swap((entry_cmp&)(*this), (entry_cmp&)other); + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) +} + +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<resize_policy*>(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); +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp new file mode 100644 index 0000000..b9c645c --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp @@ -0,0 +1,72 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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 char* __file, int __line) const +{ +#ifdef PB_DS_REGRESSION + s_entry_allocator.check_allocated(m_a_entries, m_actual_size); +#endif + + resize_policy::assert_valid(__file, __line); + PB_DS_DEBUG_VERIFY(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) + PB_DS_DEBUG_VERIFY(!entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child(i)])); + + PB_DS_DEBUG_VERIFY(parent(left_child(i)) == i); + + if (right_child(i) < m_size) + PB_DS_DEBUG_VERIFY(!entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child(i)])); + + PB_DS_DEBUG_VERIFY(parent(right_child(i)) == i); + } +} + +#endif diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp new file mode 100644 index 0000000..3908206 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp @@ -0,0 +1,85 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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 + { + /// Entry compare, primary template. + template<typename _VTp, typename Cmp_Fn, typename _Alloc, bool No_Throw> + struct entry_cmp; + + /// Specialization, true. + template<typename _VTp, typename Cmp_Fn, typename _Alloc> + struct entry_cmp<_VTp, Cmp_Fn, _Alloc, true> + { + /// Compare. + typedef Cmp_Fn type; + }; + + /// Specialization, false. + template<typename _VTp, typename Cmp_Fn, typename _Alloc> + struct entry_cmp<_VTp, Cmp_Fn, _Alloc, false> + { + private: + typedef typename _Alloc::template rebind<_VTp> __rebind_v; + + public: + typedef typename __rebind_v::other::const_pointer entry; + + /// Compare plus entry. + struct type : public Cmp_Fn + { + type() { } + + type(const Cmp_Fn& other) : Cmp_Fn(other) { } + + bool + operator()(entry lhs, entry rhs) const + { return Cmp_Fn::operator()(*lhs, *rhs); } + }; + }; + } // namespace detail +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_BINARY_HEAP_ENTRY_CMP_HPP diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp new file mode 100644 index 0000000..660c18a --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp @@ -0,0 +1,85 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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 + { + /// Entry predicate primary class template. + template<typename _VTp, typename Pred, typename _Alloc, bool No_Throw> + struct entry_pred; + + /// Specialization, true. + template<typename _VTp, typename Pred, typename _Alloc> + struct entry_pred<_VTp, Pred, _Alloc, true> + { + typedef Pred type; + }; + + /// Specialization, false. + template<typename _VTp, typename Pred, typename _Alloc> + struct entry_pred<_VTp, Pred, _Alloc, false> + { + private: + typedef typename _Alloc::template rebind<_VTp> __rebind_v; + + public: + typedef typename __rebind_v::other::const_pointer entry; + + struct type : public Pred + { + 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 diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp new file mode 100644 index 0000000..3fcf6c8 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp @@ -0,0 +1,208 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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 new_size = resize_policy::get_new_size_for_arbitrary(0); + entry_pointer new_entries = s_entry_allocator.allocate(new_size); + resize_policy::notify_arbitrary(new_size); + s_entry_allocator.deallocate(m_a_entries, m_actual_size); + m_actual_size = new_size; + m_a_entries = new_entries; + } + __catch(...) + { } + + m_size = 0; + PB_DS_ASSERT_VALID((*this)) +} + +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() +{ + PB_DS_ASSERT_VALID((*this)) + _GLIBCXX_DEBUG_ASSERT(!empty()); + + pop_heap(); + 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; + + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +template<typename Pred> +typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +erase_if(Pred pred) +{ + PB_DS_ASSERT_VALID((*this)) + + typedef typename entry_pred<value_type, Pred, _Alloc, simple_value>::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 new_size = + resize_policy::get_new_size_for_arbitrary(left); + + entry_pointer new_entries = s_entry_allocator.allocate(new_size); + std::copy(m_a_entries, m_a_entries + left, new_entries); + s_entry_allocator.deallocate(m_a_entries, m_actual_size); + m_actual_size = new_size; + resize_policy::notify_arbitrary(m_actual_size); + } + __catch(...) + { }; + + m_size = left; + make_heap(); + PB_DS_ASSERT_VALID((*this)) + return ersd; +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +erase(point_iterator it) +{ + PB_DS_ASSERT_VALID((*this)) + _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); + + PB_DS_ASSERT_VALID((*this)) +} + +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_size = resize_policy::get_new_size_for_shrink(); + entry_pointer new_entries = s_entry_allocator.allocate(new_size); + resize_policy::notify_shrink_resize(); + + _GLIBCXX_DEBUG_ASSERT(m_size > 0); + std::copy(m_a_entries, m_a_entries + m_size - 1, new_entries); + s_entry_allocator.deallocate(m_a_entries, m_actual_size); + m_actual_size = new_size; + m_a_entries = new_entries; + } + __catch(...) + { } +} + +PB_DS_CLASS_T_DEC +template<typename Pred> +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; +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp new file mode 100644 index 0000000..3f61fe3 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp @@ -0,0 +1,79 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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 +{ + PB_DS_ASSERT_VALID((*this)) + _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; } diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp new file mode 100644 index 0000000..2f6584f --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp @@ -0,0 +1,58 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/info_fn_imps.hpp + * Contains an implementation class for a binary_heap. + */ + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +empty() const +{ return m_size == 0; } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +size() const +{ return m_size; } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +max_size() const +{ return s_entry_allocator.max_size(); } + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp new file mode 100644 index 0000000..8ade3a9 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp @@ -0,0 +1,174 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/insert_fn_imps.hpp + * Contains an implementation class for a binary_heap. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +push(const_reference r_val) +{ + PB_DS_ASSERT_VALID((*this)) + insert_value(r_val, s_no_throw_copies_ind); + push_heap(); + PB_DS_ASSERT_VALID((*this)) + return point_iterator(m_a_entries); +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +insert_value(value_type val, true_type) +{ + resize_for_insert_if_needed(); + m_a_entries[m_size++] = val; +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +insert_value(const_reference r_val, false_type) +{ + resize_for_insert_if_needed(); + pointer p_new = s_value_allocator.allocate(1); + cond_dealtor_t cond(p_new); + new (p_new) value_type(r_val); + cond.set_no_action(); + m_a_entries[m_size++] = p_new; +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +resize_for_insert_if_needed() +{ + if (!resize_policy::resize_needed_for_grow(m_size)) + { + _GLIBCXX_DEBUG_ASSERT(m_size < m_actual_size); + return; + } + + const size_type new_size = resize_policy::get_new_size_for_grow(); + entry_pointer new_entries = s_entry_allocator.allocate(new_size); + resize_policy::notify_grow_resize(); + + std::copy(m_a_entries, m_a_entries + m_size, new_entries); + s_entry_allocator.deallocate(m_a_entries, m_actual_size); + m_actual_size = new_size; + m_a_entries = new_entries; + make_heap(); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +modify(point_iterator it, const_reference r_new_val) +{ + PB_DS_ASSERT_VALID((*this)) + swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind); + fix(it.m_p_e); + PB_DS_ASSERT_VALID((*this)) + _GLIBCXX_DEBUG_ASSERT(is_heap()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +fix(entry_pointer p_e) +{ + size_type i = p_e - m_a_entries; + if (i > 0 && entry_cmp::operator()(m_a_entries[parent(i)], m_a_entries[i])) + { + size_type parent_i = parent(i); + while (i > 0 + && entry_cmp::operator()(m_a_entries[parent_i], m_a_entries[i])) + { + std::swap(m_a_entries[i], m_a_entries[parent_i]); + i = parent_i; + parent_i = parent(i); + } + + PB_DS_ASSERT_VALID((*this)) + return; + } + + while (i < m_size) + { + const size_type lchild_i = left_child(i); + const size_type rchild_i = right_child(i); + _GLIBCXX_DEBUG_ASSERT(rchild_i > lchild_i); + + const bool smaller_than_lchild = lchild_i < m_size && + entry_cmp::operator()(m_a_entries[i], m_a_entries[lchild_i]); + + const bool smaller_than_rchild = rchild_i < m_size && + entry_cmp::operator()(m_a_entries[i], m_a_entries[rchild_i]); + + const bool swap_with_rchild = smaller_than_rchild && (!smaller_than_lchild || entry_cmp::operator()(m_a_entries[lchild_i], m_a_entries[rchild_i])); + + const bool swap_with_lchild = !swap_with_rchild && smaller_than_lchild; + + if (swap_with_lchild) + { + std::swap(m_a_entries[i], m_a_entries[lchild_i]); + i = lchild_i; + } + else if (swap_with_rchild) + { + std::swap(m_a_entries[i], m_a_entries[rchild_i]); + i = rchild_i; + } + else + i = m_size; + } +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +swap_value_imp(entry_pointer p_e, value_type new_val, true_type) +{ *p_e = new_val; } + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +swap_value_imp(entry_pointer p_e, const_reference r_new_val, false_type) +{ + value_type tmp(r_new_val); + (*p_e)->swap(tmp); +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp new file mode 100644 index 0000000..35dd014 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp @@ -0,0 +1,64 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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); } + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp new file mode 100644 index 0000000..f16a001 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp @@ -0,0 +1,144 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/point_const_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 <ext/pb_ds/tag_and_trait.hpp> +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { + /// Const point-type iterator. + template<typename Value_Type, typename Entry, bool Simple, + typename _Alloc> + class binary_heap_point_const_iterator_ + { + protected: + typedef typename _Alloc::template rebind<Entry>::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 _Alloc::template rebind<value_type>::other::pointer + pointer; + + /// Iterator's const pointer type. + typedef + typename _Alloc::template rebind<value_type>::other::const_pointer + const_pointer; + + /// Iterator's reference type. + typedef + typename _Alloc::template rebind<value_type>::other::reference + reference; + + /// Iterator's const reference type. + typedef + typename _Alloc::template rebind<value_type>::other::const_reference + const_reference; + + inline + binary_heap_point_const_iterator_(entry_pointer p_e) : m_p_e(p_e) + { } + + /// Default constructor. + inline + binary_heap_point_const_iterator_() : m_p_e(0) { } + + /// Copy constructor. + inline + binary_heap_point_const_iterator_(const binary_heap_point_const_iterator_& other) + : m_p_e(other.m_p_e) + { } + + /// Access. + inline const_pointer + operator->() const + { + _GLIBCXX_DEBUG_ASSERT(m_p_e != 0); + return to_ptr(integral_constant<int, Simple>()); + } + + /// Access. + inline const_reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(m_p_e != 0); + return *to_ptr(integral_constant<int, Simple>()); + } + + /// Compares content to a different iterator object. + inline bool + operator==(const binary_heap_point_const_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_point_const_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 diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp new file mode 100644 index 0000000..805d6af --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp @@ -0,0 +1,56 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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); +} + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp new file mode 100644 index 0000000..f5b7ccb --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp @@ -0,0 +1,240 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/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 <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { + /// Resize policy for binary heap. + template<typename _Tp> + class resize_policy + { + private: + enum + { + ratio = 8, + factor = 2 + }; + + /// Next shrink size. + _Tp m_shrink_size; + + /// Next grow size. + _Tp m_grow_size; + + public: + typedef _Tp size_type; + + static const _Tp min_size = 16; + + resize_policy() : m_shrink_size(0), m_grow_size(min_size) + { PB_DS_ASSERT_VALID((*this)) } + + resize_policy(const resize_policy& other) + : m_shrink_size(other.m_shrink_size), m_grow_size(other.m_grow_size) + { PB_DS_ASSERT_VALID((*this)) } + + inline void + swap(resize_policy<_Tp>&); + + inline bool + resize_needed_for_grow(size_type) const; + + inline bool + resize_needed_for_shrink(size_type) const; + + inline bool + grow_needed(size_type) const; + + inline bool + shrink_needed(size_type) const; + + inline size_type + get_new_size_for_grow() const; + + inline size_type + get_new_size_for_shrink() const; + + inline size_type + get_new_size_for_arbitrary(size_type) const; + + inline void + notify_grow_resize(); + + inline void + notify_shrink_resize(); + + void + notify_arbitrary(size_type); + +#ifdef _GLIBCXX_DEBUG + void + assert_valid(const char*, int) const; +#endif + +#ifdef PB_DS_BINARY_HEAP_TRACE_ + void + trace() const; +#endif + }; + + template<typename _Tp> + const _Tp resize_policy<_Tp>::min_size; + + template<typename _Tp> + inline void + resize_policy<_Tp>:: + swap(resize_policy<_Tp>& other) + { + std::swap(m_shrink_size, other.m_shrink_size); + std::swap(m_grow_size, other.m_grow_size); + } + + template<typename _Tp> + inline bool + resize_policy<_Tp>:: + resize_needed_for_grow(size_type size) const + { + _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size); + return size == m_grow_size; + } + + template<typename _Tp> + inline bool + resize_policy<_Tp>:: + resize_needed_for_shrink(size_type size) const + { + _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size); + return size == m_shrink_size; + } + + template<typename _Tp> + inline typename resize_policy<_Tp>::size_type + resize_policy<_Tp>:: + get_new_size_for_grow() const + { return m_grow_size * factor; } + + template<typename _Tp> + inline typename resize_policy<_Tp>::size_type + resize_policy<_Tp>:: + get_new_size_for_shrink() const + { + const size_type half_size = m_grow_size / factor; + return std::max(min_size, half_size); + } + + template<typename _Tp> + inline typename resize_policy<_Tp>::size_type + resize_policy<_Tp>:: + get_new_size_for_arbitrary(size_type size) const + { + size_type ret = min_size; + while (ret < size) + ret *= factor; + return ret; + } + + template<typename _Tp> + inline void + resize_policy<_Tp>:: + notify_grow_resize() + { + PB_DS_ASSERT_VALID((*this)) + _GLIBCXX_DEBUG_ASSERT(m_grow_size >= min_size); + m_grow_size *= factor; + m_shrink_size = m_grow_size / ratio; + PB_DS_ASSERT_VALID((*this)) + } + + template<typename _Tp> + inline void + resize_policy<_Tp>:: + notify_shrink_resize() + { + PB_DS_ASSERT_VALID((*this)) + m_shrink_size /= factor; + if (m_shrink_size == 1) + m_shrink_size = 0; + m_grow_size = std::max(m_grow_size / factor, min_size); + PB_DS_ASSERT_VALID((*this)) + } + + template<typename _Tp> + inline void + resize_policy<_Tp>:: + notify_arbitrary(size_type actual_size) + { + m_grow_size = actual_size; + m_shrink_size = m_grow_size / ratio; + PB_DS_ASSERT_VALID((*this)) + } + +#ifdef _GLIBCXX_DEBUG + template<typename _Tp> + void + resize_policy<_Tp>:: + assert_valid(const char* __file, int __line) const + { + PB_DS_DEBUG_VERIFY(m_shrink_size == 0 + || m_shrink_size * ratio == m_grow_size); + PB_DS_DEBUG_VERIFY(m_grow_size >= min_size); + } +#endif + +#ifdef PB_DS_BINARY_HEAP_TRACE_ + template<typename _Tp> + void + resize_policy<_Tp>:: + trace() const + { + std::cerr << "shrink = " << m_shrink_size + << " grow = " << m_grow_size << std::endl; + } +#endif + +} // namespace detail +} // namespace __gnu_pbds + +#endif diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp new file mode 100644 index 0000000..322ac08 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp @@ -0,0 +1,160 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/split_join_fn_imps.hpp + * Contains an implementation class for a binary_heap. + */ + +PB_DS_CLASS_T_DEC +template<typename Pred> +void +PB_DS_CLASS_C_DEC:: +split(Pred pred, PB_DS_CLASS_C_DEC& other) +{ + PB_DS_ASSERT_VALID((*this)) + + typedef + typename entry_pred<value_type, Pred, _Alloc, simple_value>::type + pred_t; + + const size_type left = partition(pred_t(pred)); + _GLIBCXX_DEBUG_ASSERT(m_size >= left); + + const size_type ersd = m_size - left; + _GLIBCXX_DEBUG_ASSERT(m_size >= ersd); + + const size_type new_size = resize_policy::get_new_size_for_arbitrary(left); + const size_type other_actual_size = other.get_new_size_for_arbitrary(ersd); + + entry_pointer a_entries = 0; + entry_pointer a_other_entries = 0; + + __try + { + a_entries = s_entry_allocator.allocate(new_size); + a_other_entries = s_entry_allocator.allocate(other_actual_size); + } + __catch(...) + { + if (a_entries != 0) + s_entry_allocator.deallocate(a_entries, new_size); + + if (a_other_entries != 0) + s_entry_allocator.deallocate(a_other_entries, other_actual_size); + + __throw_exception_again; + }; + + for (size_type i = 0; i < other.m_size; ++i) + erase_at(other.m_a_entries, i, s_no_throw_copies_ind); + + _GLIBCXX_DEBUG_ASSERT(new_size >= left); + std::copy(m_a_entries, m_a_entries + left, a_entries); + std::copy(m_a_entries + left, m_a_entries + m_size, a_other_entries); + + s_entry_allocator.deallocate(m_a_entries, m_actual_size); + s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size); + + m_actual_size = new_size; + other.m_actual_size = other_actual_size; + + m_size = left; + other.m_size = ersd; + + m_a_entries = a_entries; + other.m_a_entries = a_other_entries; + + make_heap(); + other.make_heap(); + + resize_policy::notify_arbitrary(m_actual_size); + other.notify_arbitrary(other.m_actual_size); + + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +join(PB_DS_CLASS_C_DEC& other) +{ + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + + const size_type len = m_size + other.m_size; + const size_type new_size = resize_policy::get_new_size_for_arbitrary(len); + + entry_pointer a_entries = 0; + entry_pointer a_other_entries = 0; + + __try + { + a_entries = s_entry_allocator.allocate(new_size); + a_other_entries = s_entry_allocator.allocate(resize_policy::min_size); + } + __catch(...) + { + if (a_entries != 0) + s_entry_allocator.deallocate(a_entries, new_size); + + if (a_other_entries != 0) + s_entry_allocator.deallocate(a_other_entries, resize_policy::min_size); + + __throw_exception_again; + } + + std::copy(m_a_entries, m_a_entries + m_size, a_entries); + std::copy(other.m_a_entries, other.m_a_entries + other.m_size, + a_entries + m_size); + + s_entry_allocator.deallocate(m_a_entries, m_actual_size); + m_a_entries = a_entries; + m_size = len; + m_actual_size = new_size; + resize_policy::notify_arbitrary(new_size); + make_heap(); + + s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size); + other.m_a_entries = a_other_entries; + other.m_size = 0; + other.m_actual_size = resize_policy::min_size; + other.notify_arbitrary(resize_policy::min_size); + other.make_heap(); + + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp new file mode 100644 index 0000000..5176a69 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp @@ -0,0 +1,78 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 binary_heap_/trace_fn_imps.hpp + * Contains an implementation class for a binary_heap. + */ + +#ifdef PB_DS_BINARY_HEAP_TRACE_ + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +trace() const +{ + std::cerr << this << std::endl; + + std::cerr << m_a_entries << std::endl; + + for (size_type i = 0; i < m_size; ++i) + trace_entry(m_a_entries[i], s_no_throw_copies_ind); + + std::cerr << std::endl; + + std::cerr << "size = " << m_size << " " << "actual_size = " << m_actual_size << std::endl; + + resize_policy::trace(); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +trace_entry(const entry& r_e, false_type) const +{ + std::cout << r_e << " " <<* r_e << std::endl; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +trace_entry(const entry& r_e, true_type) const +{ + std::cout << r_e << std::endl; +} + +#endif // #ifdef PB_DS_BINARY_HEAP_TRACE_ |