libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2011 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 ov_tree_map_/split_join_fn_imps.hpp 00038 * Contains an implementation class for ov_tree_. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 void 00043 PB_DS_CLASS_C_DEC:: 00044 split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other) 00045 { 00046 PB_DS_ASSERT_VALID((*this)) 00047 PB_DS_ASSERT_VALID(other) 00048 00049 if (m_size == 0) 00050 { 00051 other.clear(); 00052 return; 00053 } 00054 00055 if (Cmp_Fn::operator()(r_key, PB_DS_V2F(*begin()))) 00056 { 00057 value_swap(other); 00058 PB_DS_ASSERT_VALID((*this)) 00059 PB_DS_ASSERT_VALID(other) 00060 return; 00061 } 00062 00063 if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(*(end() - 1)))) 00064 { 00065 return; 00066 } 00067 00068 if (m_size == 1) 00069 { 00070 value_swap(other); 00071 PB_DS_ASSERT_VALID((*this)) 00072 PB_DS_ASSERT_VALID(other) 00073 return; 00074 } 00075 00076 iterator it = upper_bound(r_key); 00077 PB_DS_CLASS_C_DEC new_other(other, other); 00078 new_other.copy_from_ordered_range(it, end()); 00079 PB_DS_CLASS_C_DEC new_this(*this, *this); 00080 new_this.copy_from_ordered_range(begin(), it); 00081 00082 // No exceptions from this point. 00083 other.update(other.node_begin(), (node_update*)(&other)); 00084 update(node_begin(), (node_update*)this); 00085 other.value_swap(new_other); 00086 value_swap(new_this); 00087 PB_DS_ASSERT_VALID((*this)) 00088 PB_DS_ASSERT_VALID(other) 00089 } 00090 00091 PB_DS_CLASS_T_DEC 00092 void 00093 PB_DS_CLASS_C_DEC:: 00094 join(PB_DS_CLASS_C_DEC& other) 00095 { 00096 PB_DS_ASSERT_VALID((*this)) 00097 PB_DS_ASSERT_VALID(other) 00098 if (other.m_size == 0) 00099 return; 00100 00101 if (m_size == 0) 00102 { 00103 value_swap(other); 00104 PB_DS_ASSERT_VALID((*this)) 00105 PB_DS_ASSERT_VALID(other) 00106 return; 00107 } 00108 00109 const bool greater = Cmp_Fn::operator()(PB_DS_V2F(*(end() - 1)), 00110 PB_DS_V2F(*other.begin())); 00111 00112 const bool lesser = Cmp_Fn::operator()(PB_DS_V2F(*(other.end() - 1)), 00113 PB_DS_V2F(*begin())); 00114 00115 if (!greater && !lesser) 00116 __throw_join_error(); 00117 00118 PB_DS_CLASS_C_DEC new_this(*this, *this); 00119 00120 if (greater) 00121 new_this.copy_from_ordered_range(begin(), end(), 00122 other.begin(), other.end()); 00123 else 00124 new_this.copy_from_ordered_range(other.begin(), other.end(), 00125 begin(), end()); 00126 00127 // No exceptions from this point. 00128 value_swap(new_this); 00129 other.clear(); 00130 PB_DS_ASSERT_VALID((*this)) 00131 PB_DS_ASSERT_VALID(other) 00132 }