150476Speter// -*- C++ -*- 220034Sache 320034Sache// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 420034Sache// 520034Sache// This file is part of the GNU ISO C++ Library. This library is free 620215Sache// software; you can redistribute it and/or modify it under the terms 7174990Sache// of the GNU General Public License as published by the Free Software 820034Sache// Foundation; either version 2, or (at your option) any later 920034Sache// version. 1020034Sache 1120034Sache// This library is distributed in the hope that it will be useful, but 1220034Sache// WITHOUT ANY WARRANTY; without even the implied warranty of 1320034Sache// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1420034Sache// General Public License for more details. 1520034Sache 1620034Sache// You should have received a copy of the GNU General Public License 1720034Sache// along with this library; see the file COPYING. If not, write to 1820034Sache// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1920034Sache// MA 02111-1307, USA. 2020034Sache 2120034Sache// As a special exception, you may use this file as part of a free 22174990Sache// software library without restriction. Specifically, if other files 2320034Sache// instantiate templates or use macros or inline functions from this 2420034Sache// file, or you compile this file and link it with other files to 2520034Sache// produce an executable, this file does not by itself cause the 2620034Sache// resulting executable to be covered by the GNU General Public 2720034Sache// License. This exception does not however invalidate any other 2820034Sache// reasons why the executable file might be covered by the GNU General 2920034Sache// Public License. 3020034Sache 3120034Sache// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 3220034Sache 3320034Sache// Permission to use, copy, modify, sell, and distribute this software 3420034Sache// is hereby granted without fee, provided that the above copyright 3520034Sache// notice appears in all copies, and that both that copyright notice 3620034Sache// and this permission notice appear in supporting documentation. None 37174990Sache// of the above authors, nor IBM Haifa Research Laboratories, make any 3874606Sache// representation about the suitability of this software for any 3920034Sache// purpose. It is provided "as is" without express or implied 4020034Sache// warranty. 4120034Sache 4220034Sache/** 4320034Sache * @file find_fn_imps.hpp 4420034Sache * Contains an implementation class for bin_search_tree_. 4520215Sache */ 4620034Sache 47174990SachePB_DS_CLASS_T_DEC 4820034Sacheinline typename PB_DS_CLASS_C_DEC::const_point_iterator 4920034SachePB_DS_CLASS_C_DEC:: 5020215Sachelower_bound(const_key_reference r_key) const 5120215Sache{ 5220215Sache node_pointer p_pot = m_p_head; 5320215Sache node_pointer p_nd = m_p_head->m_p_parent; 5420215Sache 5520034Sache while (p_nd != NULL) 5620034Sache if (Cmp_Fn::operator()( 5720034Sache PB_DS_V2F(p_nd->m_value), 5820034Sache r_key)) 5920034Sache p_nd = p_nd->m_p_right; 6020034Sache else 6120034Sache { 6220034Sache p_pot = p_nd; 6374570Sache 6420034Sache p_nd = p_nd->m_p_left; 6520034Sache } 6620034Sache 6754090Sache return (iterator(p_pot)); 6820034Sache} 6920034Sache 7020034SachePB_DS_CLASS_T_DEC 7174606Sacheinline typename PB_DS_CLASS_C_DEC::point_iterator 7220034SachePB_DS_CLASS_C_DEC:: 7320034Sachelower_bound(const_key_reference r_key) 7420034Sache{ 7573361Sache node_pointer p_pot = m_p_head; 7620034Sache node_pointer p_nd = m_p_head->m_p_parent; 7720034Sache 7820034Sache while (p_nd != NULL) 7954090Sache if (Cmp_Fn::operator()( 8053943Sache PB_DS_V2F(p_nd->m_value), 81174990Sache r_key)) 8253943Sache p_nd = p_nd->m_p_right; 8353943Sache else 8453943Sache { 8553943Sache p_pot = p_nd; 8653943Sache 8753943Sache p_nd = p_nd->m_p_left; 8853943Sache } 8953943Sache 9053943Sache return (iterator(p_pot)); 9153943Sache} 9253943Sache 9353943SachePB_DS_CLASS_T_DEC 9453943Sacheinline typename PB_DS_CLASS_C_DEC::const_point_iterator 9553943SachePB_DS_CLASS_C_DEC:: 9674413Sacheupper_bound(const_key_reference r_key) const 9753943Sache{ 9874413Sache node_pointer p_pot = m_p_head; 9953961Sache node_pointer p_nd = m_p_head->m_p_parent; 10073361Sache 10173361Sache while (p_nd != NULL) 10273361Sache if (Cmp_Fn::operator()(r_key, 10373361Sache PB_DS_V2F(p_nd->m_value))) 104 { 105 p_pot = p_nd, 106 107 p_nd = p_nd->m_p_left; 108 } 109 else 110 p_nd = p_nd->m_p_right; 111 112 return (const_iterator(p_pot)); 113} 114 115PB_DS_CLASS_T_DEC 116inline typename PB_DS_CLASS_C_DEC::point_iterator 117PB_DS_CLASS_C_DEC:: 118upper_bound(const_key_reference r_key) 119{ 120 node_pointer p_pot = m_p_head; 121 node_pointer p_nd = m_p_head->m_p_parent; 122 123 while (p_nd != NULL) 124 if (Cmp_Fn::operator()(r_key, 125 PB_DS_V2F(p_nd->m_value))) 126 { 127 p_pot = p_nd, 128 129 p_nd = p_nd->m_p_left; 130 } 131 else 132 p_nd = p_nd->m_p_right; 133 134 return (point_iterator(p_pot)); 135} 136 137PB_DS_CLASS_T_DEC 138inline typename PB_DS_CLASS_C_DEC::point_iterator 139PB_DS_CLASS_C_DEC:: 140find(const_key_reference r_key) 141{ 142 _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) 143 144 node_pointer p_pot = m_p_head; 145 node_pointer p_nd = m_p_head->m_p_parent; 146 147 while (p_nd != NULL) 148 if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 149 { 150 p_pot = p_nd; 151 152 p_nd = p_nd->m_p_left; 153 } 154 else 155 p_nd = p_nd->m_p_right; 156 157 return point_iterator((p_pot != m_p_head&& Cmp_Fn::operator()( 158 r_key, 159 PB_DS_V2F(p_pot->m_value)))? 160 m_p_head : p_pot); 161} 162 163PB_DS_CLASS_T_DEC 164inline typename PB_DS_CLASS_C_DEC::const_point_iterator 165PB_DS_CLASS_C_DEC:: 166find(const_key_reference r_key) const 167{ 168 _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) 169 170 node_pointer p_pot = m_p_head; 171 node_pointer p_nd = m_p_head->m_p_parent; 172 173 while (p_nd != NULL) 174 if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 175 { 176 p_pot = p_nd; 177 178 p_nd = p_nd->m_p_left; 179 } 180 else 181 p_nd = p_nd->m_p_right; 182 183 return const_point_iterator((p_pot != m_p_head&& Cmp_Fn::operator()( 184 r_key, 185 PB_DS_V2F(p_pot->m_value)))? 186 m_p_head : p_pot); 187} 188 189