Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/c++/11/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp


$ cat -n /usr/include/c++/11/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp

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