[thirdparty/gcc.git] / libstdc++-v3 / include / ext / pb_ds / detail / bin_search_tree_ / traits.hpp

// -*- C++ -*-

// Copyright (C) 2005-2018 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 bin_search_tree_/traits.hpp
 * Contains an implementation for bin_search_tree_.
 */

#ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
#define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP

#include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>

namespace __gnu_pbds
{
  namespace detail
  {
    /// Binary search tree traits, primary template
    /// @ingroup traits
    template<typename Key,
	     typename Mapped,
	     class Cmp_Fn,
	     template<typename Node_CItr,
		      class Node_Itr,
		      class _Cmp_Fn,
		      typename _Alloc>
	     class Node_Update,
	     class Node,
	     typename _Alloc>
    struct bin_search_tree_traits
    {
    private:
      typedef types_traits<Key, Mapped, _Alloc, false> type_traits;

    public:
      typedef Node node;

      typedef
      bin_search_tree_const_it_<
	typename _Alloc::template rebind<
	node>::other::pointer,
	typename type_traits::value_type,
	typename type_traits::pointer,
	typename type_traits::const_pointer,
	typename type_traits::reference,
	typename type_traits::const_reference,
	true,
	_Alloc>
      point_const_iterator;

      typedef
      bin_search_tree_it_<
	typename _Alloc::template rebind<
	node>::other::pointer,
	typename type_traits::value_type,
	typename type_traits::pointer,
	typename type_traits::const_pointer,
	typename type_traits::reference,
	typename type_traits::const_reference,
	true,
	_Alloc>
      point_iterator;

      typedef
      bin_search_tree_const_it_<
	typename _Alloc::template rebind<
	node>::other::pointer,
	typename type_traits::value_type,
	typename type_traits::pointer,
	typename type_traits::const_pointer,
	typename type_traits::reference,
	typename type_traits::const_reference,
	false,
	_Alloc>
      const_reverse_iterator;

      typedef
      bin_search_tree_it_<
	typename _Alloc::template rebind<
	node>::other::pointer,
	typename type_traits::value_type,
	typename type_traits::pointer,
	typename type_traits::const_pointer,
	typename type_traits::reference,
	typename type_traits::const_reference,
	false,
	_Alloc>
      reverse_iterator;

      /// This is an iterator to an iterator: it iterates over nodes,
      /// and de-referencing it returns one of the tree's iterators.
      typedef
      bin_search_tree_const_node_it_<
	Node,
	point_const_iterator,
	point_iterator,
	_Alloc>
      node_const_iterator;

      typedef
      bin_search_tree_node_it_<
	Node,
	point_const_iterator,
	point_iterator,
	_Alloc>
      node_iterator;

      typedef
      Node_Update<
	node_const_iterator,
	node_iterator,
	Cmp_Fn,
	_Alloc>
      node_update;

      typedef
      __gnu_pbds::null_node_update<
	node_const_iterator,
	node_iterator,
	Cmp_Fn,
	_Alloc>* 
      null_node_update_pointer;
    };

    /// Specialization.
    /// @ingroup traits
    template<typename Key,
	     class Cmp_Fn,
	     template<typename Node_CItr,
		      class Node_Itr,
		      class _Cmp_Fn,
		      typename _Alloc>
	     class Node_Update,
	     class Node,
	     typename _Alloc>
    struct
    bin_search_tree_traits<Key, null_type, Cmp_Fn, Node_Update, Node, _Alloc>
    {
    private:
      typedef types_traits<Key, null_type, _Alloc, false> type_traits;

    public:
      typedef Node node;

      typedef
      bin_search_tree_const_it_<
	typename _Alloc::template rebind<
	node>::other::pointer,
	typename type_traits::value_type,
	typename type_traits::pointer,
	typename type_traits::const_pointer,
	typename type_traits::reference,
	typename type_traits::const_reference,
	true,
	_Alloc>
      point_const_iterator;

      typedef point_const_iterator point_iterator;

      typedef
      bin_search_tree_const_it_<
	typename _Alloc::template rebind<
	node>::other::pointer,
	typename type_traits::value_type,
	typename type_traits::pointer,
	typename type_traits::const_pointer,
	typename type_traits::reference,
	typename type_traits::const_reference,
	false,
	_Alloc>
      const_reverse_iterator;

      typedef const_reverse_iterator reverse_iterator;

      /// This is an iterator to an iterator: it iterates over nodes,
      /// and de-referencing it returns one of the tree's iterators.
      typedef
      bin_search_tree_const_node_it_<
	Node,
	point_const_iterator,
	point_iterator,
	_Alloc>
      node_const_iterator;

      typedef node_const_iterator node_iterator;

      typedef
      Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
      node_update;

      typedef
      __gnu_pbds::null_node_update<
	node_const_iterator,
	node_iterator,
	Cmp_Fn,
	_Alloc>* 
      null_node_update_pointer;
    };

  } // namespace detail
} // namespace __gnu_pbds

