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

// -*- C++ -*-

// Copyright (C) 2005, 2006 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 2, 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.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// 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 traits.hpp
 * Contains an implementation class for pat_trie_.
 */

#ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
#define PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP

#include <ext/pb_ds/detail/pat_trie_/node_base.hpp>
#include <ext/pb_ds/detail/pat_trie_/head.hpp>
#include <ext/pb_ds/detail/pat_trie_/leaf.hpp>
#include <ext/pb_ds/detail/pat_trie_/internal_node.hpp>
#include <ext/pb_ds/detail/pat_trie_/point_iterators.hpp>
#include <ext/pb_ds/detail/pat_trie_/node_iterators.hpp>
#include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp>

namespace __gnu_pbds
{
  namespace detail
  {

    template<typename Key,
	     typename Mapped,
	     class E_Access_Traits,
	     template<typename Const_Node_Iterator,
		      class Node_Iterator,
		      class Cmp_Fn_,
		      class Allocator_>
    class Node_Update,
	     class Allocator>
    struct trie_traits<
      Key,
      Mapped,
      E_Access_Traits,
      Node_Update,
      pat_trie_tag,
      Allocator>
    {
    private:
      typedef types_traits< Key, Mapped, Allocator, false> type_traits;

    public:
      typedef
      typename trie_node_metadata_selector<
      Key,
      Mapped,
      E_Access_Traits,
      Node_Update,
      Allocator>::type
      metadata_type;

      typedef E_Access_Traits e_access_traits;

      typedef
      __gnu_pbds::detail::synth_e_access_traits<
	type_traits,
	false,
	e_access_traits>
      synth_e_access_traits;

      typedef
      pat_trie_node_base<
	type_traits,
	synth_e_access_traits,
	metadata_type,
	Allocator>
      node;

      typedef
      pat_trie_leaf<
	type_traits,
	synth_e_access_traits,
	metadata_type,
	Allocator>
      leaf;

      typedef
      pat_trie_head<
	type_traits,
	synth_e_access_traits,
	metadata_type,
	Allocator>
      head;

      typedef
      pat_trie_internal_node<
	type_traits,
	synth_e_access_traits,
	metadata_type,
	Allocator>
      internal_node;

      typedef
      pat_trie_const_it_<
	type_traits,
	node,
	leaf,
	head,
	internal_node,
	true,
	Allocator>
      const_iterator;

      typedef
      pat_trie_it_<
	type_traits,
	node,
	leaf,
	head,
	internal_node,
	true,
	Allocator>
      iterator;

      typedef
      pat_trie_const_it_<
	type_traits,
	node,
	leaf,
	head,
	internal_node,
	false,
	Allocator>
      const_reverse_iterator;

      typedef
      pat_trie_it_<
	type_traits,
	node,
	leaf,
	head,
	internal_node,
	false,
	Allocator>
      reverse_iterator;

      typedef
      pat_trie_const_node_it_<
	node,
	leaf,
	head,
	internal_node,
	const_iterator,
	iterator,
	synth_e_access_traits,
	Allocator>
      const_node_iterator;

      typedef
      pat_trie_node_it_<
	node,
	leaf,
	head,
	internal_node,
	const_iterator,
	iterator,
	synth_e_access_traits,
	Allocator>
      node_iterator;

      typedef
      Node_Update<
	const_node_iterator,
	node_iterator,
	E_Access_Traits,
	Allocator>
      node_update;

      typedef
      __gnu_pbds::null_trie_node_update<
	const_node_iterator,
	node_iterator,
	E_Access_Traits,
	Allocator>* 
      null_node_update_pointer;
    };

    template<typename Key,
	     class E_Access_Traits,
	     template<typename Const_Node_Iterator,
		      class Node_Iterator,
		      class Cmp_Fn_,
		      class Allocator_>
    class Node_Update,
	     class Allocator>
    struct trie_traits<
      Key,
      null_mapped_type,
      E_Access_Traits,
      Node_Update,
      pat_trie_tag,
      Allocator>
    {
    private:
      typedef
      types_traits<
      Key,
      null_mapped_type,
      Allocator,
      false>
      type_traits;

    public:
      typedef
      typename trie_node_metadata_selector<
      Key,
      null_mapped_type,
      E_Access_Traits,
      Node_Update,
      Allocator>::type
      metadata_type;

      typedef E_Access_Traits e_access_traits;

      typedef
      __gnu_pbds::detail::synth_e_access_traits<
	type_traits,
	true,
	e_access_traits>
      synth_e_access_traits;

      typedef
      pat_trie_node_base<
	type_traits,
	synth_e_access_traits,
	metadata_type,
	Allocator>
      node;

      typedef
      pat_trie_leaf<
	type_traits,
	synth_e_access_traits,
	metadata_type,
	Allocator>
      leaf;

      typedef
      pat_trie_head<
	type_traits,
	synth_e_access_traits,
	metadata_type,
	Allocator>
      head;

      typedef
      pat_trie_internal_node<
	type_traits,
	synth_e_access_traits,
	metadata_type,
	Allocator>
      internal_node;

      typedef
      pat_trie_const_it_<
	type_traits,
	node,
	leaf,
	head,
	internal_node,
	true,
	Allocator>
      const_iterator;

      typedef const_iterator iterator;

      typedef
      pat_trie_const_it_<
	type_traits,
	node,
	leaf,
	head,
	internal_node,
	false,
	Allocator>
      const_reverse_iterator;

      typedef const_reverse_iterator reverse_iterator;

      typedef
      pat_trie_const_node_it_<
	node,
	leaf,
	head,
	internal_node,
	const_iterator,
	iterator,
	synth_e_access_traits,
	Allocator>
      const_node_iterator;

      typedef const_node_iterator node_iterator;

      typedef
      Node_Update<
	const_node_iterator,
	node_iterator,
	E_Access_Traits,
	Allocator>
      node_update;

      typedef
      __gnu_pbds::null_trie_node_update<
	const_node_iterator,
	const_node_iterator,
	E_Access_Traits,
	Allocator>* 
      null_node_update_pointer;
    };

  } // namespace detail
} // namespace __gnu_pbds

#endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
Commit	Line	Data
4569a895 AT	1	// -- C++ --
	2
	3	// Copyright (C) 2005, 2006 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 2, 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	// You should have received a copy of the GNU General Public License
	17	// along with this library; see the file COPYING. If not, write to
	18	// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
	19	// MA 02111-1307, USA.
	20
	21	// As a special exception, you may use this file as part of a free
	22	// software library without restriction. Specifically, if other files
	23	// instantiate templates or use macros or inline functions from this
	24	// file, or you compile this file and link it with other files to
	25	// produce an executable, this file does not by itself cause the
	26	// resulting executable to be covered by the GNU General Public
	27	// License. This exception does not however invalidate any other
	28	// reasons why the executable file might be covered by the GNU General
	29	// Public License.
	30
	31	// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
	32
	33	// Permission to use, copy, modify, sell, and distribute this software
	34	// is hereby granted without fee, provided that the above copyright
	35	// notice appears in all copies, and that both that copyright notice
	36	// and this permission notice appear in supporting documentation. None
	37	// of the above authors, nor IBM Haifa Research Laboratories, make any
	38	// representation about the suitability of this software for any
	39	// purpose. It is provided "as is" without express or implied
	40	// warranty.
	41
	42	/**
	43	* @file traits.hpp
	44	* Contains an implementation class for pat_trie_.
	45	*/
	46
	47	#ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
	48	#define PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
	49
	50	#include <ext/pb_ds/detail/pat_trie_/node_base.hpp>
	51	#include <ext/pb_ds/detail/pat_trie_/head.hpp>
	52	#include <ext/pb_ds/detail/pat_trie_/leaf.hpp>
	53	#include <ext/pb_ds/detail/pat_trie_/internal_node.hpp>
	54	#include <ext/pb_ds/detail/pat_trie_/point_iterators.hpp>
	55	#include <ext/pb_ds/detail/pat_trie_/node_iterators.hpp>
	56	#include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp>
	57
