Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/c++/11/ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp


$ cat -n /usr/include/c++/11/ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.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 trie_policy/prefix_search_node_update_imp.hpp
    38	 * Contains an implementation of prefix_search_node_update.
    39	 */
    40	
    41	#ifdef PB_DS_CLASS_C_DEC
    42	
    43	PB_DS_CLASS_T_DEC
    44	std::pair<
    45	  typename PB_DS_CLASS_C_DEC::const_iterator,
    46	  typename PB_DS_CLASS_C_DEC::const_iterator>
    47	PB_DS_CLASS_C_DEC::
    48	prefix_range(key_const_reference r_key) const
    49	{
    50	  const access_traits& r_traits = get_access_traits();
    51	  return (prefix_range(r_traits.begin(r_key), r_traits.end(r_key)));
    52	}
    53	
    54	PB_DS_CLASS_T_DEC
    55	std::pair<
    56	  typename PB_DS_CLASS_C_DEC::iterator,
    57	  typename PB_DS_CLASS_C_DEC::iterator>
    58	PB_DS_CLASS_C_DEC::
    59	prefix_range(key_const_reference r_key)
    60	{
    61	  return (prefix_range(get_access_traits().begin(r_key),
    62			       get_access_traits().end(r_key)));
    63	}
    64	
    65	PB_DS_CLASS_T_DEC
    66	std::pair<
    67	  typename PB_DS_CLASS_C_DEC::const_iterator,
    68	  typename PB_DS_CLASS_C_DEC::const_iterator>
    69	PB_DS_CLASS_C_DEC::
    70	prefix_range(typename access_traits::const_iterator b,
    71		     typename access_traits::const_iterator e) const
    72	{
    73	  const std::pair<iterator, iterator> non_const_ret =
    74	    const_cast<PB_DS_CLASS_C_DEC* >(this)->prefix_range(b, e);
    75	
    76	  return (std::make_pair(const_iterator(non_const_ret.first),
    77				 const_iterator(non_const_ret.second)));
    78	}
    79	
    80	PB_DS_CLASS_T_DEC
    81	std::pair<
    82	  typename PB_DS_CLASS_C_DEC::iterator,
    83	  typename PB_DS_CLASS_C_DEC::iterator>
    84	PB_DS_CLASS_C_DEC::
    85	prefix_range(typename access_traits::const_iterator b,
    86		     typename access_traits::const_iterator e)
    87	{
    88	  Node_Itr nd_it = node_begin();
    89	  Node_Itr end_nd_it = node_end();
    90	
    91	  const access_traits& r_traits = get_access_traits();
    92	  const size_type given_range_length = std::distance(b, e);
    93	
    94	  while (true)
    95	    {
    96	      if (nd_it == end_nd_it)
    97		return (std::make_pair(end(), end()));
    98	
    99	      const size_type common_range_length =
   100		base_type::common_prefix_len(nd_it, b, e, r_traits);
   101	
   102	      if (common_range_length >= given_range_length)
   103		{
   104		  iterator ret_b = this->leftmost_it(nd_it);
   105		  iterator ret_e = this->rightmost_it(nd_it);
   106		  return (std::make_pair(ret_b, ++ret_e));
   107		}
   108	      nd_it = next_child(nd_it, b, e, end_nd_it, r_traits);
   109	    }
   110	}
   111	
   112	PB_DS_CLASS_T_DEC
   113	typename PB_DS_CLASS_C_DEC::node_iterator
   114	PB_DS_CLASS_C_DEC::
   115	next_child(node_iterator nd_it, typename access_traits::const_iterator b,
   116		   typename access_traits::const_iterator e, node_iterator end_nd_it,
   117		   const access_traits& r_traits)
   118	{
   119	  const size_type num_children = nd_it.num_children();
   120	  node_iterator ret = end_nd_it;
   121	  size_type max_length = 0;
   122	  for (size_type i = 0; i < num_children; ++i)
   123	    {
   124	      node_iterator pot = nd_it.get_child(i);
   125	      const size_type common_range_length =
   126		base_type::common_prefix_len(pot, b, e, r_traits);
   127	
   128	      if (common_range_length > max_length)
   129		{
   130		  ret = pot;
   131		  max_length = common_range_length;
   132		}
   133	    }
   134	  return (ret);
   135	}
   136	
   137	PB_DS_CLASS_T_DEC
   138	inline void
   139	PB_DS_CLASS_C_DEC::
   140	operator()(node_iterator /*nd_it*/, node_const_iterator /*end_nd_it*/) const
   141	{ }
   142	#endif