libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file pat_trie_/rotate_fn_imps.hpp 00038 * Contains imps for rotating nodes. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 inline void 00043 PB_DS_CLASS_C_DEC:: 00044 rotate_left(node_pointer p_x) 00045 { 00046 node_pointer p_y = p_x->m_p_right; 00047 p_x->m_p_right = p_y->m_p_left; 00048 00049 if (p_y->m_p_left != 0) 00050 p_y->m_p_left->m_p_parent = p_x; 00051 00052 p_y->m_p_parent = p_x->m_p_parent; 00053 if (p_x == m_p_head->m_p_parent) 00054 m_p_head->m_p_parent = p_y; 00055 else if (p_x == p_x->m_p_parent->m_p_left) 00056 p_x->m_p_parent->m_p_left = p_y; 00057 else 00058 p_x->m_p_parent->m_p_right = p_y; 00059 00060 p_y->m_p_left = p_x; 00061 p_x->m_p_parent = p_y; 00062 00063 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) 00064 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) 00065 00066 apply_update(p_x, (Node_Update*)this); 00067 apply_update(p_x->m_p_parent, (Node_Update*)this); 00068 } 00069 00070 PB_DS_CLASS_T_DEC 00071 inline void 00072 PB_DS_CLASS_C_DEC:: 00073 rotate_right(node_pointer p_x) 00074 { 00075 node_pointer p_y = p_x->m_p_left; 00076 p_x->m_p_left = p_y->m_p_right; 00077 00078 if (p_y->m_p_right != 0) 00079 p_y->m_p_right->m_p_parent = p_x; 00080 00081 p_y->m_p_parent = p_x->m_p_parent; 00082 if (p_x == m_p_head->m_p_parent) 00083 m_p_head->m_p_parent = p_y; 00084 else if (p_x == p_x->m_p_parent->m_p_right) 00085 p_x->m_p_parent->m_p_right = p_y; 00086 else 00087 p_x->m_p_parent->m_p_left = p_y; 00088 00089 p_y->m_p_right = p_x; 00090 p_x->m_p_parent = p_y; 00091 00092 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) 00093 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) 00094 00095 apply_update(p_x, (Node_Update*)this); 00096 apply_update(p_x->m_p_parent, (Node_Update*)this); 00097 } 00098 00099 PB_DS_CLASS_T_DEC 00100 inline void 00101 PB_DS_CLASS_C_DEC:: 00102 rotate_parent(node_pointer p_nd) 00103 { 00104 node_pointer p_parent = p_nd->m_p_parent; 00105 if (p_nd == p_parent->m_p_left) 00106 rotate_right(p_parent); 00107 else 00108 rotate_left(p_parent); 00109 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_parent = p_nd); 00110 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == p_parent || p_nd->m_p_right == p_parent); 00111 } 00112 00113 PB_DS_CLASS_T_DEC 00114 inline void 00115 PB_DS_CLASS_C_DEC:: 00116 apply_update(node_pointer /*p_nd*/, __gnu_pbds::null_node_update* /*p_update*/) 00117 { } 00118 00119 PB_DS_CLASS_T_DEC 00120 template<typename Node_Update_> 00121 inline void 00122 PB_DS_CLASS_C_DEC:: 00123 apply_update(node_pointer p_nd, Node_Update_* p_update) 00124 { 00125 p_update->operator()(& PB_DS_V2F(p_nd->m_value),(p_nd->m_p_left == 0) ? 00126 0 : 00127 & PB_DS_V2F(p_nd->m_p_left->m_value),(p_nd->m_p_right == 0) ? 00128 0 : 00129 & PB_DS_V2F(p_nd->m_p_right->m_value)); 00130 } 00131 00132 PB_DS_CLASS_T_DEC 00133 template<typename Node_Update_> 00134 inline void 00135 PB_DS_CLASS_C_DEC:: 00136 update_to_top(node_pointer p_nd, Node_Update_* p_update) 00137 { 00138 while (p_nd != m_p_head) 00139 { 00140 apply_update(p_nd, p_update); 00141 p_nd = p_nd->m_p_parent; 00142 } 00143 } 00144 00145 PB_DS_CLASS_T_DEC 00146 inline void 00147 PB_DS_CLASS_C_DEC:: 00148 update_to_top(node_pointer /*p_nd*/, __gnu_pbds::null_node_update* /*p_update*/) 00149 { } 00150