The C and C++ Include Header Files

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


$ cat -n /usr/include/c++/11/ext/pb_ds/trie_policy.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.hpp
    38	 * Contains trie-related policies.
    39	 */
    40	
    41	#ifndef PB_DS_TRIE_POLICY_HPP
    42	#define PB_DS_TRIE_POLICY_HPP
    43	
    44	#include <bits/c++config.h>
    45	#include <string>
    46	#include <ext/pb_ds/detail/type_utils.hpp>
    47	#include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>
    48	
    49	namespace __gnu_pbds
    50	{
    51	#define PB_DS_CLASS_T_DEC \
    52	  template<typename String, typename String::value_type Min_E_Val, \
    53		   typename String::value_type Max_E_Val, bool Reverse, \
    54		   typename _Alloc>
    55	
    56	#define PB_DS_CLASS_C_DEC \
    57	  trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc>
    58	
    59	  /**
    60	   *  Element access traits for string types.
    61	   *
    62	   *  @tparam String 	    	String type.
    63	   *  @tparam Min_E_Val        	Minimal element value.
    64	   *  @tparam Max_E_Val	    	Maximum element value.
    65	   *  @tparam Reverse	        Reverse iteration should be used.
    66	   *                            Default: false.
    67	   *  @tparam _Alloc 	    	Allocator type.
    68	   */
    69	  template<typename String = std::string,
    70		   typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min,
    71		   typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max,
    72		   bool Reverse = false,
    73		   typename _Alloc = std::allocator<char> >
    74	  struct trie_string_access_traits
    75	  {
    76	  public:
    77	    typedef typename _Alloc::size_type			  size_type;
    78	    typedef String 					  key_type;
    79	    typedef typename detail::rebind_traits<_Alloc, key_type>::const_reference
    80	      key_const_reference;
    81	
    82	    enum
    83	      {
    84		reverse = Reverse
    85	      };
    86	
    87	    /// Element const iterator type.
    88	    typedef typename detail::__conditional_type<Reverse, \
    89			       typename String::const_reverse_iterator, \
    90			       typename String::const_iterator>::__type const_iterator;
    91	
    92	    /// Element type.
    93	    typedef typename std::iterator_traits<const_iterator>::value_type e_type;
    94	
    95	    enum
    96	      {
    97		min_e_val = Min_E_Val,
    98		max_e_val = Max_E_Val,
    99		max_size = max_e_val - min_e_val + 1
   100	      };
   101	    PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
   102	
   103	    /// Returns a const_iterator to the first element of
   104	    /// key_const_reference agumnet.
   105	    inline static const_iterator
   106	    begin(key_const_reference);
   107	
   108	    /// Returns a const_iterator to the after-last element of
   109	    /// key_const_reference argument.
   110	    inline static const_iterator
   111	    end(key_const_reference);
   112	
   113	    /// Maps an element to a position.
   114	    inline static size_type
   115	    e_pos(e_type e);
   116	
   117	  private:
   118	    inline static const_iterator
   119	    begin_imp(key_const_reference, detail::false_type);
   120	
   121	    inline static const_iterator
   122	    begin_imp(key_const_reference, detail::true_type);
   123	
   124	    inline static const_iterator
   125	    end_imp(key_const_reference, detail::false_type);
   126	
   127	    inline static const_iterator
   128	    end_imp(key_const_reference, detail::true_type);
   129	
   130	    static detail::integral_constant<int, Reverse> s_rev_ind;
   131	  };
   132	
   133	#include <ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp>
   134	
   135	#undef PB_DS_CLASS_T_DEC
   136	#undef PB_DS_CLASS_C_DEC
   137	
   138	#define PB_DS_CLASS_T_DEC \
   139	  template<typename Node_CItr,typename Node_Itr, \
   140		   typename _ATraits, typename _Alloc>
   141	
   142	#define PB_DS_CLASS_C_DEC \
   143	  trie_prefix_search_node_update<Node_CItr, Node_Itr, \
   144					 _ATraits,_Alloc>
   145	
   146	#define PB_DS_TRIE_POLICY_BASE \
   147	  detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc>
   148	
   149	  /// A node updator that allows tries to be searched for the range of
   150	  /// values that match a certain prefix.
   151	  template<typename Node_CItr,
   152		   typename Node_Itr,
   153		   typename _ATraits,
   154		   typename _Alloc>
   155	  class trie_prefix_search_node_update : private PB_DS_TRIE_POLICY_BASE
   156	  {
   157	  private:
   158	    typedef PB_DS_TRIE_POLICY_BASE 		       	base_type;
   159	
   160	  public:
   161	    typedef typename base_type::key_type 		key_type;
   162	    typedef typename base_type::key_const_reference 	key_const_reference;
   163	
   164	    /// Element access traits.
   165	    typedef _ATraits 				access_traits;
   166	
   167	    /// Const element iterator.
   168	    typedef typename access_traits::const_iterator 	a_const_iterator;
   169	
   170	    /// _Alloc type.
   171	    typedef _Alloc 	       				allocator_type;
   172	
   173	    /// Size type.
   174	    typedef typename allocator_type::size_type 		size_type;
   175	    typedef null_type 					metadata_type;
   176	    typedef Node_Itr 					node_iterator;
   177	    typedef Node_CItr 					node_const_iterator;
   178	    typedef typename node_iterator::value_type 		iterator;
   179	    typedef typename node_const_iterator::value_type 	const_iterator;
   180	
   181	    /// Finds the const iterator range corresponding to all values
   182	    /// whose prefixes match r_key.
   183	    std::pair<const_iterator, const_iterator>
   184	    prefix_range(key_const_reference) const;
   185	
   186	    /// Finds the iterator range corresponding to all values whose
   187	    /// prefixes match r_key.
   188	    std::pair<iterator, iterator>
   189	    prefix_range(key_const_reference);
   190	
   191	    /// Finds the const iterator range corresponding to all values
   192	    /// whose prefixes match [b, e).
   193	    std::pair<const_iterator, const_iterator>
   194	    prefix_range(a_const_iterator, a_const_iterator) const;
   195	
   196	    /// Finds the iterator range corresponding to all values whose
   197	    /// prefixes match [b, e).
   198	    std::pair<iterator, iterator>
   199	    prefix_range(a_const_iterator, a_const_iterator);
   200	
   201	  protected:
   202	    /// Called to update a node's metadata.
   203	    inline void
   204	    operator()(node_iterator node_it, node_const_iterator end_nd_it) const;
   205	
   206	  private:
   207	    node_iterator
   208	    next_child(node_iterator, a_const_iterator, a_const_iterator,
   209		       node_iterator, const access_traits&);
   210	
   211	    /// Returns the const iterator associated with the just-after last element.
   212	    virtual const_iterator
   213	    end() const = 0;
   214	
   215	    /// Returns the iterator associated with the just-after last element.
   216	    virtual iterator
   217	    end() = 0;
   218	
   219	    /// Returns the node_const_iterator associated with the trie's root node.
   220	    virtual node_const_iterator
   221	    node_begin() const = 0;
   222	
   223	    /// Returns the node_iterator associated with the trie's root node.
   224	    virtual node_iterator
   225	    node_begin() = 0;
   226	
   227	    /// Returns the node_const_iterator associated with a just-after leaf node.
   228	    virtual node_const_iterator
   229	    node_end() const = 0;
   230	
   231	    /// Returns the node_iterator associated with a just-after leaf node.
   232	    virtual node_iterator
   233	    node_end() = 0;
   234	
   235	    /// Access to the cmp_fn object.
   236	    virtual const access_traits&
   237	    get_access_traits() const = 0;
   238	  };
   239	
   240	#include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp>
   241	
   242	#undef PB_DS_CLASS_C_DEC
   243	
   244	#define PB_DS_CLASS_C_DEC \
   245	  trie_order_statistics_node_update<Node_CItr, Node_Itr, \
   246					    _ATraits, _Alloc>
   247	
   248	  /// Functor updating ranks of entrees.
   249	  template<typename Node_CItr,
   250		   typename Node_Itr,
   251		   typename _ATraits,
   252		   typename _Alloc>
   253	  class trie_order_statistics_node_update : private PB_DS_TRIE_POLICY_BASE
   254	  {
   255	  private:
   256	    typedef PB_DS_TRIE_POLICY_BASE 		       	base_type;
   257	
   258	  public:
   259	    typedef _ATraits 				access_traits;
   260	    typedef typename access_traits::const_iterator 	a_const_iterator;
   261	    typedef _Alloc 					allocator_type;
   262	    typedef typename allocator_type::size_type 		size_type;
   263	    typedef typename base_type::key_type 		key_type;
   264	    typedef typename base_type::key_const_reference 	key_const_reference;
   265	
   266	    typedef size_type 					metadata_type;
   267	    typedef Node_CItr 					node_const_iterator;
   268	    typedef Node_Itr 					node_iterator;
   269	    typedef typename node_const_iterator::value_type 	const_iterator;
   270	    typedef typename node_iterator::value_type 		iterator;
   271	
   272	    /// Finds an entry by __order. Returns a const_iterator to the
   273	    /// entry with the __order order, or a const_iterator to the
   274	    /// container object's end if order is at least the size of the
   275	    /// container object.
   276	    inline const_iterator
   277	    find_by_order(size_type) const;
   278	
   279	    /// Finds an entry by __order. Returns an iterator to the entry
   280	    /// with the __order order, or an iterator to the container
   281	    /// object's end if order is at least the size of the container
   282	    /// object.
   283	    inline iterator
   284	    find_by_order(size_type);
   285	
   286	    /// Returns the order of a key within a sequence. For exapmle, if
   287	    /// r_key is the smallest key, this method will return 0; if r_key
   288	    /// is a key between the smallest and next key, this method will
   289	    /// return 1; if r_key is a key larger than the largest key, this
   290	    /// method will return the size of r_c.
   291	    inline size_type
   292	    order_of_key(key_const_reference) const;
   293	
   294	    /// Returns the order of a prefix within a sequence. For exapmle,
   295	    /// if [b, e] is the smallest prefix, this method will return 0; if
   296	    /// r_key is a key between the smallest and next key, this method
   297	    /// will return 1; if r_key is a key larger than the largest key,
   298	    /// this method will return the size of r_c.
   299	    inline size_type
   300	    order_of_prefix(a_const_iterator, a_const_iterator) const;
   301	
   302	  protected:
   303	    /// Updates the rank of a node through a node_iterator node_it;
   304	    /// end_nd_it is the end node iterator.
   305	    inline void
   306	    operator()(node_iterator, node_const_iterator) const;
   307	
   308	  private:
   309	    typedef typename base_type::const_reference 	const_reference;
   310	    typedef typename base_type::const_pointer 		const_pointer;
   311	
   312	    typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
   313	    typedef typename __rebind_m::other 			__rebind_ma;
   314	    typedef typename __rebind_ma::const_reference      metadata_const_reference;
   315	    typedef typename __rebind_ma::reference 		metadata_reference;
   316	
   317	    /// Returns true if the container is empty.
   318	    _GLIBCXX_NODISCARD virtual bool
   319	    empty() const = 0;
   320	
   321	    /// Returns the iterator associated with the trie's first element.
   322	    virtual iterator
   323	    begin() = 0;
   324	
   325	    /// Returns the iterator associated with the trie's
   326	    /// just-after-last element.
   327	    virtual iterator
   328	    end() = 0;
   329	
   330	    /// Returns the node_const_iterator associated with the trie's root node.
   331	    virtual node_const_iterator
   332	    node_begin() const = 0;
   333	
   334	    /// Returns the node_iterator associated with the trie's root node.
   335	    virtual node_iterator
   336	    node_begin() = 0;
   337	
   338	    /// Returns the node_const_iterator associated with a just-after
   339	    /// leaf node.
   340	    virtual node_const_iterator
   341	    node_end() const = 0;
   342	
   343	    /// Returns the node_iterator associated with a just-after leaf node.
   344	    virtual node_iterator
   345	    node_end() = 0;
   346	
   347	    /// Access to the cmp_fn object.
   348	    virtual access_traits&
   349	    get_access_traits() = 0;
   350	  };
   351	
   352	#include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp>
   353	
   354	#undef PB_DS_CLASS_T_DEC
   355	#undef PB_DS_CLASS_C_DEC
   356	#undef PB_DS_TRIE_POLICY_BASE
   357	
   358	} // namespace __gnu_pbds
   359	
   360	#endif