1218885Sdim// -*- C++ -*- 2218885Sdim 3218885Sdim// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4218885Sdim// 5218885Sdim// This file is part of the GNU ISO C++ Library. This library is free 6218885Sdim// software; you can redistribute it and/or modify it under the terms 7218885Sdim// of the GNU General Public License as published by the Free Software 8218885Sdim// Foundation; either version 2, or (at your option) any later 9218885Sdim// version. 10218885Sdim 11218885Sdim// This library is distributed in the hope that it will be useful, but 12218885Sdim// WITHOUT ANY WARRANTY; without even the implied warranty of 13218885Sdim// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14218885Sdim// General Public License for more details. 15218885Sdim 16218885Sdim// You should have received a copy of the GNU General Public License 17218885Sdim// along with this library; see the file COPYING. If not, write to 18218885Sdim// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19218885Sdim// MA 02111-1307, USA. 20218885Sdim 21218885Sdim// As a special exception, you may use this file as part of a free 22226633Sdim// software library without restriction. Specifically, if other files 23226633Sdim// instantiate templates or use macros or inline functions from this 24226633Sdim// file, or you compile this file and link it with other files to 25218885Sdim// produce an executable, this file does not by itself cause the 26218885Sdim// resulting executable to be covered by the GNU General Public 27263508Sdim// License. This exception does not however invalidate any other 28263508Sdim// reasons why the executable file might be covered by the GNU General 29218885Sdim// Public License. 30263508Sdim 31263508Sdim// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32218885Sdim 33234353Sdim// Permission to use, copy, modify, sell, and distribute this software 34218885Sdim// is hereby granted without fee, provided that the above copyright 35218885Sdim// notice appears in all copies, and that both that copyright notice 36263508Sdim// and this permission notice appear in supporting documentation. None 37218885Sdim// of the above authors, nor IBM Haifa Research Laboratories, make any 38218885Sdim// representation about the suitability of this software for any 39218885Sdim// purpose. It is provided "as is" without express or implied 40218885Sdim// warranty. 41218885Sdim 42263508Sdim/** 43263508Sdim * @file split_join_fn_imps.hpp 44263508Sdim * Contains an implementation class for splay_tree_. 45263508Sdim */ 46263508Sdim 47263508SdimPB_DS_CLASS_T_DEC 48263508Sdiminline void 49263508SdimPB_DS_CLASS_C_DEC:: 50218885Sdimjoin(PB_DS_CLASS_C_DEC& other) 51263508Sdim{ 52218885Sdim _GLIBCXX_DEBUG_ONLY(assert_valid();) 53218885Sdim _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 54234353Sdim if (base_type::join_prep(other) == false) 55234353Sdim { 56234353Sdim _GLIBCXX_DEBUG_ONLY(assert_valid();) 57234353Sdim _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 58218885Sdim return; 59234353Sdim } 60234353Sdim 61218885Sdim node_pointer p_target_r = other.leftmost(other.m_p_head); 62234353Sdim _GLIBCXX_DEBUG_ASSERT(p_target_r != NULL); 63234353Sdim other.splay(p_target_r); 64218885Sdim 65234353Sdim _GLIBCXX_DEBUG_ASSERT(p_target_r == other.m_p_head->m_p_parent); 66234353Sdim _GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_left == NULL); 67234353Sdim 68234353Sdim p_target_r->m_p_left = base_type::m_p_head->m_p_parent; 69234353Sdim 70234353Sdim _GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_left != NULL); 71218885Sdim p_target_r->m_p_left->m_p_parent = p_target_r; 72218885Sdim 73234353Sdim base_type::m_p_head->m_p_parent = p_target_r; 74234353Sdim p_target_r->m_p_parent = base_type::m_p_head; 75234353Sdim apply_update(p_target_r, (node_update* )this); 76234353Sdim 77218885Sdim base_type::join_finish(other); 78218885Sdim 79234353Sdim _GLIBCXX_DEBUG_ONLY(assert_valid();) 80234353Sdim _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 81234353Sdim} 82234353Sdim 83218885SdimPB_DS_CLASS_T_DEC 84218885Sdimvoid 85234353SdimPB_DS_CLASS_C_DEC:: 86234353Sdimsplit(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) 87263508Sdim{ 88234353Sdim _GLIBCXX_DEBUG_ONLY(assert_valid()); 89234353Sdim _GLIBCXX_DEBUG_ONLY(other.assert_valid()); 90234353Sdim 91234353Sdim if (base_type::split_prep(r_key, other) == false) 92234353Sdim { 93234353Sdim _GLIBCXX_DEBUG_ONLY(assert_valid()); 94218885Sdim _GLIBCXX_DEBUG_ONLY(other.assert_valid()); 95218885Sdim return; 96234353Sdim } 97234353Sdim 98218885Sdim node_pointer p_upper_bound = upper_bound(r_key).m_p_nd; 99234353Sdim _GLIBCXX_DEBUG_ASSERT(p_upper_bound != NULL); 100234353Sdim 101234353Sdim splay(p_upper_bound); 102218885Sdim _GLIBCXX_DEBUG_ASSERT(p_upper_bound->m_p_parent == this->m_p_head); 103234353Sdim 104234353Sdim node_pointer p_new_root = p_upper_bound->m_p_left; 105218885Sdim _GLIBCXX_DEBUG_ASSERT(p_new_root != NULL); 106218885Sdim 107234353Sdim base_type::m_p_head->m_p_parent = p_new_root; 108234353Sdim p_new_root->m_p_parent = base_type::m_p_head; 109218885Sdim other.m_p_head->m_p_parent = p_upper_bound; 110234353Sdim p_upper_bound->m_p_parent = other.m_p_head; 111218885Sdim p_upper_bound->m_p_left = NULL; 112234353Sdim apply_update(p_upper_bound, (node_update* )this); 113234353Sdim base_type::split_finish(other); 114234353Sdim 115234353Sdim _GLIBCXX_DEBUG_ONLY(assert_valid()); 116234353Sdim _GLIBCXX_DEBUG_ONLY(other.assert_valid()); 117218885Sdim} 118234353Sdim 119234353Sdim