]>
Commit | Line | Data |
---|---|---|
36fed23c | 1 | // -*- C++ -*- |
2 | ||
f1717362 | 3 | // Copyright (C) 2005-2016 Free Software Foundation, Inc. |
36fed23c | 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 | |
6bc9506f | 8 | // Foundation; either version 3, or (at your option) any later |
36fed23c | 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 | ||
6bc9506f | 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/>. | |
36fed23c | 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 | /** | |
4f4a327e | 37 | * @file pat_trie_/traits.hpp |
36fed23c | 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 | ||
4f4a327e | 44 | #include <ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp> |
45 | #include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp> | |
36fed23c | 46 | |
b34535d7 | 47 | namespace __gnu_pbds |
36fed23c | 48 | { |
49 | namespace detail | |
50 | { | |
4f4a327e | 51 | /// Specialization. |
3f2eba6f | 52 | /// @ingroup traits |
36fed23c | 53 | template<typename Key, |
54 | typename Mapped, | |
4f4a327e | 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> | |
36fed23c | 63 | { |
64 | private: | |
4f4a327e | 65 | typedef pat_trie_base base_type; |
66 | typedef types_traits<Key, Mapped, _Alloc, false> type_traits; | |
36fed23c | 67 | |
68 | public: | |
4f4a327e | 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; | |
36fed23c | 72 | |
3f2eba6f | 73 | /// Type for synthesized traits. |
4f4a327e | 74 | typedef __gnu_pbds::detail::synth_access_traits<type_traits, false, access_traits> synth_access_traits; |
36fed23c | 75 | |
4f4a327e | 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; | |
36fed23c | 80 | |
4f4a327e | 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; | |
36fed23c | 85 | |
3f2eba6f | 86 | /// This is an iterator to an iterator: it iterates over nodes, |
87 | /// and de-referencing it returns one of the tree's iterators. | |
4f4a327e | 88 | typedef base_type::_Node_citer<node, leaf, head, inode, const_iterator, iterator, _Alloc> node_const_iterator; |
36fed23c | 89 | |
4f4a327e | 90 | typedef base_type::_Node_iter<node, leaf, head, inode, const_iterator, iterator, _Alloc> node_iterator; |
36fed23c | 91 | |
3f2eba6f | 92 | /// Type for node update. |
4f4a327e | 93 | typedef Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc> node_update; |
36fed23c | 94 | |
4f4a327e | 95 | typedef null_node_update<node_const_iterator, node_iterator, _ATraits, _Alloc>* null_node_update_pointer; |
36fed23c | 96 | }; |
97 | ||
3f2eba6f | 98 | |
4f4a327e | 99 | /// Specialization. |
3f2eba6f | 100 | /// @ingroup traits |
36fed23c | 101 | template<typename Key, |
4f4a327e | 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> | |
36fed23c | 110 | { |
111 | private: | |
4f4a327e | 112 | typedef pat_trie_base base_type; |
113 | typedef types_traits<Key, null_type, _Alloc, false> type_traits; | |
36fed23c | 114 | |
115 | public: | |
4f4a327e | 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; | |
3f2eba6f | 119 | |
120 | /// Type for synthesized traits. | |
4f4a327e | 121 | typedef __gnu_pbds::detail::synth_access_traits<type_traits, true, access_traits> synth_access_traits; |
36fed23c | 122 | |
4f4a327e | 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; | |
36fed23c | 127 | |
4f4a327e | 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; | |
36fed23c | 132 | |
3f2eba6f | 133 | /// This is an iterator to an iterator: it iterates over nodes, |
134 | /// and de-referencing it returns one of the tree's iterators. | |
4f4a327e | 135 | typedef base_type::_Node_citer<node, leaf, head, inode, const_iterator, iterator, _Alloc> node_const_iterator; |
36fed23c | 136 | |
4f4a327e | 137 | typedef node_const_iterator node_iterator; |
36fed23c | 138 | |
3f2eba6f | 139 | /// Type for node update. |
4f4a327e | 140 | typedef Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc> node_update; |
36fed23c | 141 | |
4f4a327e | 142 | typedef null_node_update<node_const_iterator, node_const_iterator, _ATraits, _Alloc>* null_node_update_pointer; |
36fed23c | 143 | }; |
144 | ||
145 | } // namespace detail | |
b34535d7 | 146 | } // namespace __gnu_pbds |
36fed23c | 147 | |
148 | #endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP |