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 58namespace pb_ds 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 96 synth_e_access_traits< 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 211 pb_ds::null_trie_node_update< 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 257 synth_e_access_traits< 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 344 pb_ds::null_trie_node_update< 345 const_node_iterator, 346 const_node_iterator, 347 E_Access_Traits, 348 Allocator>* 349 null_node_update_pointer; 350 }; 351 352 } // namespace detail 353} // namespace pb_ds 354 355#endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP 356 357