libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp

   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
  58 namespace __gnu_pbds
  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       __gnu_pbds::detail::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       __gnu_pbds::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       __gnu_pbds::detail::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       __gnu_pbds::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 __gnu_pbds
 354
 355 #endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
 356