split_join_fn_imps.hpp [plain text]
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
if (m_size == 0)
{
other.clear();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
if (Cmp_Fn::operator()(r_key, PB_DS_V2F(*begin())))
{
value_swap(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(*(end() - 1))))
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
if (m_size == 1)
{
value_swap(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
_GLIBCXX_DEBUG_ONLY(map_debug_base::join(other);)
iterator it = upper_bound(r_key);
PB_DS_CLASS_C_DEC new_other(other, other);
new_other.copy_from_ordered_range(it, end());
PB_DS_CLASS_C_DEC new_this(*this, * this);
new_this.copy_from_ordered_range(begin(), it);
_GLIBCXX_DEBUG_ONLY(map_debug_base::split(r_key,(Cmp_Fn& )(*this), other);)
other.update(other.node_begin(), (node_update* )(&other));
update(node_begin(), (node_update* )this);
other.value_swap(new_other);
value_swap(new_this);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
join(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
if (other.m_size == 0)
return;
if (m_size == 0)
{
value_swap(other);
return;
}
const bool greater = Cmp_Fn::operator()(PB_DS_V2F(*(end() - 1)),
PB_DS_V2F(*other.begin()));
const bool lesser = Cmp_Fn::operator()(PB_DS_V2F(*(other.end() - 1)),
PB_DS_V2F(*begin()));
if (!greater && !lesser)
__throw_join_error();
PB_DS_CLASS_C_DEC new_this(*this, *this);
if (greater)
new_this.copy_from_ordered_range(begin(), end(),
other.begin(), other.end());
else
new_this.copy_from_ordered_range(other.begin(), other.end(),
begin(), end());
_GLIBCXX_DEBUG_ONLY(map_debug_base::join(other);)
value_swap(new_this);
other.clear();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}