[thirdparty/gcc.git] / libstdc++-v3 / include / ext / pb_ds / trie_policy.hpp

// -*- C++ -*-

// Copyright (C) 2005-2023 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file trie_policy.hpp
 * Contains trie-related policies.
 */

#ifndef PB_DS_TRIE_POLICY_HPP
#define PB_DS_TRIE_POLICY_HPP

#include <bits/c++config.h>
#include <string>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>

namespace __gnu_pbds
{
#define PB_DS_CLASS_T_DEC \
  template<typename String, typename String::value_type Min_E_Val, \
	   typename String::value_type Max_E_Val, bool Reverse, \
	   typename _Alloc>

#define PB_DS_CLASS_C_DEC \
  trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc>

  /**
   *  Element access traits for string types.
   *
   *  @tparam String 	    	String type.
   *  @tparam Min_E_Val        	Minimal element value.
   *  @tparam Max_E_Val	    	Maximum element value.
   *  @tparam Reverse	        Reverse iteration should be used.
   *                            Default: false.
   *  @tparam _Alloc 	    	Allocator type.
   */
  template<typename String = std::string,
	   typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min,
	   typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max,
	   bool Reverse = false,
	   typename _Alloc = std::allocator<char> >
  struct trie_string_access_traits
  {
  public:
    typedef typename _Alloc::size_type			  size_type;
    typedef String 					  key_type;
    typedef typename detail::rebind_traits<_Alloc, key_type>::const_reference
      key_const_reference;

    enum
      {
	reverse = Reverse
      };

    /// Element const iterator type.
    typedef typename detail::__conditional_type<Reverse, \
		       typename String::const_reverse_iterator, \
		       typename String::const_iterator>::__type const_iterator;

    /// Element type.
    typedef typename std::iterator_traits<const_iterator>::value_type e_type;

    enum
      {
	min_e_val = Min_E_Val,
	max_e_val = Max_E_Val,
	max_size = max_e_val - min_e_val + 1
      };
    PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);

    /// Returns a const_iterator to the first element of
    /// key_const_reference agumnet.
    inline static const_iterator
    begin(key_const_reference);

    /// Returns a const_iterator to the after-last element of
    /// key_const_reference argument.
    inline static const_iterator
    end(key_const_reference);

    /// Maps an element to a position.
    inline static size_type
    e_pos(e_type e);

  private:
    inline static const_iterator
    begin_imp(key_const_reference, detail::false_type);

    inline static const_iterator
    begin_imp(key_const_reference, detail::true_type);

    inline static const_iterator
    end_imp(key_const_reference, detail::false_type);

    inline static const_iterator
    end_imp(key_const_reference, detail::true_type);

    static detail::integral_constant<int, Reverse> s_rev_ind;
  };

#include <ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC \
  template<typename Node_CItr,typename Node_Itr, \
	   typename _ATraits, typename _Alloc>

#define PB_DS_CLASS_C_DEC \
  trie_prefix_search_node_update<Node_CItr, Node_Itr, \
				 _ATraits,_Alloc>