5e11f978	58	namespace __gnu_pbds
4569a895 AT	59	{
	60	namespace detail
	61	{
	62
	63	template<typename Key,
	64	typename Mapped,
	65	class E_Access_Traits,
	66	template<typename Const_Node_Iterator,
	67	class Node_Iterator,
	68	class Cmp_Fn_,
	69	class Allocator_>
	70	class Node_Update,
	71	class Allocator>
	72	struct trie_traits<
	73	Key,
	74	Mapped,
	75	E_Access_Traits,
	76	Node_Update,
	77	pat_trie_tag,
	78	Allocator>
	79	{
	80	private:
	81	typedef types_traits< Key, Mapped, Allocator, false> type_traits;
	82
	83	public:
	84	typedef
	85	typename trie_node_metadata_selector<
	86	Key,
	87	Mapped,
	88	E_Access_Traits,
	89	Node_Update,
	90	Allocator>::type
	91	metadata_type;
	92
	93	typedef E_Access_Traits e_access_traits;
	94
	95	typedef
5e11f978	96	__gnu_pbds::detail::synth_e_access_traits<
4569a895 AT	97	type_traits,
	98	false,
	99	e_access_traits>
	100	synth_e_access_traits;
	101
	102	typedef
	103	pat_trie_node_base<
	104	type_traits,
	105	synth_e_access_traits,
	106	metadata_type,
	107	Allocator>
	108	node;
	109
	110	typedef
	111	pat_trie_leaf<
	112	type_traits,
	113	synth_e_access_traits,
	114	metadata_type,
	115	Allocator>
	116	leaf;
	117
	118	typedef
	119	pat_trie_head<
	120	type_traits,
	121	synth_e_access_traits,
	122	metadata_type,
	123	Allocator>
	124	head;
	125
	126	typedef
	127	pat_trie_internal_node<
	128	type_traits,
	129	synth_e_access_traits,
	130	metadata_type,
	131	Allocator>
	132	internal_node;
	133
	134	typedef
	135	pat_trie_const_it_<
	136	type_traits,
	137	node,
	138	leaf,
	139	head,
	140	internal_node,
	141	true,
	142	Allocator>
	143	const_iterator;
	144
	145	typedef
	146	pat_trie_it_<
	147	type_traits,
	148	node,
	149	leaf,
	150	head,
	151	internal_node,
	152	true,
	153	Allocator>
	154	iterator;
	155
	156	typedef
	157	pat_trie_const_it_<
	158	type_traits,
	159	node,
	160	leaf,
161	head,
162	internal_node,
163	false,
164	Allocator>
165	const_reverse_iterator;
166
167	typedef
168	pat_trie_it_<
169	type_traits,
170	node,
171	leaf,
172	head,
173	internal_node,
174	false,
175	Allocator>
176	reverse_iterator;
177
178	typedef
179	pat_trie_const_node_it_<
180	node,
181	leaf,
182	head,
183	internal_node,
184	const_iterator,
185	iterator,
186	synth_e_access_traits,
187	Allocator>
188	const_node_iterator;
189
190	typedef
191	pat_trie_node_it_<
192	node,
193	leaf,
194	head,
195	internal_node,
196	const_iterator,
197	iterator,
198	synth_e_access_traits,
199	Allocator>
200	node_iterator;
201
202	typedef
203	Node_Update<
204	const_node_iterator,
205	node_iterator,
206	E_Access_Traits,
207	Allocator>
208	node_update;
209
210	typedef
5e11f978	211	__gnu_pbds::null_trie_node_update<
4569a895 AT	212	const_node_iterator,
	213	node_iterator,
	214	E_Access_Traits,
	215	Allocator>*
	216	null_node_update_pointer;
	217	};
	218
	219	template<typename Key,
	220	class E_Access_Traits,
	221	template<typename Const_Node_Iterator,
	222	class Node_Iterator,
	223	class Cmp_Fn_,
	224	class Allocator_>
	225	class Node_Update,
	226	class Allocator>
	227	struct trie_traits<
	228	Key,
	229	null_mapped_type,
	230	E_Access_Traits,
	231	Node_Update,
	232	pat_trie_tag,
	233	Allocator>
	234	{
	235	private:
	236	typedef
	237	types_traits<
	238	Key,
	239	null_mapped_type,
	240	Allocator,
	241	false>
	242	type_traits;
	243
	244	public:
	245	typedef
	246	typename trie_node_metadata_selector<
	247	Key,
	248	null_mapped_type,
	249	E_Access_Traits,
	250	Node_Update,
	251	Allocator>::type
	252	metadata_type;
	253
	254	typedef E_Access_Traits e_access_traits;
	255
	256	typedef
5e11f978	257	__gnu_pbds::detail::synth_e_access_traits<
4569a895 AT	258	type_traits,
	259	true,
	260	e_access_traits>
	261	synth_e_access_traits;
	262
	263	typedef
	264	pat_trie_node_base<
	265	type_traits,
	266	synth_e_access_traits,
	267	metadata_type,
	268	Allocator>
	269	node;
	270
	271	typedef
	272	pat_trie_leaf<
	273	type_traits,
	274	synth_e_access_traits,
	275	metadata_type,
	276	Allocator>
	277	leaf;
	278
	279	typedef
	280	pat_trie_head<
	281	type_traits,
	282	synth_e_access_traits,
	283	metadata_type,
	284	Allocator>
	285	head;
	286
	287	typedef
	288	pat_trie_internal_node<
	289	type_traits,
	290	synth_e_access_traits,
	291	metadata_type,
	292	Allocator>
	293	internal_node;
	294
	295	typedef
	296	pat_trie_const_it_<
	297	type_traits,
	298	node,
	299	leaf,
	300	head,
	301	internal_node,
	302	true,
	303	Allocator>
	304	const_iterator;
	305
	306	typedef const_iterator iterator;
	307
	308	typedef
	309	pat_trie_const_it_<
	310	type_traits,
	311	node,
	312	leaf,
	313	head,
	314	internal_node,
	315	false,
	316	Allocator>
	317	const_reverse_iterator;
	318
	319	typedef const_reverse_iterator reverse_iterator;
	320
	321	typedef
322	pat_trie_const_node_it_<
323	node,
324	leaf,
325	head,
326	internal_node,
327	const_iterator,
328	iterator,
329	synth_e_access_traits,
330	Allocator>
331	const_node_iterator;
332
333	typedef const_node_iterator node_iterator;
334
335	typedef
336	Node_Update<
337	const_node_iterator,
338	node_iterator,
339	E_Access_Traits,
340	Allocator>
341	node_update;
342
343	typedef
5e11f978	344	__gnu_pbds::null_trie_node_update<
4569a895 AT	345	const_node_iterator,
	346	const_node_iterator,
	347	E_Access_Traits,
	348	Allocator>*
	349	null_node_update_pointer;
	350	};
	351
	352	} // namespace detail
5e11f978	353	} // namespace __gnu_pbds
4569a895 AT	354
	355	#endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
	356