1275072Semaste// -*- C++ -*- 2275072Semaste 3275072Semaste// Copyright (C) 2005-2015 Free Software Foundation, Inc. 4275072Semaste// 5275072Semaste// This file is part of the GNU ISO C++ Library. This library is free 6275072Semaste// software; you can redistribute it and/or modify it under the terms 7275072Semaste// of the GNU General Public License as published by the Free Software 8275072Semaste// Foundation; either version 3, or (at your option) any later 9275072Semaste// version. 10275072Semaste 11275072Semaste// This library is distributed in the hope that it will be useful, but 12275072Semaste// WITHOUT ANY WARRANTY; without even the implied warranty of 13275072Semaste// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14275072Semaste// General Public License for more details. 15275072Semaste 16275072Semaste// Under Section 7 of GPL version 3, you are granted additional 17288943Sdim// permissions described in the GCC Runtime Library Exception, version 18275072Semaste// 3.1, as published by the Free Software Foundation. 19296417Sdim 20296417Sdim// You should have received a copy of the GNU General Public License and 21275072Semaste// a copy of the GCC Runtime Library Exception along with this program; 22296417Sdim// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23296417Sdim// <http://www.gnu.org/licenses/>. 24280031Sdim 25275072Semaste// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26275072Semaste 27275072Semaste// Permission to use, copy, modify, sell, and distribute this software 28275072Semaste// is hereby granted without fee, provided that the above copyright 29275072Semaste// notice appears in all copies, and that both that copyright notice 30275072Semaste// and this permission notice appear in supporting documentation. None 31275072Semaste// of the above authors, nor IBM Haifa Research Laboratories, make any 32275072Semaste// representation about the suitability of this software for any 33296417Sdim// purpose. It is provided "as is" without express or implied 34296417Sdim// warranty. 35296417Sdim 36296417Sdim/** 37296417Sdim * @file bin_search_tree_/find_fn_imps.hpp 38296417Sdim * Contains an implementation class for bin_search_tree_. 39296417Sdim */ 40296417Sdim 41296417SdimPB_DS_CLASS_T_DEC 42296417Sdiminline typename PB_DS_CLASS_C_DEC::point_const_iterator 43296417SdimPB_DS_CLASS_C_DEC:: 44296417Sdimlower_bound(key_const_reference r_key) const 45296417Sdim{ 46296417Sdim node_pointer p_pot = m_p_head; 47296417Sdim node_pointer p_nd = m_p_head->m_p_parent; 48296417Sdim 49296417Sdim while (p_nd != 0) 50275072Semaste if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 51275072Semaste p_nd = p_nd->m_p_right; 52275072Semaste else 53275072Semaste { 54275072Semaste p_pot = p_nd; 55275072Semaste p_nd = p_nd->m_p_left; 56275072Semaste } 57275072Semaste return iterator(p_pot); 58275072Semaste} 59275072Semaste 60275072SemastePB_DS_CLASS_T_DEC 61275072Semasteinline typename PB_DS_CLASS_C_DEC::point_iterator 62275072SemastePB_DS_CLASS_C_DEC:: 63280031Sdimlower_bound(key_const_reference r_key) 64280031Sdim{ 65288943Sdim node_pointer p_pot = m_p_head; 66288943Sdim node_pointer p_nd = m_p_head->m_p_parent; 67288943Sdim 68288943Sdim while (p_nd != 0) 69288943Sdim if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 70288943Sdim p_nd = p_nd->m_p_right; 71288943Sdim else 72288943Sdim { 73288943Sdim p_pot = p_nd; 74288943Sdim p_nd = p_nd->m_p_left; 75288943Sdim } 76275072Semaste return iterator(p_pot); 77275072Semaste} 78275072Semaste 79275072SemastePB_DS_CLASS_T_DEC 80275072Semasteinline typename PB_DS_CLASS_C_DEC::point_const_iterator 81275072SemastePB_DS_CLASS_C_DEC:: 82275072Semasteupper_bound(key_const_reference r_key) const 83275072Semaste{ 84275072Semaste node_pointer p_pot = m_p_head; 85275072Semaste node_pointer p_nd = m_p_head->m_p_parent; 86275072Semaste 87275072Semaste while (p_nd != 0) 88275072Semaste if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 89296417Sdim { 90275072Semaste p_pot = p_nd; 91296417Sdim p_nd = p_nd->m_p_left; 92275072Semaste } 93296417Sdim else 94296417Sdim p_nd = p_nd->m_p_right; 95275072Semaste return const_iterator(p_pot); 96296417Sdim} 97296417Sdim 98296417SdimPB_DS_CLASS_T_DEC 99296417Sdiminline typename PB_DS_CLASS_C_DEC::point_iterator 100296417SdimPB_DS_CLASS_C_DEC:: 101296417Sdimupper_bound(key_const_reference r_key) 102296417Sdim{ 103296417Sdim node_pointer p_pot = m_p_head; 104296417Sdim node_pointer p_nd = m_p_head->m_p_parent; 105296417Sdim 106296417Sdim while (p_nd != 0) 107296417Sdim if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 108296417Sdim { 109296417Sdim p_pot = p_nd; 110296417Sdim p_nd = p_nd->m_p_left; 111296417Sdim } 112296417Sdim else 113296417Sdim p_nd = p_nd->m_p_right; 114296417Sdim return point_iterator(p_pot); 115296417Sdim} 116275072Semaste 117275072SemastePB_DS_CLASS_T_DEC 118296417Sdiminline typename PB_DS_CLASS_C_DEC::point_iterator 119296417SdimPB_DS_CLASS_C_DEC:: 120275072Semastefind(key_const_reference r_key) 121296417Sdim{ 122296417Sdim PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 123275072Semaste node_pointer p_pot = m_p_head; 124296417Sdim node_pointer p_nd = m_p_head->m_p_parent; 125296417Sdim 126296417Sdim while (p_nd != 0) 127296417Sdim if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 128296417Sdim { 129275072Semaste p_pot = p_nd; 130296417Sdim p_nd = p_nd->m_p_left; 131296417Sdim } 132296417Sdim else 133296417Sdim p_nd = p_nd->m_p_right; 134275072Semaste 135296417Sdim node_pointer ret = p_pot; 136296417Sdim if (p_pot != m_p_head) 137296417Sdim { 138275072Semaste const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value)); 139275072Semaste if (__cmp) 140275072Semaste ret = m_p_head; 141275072Semaste } 142296417Sdim return point_iterator(ret); 143296417Sdim} 144296417Sdim 145296417SdimPB_DS_CLASS_T_DEC 146296417Sdiminline typename PB_DS_CLASS_C_DEC::point_const_iterator 147296417SdimPB_DS_CLASS_C_DEC:: 148275072Semastefind(key_const_reference r_key) const 149275072Semaste{ 150275072Semaste PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 151296417Sdim node_pointer p_pot = m_p_head; 152275072Semaste node_pointer p_nd = m_p_head->m_p_parent; 153296417Sdim 154275072Semaste while (p_nd != 0) 155275072Semaste if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 156275072Semaste { 157275072Semaste p_pot = p_nd; 158275072Semaste p_nd = p_nd->m_p_left; 159275072Semaste } 160296417Sdim else 161296417Sdim p_nd = p_nd->m_p_right; 162296417Sdim 163296417Sdim node_pointer ret = p_pot; 164296417Sdim if (p_pot != m_p_head) 165296417Sdim { 166275072Semaste const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value)); 167275072Semaste if (__cmp) 168275072Semaste ret = m_p_head; 169275072Semaste } 170275072Semaste return point_const_iterator(ret); 171275072Semaste} 172288943Sdim