#define PB_DS_TRIE_POLICY_BASE \
  detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc>

  /// A node updator that allows tries to be searched for the range of
  /// values that match a certain prefix.
  template<typename Node_CItr,
	   typename Node_Itr,
	   typename _ATraits,
	   typename _Alloc>
  class trie_prefix_search_node_update : private PB_DS_TRIE_POLICY_BASE
  {
  private:
    typedef PB_DS_TRIE_POLICY_BASE 		       	base_type;

  public:
    typedef typename base_type::key_type 		key_type;
    typedef typename base_type::key_const_reference 	key_const_reference;

    /// Element access traits.
    typedef _ATraits 				access_traits;

    /// Const element iterator.
    typedef typename access_traits::const_iterator 	a_const_iterator;

    /// _Alloc type.
    typedef _Alloc 	       				allocator_type;

    /// Size type.
    typedef typename allocator_type::size_type 		size_type;
    typedef null_type 					metadata_type;
    typedef Node_Itr 					node_iterator;
    typedef Node_CItr 					node_const_iterator;
    typedef typename node_iterator::value_type 		iterator;
    typedef typename node_const_iterator::value_type 	const_iterator;

    /// Finds the const iterator range corresponding to all values
    /// whose prefixes match r_key.
    std::pair<const_iterator, const_iterator>
    prefix_range(key_const_reference) const;

    /// Finds the iterator range corresponding to all values whose
    /// prefixes match r_key.
    std::pair<iterator, iterator>
    prefix_range(key_const_reference);

    /// Finds the const iterator range corresponding to all values
    /// whose prefixes match [b, e).
    std::pair<const_iterator, const_iterator>
    prefix_range(a_const_iterator, a_const_iterator) const;

    /// Finds the iterator range corresponding to all values whose
    /// prefixes match [b, e).
    std::pair<iterator, iterator>
    prefix_range(a_const_iterator, a_const_iterator);

  protected:
    /// Called to update a node's metadata.
    inline void
    operator()(node_iterator node_it, node_const_iterator end_nd_it) const;

  private:
    node_iterator
    next_child(node_iterator, a_const_iterator, a_const_iterator,
	       node_iterator, const access_traits&);

    /// Returns the const iterator associated with the just-after last element.
    virtual const_iterator
    end() const = 0;

    /// Returns the iterator associated with the just-after last element.
    virtual iterator
    end() = 0;

    /// Returns the node_const_iterator associated with the trie's root node.
    virtual node_const_iterator
    node_begin() const = 0;

    /// Returns the node_iterator associated with the trie's root node.
    virtual node_iterator
    node_begin() = 0;

    /// Returns the node_const_iterator associated with a just-after leaf node.
    virtual node_const_iterator
    node_end() const = 0;

    /// Returns the node_iterator associated with a just-after leaf node.
    virtual node_iterator
    node_end() = 0;

    /// Access to the cmp_fn object.
    virtual const access_traits&
    get_access_traits() const = 0;
  };

#include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp>

#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_C_DEC \
  trie_order_statistics_node_update<Node_CItr, Node_Itr, \
				    _ATraits, _Alloc>

  /// Functor updating ranks of entrees.
  template<typename Node_CItr,
	   typename Node_Itr,
	   typename _ATraits,
	   typename _Alloc>
  class trie_order_statistics_node_update : private PB_DS_TRIE_POLICY_BASE
  {
  private:
    typedef PB_DS_TRIE_POLICY_BASE 		       	base_type;

  public:
    typedef _ATraits 				access_traits;
    typedef typename access_traits::const_iterator 	a_const_iterator;
    typedef _Alloc 					allocator_type;
    typedef typename allocator_type::size_type 		size_type;
    typedef typename base_type::key_type 		key_type;
    typedef typename base_type::key_const_reference 	key_const_reference;

    typedef size_type 					metadata_type;
    typedef Node_CItr 					node_const_iterator;
    typedef Node_Itr 					node_iterator;
    typedef typename node_const_iterator::value_type 	const_iterator;
    typedef typename node_iterator::value_type 		iterator;

    /// Finds an entry by __order. Returns a const_iterator to the
    /// entry with the __order order, or a const_iterator to the
    /// container object's end if order is at least the size of the
    /// container object.
    inline const_iterator
    find_by_order(size_type) const;

    /// Finds an entry by __order. Returns an iterator to the entry
    /// with the __order order, or an iterator to the container
    /// object's end if order is at least the size of the container
    /// object.
    inline iterator
    find_by_order(size_type);

    /// Returns the order of a key within a sequence. For exapmle, if
    /// r_key is the smallest key, this method will return 0; if r_key
    /// is a key between the smallest and next key, this method will
    /// return 1; if r_key is a key larger than the largest key, this
    /// method will return the size of r_c.
    inline size_type
    order_of_key(key_const_reference) const;

    /// Returns the order of a prefix within a sequence. For exapmle,
    /// if [b, e] is the smallest prefix, this method will return 0; if
    /// r_key is a key between the smallest and next key, this method
    /// will return 1; if r_key is a key larger than the largest key,
    /// this method will return the size of r_c.
    inline size_type
    order_of_prefix(a_const_iterator, a_const_iterator) const;

  protected:
    /// Updates the rank of a node through a node_iterator node_it;
    /// end_nd_it is the end node iterator.
    inline void
    operator()(node_iterator, node_const_iterator) const;

  private:
    typedef typename base_type::const_reference 	const_reference;
    typedef typename base_type::const_pointer 		const_pointer;

    typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
    typedef typename __rebind_m::other 			__rebind_ma;
    typedef typename __rebind_ma::const_reference      metadata_const_reference;
    typedef typename __rebind_ma::reference 		metadata_reference;

    /// Returns true if the container is empty.
    _GLIBCXX_NODISCARD virtual bool
    empty() const = 0;

    /// Returns the iterator associated with the trie's first element.
    virtual iterator
    begin() = 0;

    /// Returns the iterator associated with the trie's
    /// just-after-last element.
    virtual iterator
    end() = 0;

    /// Returns the node_const_iterator associated with the trie's root node.
    virtual node_const_iterator
    node_begin() const = 0;

    /// Returns the node_iterator associated with the trie's root node.
    virtual node_iterator
    node_begin() = 0;

    /// Returns the node_const_iterator associated with a just-after
    /// leaf node.
    virtual node_const_iterator
    node_end() const = 0;

    /// Returns the node_iterator associated with a just-after leaf node.
    virtual node_iterator
    node_end() = 0;

    /// Access to the cmp_fn object.
    virtual access_traits&
    get_access_traits() = 0;
  };

