diff options
Diffstat (limited to 'i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_')
16 files changed, 2285 insertions, 0 deletions
diff --git a/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp new file mode 100644 index 0000000..576cba2 --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp @@ -0,0 +1,357 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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_.hpp + * Contains an implementation class for a binary heap. + */ + +#ifndef PB_DS_BINARY_HEAP_HPP +#define PB_DS_BINARY_HEAP_HPP + +/* + * Based on CLRS. + */ + +#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_/const_point_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, class Cmp_Fn, class Allocator> + +#define PB_DS_CLASS_C_DEC \ + binary_heap_<Value_Type, Cmp_Fn, Allocator> + +#define PB_DS_ENTRY_CMP_DEC \ + entry_cmp<Value_Type, Cmp_Fn, is_simple<Value_Type>::value, Allocator>::type + +#define PB_DS_RESIZE_POLICY_DEC \ + __gnu_pbds::detail::resize_policy<typename Allocator::size_type> + + /** + * class description = "Base class for some types of h3ap$"> + **/ + template<typename Value_Type, class Cmp_Fn, class Allocator> + class binary_heap_ : public PB_DS_ENTRY_CMP_DEC, + public PB_DS_RESIZE_POLICY_DEC + { + + private: + enum + { + simple_value = is_simple<Value_Type>::value + }; + + typedef integral_constant<int, simple_value> no_throw_copies_t; + + typedef + typename Allocator::template rebind< + Value_Type>::other + value_allocator; + + typedef + typename __conditional_type< + simple_value, + Value_Type, + typename value_allocator::pointer>::__type + entry; + + typedef + typename Allocator::template rebind< + entry>::other + entry_allocator; + + typedef typename entry_allocator::pointer entry_pointer; + + typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp; + + typedef PB_DS_RESIZE_POLICY_DEC resize_policy; + + typedef + cond_dealtor< + Value_Type, + Allocator> + cond_dealtor_t; + + public: + + typedef typename Allocator::size_type size_type; + + typedef typename Allocator::difference_type difference_type; + + typedef Value_Type value_type; + + typedef + typename Allocator::template rebind< + value_type>::other::pointer + pointer; + + typedef + typename Allocator::template rebind< + value_type>::other::const_pointer + const_pointer; + + typedef + typename Allocator::template rebind< + value_type>::other::reference + reference; + + typedef + typename Allocator::template rebind< + value_type>::other::const_reference + const_reference; + + typedef + binary_heap_const_point_iterator_< + value_type, + entry, + simple_value, + Allocator> + const_point_iterator; + + typedef const_point_iterator point_iterator; + + typedef + binary_heap_const_iterator_< + value_type, + entry, + simple_value, + Allocator> + const_iterator; + + typedef const_iterator iterator; + + typedef Cmp_Fn cmp_fn; + + typedef Allocator allocator_type; + + 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 Pred> + 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<typename Pred> + 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<typename It> + 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<typename Pred> + 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 <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/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/const_iterator.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/const_iterator.hpp new file mode 100644 index 0000000..9cb13f9 --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/const_iterator.hpp @@ -0,0 +1,152 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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_/const_point_iterator.hpp> +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { + +#define PB_DS_CLASS_C_DEC \ + binary_heap_const_iterator_<Value_Type, Entry, Simple, Allocator> + +#define PB_DS_BASE_C_DEC \ + binary_heap_const_point_iterator_<Value_Type, Entry, Simple, Allocator> + + // Const point-type iterator. + template<typename Value_Type, + typename Entry, + bool Simple, + class Allocator> + 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 diff --git a/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp new file mode 100644 index 0000000..d4013db --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp @@ -0,0 +1,144 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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 <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 Allocator> + class binary_heap_const_point_iterator_ + { + protected: + typedef typename Allocator::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 Allocator::template rebind<value_type>::other::pointer + pointer; + + // Iterator's const pointer type. + typedef + typename Allocator::template rebind<value_type>::other::const_pointer + const_pointer; + + // Iterator's reference type. + typedef + typename Allocator::template rebind<value_type>::other::reference + reference; + + // Iterator's const reference type. + typedef + typename Allocator::template rebind<value_type>::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<int, Simple>()); + } + + // Access. + inline const_reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(m_p_e != NULL); + return *to_ptr(integral_constant<int, Simple>()); + } + + // 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 diff --git a/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp new file mode 100644 index 0000000..a77a025 --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/constructors_destructor_fn_imps.hpp @@ -0,0 +1,159 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2008, 2009 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 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; + } + + std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*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<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/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp new file mode 100644 index 0000000..fcfecfd --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/debug_fn_imps.hpp @@ -0,0 +1,72 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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 diff --git a/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp new file mode 100644 index 0000000..b0a9b5b --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp @@ -0,0 +1,93 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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<typename Value_Type, + class Cmp_Fn, + bool No_Throw, + class Allocator> + struct entry_cmp + { + typedef Cmp_Fn type; + }; + + template<typename Value_Type, class Cmp_Fn, class Allocator> + 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 diff --git a/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/entry_pred.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/entry_pred.hpp new file mode 100644 index 0000000..185529e --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/entry_pred.hpp @@ -0,0 +1,93 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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<typename Value_Type, + class Pred, + bool No_Throw, + class Allocator> + struct entry_pred + { + typedef Pred type; + }; + + template<typename Value_Type, class Pred, class Allocator> + 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 diff --git a/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp new file mode 100644 index 0000000..30f3a48 --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/erase_fn_imps.hpp @@ -0,0 +1,246 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2008, 2009 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 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<entry_cmp& >(*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 Pred> +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<entry_cmp& >(*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 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/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp new file mode 100644 index 0000000..28d4a8c --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/find_fn_imps.hpp @@ -0,0 +1,91 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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; +} + diff --git a/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp new file mode 100644 index 0000000..d292793 --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp @@ -0,0 +1,64 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp new file mode 100644 index 0000000..f13a3cb --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp @@ -0,0 +1,183 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + insert_value(r_val, s_no_throw_copies_ind); + std::push_heap(m_a_entries, m_a_entries + m_size, + static_cast<entry_cmp&>(*this)); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + 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:: +insert_entry(entry e) +{ + resize_for_insert_if_needed(); + m_a_entries[m_size++] = e; +} + +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_actual_size = resize_policy::get_new_size_for_grow(); + entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size); + resize_policy::notify_grow_resize(); + std::copy(m_a_entries, m_a_entries + m_size, 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; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +modify(point_iterator it, const_reference r_new_val) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind); + fix(it.m_p_e); + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} + +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); + } + + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return; + } + + while (i < m_size) + { + const size_type left_child_i = left_child(i); + const size_type right_child_i = right_child(i); + _GLIBCXX_DEBUG_ASSERT(right_child_i > left_child_i); + const bool smaller_than_left_child = left_child_i < m_size && + entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child_i]); + + const bool smaller_than_right_child = right_child_i < m_size && + entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child_i]); + + const bool swap_with_r_child = smaller_than_right_child && (!smaller_than_left_child || entry_cmp::operator()(m_a_entries[left_child_i], m_a_entries[right_child_i])); + + const bool swap_with_l_child = !swap_with_r_child && smaller_than_left_child; + + if (swap_with_l_child) + { + std::swap(m_a_entries[i], m_a_entries[left_child_i]); + i = left_child_i; + } + else if (swap_with_r_child) + { + std::swap(m_a_entries[i], m_a_entries[right_child_i]); + i = right_child_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/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp new file mode 100644 index 0000000..db0a64e --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/iterators_fn_imps.hpp @@ -0,0 +1,72 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp new file mode 100644 index 0000000..11a7b89 --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/policy_access_fn_imps.hpp @@ -0,0 +1,56 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/resize_policy.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/resize_policy.hpp new file mode 100644 index 0000000..588fb3d --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/resize_policy.hpp @@ -0,0 +1,253 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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 + { + +#define PB_DS_CLASS_T_DEC template<typename Size_Type> + +#define PB_DS_CLASS_C_DEC resize_policy<Size_Type> + + template<typename Size_Type> + 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<size_type>(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<size_type>(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 diff --git a/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp new file mode 100644 index 0000000..04b7d54 --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp @@ -0,0 +1,172 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2008, 2009 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 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) +{ + _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; + + _GLIBCXX_DEBUG_ASSERT(m_size >= ersd); + + const size_type actual_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 = NULL; + entry_pointer a_other_entries = NULL; + + __try + { + a_entries = s_entry_allocator.allocate(actual_size); + + a_other_entries = s_entry_allocator.allocate(other_actual_size); + } + __catch(...) + { + if (a_entries != NULL) + s_entry_allocator.deallocate(a_entries, actual_size); + + if (a_other_entries != NULL) + 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(actual_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 = actual_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; + + std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); + std::make_heap(other.m_a_entries, other.m_a_entries + other.m_size, static_cast<entry_cmp& >(other)); + + resize_policy::notify_arbitrary(m_actual_size); + other.notify_arbitrary(other.m_actual_size); + + _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();) + + const size_type len = m_size + other.m_size; + const size_type actual_size = resize_policy::get_new_size_for_arbitrary(len); + + entry_pointer a_entries = NULL; + entry_pointer a_other_entries = NULL; + + __try + { + a_entries = s_entry_allocator.allocate(actual_size); + a_other_entries = s_entry_allocator.allocate(resize_policy::min_size); + } + __catch(...) + { + if (a_entries != NULL) + s_entry_allocator.deallocate(a_entries, actual_size); + + if (a_other_entries != NULL) + 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 = actual_size; + + resize_policy::notify_arbitrary(actual_size); + + std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); + + 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); + + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) +} + diff --git a/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp new file mode 100644 index 0000000..36bd66f --- /dev/null +++ b/i686-linux/include/c++/4.4.3/ext/pb_ds/detail/binary_heap_/trace_fn_imps.hpp @@ -0,0 +1,78 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 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_ |