find_fn_imps.hpp revision 1.1.1.11
1// -*- C++ -*- 2 3// Copyright (C) 2005-2022 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 3, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27// Permission to use, copy, modify, sell, and distribute this software 28// is hereby granted without fee, provided that the above copyright 29// notice appears in all copies, and that both that copyright notice 30// and this permission notice appear in supporting documentation. None 31// of the above authors, nor IBM Haifa Research Laboratories, make any 32// representation about the suitability of this software for any 33// purpose. It is provided "as is" without express or implied 34// warranty. 35 36/** 37 * @file bin_search_tree_/find_fn_imps.hpp 38 * Contains an implementation class for bin_search_tree_. 39 */ 40 41#ifdef PB_DS_CLASS_C_DEC 42 43PB_DS_CLASS_T_DEC 44inline typename PB_DS_CLASS_C_DEC::point_const_iterator 45PB_DS_CLASS_C_DEC:: 46lower_bound(key_const_reference r_key) const 47{ 48 node_pointer p_pot = m_p_head; 49 node_pointer p_nd = m_p_head->m_p_parent; 50 51 while (p_nd != 0) 52 if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 53 p_nd = p_nd->m_p_right; 54 else 55 { 56 p_pot = p_nd; 57 p_nd = p_nd->m_p_left; 58 } 59 return iterator(p_pot); 60} 61 62PB_DS_CLASS_T_DEC 63inline typename PB_DS_CLASS_C_DEC::point_iterator 64PB_DS_CLASS_C_DEC:: 65lower_bound(key_const_reference r_key) 66{ 67 node_pointer p_pot = m_p_head; 68 node_pointer p_nd = m_p_head->m_p_parent; 69 70 while (p_nd != 0) 71 if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 72 p_nd = p_nd->m_p_right; 73 else 74 { 75 p_pot = p_nd; 76 p_nd = p_nd->m_p_left; 77 } 78 return iterator(p_pot); 79} 80 81PB_DS_CLASS_T_DEC 82inline typename PB_DS_CLASS_C_DEC::point_const_iterator 83PB_DS_CLASS_C_DEC:: 84upper_bound(key_const_reference r_key) const 85{ 86 node_pointer p_pot = m_p_head; 87 node_pointer p_nd = m_p_head->m_p_parent; 88 89 while (p_nd != 0) 90 if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 91 { 92 p_pot = p_nd; 93 p_nd = p_nd->m_p_left; 94 } 95 else 96 p_nd = p_nd->m_p_right; 97 return const_iterator(p_pot); 98} 99 100PB_DS_CLASS_T_DEC 101inline typename PB_DS_CLASS_C_DEC::point_iterator 102PB_DS_CLASS_C_DEC:: 103upper_bound(key_const_reference r_key) 104{ 105 node_pointer p_pot = m_p_head; 106 node_pointer p_nd = m_p_head->m_p_parent; 107 108 while (p_nd != 0) 109 if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 110 { 111 p_pot = p_nd; 112 p_nd = p_nd->m_p_left; 113 } 114 else 115 p_nd = p_nd->m_p_right; 116 return point_iterator(p_pot); 117} 118 119PB_DS_CLASS_T_DEC 120inline typename PB_DS_CLASS_C_DEC::point_iterator 121PB_DS_CLASS_C_DEC:: 122find(key_const_reference r_key) 123{ 124 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 125 node_pointer p_pot = m_p_head; 126 node_pointer p_nd = m_p_head->m_p_parent; 127 128 while (p_nd != 0) 129 if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 130 { 131 p_pot = p_nd; 132 p_nd = p_nd->m_p_left; 133 } 134 else 135 p_nd = p_nd->m_p_right; 136 137 node_pointer ret = p_pot; 138 if (p_pot != m_p_head) 139 { 140 const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value)); 141 if (__cmp) 142 ret = m_p_head; 143 } 144 return point_iterator(ret); 145} 146 147PB_DS_CLASS_T_DEC 148inline typename PB_DS_CLASS_C_DEC::point_const_iterator 149PB_DS_CLASS_C_DEC:: 150find(key_const_reference r_key) const 151{ 152 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 153 node_pointer p_pot = m_p_head; 154 node_pointer p_nd = m_p_head->m_p_parent; 155 156 while (p_nd != 0) 157 if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 158 { 159 p_pot = p_nd; 160 p_nd = p_nd->m_p_left; 161 } 162 else 163 p_nd = p_nd->m_p_right; 164 165 node_pointer ret = p_pot; 166 if (p_pot != m_p_head) 167 { 168 const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value)); 169 if (__cmp) 170 ret = m_p_head; 171 } 172 return point_const_iterator(ret); 173} 174#endif 175