split_join_fn_imps.hpp [plain text]
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();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
other.clear();
if (base_type::empty())
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
base_type::to_linked_list();
node_pointer p_out = base_type::prune(pred);
while (p_out != NULL)
{
_GLIBCXX_DEBUG_ASSERT(base_type::m_size > 0);
--base_type::m_size;
++other.m_size;
node_pointer p_next = p_out->m_p_next_sibling;
p_out->m_p_l_child = p_out->m_p_next_sibling = p_out->m_p_prev_or_parent = NULL;
other.push_imp(p_out);
p_out = p_next;
}
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
node_pointer p_cur = base_type::m_p_root;
base_type::m_p_root = NULL;
while (p_cur != NULL)
{
node_pointer p_next = p_cur->m_p_next_sibling;
p_cur->m_p_l_child = p_cur->m_p_next_sibling = p_cur->m_p_prev_or_parent = NULL;
push_imp(p_cur);
p_cur = p_next;
}
_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();)
if (other.m_p_root == NULL)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
if (base_type::m_p_root == NULL)
base_type::m_p_root = other.m_p_root;
else if (Cmp_Fn::operator()(base_type::m_p_root->m_value, other.m_p_root->m_value))
{
base_type::make_child_of(base_type::m_p_root, other.m_p_root);
_GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(other.m_p_root, false));
base_type::m_p_root = other.m_p_root;
}
else
{
base_type::make_child_of(other.m_p_root, base_type::m_p_root);
_GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(base_type::m_p_root, false));
}
base_type::m_size += other.m_size;
other.m_p_root = NULL;
other.m_size = 0;
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}