#include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_TRIE_POLICY_BASE

} // namespace __gnu_pbds

#endif
Commit	Line	Data
4569a895 AT	1	// -- C++ --
4569a895 AT	2
83ffe9cd	3	// Copyright (C) 2005-2023 Free Software Foundation, Inc.
4569a895 AT	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
748086b7	8	// Foundation; either version 3, or (at your option) any later
4569a895 AT	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
748086b7 JJ	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/>.
4569a895 AT	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
8fc81078	44	#include <bits/c++config.h>
4569a895	45	#include <string>
4569a895 AT	46	#include <ext/pb_ds/detail/type_utils.hpp>
	47	#include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>
	48
5e11f978	49	namespace __gnu_pbds
4569a895	50	{
a345e45d BK	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>
4569a895	55
a345e45d BK	56	#define PB_DS_CLASS_C_DEC \
a345e45d BK	57	trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc>
4569a895	58
30a96b3b BK	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	*/
4569a895	69	template<typename String = std::string,
a345e45d BK	70	typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min,
a345e45d BK	71	typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max,
4569a895	72	bool Reverse = false,
a345e45d BK	73	typename _Alloc = std::allocator<char> >
a345e45d BK	74	struct trie_string_access_traits
4569a895 AT	75	{
4569a895 AT	76	public:
a345e45d BK	77	typedef typename _Alloc::size_type size_type;
a345e45d BK	78	typedef String key_type;
ec541f1b JW	79	typedef typename detail::rebind_traits<_Alloc, key_type>::const_reference
ec541f1b JW	80	key_const_reference;
4569a895 AT	81
	82	enum
	83	{
	84	reverse = Reverse
	85	};
	86
30a96b3b	87	/// Element const iterator type.
a345e45d BK	88	typedef typename detail::__conditional_type<Reverse, \
	89	typename String::const_reverse_iterator, \
	90	typename String::const_iterator>::__type const_iterator;
4569a895	91
30a96b3b	92	/// Element type.
4569a895 AT	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	};
81ee09de	101	PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
4569a895	102
30a96b3b BK	103	/// Returns a const_iterator to the first element of
30a96b3b BK	104	/// key_const_reference agumnet.
4569a895	105	inline static const_iterator
a345e45d	106	begin(key_const_reference);
4569a895	107
30a96b3b BK	108	/// Returns a const_iterator to the after-last element of
30a96b3b BK	109	/// key_const_reference argument.
4569a895	110	inline static const_iterator
a345e45d	111	end(key_const_reference);
4569a895	112
30a96b3b	113	/// Maps an element to a position.
4569a895 AT	114	inline static size_type
	115	e_pos(e_type e);
	116
	117	private:
4569a895	118	inline static const_iterator
a345e45d	119	begin_imp(key_const_reference, detail::false_type);
4569a895 AT	120
4569a895 AT	121	inline static const_iterator
a345e45d	122	begin_imp(key_const_reference, detail::true_type);
4569a895 AT	123
4569a895 AT	124	inline static const_iterator
a345e45d	125	end_imp(key_const_reference, detail::false_type);
4569a895 AT	126
4569a895 AT	127	inline static const_iterator
a345e45d	128	end_imp(key_const_reference, detail::true_type);
4569a895	129
81ee09de	130	static detail::integral_constant<int, Reverse> s_rev_ind;
4569a895 AT	131	};
4569a895 AT	132
a345e45d	133	#include <ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp>
4569a895 AT	134
	135	#undef PB_DS_CLASS_T_DEC
	136	#undef PB_DS_CLASS_C_DEC
	137
	138	#define PB_DS_CLASS_T_DEC \