#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
Commit	Line	Data
4569a895 AT	1	// -- C++ --
4569a895 AT	2
85ec4feb	3	// Copyright (C) 2005-2018 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.
4569a895	19
748086b7 JJ	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	/**
a345e45d	37	* @file bin_search_tree_/traits.hpp
4569a895 AT	38	* Contains an implementation for bin_search_tree_.
	39	*/
	40
	41	#ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
	42	#define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
	43
	44	#include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
	45	#include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
	46
5e11f978	47	namespace __gnu_pbds
4569a895 AT	48	{
	49	namespace detail
	50	{
30a96b3b BK	51	/// Binary search tree traits, primary template
30a96b3b BK	52	/// @ingroup traits
4569a895 AT	53	template<typename Key,
	54	typename Mapped,
	55	class Cmp_Fn,
a345e45d BK	56	template<typename Node_CItr,
a345e45d BK	57	class Node_Itr,
060269c4	58	class _Cmp_Fn,
a345e45d	59	typename _Alloc>
30a96b3b	60	class Node_Update,
4569a895	61	class Node,
a345e45d	62	typename _Alloc>
4569a895 AT	63	struct bin_search_tree_traits
	64	{
	65	private:
a345e45d	66	typedef types_traits<Key, Mapped, _Alloc, false> type_traits;
4569a895 AT	67
	68	public:
	69	typedef Node node;
	70
	71	typedef
	72	bin_search_tree_const_it_<
a345e45d	73	typename _Alloc::template rebind<
4569a895 AT	74	node>::other::pointer,
	75	typename type_traits::value_type,
	76	typename type_traits::pointer,
	77	typename type_traits::const_pointer,
	78	typename type_traits::reference,
	79	typename type_traits::const_reference,
	80	true,
a345e45d BK	81	_Alloc>
a345e45d BK	82	point_const_iterator;
4569a895 AT	83
	84	typedef
	85	bin_search_tree_it_<
a345e45d	86	typename _Alloc::template rebind<
4569a895 AT	87	node>::other::pointer,
	88	typename type_traits::value_type,
	89	typename type_traits::pointer,
	90	typename type_traits::const_pointer,
	91	typename type_traits::reference,
	92	typename type_traits::const_reference,
	93	true,
a345e45d	94	_Alloc>
4569a895 AT	95	point_iterator;
	96
	97	typedef
	98	bin_search_tree_const_it_<
a345e45d	99	typename _Alloc::template rebind<
4569a895 AT	100	node>::other::pointer,
	101	typename type_traits::value_type,
	102	typename type_traits::pointer,
	103	typename type_traits::const_pointer,
	104	typename type_traits::reference,
	105	typename type_traits::const_reference,
	106	false,
a345e45d	107	_Alloc>
4569a895 AT	108	const_reverse_iterator;
	109
	110	typedef
	111	bin_search_tree_it_<
a345e45d	112	typename _Alloc::template rebind<
4569a895 AT	113	node>::other::pointer,
	114	typename type_traits::value_type,
	115	typename type_traits::pointer,
	116	typename type_traits::const_pointer,
	117	typename type_traits::reference,
	118	typename type_traits::const_reference,
	119	false,
a345e45d	120	_Alloc>
4569a895 AT	121	reverse_iterator;
4569a895 AT	122
30a96b3b BK	123	/// This is an iterator to an iterator: it iterates over nodes,
30a96b3b BK	124	/// and de-referencing it returns one of the tree's iterators.
4569a895 AT	125	typedef
	126	bin_search_tree_const_node_it_<
	127	Node,
a345e45d	128	point_const_iterator,
4569a895	129	point_iterator,
a345e45d BK	130	_Alloc>
a345e45d BK	131	node_const_iterator;
4569a895 AT	132
	133	typedef
	134	bin_search_tree_node_it_<
	135	Node,
a345e45d	136	point_const_iterator,
4569a895	137	point_iterator,
a345e45d	138	_Alloc>
4569a895 AT	139	node_iterator;
	140
	141	typedef
	142	Node_Update<
a345e45d	143	node_const_iterator,
4569a895 AT	144	node_iterator,
4569a895 AT	145	Cmp_Fn,
a345e45d	146	_Alloc>
4569a895 AT	147	node_update;
	148
	149	typedef
a345e45d BK	150	__gnu_pbds::null_node_update<
a345e45d BK	151	node_const_iterator,
4569a895 AT	152	node_iterator,
4569a895 AT	153	Cmp_Fn,
a345e45d	154	_Alloc>*
4569a895 AT	155	null_node_update_pointer;
	156	};
	157
a345e45d	158	/// Specialization.
30a96b3b	159	/// @ingroup traits
4569a895 AT	160	template<typename Key,
4569a895 AT	161	class Cmp_Fn,
a345e45d BK	162	template<typename Node_CItr,
a345e45d BK	163	class Node_Itr,
060269c4	164	class _Cmp_Fn,
a345e45d	165	typename _Alloc>
30a96b3b	166	class Node_Update,
4569a895	167	class Node,
a345e45d	168	typename _Alloc>
6b4f8906 JW	169	struct
6b4f8906 JW	170	bin_search_tree_traits<Key, null_type, Cmp_Fn, Node_Update, Node, _Alloc>
4569a895 AT	171	{
4569a895 AT	172	private:
a345e45d	173	typedef types_traits<Key, null_type, _Alloc, false> type_traits;
4569a895 AT	174
	175	public:
	176	typedef Node node;
	177
	178	typedef
	179	bin_search_tree_const_it_<
a345e45d	180	typename _Alloc::template rebind<
4569a895 AT	181	node>::other::pointer,
	182	typename type_traits::value_type,
	183	typename type_traits::pointer,
	184	typename type_traits::const_pointer,
	185	typename type_traits::reference,
	186	typename type_traits::const_reference,
	187	true,
a345e45d BK	188	_Alloc>
a345e45d BK	189	point_const_iterator;
4569a895	190
a345e45d	191	typedef point_const_iterator point_iterator;
4569a895 AT	192
	193	typedef
	194	bin_search_tree_const_it_<
a345e45d	195	typename _Alloc::template rebind<
4569a895 AT	196	node>::other::pointer,
	197	typename type_traits::value_type,
	198	typename type_traits::pointer,
	199	typename type_traits::const_pointer,
	200	typename type_traits::reference,
	201	typename type_traits::const_reference,
	202	false,
a345e45d	203	_Alloc>
4569a895 AT	204	const_reverse_iterator;
	205
	206	typedef const_reverse_iterator reverse_iterator;
	207
30a96b3b BK	208	/// This is an iterator to an iterator: it iterates over nodes,
30a96b3b BK	209	/// and de-referencing it returns one of the tree's iterators.
4569a895 AT	210	typedef
	211	bin_search_tree_const_node_it_<
	212	Node,
a345e45d	213	point_const_iterator,
4569a895	214	point_iterator,
a345e45d BK	215	_Alloc>
a345e45d BK	216	node_const_iterator;
4569a895	217
a345e45d	218	typedef node_const_iterator node_iterator;
4569a895 AT	219
4569a895 AT	220	typedef
a345e45d	221	Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
4569a895 AT	222	node_update;
	223
	224	typedef
a345e45d BK	225	__gnu_pbds::null_node_update<
a345e45d BK	226	node_const_iterator,
4569a895 AT	227	node_iterator,
4569a895 AT	228	Cmp_Fn,
a345e45d	229	_Alloc>*
4569a895 AT	230	null_node_update_pointer;
	231	};
	232
	233	} // namespace detail
5e11f978	234	} // namespace __gnu_pbds
4569a895 AT	235
4569a895 AT	236	#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP