libstdc++
pat_trie_/traits.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009, 2011 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 pat_trie_/traits.hpp
38  * Contains an implementation class for pat_trie_.
39  */
40 
41 #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
42 #define PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
43 
46 
47 namespace __gnu_pbds
48 {
49  namespace detail
50  {
51  /// Specialization.
52  /// @ingroup traits
53  template<typename Key,
54  typename Mapped,
55  typename _ATraits,
56  template<typename Node_CItr,
57  typename Node_Itr,
58  typename Cmp_Fn_,
59  typename _Alloc_>
60  class Node_Update,
61  typename _Alloc>
62  struct trie_traits<Key, Mapped, _ATraits, Node_Update, pat_trie_tag, _Alloc>
63  {
64  private:
65  typedef pat_trie_base base_type;
67 
68  public:
69  typedef typename trie_node_metadata_dispatch<Key, Mapped, _ATraits, Node_Update, _Alloc>::type metadata_type;
71  typedef _ATraits access_traits;
72 
73  /// Type for synthesized traits.
75 
80 
85 
86  /// This is an iterator to an iterator: it iterates over nodes,
87  /// and de-referencing it returns one of the tree's iterators.
89 
91 
92  /// Type for node update.
93  typedef Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc> node_update;
94 
96  };
97 
98 
99  /// Specialization.
100  /// @ingroup traits
101  template<typename Key,
102  typename _ATraits,
103  template<typename Node_CItr,
104  typename Node_Itr,
105  typename Cmp_Fn_,
106  typename _Alloc_>
107  class Node_Update,
108  typename _Alloc>
109  struct trie_traits<Key, null_type, _ATraits, Node_Update, pat_trie_tag, _Alloc>
110  {
111  private:
112  typedef pat_trie_base base_type;
114 
115  public:
116  typedef typename trie_node_metadata_dispatch<Key, null_type, _ATraits, Node_Update, _Alloc>::type metadata_type;
118  typedef _ATraits access_traits;
119 
120  /// Type for synthesized traits.
122 
127 
129  typedef const_iterator iterator;
132 
133  /// This is an iterator to an iterator: it iterates over nodes,
134  /// and de-referencing it returns one of the tree's iterators.
136 
138 
139  /// Type for node update.
140  typedef Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc> node_update;
141 
143  };
144 
145  } // namespace detail
146 } // namespace __gnu_pbds
147 
148 #endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
Metadata base primary template.
Synthetic element access traits.
__gnu_pbds::detail::synth_access_traits< type_traits, true, access_traits > synth_access_traits
Type for synthesized traits.
base_type::_Node_citer< node, leaf, head, inode, const_iterator, iterator, _Alloc > node_const_iterator
This is an iterator to an iterator: it iterates over nodes, and de-referencing it returns one of the ...
Base type for PATRICIA trees.
__gnu_pbds::detail::synth_access_traits< type_traits, false, access_traits > synth_access_traits
Type for synthesized traits.
Node_Update< node_const_iterator, node_iterator, _ATraits, _Alloc > node_update
Type for node update.
Node_Update< node_const_iterator, node_iterator, _ATraits, _Alloc > node_update
Type for node update.
base_type::_Node_citer< node, leaf, head, inode, const_iterator, iterator, _Alloc > node_const_iterator
This is an iterator to an iterator: it iterates over nodes, and de-referencing it returns one of the ...
Internal node type, PATRICIA tree.
Represents no type, or absence of type, for template tricks.
Head node for PATRICIA tree.
Leaf node for PATRICIA tree.
A null node updator, indicating that no node updates are required.
Trie traits class, primary template.