a345e45d BK	139	template<typename Node_CItr,typename Node_Itr, \
a345e45d BK	140	typename _ATraits, typename _Alloc>
4569a895 AT	141
4569a895 AT	142	#define PB_DS_CLASS_C_DEC \
a345e45d BK	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
4569a895 AT	156	{
4569a895 AT	157	private:
a345e45d	158	typedef PB_DS_TRIE_POLICY_BASE base_type;
4569a895 AT	159
4569a895 AT	160	public:
a345e45d BK	161	typedef typename base_type::key_type key_type;
a345e45d BK	162	typedef typename base_type::key_const_reference key_const_reference;
4569a895	163
30a96b3b	164	/// Element access traits.
a345e45d	165	typedef _ATraits access_traits;
4569a895	166
30a96b3b	167	/// Const element iterator.
a345e45d	168	typedef typename access_traits::const_iterator a_const_iterator;
4569a895	169
30a96b3b	170	/// _Alloc type.
a345e45d	171	typedef _Alloc allocator_type;
4569a895	172
30a96b3b	173	/// Size type.
a345e45d BK	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;
4569a895	180
30a96b3b BK	181	/// Finds the const iterator range corresponding to all values
30a96b3b BK	182	/// whose prefixes match r_key.
4569a895	183	std::pair<const_iterator, const_iterator>
a345e45d	184	prefix_range(key_const_reference) const;
4569a895	185
30a96b3b BK	186	/// Finds the iterator range corresponding to all values whose
30a96b3b BK	187	/// prefixes match r_key.
4569a895	188	std::pair<iterator, iterator>
a345e45d	189	prefix_range(key_const_reference);
4569a895	190
30a96b3b BK	191	/// Finds the const iterator range corresponding to all values
30a96b3b BK	192	/// whose prefixes match [b, e).
4569a895	193	std::pair<const_iterator, const_iterator>
a345e45d	194	prefix_range(a_const_iterator, a_const_iterator) const;
4569a895	195
30a96b3b BK	196	/// Finds the iterator range corresponding to all values whose
30a96b3b BK	197	/// prefixes match [b, e).
4569a895	198	std::pair<iterator, iterator>
a345e45d	199	prefix_range(a_const_iterator, a_const_iterator);
4569a895 AT	200
4569a895 AT	201	protected:
30a96b3b	202	/// Called to update a node's metadata.
4569a895	203	inline void
a345e45d	204	operator()(node_iterator node_it, node_const_iterator end_nd_it) const;
4569a895 AT	205
4569a895 AT	206	private:
a345e45d BK	207	node_iterator
	208	next_child(node_iterator, a_const_iterator, a_const_iterator,
	209	node_iterator, const access_traits&);
	210
30a96b3b	211	/// Returns the const iterator associated with the just-after last element.
4569a895 AT	212	virtual const_iterator
	213	end() const = 0;
	214
30a96b3b	215	/// Returns the iterator associated with the just-after last element.
4569a895 AT	216	virtual iterator
	217	end() = 0;
	218
30a96b3b	219	/// Returns the node_const_iterator associated with the trie's root node.
a345e45d	220	virtual node_const_iterator
4569a895 AT	221	node_begin() const = 0;
4569a895 AT	222
30a96b3b	223	/// Returns the node_iterator associated with the trie's root node.
4569a895 AT	224	virtual node_iterator
	225	node_begin() = 0;
	226
30a96b3b	227	/// Returns the node_const_iterator associated with a just-after leaf node.
a345e45d	228	virtual node_const_iterator
4569a895 AT	229	node_end() const = 0;
4569a895 AT	230
30a96b3b	231	/// Returns the node_iterator associated with a just-after leaf node.
4569a895 AT	232	virtual node_iterator
	233	node_end() = 0;
	234
30a96b3b	235	/// Access to the cmp_fn object.
a345e45d BK	236	virtual const access_traits&
a345e45d BK	237	get_access_traits() const = 0;
4569a895 AT	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 \
a345e45d BK	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
4569a895 AT	254	{
4569a895 AT	255	private:
a345e45d	256	typedef PB_DS_TRIE_POLICY_BASE base_type;
4569a895 AT	257
4569a895 AT	258	public:
a345e45d BK	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;
4569a895	271
30a96b3b BK	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.
4569a895 AT	276	inline const_iterator
	277	find_by_order(size_type) const;
	278
30a96b3b BK	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.
4569a895 AT	283	inline iterator
	284	find_by_order(size_type);
	285
30a96b3b BK	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.
4569a895	291	inline size_type
a345e45d	292	order_of_key(key_const_reference) const;
4569a895	293
30a96b3b BK	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.
4569a895	299	inline size_type
a345e45d BK	300	order_of_prefix(a_const_iterator, a_const_iterator) const;
	301
	302	protected:
30a96b3b BK	303	/// Updates the rank of a node through a node_iterator node_it;
30a96b3b BK	304	/// end_nd_it is the end node iterator.
a345e45d BK	305	inline void
a345e45d BK	306	operator()(node_iterator, node_const_iterator) const;
4569a895 AT	307
4569a895 AT	308	private:
a345e45d BK	309	typedef typename base_type::const_reference const_reference;
a345e45d BK	310	typedef typename base_type::const_pointer const_pointer;
4569a895	311
a345e45d BK	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;
4569a895	316
30a96b3b	317	/// Returns true if the container is empty.
d715f554	318	_GLIBCXX_NODISCARD virtual bool
4569a895 AT	319	empty() const = 0;
4569a895 AT	320
30a96b3b	321	/// Returns the iterator associated with the trie's first element.
4569a895 AT	322	virtual iterator
	323	begin() = 0;
	324
30a96b3b BK	325	/// Returns the iterator associated with the trie's
30a96b3b BK	326	/// just-after-last element.
4569a895 AT	327	virtual iterator
	328	end() = 0;
	329
30a96b3b	330	/// Returns the node_const_iterator associated with the trie's root node.
a345e45d	331	virtual node_const_iterator
4569a895 AT	332	node_begin() const = 0;
4569a895 AT	333
30a96b3b	334	/// Returns the node_iterator associated with the trie's root node.
4569a895 AT	335	virtual node_iterator
	336	node_begin() = 0;
	337
30a96b3b BK	338	/// Returns the node_const_iterator associated with a just-after
30a96b3b BK	339	/// leaf node.
a345e45d	340	virtual node_const_iterator
4569a895 AT	341	node_end() const = 0;
4569a895 AT	342
30a96b3b	343	/// Returns the node_iterator associated with a just-after leaf node.
4569a895 AT	344	virtual node_iterator
	345	node_end() = 0;
	346
30a96b3b	347	/// Access to the cmp_fn object.
a345e45d BK	348	virtual access_traits&
a345e45d BK	349	get_access_traits() = 0;
4569a895 AT	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
a345e45d	356	#undef PB_DS_TRIE_POLICY_BASE
4569a895	357
5e11f978	358	} // namespace __gnu_pbds
4569a895 AT	359
4569a895 AT	360	#endif