3 // Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
37 * @file split_join_fn_imps.hpp
38 * Contains an implementation class for a binary_heap.
42 template<typename Pred
>
45 split(Pred pred
, PB_DS_CLASS_C_DEC
& other
)
47 _GLIBCXX_DEBUG_ONLY(assert_valid();)
57 const size_type left
= partition(pred_t(pred
));
59 _GLIBCXX_DEBUG_ASSERT(m_size
>= left
);
61 const size_type ersd
= m_size
- left
;
63 _GLIBCXX_DEBUG_ASSERT(m_size
>= ersd
);
65 const size_type actual_size
=
66 resize_policy::get_new_size_for_arbitrary(left
);
68 const size_type other_actual_size
=
69 other
.get_new_size_for_arbitrary(ersd
);
71 entry_pointer a_entries
= NULL
;
72 entry_pointer a_other_entries
= NULL
;
76 a_entries
= s_entry_allocator
.allocate(actual_size
);
78 a_other_entries
= s_entry_allocator
.allocate(other_actual_size
);
82 if (a_entries
!= NULL
)
83 s_entry_allocator
.deallocate(a_entries
, actual_size
);
85 if (a_other_entries
!= NULL
)
86 s_entry_allocator
.deallocate(a_other_entries
, other_actual_size
);
88 __throw_exception_again
;
91 for (size_type i
= 0; i
< other
.m_size
; ++i
)
92 erase_at(other
.m_a_entries
, i
, s_no_throw_copies_ind
);
94 _GLIBCXX_DEBUG_ASSERT(actual_size
>= left
);
95 std::copy(m_a_entries
, m_a_entries
+ left
, a_entries
);
96 std::copy(m_a_entries
+ left
, m_a_entries
+ m_size
, a_other_entries
);
98 s_entry_allocator
.deallocate(m_a_entries
, m_actual_size
);
99 s_entry_allocator
.deallocate(other
.m_a_entries
, other
.m_actual_size
);
101 m_actual_size
= actual_size
;
102 other
.m_actual_size
= other_actual_size
;
107 m_a_entries
= a_entries
;
108 other
.m_a_entries
= a_other_entries
;
110 std::make_heap(m_a_entries
, m_a_entries
+ m_size
, static_cast<entry_cmp
& >(*this));
111 std::make_heap(other
.m_a_entries
, other
.m_a_entries
+ other
.m_size
, static_cast<entry_cmp
& >(other
));
113 resize_policy::notify_arbitrary(m_actual_size
);
114 other
.notify_arbitrary(other
.m_actual_size
);
116 _GLIBCXX_DEBUG_ONLY(assert_valid();)
117 _GLIBCXX_DEBUG_ONLY(other
.assert_valid();)
123 join(PB_DS_CLASS_C_DEC
& other
)
125 _GLIBCXX_DEBUG_ONLY(assert_valid();)
126 _GLIBCXX_DEBUG_ONLY(other
.assert_valid();)
128 const size_type len
= m_size
+ other
.m_size
;
129 const size_type actual_size
= resize_policy::get_new_size_for_arbitrary(len
);
131 entry_pointer a_entries
= NULL
;
132 entry_pointer a_other_entries
= NULL
;
136 a_entries
= s_entry_allocator
.allocate(actual_size
);
137 a_other_entries
= s_entry_allocator
.allocate(resize_policy::min_size
);
141 if (a_entries
!= NULL
)
142 s_entry_allocator
.deallocate(a_entries
, actual_size
);
144 if (a_other_entries
!= NULL
)
145 s_entry_allocator
.deallocate(a_other_entries
, resize_policy::min_size
);
147 __throw_exception_again
;
150 std::copy(m_a_entries
, m_a_entries
+ m_size
, a_entries
);
151 std::copy(other
.m_a_entries
, other
.m_a_entries
+ other
.m_size
, a_entries
+ m_size
);
153 s_entry_allocator
.deallocate(m_a_entries
, m_actual_size
);
154 m_a_entries
= a_entries
;
156 m_actual_size
= actual_size
;
158 resize_policy::notify_arbitrary(actual_size
);
160 std::make_heap(m_a_entries
, m_a_entries
+ m_size
, static_cast<entry_cmp
& >(*this));
162 s_entry_allocator
.deallocate(other
.m_a_entries
, other
.m_actual_size
);
163 other
.m_a_entries
= a_other_entries
;
165 other
.m_actual_size
= resize_policy::min_size
;
167 other
.notify_arbitrary(resize_policy::min_size
);
169 _GLIBCXX_DEBUG_ONLY(assert_valid();)
170 _GLIBCXX_DEBUG_ONLY(other
.assert_valid();)