URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
Compare Revisions
- This comparison shows the changes necessary to convert path
/openrisc/tags/gnu-src/gcc-4.5.1/gcc-4.5.1-or32-1.0rc4/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_
- from Rev 424 to Rev 519
- ↔ Reverse comparison
Rev 424 → Rev 519
/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; |
} |
|
/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); |
} |
|
/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 |
/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 |
/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); |
} |
|
/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 |
/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()); |
} |
|
/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 |
/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_ |
/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; |
} |
|
/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 |
/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); |
} |
/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 |
/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 |
/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();) |
} |
|
/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)); |
} |
|