libstdc++
bin_search_tree_/find_fn_imps.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file bin_search_tree_/find_fn_imps.hpp
00038  * Contains an implementation class for bin_search_tree_.
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 inline typename PB_DS_CLASS_C_DEC::point_const_iterator
00043 PB_DS_CLASS_C_DEC::
00044 lower_bound(key_const_reference r_key) const
00045 {
00046   node_pointer p_pot = m_p_head;
00047   node_pointer p_nd = m_p_head->m_p_parent;
00048 
00049   while (p_nd != 0)
00050     if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
00051       p_nd = p_nd->m_p_right;
00052     else
00053       {
00054     p_pot = p_nd;
00055     p_nd = p_nd->m_p_left;
00056       }
00057   return iterator(p_pot);
00058 }
00059 
00060 PB_DS_CLASS_T_DEC
00061 inline typename PB_DS_CLASS_C_DEC::point_iterator
00062 PB_DS_CLASS_C_DEC::
00063 lower_bound(key_const_reference r_key)
00064 {
00065   node_pointer p_pot = m_p_head;
00066   node_pointer p_nd = m_p_head->m_p_parent;
00067 
00068   while (p_nd != 0)
00069     if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
00070       p_nd = p_nd->m_p_right;
00071     else
00072       {
00073     p_pot = p_nd;
00074     p_nd = p_nd->m_p_left;
00075       }
00076   return iterator(p_pot);
00077 }
00078 
00079 PB_DS_CLASS_T_DEC
00080 inline typename PB_DS_CLASS_C_DEC::point_const_iterator
00081 PB_DS_CLASS_C_DEC::
00082 upper_bound(key_const_reference r_key) const
00083 {
00084   node_pointer p_pot = m_p_head;
00085   node_pointer p_nd = m_p_head->m_p_parent;
00086 
00087   while (p_nd != 0)
00088     if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
00089       {
00090     p_pot = p_nd;
00091     p_nd = p_nd->m_p_left;
00092       }
00093     else
00094       p_nd = p_nd->m_p_right;
00095   return const_iterator(p_pot);
00096 }
00097 
00098 PB_DS_CLASS_T_DEC
00099 inline typename PB_DS_CLASS_C_DEC::point_iterator
00100 PB_DS_CLASS_C_DEC::
00101 upper_bound(key_const_reference r_key)
00102 {
00103   node_pointer p_pot = m_p_head;
00104   node_pointer p_nd = m_p_head->m_p_parent;
00105 
00106   while (p_nd != 0)
00107     if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
00108       {
00109     p_pot = p_nd;
00110     p_nd = p_nd->m_p_left;
00111       }
00112     else
00113       p_nd = p_nd->m_p_right;
00114   return point_iterator(p_pot);
00115 }
00116 
00117 PB_DS_CLASS_T_DEC
00118 inline typename PB_DS_CLASS_C_DEC::point_iterator
00119 PB_DS_CLASS_C_DEC::
00120 find(key_const_reference r_key)
00121 {
00122   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
00123   node_pointer p_pot = m_p_head;
00124   node_pointer p_nd = m_p_head->m_p_parent;
00125 
00126   while (p_nd != 0)
00127     if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
00128       {
00129     p_pot = p_nd;
00130     p_nd = p_nd->m_p_left;
00131       }
00132     else
00133       p_nd = p_nd->m_p_right;
00134 
00135   node_pointer ret = p_pot;
00136   if (p_pot != m_p_head)
00137     {
00138       const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value));
00139       if (__cmp)
00140     ret = m_p_head;
00141     }
00142   return point_iterator(ret);
00143 }
00144 
00145 PB_DS_CLASS_T_DEC
00146 inline typename PB_DS_CLASS_C_DEC::point_const_iterator
00147 PB_DS_CLASS_C_DEC::
00148 find(key_const_reference r_key) const
00149 {
00150   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
00151   node_pointer p_pot = m_p_head;
00152   node_pointer p_nd = m_p_head->m_p_parent;
00153 
00154   while (p_nd != 0)
00155     if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
00156       {
00157     p_pot = p_nd;
00158     p_nd = p_nd->m_p_left;
00159       }
00160     else
00161       p_nd = p_nd->m_p_right;
00162 
00163   node_pointer ret = p_pot;
00164   if (p_pot != m_p_head)
00165     {
00166       const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value));
00167       if (__cmp)
00168     ret = m_p_head;
00169     }
00170   return point_const_iterator(ret);
00171 }