1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2009 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 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_/node_base.hpp> 45 #include <ext/pb_ds/detail/pat_trie_/head.hpp> 46 #include <ext/pb_ds/detail/pat_trie_/leaf.hpp> 47 #include <ext/pb_ds/detail/pat_trie_/internal_node.hpp> 48 #include <ext/pb_ds/detail/pat_trie_/point_iterators.hpp> 49 #include <ext/pb_ds/detail/pat_trie_/node_iterators.hpp> 50 #include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp> 51 52 namespace __gnu_pbds 53 { 54 namespace detail 55 { 56 57 template<typename Key, 58 typename Mapped, 59 class E_Access_Traits, 60 template<typename Const_Node_Iterator, 61 class Node_Iterator, 62 class Cmp_Fn_, 63 class Allocator_> 64 class Node_Update, 65 class Allocator> 66 struct trie_traits< 67 Key, 68 Mapped, 69 E_Access_Traits, 70 Node_Update, 71 pat_trie_tag, 72 Allocator> 73 { 74 private: 75 typedef types_traits< Key, Mapped, Allocator, false> type_traits; 76 77 public: 78 typedef 79 typename trie_node_metadata_selector< 80 Key, 81 Mapped, 82 E_Access_Traits, 83 Node_Update, 84 Allocator>::type 85 metadata_type; 86 87 typedef E_Access_Traits e_access_traits; 88 89 typedef 90 __gnu_pbds::detail::synth_e_access_traits< 91 type_traits, 92 false, 93 e_access_traits> 94 synth_e_access_traits; 95 96 typedef 97 pat_trie_node_base< 98 type_traits, 99 synth_e_access_traits, 100 metadata_type, 101 Allocator> 102 node; 103 104 typedef 105 pat_trie_leaf< 106 type_traits, 107 synth_e_access_traits, 108 metadata_type, 109 Allocator> 110 leaf; 111 112 typedef 113 pat_trie_head< 114 type_traits, 115 synth_e_access_traits, 116 metadata_type, 117 Allocator> 118 head; 119 120 typedef 121 pat_trie_internal_node< 122 type_traits, 123 synth_e_access_traits, 124 metadata_type, 125 Allocator> 126 internal_node; 127 128 typedef 129 pat_trie_const_it_< 130 type_traits, 131 node, 132 leaf, 133 head, 134 internal_node, 135 true, 136 Allocator> 137 const_iterator; 138 139 typedef 140 pat_trie_it_< 141 type_traits, 142 node, 143 leaf, 144 head, 145 internal_node, 146 true, 147 Allocator> 148 iterator; 149 150 typedef 151 pat_trie_const_it_< 152 type_traits, 153 node, 154 leaf, 155 head, 156 internal_node, 157 false, 158 Allocator> 159 const_reverse_iterator; 160 161 typedef 162 pat_trie_it_< 163 type_traits, 164 node, 165 leaf, 166 head, 167 internal_node, 168 false, 169 Allocator> 170 reverse_iterator; 171 172 typedef 173 pat_trie_const_node_it_< 174 node, 175 leaf, 176 head, 177 internal_node, 178 const_iterator, 179 iterator, 180 synth_e_access_traits, 181 Allocator> 182 const_node_iterator; 183 184 typedef 185 pat_trie_node_it_< 186 node, 187 leaf, 188 head, 189 internal_node, 190 const_iterator, 191 iterator, 192 synth_e_access_traits, 193 Allocator> 194 node_iterator; 195 196 typedef 197 Node_Update< 198 const_node_iterator, 199 node_iterator, 200 E_Access_Traits, 201 Allocator> 202 node_update; 203 204 typedef 205 __gnu_pbds::null_trie_node_update< 206 const_node_iterator, 207 node_iterator, 208 E_Access_Traits, 209 Allocator>* 210 null_node_update_pointer; 211 }; 212 213 template<typename Key, 214 class E_Access_Traits, 215 template<typename Const_Node_Iterator, 216 class Node_Iterator, 217 class Cmp_Fn_, 218 class Allocator_> 219 class Node_Update, 220 class Allocator> 221 struct trie_traits< 222 Key, 223 null_mapped_type, 224 E_Access_Traits, 225 Node_Update, 226 pat_trie_tag, 227 Allocator> 228 { 229 private: 230 typedef 231 types_traits< 232 Key, 233 null_mapped_type, 234 Allocator, 235 false> 236 type_traits; 237 238 public: 239 typedef 240 typename trie_node_metadata_selector< 241 Key, 242 null_mapped_type, 243 E_Access_Traits, 244 Node_Update, 245 Allocator>::type 246 metadata_type; 247 248 typedef E_Access_Traits e_access_traits; 249 250 typedef 251 __gnu_pbds::detail::synth_e_access_traits< 252 type_traits, 253 true, 254 e_access_traits> 255 synth_e_access_traits; 256 257 typedef 258 pat_trie_node_base< 259 type_traits, 260 synth_e_access_traits, 261 metadata_type, 262 Allocator> 263 node; 264 265 typedef 266 pat_trie_leaf< 267 type_traits, 268 synth_e_access_traits, 269 metadata_type, 270 Allocator> 271 leaf; 272 273 typedef 274 pat_trie_head< 275 type_traits, 276 synth_e_access_traits, 277 metadata_type, 278 Allocator> 279 head; 280 281 typedef 282 pat_trie_internal_node< 283 type_traits, 284 synth_e_access_traits, 285 metadata_type, 286 Allocator> 287 internal_node; 288 289 typedef 290 pat_trie_const_it_< 291 type_traits, 292 node, 293 leaf, 294 head, 295 internal_node, 296 true, 297 Allocator> 298 const_iterator; 299 300 typedef const_iterator iterator; 301 302 typedef 303 pat_trie_const_it_< 304 type_traits, 305 node, 306 leaf, 307 head, 308 internal_node, 309 false, 310 Allocator> 311 const_reverse_iterator; 312 313 typedef const_reverse_iterator reverse_iterator; 314 315 typedef 316 pat_trie_const_node_it_< 317 node, 318 leaf, 319 head, 320 internal_node, 321 const_iterator, 322 iterator, 323 synth_e_access_traits, 324 Allocator> 325 const_node_iterator; 326 327 typedef const_node_iterator node_iterator; 328 329 typedef 330 Node_Update< 331 const_node_iterator, 332 node_iterator, 333 E_Access_Traits, 334 Allocator> 335 node_update; 336 337 typedef 338 __gnu_pbds::null_trie_node_update< 339 const_node_iterator, 340 const_node_iterator, 341 E_Access_Traits, 342 Allocator>* 343 null_node_update_pointer; 344 }; 345 346 } // namespace detail 347 } // namespace __gnu_pbds 348 349 #endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP 350 351
