find_fn_imps.hpp revision 169691
192108Sphk// -*- C++ -*- 292108Sphk 392108Sphk// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 492108Sphk// 592108Sphk// This file is part of the GNU ISO C++ Library. This library is free 692108Sphk// software; you can redistribute it and/or modify it under the terms 792108Sphk// of the GNU General Public License as published by the Free Software 892108Sphk// Foundation; either version 2, or (at your option) any later 992108Sphk// version. 1092108Sphk 1192108Sphk// This library is distributed in the hope that it will be useful, but 1292108Sphk// WITHOUT ANY WARRANTY; without even the implied warranty of 1392108Sphk// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1492108Sphk// General Public License for more details. 1592108Sphk 1692108Sphk// You should have received a copy of the GNU General Public License 1792108Sphk// along with this library; see the file COPYING. If not, write to 1892108Sphk// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1992108Sphk// MA 02111-1307, USA. 2092108Sphk 2192108Sphk// As a special exception, you may use this file as part of a free 2292108Sphk// software library without restriction. Specifically, if other files 2392108Sphk// instantiate templates or use macros or inline functions from this 2492108Sphk// file, or you compile this file and link it with other files to 2592108Sphk// produce an executable, this file does not by itself cause the 2692108Sphk// resulting executable to be covered by the GNU General Public 2792108Sphk// License. This exception does not however invalidate any other 2892108Sphk// reasons why the executable file might be covered by the GNU General 2992108Sphk// Public License. 3092108Sphk 3192108Sphk// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 3292108Sphk 3392108Sphk// Permission to use, copy, modify, sell, and distribute this software 3492108Sphk// is hereby granted without fee, provided that the above copyright 3592108Sphk// notice appears in all copies, and that both that copyright notice 36116196Sobrien// and this permission notice appear in supporting documentation. None 37116196Sobrien// of the above authors, nor IBM Haifa Research Laboratories, make any 38116196Sobrien// representation about the suitability of this software for any 39104519Sphk// purpose. It is provided "as is" without express or implied 40104519Sphk// warranty. 4192108Sphk 4292108Sphk/** 4392108Sphk * @file find_fn_imps.hpp 4492108Sphk * Contains an implementation class for bin_search_tree_. 4592108Sphk */ 46196823Spjd 47110119SphkPB_DS_CLASS_T_DEC 4892108Sphkinline typename PB_DS_CLASS_C_DEC::const_point_iterator 49223921SaePB_DS_CLASS_C_DEC:: 5092108Sphklower_bound(const_key_reference r_key) const 51111979Sphk{ 5292108Sphk node_pointer p_pot = m_p_head; 5392108Sphk node_pointer p_nd = m_p_head->m_p_parent; 5492108Sphk 5592108Sphk while (p_nd != NULL) 5692108Sphk if (Cmp_Fn::operator()( 57112952Sphk PB_DS_V2F(p_nd->m_value), 58112476Sphk r_key)) 5992108Sphk p_nd = p_nd->m_p_right; 60219970Smav else 61219970Smav { 62219970Smav p_pot = p_nd; 63248694Smav 64219970Smav p_nd = p_nd->m_p_left; 65219970Smav } 66219970Smav 67219970Smav return (iterator(p_pot)); 68219970Smav} 69219970Smav 70219970SmavPB_DS_CLASS_T_DEC 7192108Sphkinline typename PB_DS_CLASS_C_DEC::point_iterator 72133314SphkPB_DS_CLASS_C_DEC:: 73133314Sphklower_bound(const_key_reference r_key) 74133314Sphk{ 75237518Sken node_pointer p_pot = m_p_head; 7692108Sphk node_pointer p_nd = m_p_head->m_p_parent; 77141624Sphk 78249507Sivoras while (p_nd != NULL) 79133318Sphk if (Cmp_Fn::operator()( 80133314Sphk PB_DS_V2F(p_nd->m_value), 81133314Sphk r_key)) 82133314Sphk p_nd = p_nd->m_p_right; 83237518Sken else 84133314Sphk { 8592108Sphk p_pot = p_nd; 8692108Sphk 87219970Smav p_nd = p_nd->m_p_left; 88227309Sed } 89227309Sed 90219970Smav return (iterator(p_pot)); 91115473Sphk} 92115473Sphk 93110052SphkPB_DS_CLASS_T_DEC 94110052Sphkinline typename PB_DS_CLASS_C_DEC::const_point_iterator 95110052SphkPB_DS_CLASS_C_DEC:: 96226736Spjdupper_bound(const_key_reference r_key) const 97125975Sphk{ 98125975Sphk node_pointer p_pot = m_p_head; 99110052Sphk node_pointer p_nd = m_p_head->m_p_parent; 100110052Sphk 101110052Sphk while (p_nd != NULL) 102110052Sphk if (Cmp_Fn::operator()(r_key, 103110052Sphk PB_DS_V2F(p_nd->m_value))) 104226736Spjd { 105125975Sphk p_pot = p_nd, 106125975Sphk 107110052Sphk p_nd = p_nd->m_p_left; 108110052Sphk } 10992108Sphk else 11092108Sphk p_nd = p_nd->m_p_right; 11192108Sphk 11292108Sphk return (const_iterator(p_pot)); 113219970Smav} 11492108Sphk 11592108SphkPB_DS_CLASS_T_DEC 11692108Sphkinline typename PB_DS_CLASS_C_DEC::point_iterator 11792108SphkPB_DS_CLASS_C_DEC:: 11892108Sphkupper_bound(const_key_reference r_key) 119248694Smav{ 120219970Smav node_pointer p_pot = m_p_head; 121125539Spjd node_pointer p_nd = m_p_head->m_p_parent; 122125539Spjd 123125539Spjd while (p_nd != NULL) 124125539Spjd if (Cmp_Fn::operator()(r_key, 125125539Spjd PB_DS_V2F(p_nd->m_value))) 126125539Spjd { 127125975Sphk p_pot = p_nd, 128125539Spjd 12992108Sphk p_nd = p_nd->m_p_left; 13092108Sphk } 13192108Sphk else 132110119Sphk p_nd = p_nd->m_p_right; 13392108Sphk 134111668Sphk return (point_iterator(p_pot)); 135110119Sphk} 136111668Sphk 137166861Sn_hibmaPB_DS_CLASS_T_DEC 138110119Sphkinline typename PB_DS_CLASS_C_DEC::point_iterator 139110119SphkPB_DS_CLASS_C_DEC:: 140110119Sphkfind(const_key_reference r_key) 141251616Smav{ 142251616Smav _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) 143110119Sphk 144105551Sphk node_pointer p_pot = m_p_head; 145105551Sphk node_pointer p_nd = m_p_head->m_p_parent; 146110727Sphk 147110727Sphk while (p_nd != NULL) 148110727Sphk if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 149110727Sphk { 150110727Sphk p_pot = p_nd; 151249940Ssmh 152249940Ssmh p_nd = p_nd->m_p_left; 153249940Ssmh } 154249940Ssmh else 155249940Ssmh p_nd = p_nd->m_p_right; 156249940Ssmh 157249940Ssmh return point_iterator((p_pot != m_p_head&& Cmp_Fn::operator()( 158249940Ssmh r_key, 159249940Ssmh PB_DS_V2F(p_pot->m_value)))? 160249940Ssmh m_p_head : p_pot); 161249940Ssmh} 162249940Ssmh 16392108SphkPB_DS_CLASS_T_DEC 164111668Sphkinline typename PB_DS_CLASS_C_DEC::const_point_iterator 165110119SphkPB_DS_CLASS_C_DEC:: 166111668Sphkfind(const_key_reference r_key) const 167110119Sphk{ 168110119Sphk _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) 169110119Sphk 170110119Sphk node_pointer p_pot = m_p_head; 171110119Sphk node_pointer p_nd = m_p_head->m_p_parent; 172219970Smav 173219970Smav while (p_nd != NULL) 174219970Smav if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) 175110119Sphk { 17692108Sphk p_pot = p_nd; 17792108Sphk 17892108Sphk p_nd = p_nd->m_p_left; 17992108Sphk } 18092108Sphk else 18195038Sphk p_nd = p_nd->m_p_right; 182219950Smav 18395038Sphk return const_point_iterator((p_pot != m_p_head&& Cmp_Fn::operator()( 184104450Sphk r_key, 18595038Sphk PB_DS_V2F(p_pot->m_value)))? 18695038Sphk m_p_head : p_pot); 187104450Sphk} 188104450Sphk 189104450Sphk