Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2015 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. PB_DS_CLASS_T_DEC
  42. inline typename PB_DS_CLASS_C_DEC::point_const_iterator
  43. PB_DS_CLASS_C_DEC::
  44. lower_bound(key_const_reference r_key) const
  45. {
  46.   node_pointer p_pot = m_p_head;
  47.   node_pointer p_nd = m_p_head->m_p_parent;
  48.  
  49.   while (p_nd != 0)
  50.     if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
  51.       p_nd = p_nd->m_p_right;
  52.     else
  53.       {
  54.         p_pot = p_nd;
  55.         p_nd = p_nd->m_p_left;
  56.       }
  57.   return iterator(p_pot);
  58. }
  59.  
  60. PB_DS_CLASS_T_DEC
  61. inline typename PB_DS_CLASS_C_DEC::point_iterator
  62. PB_DS_CLASS_C_DEC::
  63. lower_bound(key_const_reference r_key)
  64. {
  65.   node_pointer p_pot = m_p_head;
  66.   node_pointer p_nd = m_p_head->m_p_parent;
  67.  
  68.   while (p_nd != 0)
  69.     if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
  70.       p_nd = p_nd->m_p_right;
  71.     else
  72.       {
  73.         p_pot = p_nd;
  74.         p_nd = p_nd->m_p_left;
  75.       }
  76.   return iterator(p_pot);
  77. }
  78.  
  79. PB_DS_CLASS_T_DEC
  80. inline typename PB_DS_CLASS_C_DEC::point_const_iterator
  81. PB_DS_CLASS_C_DEC::
  82. upper_bound(key_const_reference r_key) const
  83. {
  84.   node_pointer p_pot = m_p_head;
  85.   node_pointer p_nd = m_p_head->m_p_parent;
  86.  
  87.   while (p_nd != 0)
  88.     if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
  89.       {
  90.         p_pot = p_nd;
  91.         p_nd = p_nd->m_p_left;
  92.       }
  93.     else
  94.       p_nd = p_nd->m_p_right;
  95.   return const_iterator(p_pot);
  96. }
  97.  
  98. PB_DS_CLASS_T_DEC
  99. inline typename PB_DS_CLASS_C_DEC::point_iterator
  100. PB_DS_CLASS_C_DEC::
  101. upper_bound(key_const_reference r_key)
  102. {
  103.   node_pointer p_pot = m_p_head;
  104.   node_pointer p_nd = m_p_head->m_p_parent;
  105.  
  106.   while (p_nd != 0)
  107.     if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
  108.       {
  109.         p_pot = p_nd;
  110.         p_nd = p_nd->m_p_left;
  111.       }
  112.     else
  113.       p_nd = p_nd->m_p_right;
  114.   return point_iterator(p_pot);
  115. }
  116.  
  117. PB_DS_CLASS_T_DEC
  118. inline typename PB_DS_CLASS_C_DEC::point_iterator
  119. PB_DS_CLASS_C_DEC::
  120. find(key_const_reference r_key)
  121. {
  122.   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
  123.   node_pointer p_pot = m_p_head;
  124.   node_pointer p_nd = m_p_head->m_p_parent;
  125.  
  126.   while (p_nd != 0)
  127.     if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
  128.       {
  129.         p_pot = p_nd;
  130.         p_nd = p_nd->m_p_left;
  131.       }
  132.     else
  133.       p_nd = p_nd->m_p_right;
  134.  
  135.   node_pointer ret = p_pot;
  136.   if (p_pot != m_p_head)
  137.     {
  138.       const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value));
  139.       if (__cmp)
  140.         ret = m_p_head;
  141.     }
  142.   return point_iterator(ret);
  143. }
  144.  
  145. PB_DS_CLASS_T_DEC
  146. inline typename PB_DS_CLASS_C_DEC::point_const_iterator
  147. PB_DS_CLASS_C_DEC::
  148. find(key_const_reference r_key) const
  149. {
  150.   PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
  151.   node_pointer p_pot = m_p_head;
  152.   node_pointer p_nd = m_p_head->m_p_parent;
  153.  
  154.   while (p_nd != 0)
  155.     if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
  156.       {
  157.         p_pot = p_nd;
  158.         p_nd = p_nd->m_p_left;
  159.       }
  160.     else
  161.       p_nd = p_nd->m_p_right;
  162.  
  163.   node_pointer ret = p_pot;
  164.   if (p_pot != m_p_head)
  165.     {
  166.       const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value));
  167.       if (__cmp)
  168.         ret = m_p_head;
  169.     }
  170.   return point_const_iterator(ret);
  171. }
  172.