| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp |
|---|
| 0,0 → 1,100 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/constructors_destructor_fn_imps.hpp |
| * Contains an implementation for rb_tree_. |
| */ |
| 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(*(first_it++)); |
| } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| PB_DS_RB_TREE_NAME() |
| { |
| initialize(); |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| PB_DS_RB_TREE_NAME(const Cmp_Fn& r_cmp_fn) : |
| base_type(r_cmp_fn) |
| { |
| initialize(); |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| PB_DS_RB_TREE_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) : |
| base_type(r_cmp_fn, r_node_update) |
| { |
| initialize(); |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| PB_DS_RB_TREE_NAME(const PB_DS_CLASS_C_DEC& other) : |
| base_type(other) |
| { |
| initialize(); |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| swap(PB_DS_CLASS_C_DEC& other) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| base_type::swap(other); |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| initialize() |
| { base_type::m_p_head->m_red = true; } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp |
|---|
| 0,0 → 1,81 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/debug_fn_imps.hpp |
| * Contains an implementation for rb_tree_. |
| */ |
| #ifdef _GLIBCXX_DEBUG |
| PB_DS_CLASS_T_DEC |
| typename PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| assert_node_consistent(const node_pointer p_nd, const char* __file, |
| int __line) const |
| { |
| if (p_nd == 0) |
| return 1; |
| const size_type l_height = |
| assert_node_consistent(p_nd->m_p_left, __file, __line); |
| const size_type r_height = |
| assert_node_consistent(p_nd->m_p_right, __file, __line); |
| if (p_nd->m_red) |
| { |
| PB_DS_DEBUG_VERIFY(is_effectively_black(p_nd->m_p_left)); |
| PB_DS_DEBUG_VERIFY(is_effectively_black(p_nd->m_p_right)); |
| } |
| PB_DS_DEBUG_VERIFY(l_height == r_height); |
| return (p_nd->m_red ? 0 : 1) + l_height; |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| assert_valid(const char* __file, int __line) const |
| { |
| base_type::assert_valid(__file, __line); |
| const node_pointer p_head = base_type::m_p_head; |
| PB_DS_DEBUG_VERIFY(p_head->m_red); |
| if (p_head->m_p_parent != 0) |
| { |
| PB_DS_DEBUG_VERIFY(!p_head->m_p_parent->m_red); |
| assert_node_consistent(p_head->m_p_parent, __file, __line); |
| } |
| } |
| #endif |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp |
|---|
| 0,0 → 1,289 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/erase_fn_imps.hpp |
| * Contains an implementation for rb_tree_. |
| */ |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| erase(key_const_reference r_key) |
| { |
| point_iterator it = this->find(r_key); |
| if (it == base_type::end()) |
| return false; |
| erase(it); |
| return true; |
| } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::iterator |
| PB_DS_CLASS_C_DEC:: |
| erase(iterator it) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| if (it == base_type::end()) |
| return it; |
| iterator ret_it = it; |
| ++ret_it; |
| erase_node(it.m_p_nd); |
| PB_DS_ASSERT_VALID((*this)) |
| return ret_it; |
| } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::reverse_iterator |
| PB_DS_CLASS_C_DEC:: |
| erase(reverse_iterator it) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| if (it.m_p_nd == base_type::m_p_head) |
| return it; |
| reverse_iterator ret_it = it; |
| ++ret_it; |
| erase_node(it.m_p_nd); |
| PB_DS_ASSERT_VALID((*this)) |
| return ret_it; |
| } |
| PB_DS_CLASS_T_DEC |
| template<typename Pred> |
| inline typename PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| erase_if(Pred pred) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| size_type num_ersd = 0; |
| iterator it = base_type::begin(); |
| while (it != base_type::end()) |
| { |
| if (pred(*it)) |
| { |
| ++num_ersd; |
| it = erase(it); |
| } |
| else |
| ++it; |
| } |
| PB_DS_ASSERT_VALID((*this)) |
| return num_ersd; |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| erase_node(node_pointer p_nd) |
| { |
| remove_node(p_nd); |
| base_type::actual_erase_node(p_nd); |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| remove_node(node_pointer p_z) |
| { |
| this->update_min_max_for_erased_node(p_z); |
| node_pointer p_y = p_z; |
| node_pointer p_x = 0; |
| node_pointer p_new_x_parent = 0; |
| if (p_y->m_p_left == 0) |
| p_x = p_y->m_p_right; |
| else if (p_y->m_p_right == 0) |
| p_x = p_y->m_p_left; |
| else |
| { |
| p_y = p_y->m_p_right; |
| while (p_y->m_p_left != 0) |
| p_y = p_y->m_p_left; |
| p_x = p_y->m_p_right; |
| } |
| if (p_y == p_z) |
| { |
| p_new_x_parent = p_y->m_p_parent; |
| if (p_x != 0) |
| p_x->m_p_parent = p_y->m_p_parent; |
| if (base_type::m_p_head->m_p_parent == p_z) |
| base_type::m_p_head->m_p_parent = p_x; |
| else if (p_z->m_p_parent->m_p_left == p_z) |
| { |
| p_y->m_p_left = p_z->m_p_parent; |
| p_z->m_p_parent->m_p_left = p_x; |
| } |
| else |
| { |
| p_y->m_p_left = 0; |
| p_z->m_p_parent->m_p_right = p_x; |
| } |
| } |
| else |
| { |
| p_z->m_p_left->m_p_parent = p_y; |
| p_y->m_p_left = p_z->m_p_left; |
| if (p_y != p_z->m_p_right) |
| { |
| p_new_x_parent = p_y->m_p_parent; |
| if (p_x != 0) |
| p_x->m_p_parent = p_y->m_p_parent; |
| p_y->m_p_parent->m_p_left = p_x; |
| p_y->m_p_right = p_z->m_p_right; |
| p_z->m_p_right->m_p_parent = p_y; |
| } |
| else |
| p_new_x_parent = p_y; |
| if (base_type::m_p_head->m_p_parent == p_z) |
| base_type::m_p_head->m_p_parent = p_y; |
| else if (p_z->m_p_parent->m_p_left == p_z) |
| p_z->m_p_parent->m_p_left = p_y; |
| else |
| p_z->m_p_parent->m_p_right = p_y; |
| p_y->m_p_parent = p_z->m_p_parent; |
| std::swap(p_y->m_red, p_z->m_red); |
| p_y = p_z; |
| } |
| this->update_to_top(p_new_x_parent, (node_update* )this); |
| if (p_y->m_red) |
| return; |
| remove_fixup(p_x, p_new_x_parent); |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| remove_fixup(node_pointer p_x, node_pointer p_new_x_parent) |
| { |
| _GLIBCXX_DEBUG_ASSERT(p_x == 0 || p_x->m_p_parent == p_new_x_parent); |
| while (p_x != base_type::m_p_head->m_p_parent && is_effectively_black(p_x)) |
| if (p_x == p_new_x_parent->m_p_left) |
| { |
| node_pointer p_w = p_new_x_parent->m_p_right; |
| if (p_w->m_red) |
| { |
| p_w->m_red = false; |
| p_new_x_parent->m_red = true; |
| base_type::rotate_left(p_new_x_parent); |
| p_w = p_new_x_parent->m_p_right; |
| } |
| if (is_effectively_black(p_w->m_p_left) |
| && is_effectively_black(p_w->m_p_right)) |
| { |
| p_w->m_red = true; |
| p_x = p_new_x_parent; |
| p_new_x_parent = p_new_x_parent->m_p_parent; |
| } |
| else |
| { |
| if (is_effectively_black(p_w->m_p_right)) |
| { |
| if (p_w->m_p_left != 0) |
| p_w->m_p_left->m_red = false; |
| p_w->m_red = true; |
| base_type::rotate_right(p_w); |
| p_w = p_new_x_parent->m_p_right; |
| } |
| p_w->m_red = p_new_x_parent->m_red; |
| p_new_x_parent->m_red = false; |
| if (p_w->m_p_right != 0) |
| p_w->m_p_right->m_red = false; |
| base_type::rotate_left(p_new_x_parent); |
| this->update_to_top(p_new_x_parent, (node_update* )this); |
| break; |
| } |
| } |
| else |
| { |
| node_pointer p_w = p_new_x_parent->m_p_left; |
| if (p_w->m_red == true) |
| { |
| p_w->m_red = false; |
| p_new_x_parent->m_red = true; |
| base_type::rotate_right(p_new_x_parent); |
| p_w = p_new_x_parent->m_p_left; |
| } |
| if (is_effectively_black(p_w->m_p_right) |
| && is_effectively_black(p_w->m_p_left)) |
| { |
| p_w->m_red = true; |
| p_x = p_new_x_parent; |
| p_new_x_parent = p_new_x_parent->m_p_parent; |
| } |
| else |
| { |
| if (is_effectively_black(p_w->m_p_left)) |
| { |
| if (p_w->m_p_right != 0) |
| p_w->m_p_right->m_red = false; |
| p_w->m_red = true; |
| base_type::rotate_left(p_w); |
| p_w = p_new_x_parent->m_p_left; |
| } |
| p_w->m_red = p_new_x_parent->m_red; |
| p_new_x_parent->m_red = false; |
| if (p_w->m_p_left != 0) |
| p_w->m_p_left->m_red = false; |
| base_type::rotate_right(p_new_x_parent); |
| this->update_to_top(p_new_x_parent, (node_update* )this); |
| break; |
| } |
| } |
| if (p_x != 0) |
| p_x->m_red = false; |
| } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/find_fn_imps.hpp |
|---|
| 0,0 → 1,39 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/find_fn_imps.hpp |
| * Contains an implementation for rb_tree_. |
| */ |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp |
|---|
| 0,0 → 1,46 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/info_fn_imps.hpp |
| * Contains an implementation for rb_tree_. |
| */ |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| is_effectively_black(const node_pointer p_nd) |
| { return (p_nd == 0 || !p_nd->m_red); } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp |
|---|
| 0,0 → 1,115 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/insert_fn_imps.hpp |
| * Contains an implementation for rb_tree_. |
| */ |
| PB_DS_CLASS_T_DEC |
| inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> |
| PB_DS_CLASS_C_DEC:: |
| insert(const_reference r_value) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| std::pair<point_iterator, bool> ins_pair = base_type::insert_leaf(r_value); |
| if (ins_pair.second == true) |
| { |
| ins_pair.first.m_p_nd->m_red = true; |
| PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
| insert_fixup(ins_pair.first.m_p_nd); |
| } |
| PB_DS_ASSERT_VALID((*this)) |
| return ins_pair; |
| } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| insert_fixup(node_pointer p_nd) |
| { |
| _GLIBCXX_DEBUG_ASSERT(p_nd->m_red == true); |
| while (p_nd != base_type::m_p_head->m_p_parent && p_nd->m_p_parent->m_red) |
| { |
| if (p_nd->m_p_parent == p_nd->m_p_parent->m_p_parent->m_p_left) |
| { |
| node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_right; |
| if (p_y != 0 && p_y->m_red) |
| { |
| p_nd->m_p_parent->m_red = false; |
| p_y->m_red = false; |
| p_nd->m_p_parent->m_p_parent->m_red = true; |
| p_nd = p_nd->m_p_parent->m_p_parent; |
| } |
| else |
| { |
| if (p_nd == p_nd->m_p_parent->m_p_right) |
| { |
| p_nd = p_nd->m_p_parent; |
| base_type::rotate_left(p_nd); |
| } |
| p_nd->m_p_parent->m_red = false; |
| p_nd->m_p_parent->m_p_parent->m_red = true; |
| base_type::rotate_right(p_nd->m_p_parent->m_p_parent); |
| } |
| } |
| else |
| { |
| node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_left; |
| if (p_y != 0 && p_y->m_red) |
| { |
| p_nd->m_p_parent->m_red = false; |
| p_y->m_red = false; |
| p_nd->m_p_parent->m_p_parent->m_red = true; |
| p_nd = p_nd->m_p_parent->m_p_parent; |
| } |
| else |
| { |
| if (p_nd == p_nd->m_p_parent->m_p_left) |
| { |
| p_nd = p_nd->m_p_parent; |
| base_type::rotate_right(p_nd); |
| } |
| p_nd->m_p_parent->m_red = false; |
| p_nd->m_p_parent->m_p_parent->m_red = true; |
| base_type::rotate_left(p_nd->m_p_parent->m_p_parent); |
| } |
| } |
| } |
| base_type::update_to_top(p_nd, (node_update* )this); |
| base_type::m_p_head->m_p_parent->m_red = false; |
| } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp |
|---|
| 0,0 → 1,139 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/node.hpp |
| * Contains an implementation for rb_tree_. |
| */ |
| #ifndef PB_DS_RB_TREE_NODE_HPP |
| #define PB_DS_RB_TREE_NODE_HPP |
| #include <ext/pb_ds/detail/branch_policy/null_node_metadata.hpp> |
| namespace __gnu_pbds |
| { |
| namespace detail |
| { |
| /// Node for Red-Black trees. |
| template<typename Value_Type, class Metadata, typename _Alloc> |
| struct rb_tree_node_ |
| { |
| public: |
| typedef Value_Type value_type; |
| typedef Metadata metadata_type; |
| typedef |
| typename _Alloc::template rebind< |
| rb_tree_node_< |
| Value_Type, |
| Metadata, |
| _Alloc> >::other::pointer |
| node_pointer; |
| typedef |
| typename _Alloc::template rebind< |
| metadata_type>::other::reference |
| metadata_reference; |
| typedef |
| typename _Alloc::template rebind< |
| metadata_type>::other::const_reference |
| metadata_const_reference; |
| bool |
| special() const |
| { return m_red; } |
| metadata_const_reference |
| get_metadata() const |
| { return m_metadata; } |
| metadata_reference |
| get_metadata() |
| { return m_metadata; } |
| #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ |
| void |
| trace() const |
| { |
| std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> ") |
| << "(" << m_metadata << ")"; |
| } |
| #endif |
| node_pointer m_p_left; |
| node_pointer m_p_right; |
| node_pointer m_p_parent; |
| value_type m_value; |
| bool m_red; |
| metadata_type m_metadata; |
| }; |
| template<typename Value_Type, typename _Alloc> |
| struct rb_tree_node_<Value_Type, null_type, _Alloc> |
| { |
| public: |
| typedef Value_Type value_type; |
| typedef null_type metadata_type; |
| typedef |
| typename _Alloc::template rebind< |
| rb_tree_node_< |
| Value_Type, |
| null_type, |
| _Alloc> >::other::pointer |
| node_pointer; |
| bool |
| special() const |
| { return m_red; } |
| #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ |
| void |
| trace() const |
| { std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> "); } |
| #endif |
| node_pointer m_p_left; |
| node_pointer m_p_right; |
| node_pointer m_p_parent; |
| value_type m_value; |
| bool m_red; |
| }; |
| } // namespace detail |
| } // namespace __gnu_pbds |
| #endif |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp |
|---|
| 0,0 → 1,248 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/rb_tree_.hpp |
| * Contains an implementation for Red Black trees. |
| */ |
| #include <ext/pb_ds/detail/standard_policies.hpp> |
| #include <utility> |
| #include <vector> |
| #include <assert.h> |
| #include <debug/debug.h> |
| namespace __gnu_pbds |
| { |
| namespace detail |
| { |
| #define PB_DS_CLASS_T_DEC \ |
| template<typename Key, typename Mapped, typename Cmp_Fn, \ |
| typename Node_And_It_Traits, typename _Alloc> |
| #ifdef PB_DS_DATA_TRUE_INDICATOR |
| # define PB_DS_RB_TREE_NAME rb_tree_map |
| # define PB_DS_RB_TREE_BASE_NAME bin_search_tree_map |
| #endif |
| #ifdef PB_DS_DATA_FALSE_INDICATOR |
| # define PB_DS_RB_TREE_NAME rb_tree_set |
| # define PB_DS_RB_TREE_BASE_NAME bin_search_tree_set |
| #endif |
| #define PB_DS_CLASS_C_DEC \ |
| PB_DS_RB_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> |
| #define PB_DS_RB_TREE_BASE \ |
| PB_DS_RB_TREE_BASE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> |
| /** |
| * @brief Red-Black tree. |
| * @ingroup branch-detail |
| * |
| * This implementation uses an idea from the SGI STL (using a |
| * @a header node which is needed for efficient iteration). |
| */ |
| template<typename Key, |
| typename Mapped, |
| typename Cmp_Fn, |
| typename Node_And_It_Traits, |
| typename _Alloc> |
| class PB_DS_RB_TREE_NAME : public PB_DS_RB_TREE_BASE |
| { |
| private: |
| typedef PB_DS_RB_TREE_BASE base_type; |
| typedef typename base_type::node_pointer node_pointer; |
| public: |
| typedef rb_tree_tag container_category; |
| typedef Cmp_Fn cmp_fn; |
| typedef _Alloc allocator_type; |
| typedef typename _Alloc::size_type size_type; |
| typedef typename _Alloc::difference_type difference_type; |
| typedef typename base_type::key_type key_type; |
| typedef typename base_type::key_pointer key_pointer; |
| typedef typename base_type::key_const_pointer key_const_pointer; |
| typedef typename base_type::key_reference key_reference; |
| typedef typename base_type::key_const_reference key_const_reference; |
| typedef typename base_type::mapped_type mapped_type; |
| typedef typename base_type::mapped_pointer mapped_pointer; |
| typedef typename base_type::mapped_const_pointer mapped_const_pointer; |
| typedef typename base_type::mapped_reference mapped_reference; |
| typedef typename base_type::mapped_const_reference mapped_const_reference; |
| typedef typename base_type::value_type value_type; |
| typedef typename base_type::pointer pointer; |
| typedef typename base_type::const_pointer const_pointer; |
| typedef typename base_type::reference reference; |
| typedef typename base_type::const_reference const_reference; |
| typedef typename base_type::point_iterator point_iterator; |
| typedef typename base_type::const_iterator point_const_iterator; |
| typedef typename base_type::iterator iterator; |
| typedef typename base_type::const_iterator const_iterator; |
| typedef typename base_type::reverse_iterator reverse_iterator; |
| typedef typename base_type::const_reverse_iterator const_reverse_iterator; |
| typedef typename base_type::node_update node_update; |
| PB_DS_RB_TREE_NAME(); |
| PB_DS_RB_TREE_NAME(const Cmp_Fn&); |
| PB_DS_RB_TREE_NAME(const Cmp_Fn&, const node_update&); |
| PB_DS_RB_TREE_NAME(const PB_DS_CLASS_C_DEC&); |
| void |
| swap(PB_DS_CLASS_C_DEC&); |
| template<typename It> |
| void |
| copy_from_range(It, It); |
| inline std::pair<point_iterator, bool> |
| insert(const_reference); |
| inline mapped_reference |
| operator[](key_const_reference r_key) |
| { |
| #ifdef PB_DS_DATA_TRUE_INDICATOR |
| _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
| std::pair<point_iterator, bool> ins_pair = |
| base_type::insert_leaf(value_type(r_key, mapped_type())); |
| if (ins_pair.second == true) |
| { |
| ins_pair.first.m_p_nd->m_red = true; |
| _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid(__FILE__, __LINE__);) |
| insert_fixup(ins_pair.first.m_p_nd); |
| } |
| _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
| return ins_pair.first.m_p_nd->m_value.second; |
| #else |
| insert(r_key); |
| return base_type::s_null_type; |
| #endif |
| } |
| inline bool |
| erase(key_const_reference); |
| inline iterator |
| erase(iterator); |
| inline reverse_iterator |
| erase(reverse_iterator); |
| template<typename Pred> |
| inline size_type |
| erase_if(Pred); |
| void |
| join(PB_DS_CLASS_C_DEC&); |
| void |
| split(key_const_reference, PB_DS_CLASS_C_DEC&); |
| private: |
| #ifdef _GLIBCXX_DEBUG |
| void |
| assert_valid(const char*, int) const; |
| size_type |
| assert_node_consistent(const node_pointer, const char*, int) const; |
| #endif |
| inline static bool |
| is_effectively_black(const node_pointer); |
| void |
| initialize(); |
| void |
| insert_fixup(node_pointer); |
| void |
| erase_node(node_pointer); |
| void |
| remove_node(node_pointer); |
| void |
| remove_fixup(node_pointer, node_pointer); |
| void |
| split_imp(node_pointer, PB_DS_CLASS_C_DEC&); |
| inline node_pointer |
| split_min(); |
| std::pair<node_pointer, node_pointer> |
| split_min_imp(); |
| void |
| join_imp(node_pointer, node_pointer); |
| std::pair<node_pointer, node_pointer> |
| find_join_pos_right(node_pointer, size_type, size_type); |
| std::pair<node_pointer, node_pointer> |
| find_join_pos_left(node_pointer, size_type, size_type); |
| inline size_type |
| black_height(node_pointer); |
| void |
| split_at_node(node_pointer, PB_DS_CLASS_C_DEC&); |
| }; |
| #define PB_DS_STRUCT_ONLY_ASSERT_VALID(X) \ |
| _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);) |
| #include <ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp> |
| #include <ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp> |
| #include <ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp> |
| #include <ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp> |
| #include <ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp> |
| #include <ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp> |
| #undef PB_DS_STRUCT_ONLY_ASSERT_VALID |
| #undef PB_DS_CLASS_T_DEC |
| #undef PB_DS_CLASS_C_DEC |
| #undef PB_DS_RB_TREE_NAME |
| #undef PB_DS_RB_TREE_BASE_NAME |
| #undef PB_DS_RB_TREE_BASE |
| } // namespace detail |
| } // namespace __gnu_pbds |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp |
|---|
| 0,0 → 1,306 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/split_join_fn_imps.hpp |
| * Contains an implementation for rb_tree_. |
| */ |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| join(PB_DS_CLASS_C_DEC& other) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| PB_DS_ASSERT_VALID(other) |
| if (base_type::join_prep(other) == false) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| PB_DS_ASSERT_VALID(other) |
| return; |
| } |
| const node_pointer p_x = other.split_min(); |
| join_imp(p_x, other.m_p_head->m_p_parent); |
| base_type::join_finish(other); |
| PB_DS_ASSERT_VALID((*this)) |
| PB_DS_ASSERT_VALID(other) |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| join_imp(node_pointer p_x, node_pointer p_r) |
| { |
| _GLIBCXX_DEBUG_ASSERT(p_x != 0); |
| if (p_r != 0) |
| p_r->m_red = false; |
| const size_type h = black_height(base_type::m_p_head->m_p_parent); |
| const size_type other_h = black_height(p_r); |
| node_pointer p_x_l; |
| node_pointer p_x_r; |
| std::pair<node_pointer, node_pointer> join_pos; |
| const bool right_join = h >= other_h; |
| if (right_join) |
| { |
| join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent, |
| h, other_h); |
| p_x_l = join_pos.first; |
| p_x_r = p_r; |
| } |
| else |
| { |
| p_x_l = base_type::m_p_head->m_p_parent; |
| base_type::m_p_head->m_p_parent = p_r; |
| if (p_r != 0) |
| p_r->m_p_parent = base_type::m_p_head; |
| join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent, |
| h, other_h); |
| p_x_r = join_pos.first; |
| } |
| node_pointer p_parent = join_pos.second; |
| if (p_parent == base_type::m_p_head) |
| { |
| base_type::m_p_head->m_p_parent = p_x; |
| p_x->m_p_parent = base_type::m_p_head; |
| } |
| else |
| { |
| p_x->m_p_parent = p_parent; |
| if (right_join) |
| p_x->m_p_parent->m_p_right = p_x; |
| else |
| p_x->m_p_parent->m_p_left = p_x; |
| } |
| p_x->m_p_left = p_x_l; |
| if (p_x_l != 0) |
| p_x_l->m_p_parent = p_x; |
| p_x->m_p_right = p_x_r; |
| if (p_x_r != 0) |
| p_x_r->m_p_parent = p_x; |
| p_x->m_red = true; |
| base_type::initialize_min_max(); |
| PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
| base_type::update_to_top(p_x, (node_update* )this); |
| insert_fixup(p_x); |
| PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::node_pointer |
| PB_DS_CLASS_C_DEC:: |
| split_min() |
| { |
| node_pointer p_min = base_type::m_p_head->m_p_left; |
| #ifdef _GLIBCXX_DEBUG |
| const node_pointer p_head = base_type::m_p_head; |
| _GLIBCXX_DEBUG_ASSERT(p_min != p_head); |
| #endif |
| remove_node(p_min); |
| return p_min; |
| } |
| PB_DS_CLASS_T_DEC |
| std::pair< |
| typename PB_DS_CLASS_C_DEC::node_pointer, |
| typename PB_DS_CLASS_C_DEC::node_pointer> |
| PB_DS_CLASS_C_DEC:: |
| find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r) |
| { |
| _GLIBCXX_DEBUG_ASSERT(h_l >= h_r); |
| if (base_type::m_p_head->m_p_parent == 0) |
| return (std::make_pair((node_pointer)0, base_type::m_p_head)); |
| node_pointer p_l_parent = base_type::m_p_head; |
| while (h_l > h_r) |
| { |
| if (p_l->m_red == false) |
| { |
| _GLIBCXX_DEBUG_ASSERT(h_l > 0); |
| --h_l; |
| } |
| p_l_parent = p_l; |
| p_l = p_l->m_p_right; |
| } |
| if (!is_effectively_black(p_l)) |
| { |
| p_l_parent = p_l; |
| p_l = p_l->m_p_right; |
| } |
| _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l)); |
| _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r); |
| _GLIBCXX_DEBUG_ASSERT(p_l == 0 || p_l->m_p_parent == p_l_parent); |
| return std::make_pair(p_l, p_l_parent); |
| } |
| PB_DS_CLASS_T_DEC |
| std::pair< |
| typename PB_DS_CLASS_C_DEC::node_pointer, |
| typename PB_DS_CLASS_C_DEC::node_pointer> |
| PB_DS_CLASS_C_DEC:: |
| find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r) |
| { |
| _GLIBCXX_DEBUG_ASSERT(h_r > h_l); |
| if (base_type::m_p_head->m_p_parent == 0) |
| return (std::make_pair((node_pointer)0, |
| base_type::m_p_head)); |
| node_pointer p_r_parent = base_type::m_p_head; |
| while (h_r > h_l) |
| { |
| if (p_r->m_red == false) |
| { |
| _GLIBCXX_DEBUG_ASSERT(h_r > 0); |
| --h_r; |
| } |
| p_r_parent = p_r; |
| p_r = p_r->m_p_left; |
| } |
| if (!is_effectively_black(p_r)) |
| { |
| p_r_parent = p_r; |
| p_r = p_r->m_p_left; |
| } |
| _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r)); |
| _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l); |
| _GLIBCXX_DEBUG_ASSERT(p_r == 0 || p_r->m_p_parent == p_r_parent); |
| return std::make_pair(p_r, p_r_parent); |
| } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| black_height(node_pointer p_nd) |
| { |
| size_type h = 1; |
| while (p_nd != 0) |
| { |
| if (p_nd->m_red == false) |
| ++h; |
| p_nd = p_nd->m_p_left; |
| } |
| return h; |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| PB_DS_ASSERT_VALID(other) |
| if (base_type::split_prep(r_key, other) == false) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| PB_DS_ASSERT_VALID(other) |
| return; |
| } |
| PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
| PB_DS_STRUCT_ONLY_ASSERT_VALID(other) |
| node_pointer p_nd = this->upper_bound(r_key).m_p_nd; |
| do |
| { |
| node_pointer p_next_nd = p_nd->m_p_parent; |
| if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) |
| split_at_node(p_nd, other); |
| PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
| PB_DS_STRUCT_ONLY_ASSERT_VALID(other) |
| p_nd = p_next_nd; |
| } |
| while (p_nd != base_type::m_p_head); |
| base_type::split_finish(other); |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) |
| { |
| _GLIBCXX_DEBUG_ASSERT(p_nd != 0); |
| node_pointer p_l = p_nd->m_p_left; |
| node_pointer p_r = p_nd->m_p_right; |
| node_pointer p_parent = p_nd->m_p_parent; |
| if (p_parent == base_type::m_p_head) |
| { |
| base_type::m_p_head->m_p_parent = p_l; |
| if (p_l != 0) |
| { |
| p_l->m_p_parent = base_type::m_p_head; |
| p_l->m_red = false; |
| } |
| } |
| else |
| { |
| if (p_parent->m_p_left == p_nd) |
| p_parent->m_p_left = p_l; |
| else |
| p_parent->m_p_right = p_l; |
| if (p_l != 0) |
| p_l->m_p_parent = p_parent; |
| this->update_to_top(p_parent, (node_update* )this); |
| if (!p_nd->m_red) |
| remove_fixup(p_l, p_parent); |
| } |
| base_type::initialize_min_max(); |
| other.join_imp(p_nd, p_r); |
| PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
| PB_DS_STRUCT_ONLY_ASSERT_VALID(other) |
| } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp |
|---|
| 0,0 → 1,102 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 rb_tree_map_/traits.hpp |
| * Contains an implementation for rb_tree_. |
| */ |
| #ifndef PB_DS_RB_TREE_NODE_AND_IT_TRAITS_HPP |
| #define PB_DS_RB_TREE_NODE_AND_IT_TRAITS_HPP |
| #include <ext/pb_ds/detail/rb_tree_map_/node.hpp> |
| namespace __gnu_pbds |
| { |
| namespace detail |
| { |
| /// Specialization. |
| /// @ingroup traits |
| template<typename Key, |
| typename Mapped, |
| typename Cmp_Fn, |
| template<typename Node_CItr, |
| typename Node_Itr, |
| typename Cmp_Fn_, |
| typename _Alloc_> |
| class Node_Update, |
| typename _Alloc> |
| struct tree_traits<Key, Mapped, Cmp_Fn, Node_Update, rb_tree_tag,_Alloc> |
| : public bin_search_tree_traits< |
| Key, |
| Mapped, |
| Cmp_Fn, |
| Node_Update, |
| rb_tree_node_< |
| typename types_traits<Key, Mapped, _Alloc, false>::value_type, |
| typename tree_node_metadata_dispatch<Key, Mapped, Cmp_Fn, Node_Update, |
| _Alloc>::type, |
| _Alloc>, |
| _Alloc> |
| { }; |
| /// Specialization. |
| /// @ingroup traits |
| template<typename Key, |
| typename Cmp_Fn, |
| template<typename Node_CItr, |
| typename Node_Itr, |
| typename Cmp_Fn_, |
| typename _Alloc_> |
| class Node_Update, |
| typename _Alloc> |
| struct tree_traits<Key, null_type, Cmp_Fn, Node_Update, rb_tree_tag,_Alloc> |
| : public bin_search_tree_traits< |
| Key, |
| null_type, |
| Cmp_Fn, |
| Node_Update, |
| rb_tree_node_< |
| typename types_traits<Key, null_type, _Alloc, false>::value_type, |
| typename tree_node_metadata_dispatch<Key, null_type, Cmp_Fn, Node_Update, |
| _Alloc>::type, |
| _Alloc>, |
| _Alloc> |
| { }; |
| } // namespace detail |
| } // namespace __gnu_pbds |
| #endif |