find_fn_imps.hpp revision 1.1.1.9
1193323Sed// -*- C++ -*- 2193323Sed 3193323Sed// Copyright (C) 2005-2019 Free Software Foundation, Inc. 4193323Sed// 5193323Sed// This file is part of the GNU ISO C++ Library. This library is free 6193323Sed// software; you can redistribute it and/or modify it under the terms 7193323Sed// of the GNU General Public License as published by the Free Software 8193323Sed// Foundation; either version 3, or (at your option) any later 9193323Sed// version. 10193323Sed 11193323Sed// This library is distributed in the hope that it will be useful, but 12193323Sed// WITHOUT ANY WARRANTY; without even the implied warranty of 13204961Srdivacky// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14198090Srdivacky// General Public License for more details. 15193323Sed 16206274Srdivacky// Under Section 7 of GPL version 3, you are granted additional 17263508Sdim// permissions described in the GCC Runtime Library Exception, version 18234353Sdim// 3.1, as published by the Free Software Foundation. 19221345Sdim 20249423Sdim// You should have received a copy of the GNU General Public License and 21249423Sdim// a copy of the GCC Runtime Library Exception along with this program; 22249423Sdim// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23249423Sdim// <http://www.gnu.org/licenses/>. 24198090Srdivacky 25193323Sed// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26249423Sdim 27249423Sdim// Permission to use, copy, modify, sell, and distribute this software 28249423Sdim// is hereby granted without fee, provided that the above copyright 29249423Sdim// notice appears in all copies, and that both that copyright notice 30249423Sdim// and this permission notice appear in supporting documentation. None 31249423Sdim// of the above authors, nor IBM Haifa Research Laboratories, make any 32204961Srdivacky// representation about the suitability of this software for any 33198090Srdivacky// purpose. It is provided "as is" without express or implied 34198090Srdivacky// warranty. 35204961Srdivacky 36207618Srdivacky/** 37198090Srdivacky * @file bin_search_tree_/find_fn_imps.hpp 38263508Sdim * Contains an implementation class for bin_search_tree_. 39198090Srdivacky */ 40202878Srdivacky 41263508SdimPB_DS_CLASS_T_DEC 42249423Sdiminline typename PB_DS_CLASS_C_DEC::point_const_iterator 43193323SedPB_DS_CLASS_C_DEC:: 44249423Sdimlower_bound(key_const_reference r_key) const 45249423Sdim{ 46249423Sdim node_pointer p_pot = m_p_head; 47249423Sdim node_pointer p_nd = m_p_head->m_p_parent; 48249423Sdim 49249423Sdim while (p_nd != 0) 50193323Sed if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 51193323Sed p_nd = p_nd->m_p_right; 52263508Sdim else 53263508Sdim { 54263508Sdim p_pot = p_nd; 55207618Srdivacky p_nd = p_nd->m_p_left; 56263508Sdim } 57263508Sdim return iterator(p_pot); 58263508Sdim} 59263508Sdim 60208599SrdivackyPB_DS_CLASS_T_DEC 61263508Sdiminline typename PB_DS_CLASS_C_DEC::point_iterator 62263508SdimPB_DS_CLASS_C_DEC:: 63263508Sdimlower_bound(key_const_reference r_key) 64263508Sdim{ 65249423Sdim node_pointer p_pot = m_p_head; 66263508Sdim node_pointer p_nd = m_p_head->m_p_parent; 67263508Sdim 68263508Sdim while (p_nd != 0) 69263508Sdim if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 70263508Sdim p_nd = p_nd->m_p_right; 71263508Sdim else 72263508Sdim { 73263508Sdim p_pot = p_nd; 74263508Sdim p_nd = p_nd->m_p_left; 75263508Sdim } 76243830Sdim return iterator(p_pot); 77263508Sdim} 78263508Sdim 79263508SdimPB_DS_CLASS_T_DEC 80263508Sdiminline typename PB_DS_CLASS_C_DEC::point_const_iterator 81263508SdimPB_DS_CLASS_C_DEC:: 82243830Sdimupper_bound(key_const_reference r_key) const 83243830Sdim{ 84263508Sdim node_pointer p_pot = m_p_head; 85263508Sdim node_pointer p_nd = m_p_head->m_p_parent; 86263508Sdim 87263508Sdim while (p_nd != 0) 88263508Sdim if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 89263508Sdim { 90263508Sdim p_pot = p_nd; 91234353Sdim p_nd = p_nd->m_p_left; 92263508Sdim } 93263508Sdim else 94263508Sdim p_nd = p_nd->m_p_right; 95263508Sdim return const_iterator(p_pot); 96263508Sdim} 97263508Sdim 98263508SdimPB_DS_CLASS_T_DEC 99243830Sdiminline typename PB_DS_CLASS_C_DEC::point_iterator 100263508SdimPB_DS_CLASS_C_DEC:: 101263508Sdimupper_bound(key_const_reference r_key) 102263508Sdim{ 103263508Sdim node_pointer p_pot = m_p_head; 104263508Sdim node_pointer p_nd = m_p_head->m_p_parent; 105263508Sdim 106263508Sdim while (p_nd != 0) 107249423Sdim if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 108263508Sdim { 109263508Sdim p_pot = p_nd; 110263508Sdim p_nd = p_nd->m_p_left; 111263508Sdim } 112251662Sdim else 113263508Sdim p_nd = p_nd->m_p_right; 114263508Sdim return point_iterator(p_pot); 115207618Srdivacky} 116193323Sed 117193323SedPB_DS_CLASS_T_DEC 118249423Sdiminline typename PB_DS_CLASS_C_DEC::point_iterator 119249423SdimPB_DS_CLASS_C_DEC:: 120193323Sedfind(key_const_reference r_key) 121193323Sed{ 122193323Sed PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 123193323Sed node_pointer p_pot = m_p_head; 124263508Sdim node_pointer p_nd = m_p_head->m_p_parent; 125263508Sdim 126263508Sdim while (p_nd != 0) 127263508Sdim if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 128263508Sdim { 129263508Sdim p_pot = p_nd; 130263508Sdim p_nd = p_nd->m_p_left; 131226633Sdim } 132221345Sdim else 133221345Sdim p_nd = p_nd->m_p_right; 134221345Sdim 135221345Sdim node_pointer ret = p_pot; 136221345Sdim if (p_pot != m_p_head) 137221345Sdim { 138221345Sdim const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value)); 139221345Sdim if (__cmp) 140221345Sdim ret = m_p_head; 141221345Sdim } 142249423Sdim return point_iterator(ret); 143221345Sdim} 144221345Sdim 145249423SdimPB_DS_CLASS_T_DEC 146221345Sdiminline typename PB_DS_CLASS_C_DEC::point_const_iterator 147221345SdimPB_DS_CLASS_C_DEC:: 148221345Sdimfind(key_const_reference r_key) const 149221345Sdim{ 150221345Sdim PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 151249423Sdim node_pointer p_pot = m_p_head; 152221345Sdim node_pointer p_nd = m_p_head->m_p_parent; 153221345Sdim 154249423Sdim while (p_nd != 0) 155221345Sdim if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 156221345Sdim { 157221345Sdim p_pot = p_nd; 158221345Sdim p_nd = p_nd->m_p_left; 159221345Sdim } 160221345Sdim else 161263508Sdim p_nd = p_nd->m_p_right; 162249423Sdim 163263508Sdim node_pointer ret = p_pot; 164263508Sdim if (p_pot != m_p_head) 165249423Sdim { 166263508Sdim const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value)); 167221345Sdim if (__cmp) 168263508Sdim ret = m_p_head; 169221345Sdim } 170263508Sdim return point_const_iterator(ret); 171221345Sdim} 172212904Sdim