libstdc++
pat_trie_/traits.hpp
Go to the documentation of this file.
1
// -*- C++ -*-
2
3
// Copyright (C) 2005-2013 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
44
#include <
ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
>
45
#include <
ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp
>
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
;
66
typedef
types_traits<Key, Mapped, _Alloc, false>
type_traits
;
67
68
public
:
69
typedef
typename
trie_node_metadata_dispatch<Key, Mapped, _ATraits, Node_Update, _Alloc>::type metadata_type;
70
typedef
base_type::_Metadata<metadata_type, _Alloc>
metadata
;
71
typedef
_ATraits access_traits;
72
73
/// Type for synthesized traits.
74
typedef
__gnu_pbds::detail::synth_access_traits<type_traits, false, access_traits>
synth_access_traits
;
75
76
typedef
base_type::_Node_base<synth_access_traits, metadata>
node
;
77
typedef
base_type::_Head<synth_access_traits, metadata>
head
;
78
typedef
base_type::_Leaf<synth_access_traits, metadata>
leaf
;
79
typedef
base_type::_Inode<synth_access_traits, metadata>
inode
;
80
81
typedef
base_type::_Iter<node, leaf, head, inode, true>
iterator
;
82
typedef
base_type::_CIter<node, leaf, head, inode, true>
const_iterator
;
83
typedef
base_type::_Iter<node, leaf, head, inode, false>
reverse_iterator
;
84
typedef
base_type::_CIter<node, leaf, head, inode, false>
const_reverse_iterator
;
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.
88
typedef
base_type::_Node_citer<node, leaf, head, inode, const_iterator, iterator, _Alloc>
node_const_iterator
;
89
90
typedef
base_type::_Node_iter<node, leaf, head, inode, const_iterator, iterator, _Alloc>
node_iterator
;
91
92
/// Type for node update.
93
typedef
Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc>
node_update
;
94
95
typedef
null_node_update<node_const_iterator, node_iterator, _ATraits, _Alloc>
*
null_node_update_pointer
;
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
;
113
typedef
types_traits<Key, null_type, _Alloc, false>
type_traits
;
114
115
public
:
116
typedef
typename
trie_node_metadata_dispatch<Key, null_type, _ATraits, Node_Update, _Alloc>::type metadata_type;
117
typedef
base_type::_Metadata<metadata_type, _Alloc>
metadata
;
118
typedef
_ATraits access_traits;
119
120
/// Type for synthesized traits.
121
typedef
__gnu_pbds::detail::synth_access_traits<type_traits, true, access_traits>
synth_access_traits
;
122
123
typedef
base_type::_Node_base<synth_access_traits, metadata>
node
;
124
typedef
base_type::_Head<synth_access_traits, metadata>
head
;
125
typedef
base_type::_Leaf<synth_access_traits, metadata>
leaf
;
126
typedef
base_type::_Inode<synth_access_traits, metadata>
inode
;
127
128
typedef
base_type::_CIter<node, leaf, head, inode, true>
const_iterator
;
129
typedef
const_iterator
iterator
;
130
typedef
base_type::_CIter<node, leaf, head, inode, false>
const_reverse_iterator
;
131
typedef
const_reverse_iterator
reverse_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.
135
typedef
base_type::_Node_citer<node, leaf, head, inode, const_iterator, iterator, _Alloc>
node_const_iterator
;
136
137
typedef
node_const_iterator
node_iterator
;
138
139
/// Type for node update.
140
typedef
Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc>
node_update
;
141
142
typedef
null_node_update<node_const_iterator, node_const_iterator, _ATraits, _Alloc>
*
null_node_update_pointer
;
143
};
144
145
}
// namespace detail
146
}
// namespace __gnu_pbds
147
148
#endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
include
ext
pb_ds
detail
pat_trie_
traits.hpp
Generated by
1.8.3.1