libstdc++-v3/include/ext/pb_ds/trie_policy.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the terms
   8 // of the GNU General Public License as published by the Free Software
   9 // Foundation; either version 3, or (at your option) any later
  10 // version.
  11
  12 // This library is distributed in the hope that it will be useful, but
  13 // WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 // General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  27
  28 // Permission to use, copy, modify, sell, and distribute this software
  29 // is hereby granted without fee, provided that the above copyright
  30 // notice appears in all copies, and that both that copyright notice
  31 // and this permission notice appear in supporting documentation. None
  32 // of the above authors, nor IBM Haifa Research Laboratories, make any
  33 // representation about the suitability of this software for any
  34 // purpose. It is provided "as is" without express or implied
  35 // warranty.
  36
  37 /**
  38  * @file trie_policy.hpp
  39  * Contains trie-related policies.
  40  */
  41
  42 #ifndef PB_DS_TRIE_POLICY_HPP
  43 #define PB_DS_TRIE_POLICY_HPP
  44
  45 #include <bits/c++config.h>
  46 #include <string>
  47 #include <ext/pb_ds/detail/type_utils.hpp>
  48 #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>
  49
  50 namespace __gnu_pbds
  51 {
  52 #define PB_DS_CLASS_T_DEC \
  53   template<typename String, typename String::value_type Min_E_Val, \
  54            typename String::value_type Max_E_Val, bool Reverse, \
  55            typename _Alloc>
  56
  57 #define PB_DS_CLASS_C_DEC \
  58   trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc>
  59
  60   /// Element access traits for string types.
  61   template<typename String = std::string,
  62            typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min,
  63            typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max,
  64            bool Reverse = false,
  65            typename _Alloc = std::allocator<char> >
  66   struct trie_string_access_traits
  67   {
  68   public:
  69     typedef typename _Alloc::size_type                    size_type;
  70     typedef String                                        key_type;
  71     typedef typename _Alloc::template rebind<key_type>    __rebind_k;
  72     typedef typename __rebind_k::other::const_reference   key_const_reference;
  73
  74     enum
  75       {
  76         reverse = Reverse
  77       };
  78
  79     // Element const iterator type.
  80     typedef typename detail::__conditional_type<Reverse, \
  81                        typename String::const_reverse_iterator, \
  82                        typename String::const_iterator>::__type const_iterator;
  83
  84     // Element type.
  85     typedef typename std::iterator_traits<const_iterator>::value_type e_type;
  86
  87     enum
  88       {
  89         min_e_val = Min_E_Val,
  90         max_e_val = Max_E_Val,
  91         max_size = max_e_val - min_e_val + 1
  92       };
  93     PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
  94
  95     // Returns a const_iterator to the first element of
  96     // key_const_reference agumnet.
  97     inline static const_iterator
  98     begin(key_const_reference);
  99
 100     // Returns a const_iterator to the after-last element of
 101     // key_const_reference argument.
 102     inline static const_iterator
 103     end(key_const_reference);
 104
 105     // Maps an element to a position.
 106     inline static size_type
 107     e_pos(e_type e);
 108
 109   private:
 110     inline static const_iterator
 111     begin_imp(key_const_reference, detail::false_type);
 112
 113     inline static const_iterator
 114     begin_imp(key_const_reference, detail::true_type);
 115
 116     inline static const_iterator
 117     end_imp(key_const_reference, detail::false_type);
 118
 119     inline static const_iterator
 120     end_imp(key_const_reference, detail::true_type);
 121
 122     static detail::integral_constant<int, Reverse> s_rev_ind;
 123   };
 124
 125 #include <ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp>
 126
 127 #undef PB_DS_CLASS_T_DEC
 128 #undef PB_DS_CLASS_C_DEC
 129
 130 #define PB_DS_CLASS_T_DEC \
 131   template<typename Node_CItr,typename Node_Itr, \
 132            typename _ATraits, typename _Alloc>
 133
 134 #define PB_DS_CLASS_C_DEC \
 135   trie_prefix_search_node_update<Node_CItr, Node_Itr, \
 136                                  _ATraits,_Alloc>
 137
 138 #define PB_DS_TRIE_POLICY_BASE \
 139   detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc>
 140
 141   /// A node updator that allows tries to be searched for the range of
 142   /// values that match a certain prefix.
 143   template<typename Node_CItr,
 144            typename Node_Itr,
 145            typename _ATraits,
 146            typename _Alloc>
 147   class trie_prefix_search_node_update : private PB_DS_TRIE_POLICY_BASE
 148   {
 149   private:
 150     typedef PB_DS_TRIE_POLICY_BASE                      base_type;
 151
 152   public:
 153     typedef typename base_type::key_type                key_type;
 154     typedef typename base_type::key_const_reference     key_const_reference;
 155
 156     // Element access traits.
 157     typedef _ATraits                            access_traits;
 158
 159     // Const element iterator.
 160     typedef typename access_traits::const_iterator      a_const_iterator;
 161
 162     // _Alloc type.
 163     typedef _Alloc                                      allocator_type;
 164
 165     // Size type.
 166     typedef typename allocator_type::size_type          size_type;
 167     typedef null_type                                   metadata_type;
 168     typedef Node_Itr                                    node_iterator;
 169     typedef Node_CItr                                   node_const_iterator;
 170     typedef typename node_iterator::value_type          iterator;
 171     typedef typename node_const_iterator::value_type    const_iterator;
 172
 173     // Finds the const iterator range corresponding to all values
 174     // whose prefixes match r_key.
 175     std::pair<const_iterator, const_iterator>
 176     prefix_range(key_const_reference) const;
 177
 178     // Finds the iterator range corresponding to all values whose
 179     // prefixes match r_key.
 180     std::pair<iterator, iterator>
 181     prefix_range(key_const_reference);
 182
 183     // Finds the const iterator range corresponding to all values
 184     // whose prefixes match [b, e).
 185     std::pair<const_iterator, const_iterator>
 186     prefix_range(a_const_iterator, a_const_iterator) const;
 187
 188     // Finds the iterator range corresponding to all values whose
 189     // prefixes match [b, e).
 190     std::pair<iterator, iterator>
 191     prefix_range(a_const_iterator, a_const_iterator);
 192
 193   protected:
 194     // Called to update a node's metadata.
 195     inline void
 196     operator()(node_iterator node_it, node_const_iterator end_nd_it) const;
 197
 198   private:
 199     node_iterator
 200     next_child(node_iterator, a_const_iterator, a_const_iterator,
 201                node_iterator, const access_traits&);
 202
 203     // Returns the const iterator associated with the just-after last element.
 204     virtual const_iterator
 205     end() const = 0;
 206
 207     // Returns the iterator associated with the just-after last element.
 208     virtual iterator
 209     end() = 0;
 210
 211     // Returns the node_const_iterator associated with the trie's root node.
 212     virtual node_const_iterator
 213     node_begin() const = 0;
 214
 215     // Returns the node_iterator associated with the trie's root node.
 216     virtual node_iterator
 217     node_begin() = 0;
 218
 219     // Returns the node_const_iterator associated with a just-after leaf node.
 220     virtual node_const_iterator
 221     node_end() const = 0;
 222
 223     // Returns the node_iterator associated with a just-after leaf node.
 224     virtual node_iterator
 225     node_end() = 0;
 226
 227     // Access to the cmp_fn object.
 228     virtual const access_traits&
 229     get_access_traits() const = 0;
 230   };
 231
 232 #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp>
 233
 234 #undef PB_DS_CLASS_C_DEC
 235
 236 #define PB_DS_CLASS_C_DEC \
 237   trie_order_statistics_node_update<Node_CItr, Node_Itr, \
 238                                     _ATraits, _Alloc>
 239
 240   /// Functor updating ranks of entrees.
 241   template<typename Node_CItr,
 242            typename Node_Itr,
 243            typename _ATraits,
 244            typename _Alloc>
 245   class trie_order_statistics_node_update : private PB_DS_TRIE_POLICY_BASE
 246   {
 247   private:
 248     typedef PB_DS_TRIE_POLICY_BASE                      base_type;
 249
 250   public:
 251     typedef _ATraits                            access_traits;
 252     typedef typename access_traits::const_iterator      a_const_iterator;
 253     typedef _Alloc                                      allocator_type;
 254     typedef typename allocator_type::size_type          size_type;
 255     typedef typename base_type::key_type                key_type;
 256     typedef typename base_type::key_const_reference     key_const_reference;
 257
 258     typedef size_type                                   metadata_type;
 259     typedef Node_CItr                                   node_const_iterator;
 260     typedef Node_Itr                                    node_iterator;
 261     typedef typename node_const_iterator::value_type    const_iterator;
 262     typedef typename node_iterator::value_type          iterator;
 263
 264     // Finds an entry by __order. Returns a const_iterator to the
 265     // entry with the __order order, or a const_iterator to the
 266     // container object's end if order is at least the size of the
 267     // container object.
 268     inline const_iterator
 269     find_by_order(size_type) const;
 270
 271     // Finds an entry by __order. Returns an iterator to the entry
 272     // with the __order order, or an iterator to the container
 273     // object's end if order is at least the size of the container
 274     // object.
 275     inline iterator
 276     find_by_order(size_type);
 277
 278     // Returns the order of a key within a sequence. For exapmle, if
 279     // r_key is the smallest key, this method will return 0; if r_key
 280     // is a key between the smallest and next key, this method will
 281     // return 1; if r_key is a key larger than the largest key, this
 282     // method will return the size of r_c.
 283     inline size_type
 284     order_of_key(key_const_reference) const;
 285
 286     // Returns the order of a prefix within a sequence. For exapmle,
 287     // if [b, e] is the smallest prefix, this method will return 0; if
 288     // r_key is a key between the smallest and next key, this method
 289     // will return 1; if r_key is a key larger than the largest key,
 290     // this method will return the size of r_c.
 291     inline size_type
 292     order_of_prefix(a_const_iterator, a_const_iterator) const;
 293
 294   protected:
 295     // Updates the rank of a node through a node_iterator node_it;
 296     // end_nd_it is the end node iterator.
 297     inline void
 298     operator()(node_iterator, node_const_iterator) const;
 299
 300   private:
 301     typedef typename base_type::const_reference         const_reference;
 302     typedef typename base_type::const_pointer           const_pointer;
 303
 304     typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
 305     typedef typename __rebind_m::other                  __rebind_ma;
 306     typedef typename __rebind_ma::const_reference      metadata_const_reference;
 307     typedef typename __rebind_ma::reference             metadata_reference;
 308
 309     // Returns true if the container is empty.
 310     virtual bool
 311     empty() const = 0;
 312
 313     // Returns the iterator associated with the trie's first element.
 314     virtual iterator
 315     begin() = 0;
 316
 317     // Returns the iterator associated with the trie's
 318     // just-after-last element.
 319     virtual iterator
 320     end() = 0;
 321
 322     // Returns the node_const_iterator associated with the trie's root node.
 323     virtual node_const_iterator
 324     node_begin() const = 0;
 325
 326     // Returns the node_iterator associated with the trie's root node.
 327     virtual node_iterator
 328     node_begin() = 0;
 329
 330     // Returns the node_const_iterator associated with a just-after
 331     // leaf node.
 332     virtual node_const_iterator
 333     node_end() const = 0;
 334
 335     // Returns the node_iterator associated with a just-after leaf node.
 336     virtual node_iterator
 337     node_end() = 0;
 338
 339     // Access to the cmp_fn object.
 340     virtual access_traits&
 341     get_access_traits() = 0;
 342   };
 343
 344 #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp>
 345
 346 #undef PB_DS_CLASS_T_DEC
 347 #undef PB_DS_CLASS_C_DEC
 348 #undef PB_DS_TRIE_POLICY_BASE
 349
 350 } // namespace __gnu_pbds
 351
 352 #endif