libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010, 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 bin_search_tree_/find_fn_imps.hpp 00038 * Contains an implementation class for bin_search_tree_. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 inline typename PB_DS_CLASS_C_DEC::point_const_iterator 00043 PB_DS_CLASS_C_DEC:: 00044 lower_bound(key_const_reference r_key) const 00045 { 00046 node_pointer p_pot = m_p_head; 00047 node_pointer p_nd = m_p_head->m_p_parent; 00048 00049 while (p_nd != 0) 00050 if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 00051 p_nd = p_nd->m_p_right; 00052 else 00053 { 00054 p_pot = p_nd; 00055 p_nd = p_nd->m_p_left; 00056 } 00057 return iterator(p_pot); 00058 } 00059 00060 PB_DS_CLASS_T_DEC 00061 inline typename PB_DS_CLASS_C_DEC::point_iterator 00062 PB_DS_CLASS_C_DEC:: 00063 lower_bound(key_const_reference r_key) 00064 { 00065 node_pointer p_pot = m_p_head; 00066 node_pointer p_nd = m_p_head->m_p_parent; 00067 00068 while (p_nd != 0) 00069 if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 00070 p_nd = p_nd->m_p_right; 00071 else 00072 { 00073 p_pot = p_nd; 00074 p_nd = p_nd->m_p_left; 00075 } 00076 return iterator(p_pot); 00077 } 00078 00079 PB_DS_CLASS_T_DEC 00080 inline typename PB_DS_CLASS_C_DEC::point_const_iterator 00081 PB_DS_CLASS_C_DEC:: 00082 upper_bound(key_const_reference r_key) const 00083 { 00084 node_pointer p_pot = m_p_head; 00085 node_pointer p_nd = m_p_head->m_p_parent; 00086 00087 while (p_nd != 0) 00088 if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 00089 { 00090 p_pot = p_nd; 00091 p_nd = p_nd->m_p_left; 00092 } 00093 else 00094 p_nd = p_nd->m_p_right; 00095 return const_iterator(p_pot); 00096 } 00097 00098 PB_DS_CLASS_T_DEC 00099 inline typename PB_DS_CLASS_C_DEC::point_iterator 00100 PB_DS_CLASS_C_DEC:: 00101 upper_bound(key_const_reference r_key) 00102 { 00103 node_pointer p_pot = m_p_head; 00104 node_pointer p_nd = m_p_head->m_p_parent; 00105 00106 while (p_nd != 0) 00107 if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 00108 { 00109 p_pot = p_nd; 00110 p_nd = p_nd->m_p_left; 00111 } 00112 else 00113 p_nd = p_nd->m_p_right; 00114 return point_iterator(p_pot); 00115 } 00116 00117 PB_DS_CLASS_T_DEC 00118 inline typename PB_DS_CLASS_C_DEC::point_iterator 00119 PB_DS_CLASS_C_DEC:: 00120 find(key_const_reference r_key) 00121 { 00122 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00123 node_pointer p_pot = m_p_head; 00124 node_pointer p_nd = m_p_head->m_p_parent; 00125 00126 while (p_nd != 0) 00127 if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 00128 { 00129 p_pot = p_nd; 00130 p_nd = p_nd->m_p_left; 00131 } 00132 else 00133 p_nd = p_nd->m_p_right; 00134 00135 node_pointer ret = p_pot; 00136 if (p_pot != m_p_head) 00137 { 00138 const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value)); 00139 if (__cmp) 00140 ret = m_p_head; 00141 } 00142 return point_iterator(ret); 00143 } 00144 00145 PB_DS_CLASS_T_DEC 00146 inline typename PB_DS_CLASS_C_DEC::point_const_iterator 00147 PB_DS_CLASS_C_DEC:: 00148 find(key_const_reference r_key) const 00149 { 00150 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00151 node_pointer p_pot = m_p_head; 00152 node_pointer p_nd = m_p_head->m_p_parent; 00153 00154 while (p_nd != 0) 00155 if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 00156 { 00157 p_pot = p_nd; 00158 p_nd = p_nd->m_p_left; 00159 } 00160 else 00161 p_nd = p_nd->m_p_right; 00162 00163 node_pointer ret = p_pot; 00164 if (p_pot != m_p_head) 00165 { 00166 const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value)); 00167 if (__cmp) 00168 ret = m_p_head; 00169 } 00170 return point_const_iterator(ret); 00171 }