rotate_fn_imps.hpp revision 256281
1139749Simp// -*- C++ -*- 243410Snewton 343410Snewton// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 443410Snewton// 543410Snewton// This file is part of the GNU ISO C++ Library. This library is free 643410Snewton// software; you can redistribute it and/or modify it under the terms 743410Snewton// of the GNU General Public License as published by the Free Software 843410Snewton// Foundation; either version 2, or (at your option) any later 943410Snewton// version. 1043410Snewton 1143410Snewton// This library is distributed in the hope that it will be useful, but 1243410Snewton// WITHOUT ANY WARRANTY; without even the implied warranty of 1343410Snewton// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1443410Snewton// General Public License for more details. 1543410Snewton 1643410Snewton// You should have received a copy of the GNU General Public License 1743410Snewton// along with this library; see the file COPYING. If not, write to 1843410Snewton// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1943410Snewton// MA 02111-1307, USA. 2043410Snewton 2143410Snewton// As a special exception, you may use this file as part of a free 2243410Snewton// software library without restriction. Specifically, if other files 2343410Snewton// instantiate templates or use macros or inline functions from this 2443410Snewton// file, or you compile this file and link it with other files to 2543410Snewton// produce an executable, this file does not by itself cause the 2643410Snewton// resulting executable to be covered by the GNU General Public 2743410Snewton// License. This exception does not however invalidate any other 2843410Snewton// reasons why the executable file might be covered by the GNU General 2943410Snewton// Public License. 3043410Snewton 3143410Snewton// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 3249263Snewton 3343410Snewton// Permission to use, copy, modify, sell, and distribute this software 3443410Snewton// is hereby granted without fee, provided that the above copyright 35119420Sobrien// notice appears in all copies, and that both that copyright notice 36119420Sobrien// and this permission notice appear in supporting documentation. None 37119420Sobrien// of the above authors, nor IBM Haifa Research Laboratories, make any 3843410Snewton// representation about the suitability of this software for any 3943410Snewton// purpose. It is provided "as is" without express or implied 4043410Snewton// warranty. 4143410Snewton 4243410Snewton/** 4343410Snewton * @file rotate_fn_imps.hpp 4443410Snewton * Contains imps for rotating nodes. 4543410Snewton */ 4643410Snewton 4743410SnewtonPB_DS_CLASS_T_DEC 4843410Snewtoninline void 4943410SnewtonPB_DS_CLASS_C_DEC:: 50141466Sjhbrotate_left(node_pointer p_x) 5143410Snewton{ 5243410Snewton node_pointer p_y = p_x->m_p_right; 5343410Snewton p_x->m_p_right = p_y->m_p_left; 5443410Snewton 5543410Snewton if (p_y->m_p_left != NULL) 5643410Snewton p_y->m_p_left->m_p_parent = p_x; 5743410Snewton 5843410Snewton p_y->m_p_parent = p_x->m_p_parent; 5943410Snewton if (p_x == m_p_head->m_p_parent) 6065314Sobrien m_p_head->m_p_parent = p_y; 6165314Sobrien else if (p_x == p_x->m_p_parent->m_p_left) 6265314Sobrien p_x->m_p_parent->m_p_left = p_y; 6365314Sobrien else 6465314Sobrien p_x->m_p_parent->m_p_right = p_y; 6565314Sobrien 6643410Snewton p_y->m_p_left = p_x; 6792739Salfred p_x->m_p_parent = p_y; 6892739Salfred 6943410Snewton _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) 7043410Snewton _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) 7143410Snewton 7243410Snewton apply_update(p_x, (Node_Update* )this); 7343410Snewton apply_update(p_x->m_p_parent, (Node_Update* )this); 7443410Snewton} 7543410Snewton 7643410SnewtonPB_DS_CLASS_T_DEC 7743410Snewtoninline void 7843410SnewtonPB_DS_CLASS_C_DEC:: 7943410Snewtonrotate_right(node_pointer p_x) 8043410Snewton{ 8143410Snewton node_pointer p_y = p_x->m_p_left; 8243410Snewton p_x->m_p_left = p_y->m_p_right; 8343410Snewton 8443410Snewton if (p_y->m_p_right != NULL) 8543410Snewton p_y->m_p_right->m_p_parent = p_x; 8643410Snewton 87160508Sjhb p_y->m_p_parent = p_x->m_p_parent; 88160508Sjhb if (p_x == m_p_head->m_p_parent) 8952114Snewton m_p_head->m_p_parent = p_y; 9043410Snewton else if (p_x == p_x->m_p_parent->m_p_right) 91116546Sphk p_x->m_p_parent->m_p_right = p_y; 92116546Sphk else 93175140Sjhb p_x->m_p_parent->m_p_left = p_y; 94116546Sphk 95116546Sphk p_y->m_p_right = p_x; 96116546Sphk p_x->m_p_parent = p_y; 97116546Sphk 98116546Sphk _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) 9943410Snewton _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) 10043410Snewton 10143410Snewton apply_update(p_x, (Node_Update* )this); 102126080Sphk apply_update(p_x->m_p_parent, (Node_Update* )this); 103111815Sphk} 104111815Sphk 10547625SphkPB_DS_CLASS_T_DEC 10643410Snewtoninline void 10743410SnewtonPB_DS_CLASS_C_DEC:: 10843410Snewtonrotate_parent(node_pointer p_nd) 10943410Snewton{ 11043410Snewton node_pointer p_parent = p_nd->m_p_parent; 111183397Sed if (p_nd == p_parent->m_p_left) 11243410Snewton rotate_right(p_parent); 11343410Snewton else 11443410Snewton rotate_left(p_parent); 11544208Snewton _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_parent = p_nd); 11644208Snewton _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == p_parent || p_nd->m_p_right == p_parent); 11744208Snewton} 11844208Snewton 11944208SnewtonPB_DS_CLASS_T_DEC 12052114Snewtoninline void 12152114SnewtonPB_DS_CLASS_C_DEC:: 12252114Snewtonapply_update(node_pointer /*p_nd*/, pb_ds::null_node_update* /*p_update*/) 12352114Snewton{ } 12452114Snewton 12552114SnewtonPB_DS_CLASS_T_DEC 12652114Snewtontemplate<typename Node_Update_> 12752114Snewtoninline void 12852114SnewtonPB_DS_CLASS_C_DEC:: 12952114Snewtonapply_update(node_pointer p_nd, Node_Update_* p_update) 13052114Snewton{ 13152114Snewton p_update->operator()(& PB_DS_V2F(p_nd->m_value),(p_nd->m_p_left == NULL) ? 13252114Snewton NULL : 13352114Snewton & PB_DS_V2F(p_nd->m_p_left->m_value),(p_nd->m_p_right == NULL) ? 13452114Snewton NULL : 13552114Snewton & PB_DS_V2F(p_nd->m_p_right->m_value)); 13652114Snewton} 13752114Snewton 13852114SnewtonPB_DS_CLASS_T_DEC 13952114Snewtontemplate<typename Node_Update_> 14052114Snewtoninline void 14152114SnewtonPB_DS_CLASS_C_DEC:: 14252114Snewtonupdate_to_top(node_pointer p_nd, Node_Update_* p_update) 14352114Snewton{ 14452114Snewton while (p_nd != m_p_head) 14552114Snewton { 14652114Snewton apply_update(p_nd, p_update); 14744208Snewton p_nd = p_nd->m_p_parent; 14844208Snewton } 14949344Snewton} 15053000Sphk 15153000SphkPB_DS_CLASS_T_DEC 15253000Sphkinline void 15353000SphkPB_DS_CLASS_C_DEC:: 15453000Sphkupdate_to_top(node_pointer /*p_nd*/, pb_ds::null_node_update* /*p_update*/) 15553000Sphk{ } 15653000Sphk 15753000Sphk