libstdc++
trie_policy.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005-2013 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file trie_policy.hpp
00038  * Contains trie-related policies.
00039  */
00040 
00041 #ifndef PB_DS_TRIE_POLICY_HPP
00042 #define PB_DS_TRIE_POLICY_HPP
00043 
00044 #include <bits/c++config.h>
00045 #include <string>
00046 #include <ext/pb_ds/detail/type_utils.hpp>
00047 #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>
00048 
00049 namespace __gnu_pbds
00050 {
00051 #define PB_DS_CLASS_T_DEC \
00052   template<typename String, typename String::value_type Min_E_Val, \
00053        typename String::value_type Max_E_Val, bool Reverse, \
00054        typename _Alloc>
00055 
00056 #define PB_DS_CLASS_C_DEC \
00057   trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc>
00058 
00059   /**
00060    *  Element access traits for string types.
00061    *
00062    *  @tparam String            String type.
00063    *  @tparam Min_E_Val         Minimal element value.
00064    *  @tparam Max_E_Val         Maximum element value.
00065    *  @tparam Reverse           Reverse iteration should be used.
00066    *                            Default: false.
00067    *  @tparam _Alloc            Allocator type.
00068    */
00069   template<typename String = std::string,
00070        typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min,
00071        typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max,
00072        bool Reverse = false,
00073        typename _Alloc = std::allocator<char> >
00074   struct trie_string_access_traits
00075   {
00076   public:
00077     typedef typename _Alloc::size_type            size_type;
00078     typedef String                    key_type;
00079     typedef typename _Alloc::template rebind<key_type>    __rebind_k;
00080     typedef typename __rebind_k::other::const_reference   key_const_reference;
00081 
00082     enum
00083       {
00084     reverse = Reverse
00085       };
00086 
00087     /// Element const iterator type.
00088     typedef typename detail::__conditional_type<Reverse, \
00089                typename String::const_reverse_iterator, \
00090                typename String::const_iterator>::__type const_iterator;
00091 
00092     /// Element type.
00093     typedef typename std::iterator_traits<const_iterator>::value_type e_type;
00094 
00095     enum
00096       {
00097     min_e_val = Min_E_Val,
00098     max_e_val = Max_E_Val,
00099     max_size = max_e_val - min_e_val + 1
00100       };
00101     PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
00102 
00103     /// Returns a const_iterator to the first element of
00104     /// key_const_reference agumnet.
00105     inline static const_iterator
00106     begin(key_const_reference);
00107 
00108     /// Returns a const_iterator to the after-last element of
00109     /// key_const_reference argument.
00110     inline static const_iterator
00111     end(key_const_reference);
00112 
00113     /// Maps an element to a position.
00114     inline static size_type
00115     e_pos(e_type e);
00116 
00117   private:
00118     inline static const_iterator
00119     begin_imp(key_const_reference, detail::false_type);
00120 
00121     inline static const_iterator
00122     begin_imp(key_const_reference, detail::true_type);
00123 
00124     inline static const_iterator
00125     end_imp(key_const_reference, detail::false_type);
00126 
00127     inline static const_iterator
00128     end_imp(key_const_reference, detail::true_type);
00129 
00130     static detail::integral_constant<int, Reverse> s_rev_ind;
00131   };
00132 
00133 #include <ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp>
00134 
00135 #undef PB_DS_CLASS_T_DEC
00136 #undef PB_DS_CLASS_C_DEC
00137 
00138 #define PB_DS_CLASS_T_DEC \
00139   template<typename Node_CItr,typename Node_Itr, \
00140        typename _ATraits, typename _Alloc>
00141 
00142 #define PB_DS_CLASS_C_DEC \
00143   trie_prefix_search_node_update<Node_CItr, Node_Itr, \
00144                  _ATraits,_Alloc>
00145 
00146 #define PB_DS_TRIE_POLICY_BASE \
00147   detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc>
00148 
00149   /// A node updator that allows tries to be searched for the range of
00150   /// values that match a certain prefix.
00151   template<typename Node_CItr,
00152        typename Node_Itr,
00153        typename _ATraits,
00154        typename _Alloc>
00155   class trie_prefix_search_node_update : private PB_DS_TRIE_POLICY_BASE
00156   {
00157   private:
00158     typedef PB_DS_TRIE_POLICY_BASE              base_type;
00159 
00160   public:
00161     typedef typename base_type::key_type        key_type;
00162     typedef typename base_type::key_const_reference     key_const_reference;
00163 
00164     /// Element access traits.
00165     typedef _ATraits                access_traits;
00166 
00167     /// Const element iterator.
00168     typedef typename access_traits::const_iterator  a_const_iterator;
00169 
00170     /// _Alloc type.
00171     typedef _Alloc                      allocator_type;
00172 
00173     /// Size type.
00174     typedef typename allocator_type::size_type      size_type;
00175     typedef null_type                   metadata_type;
00176     typedef Node_Itr                    node_iterator;
00177     typedef Node_CItr                   node_const_iterator;
00178     typedef typename node_iterator::value_type      iterator;
00179     typedef typename node_const_iterator::value_type    const_iterator;
00180 
00181     /// Finds the const iterator range corresponding to all values
00182     /// whose prefixes match r_key.
00183     std::pair<const_iterator, const_iterator>
00184     prefix_range(key_const_reference) const;
00185 
00186     /// Finds the iterator range corresponding to all values whose
00187     /// prefixes match r_key.
00188     std::pair<iterator, iterator>
00189     prefix_range(key_const_reference);
00190 
00191     /// Finds the const iterator range corresponding to all values
00192     /// whose prefixes match [b, e).
00193     std::pair<const_iterator, const_iterator>
00194     prefix_range(a_const_iterator, a_const_iterator) const;
00195 
00196     /// Finds the iterator range corresponding to all values whose
00197     /// prefixes match [b, e).
00198     std::pair<iterator, iterator>
00199     prefix_range(a_const_iterator, a_const_iterator);
00200 
00201   protected:
00202     /// Called to update a node's metadata.
00203     inline void
00204     operator()(node_iterator node_it, node_const_iterator end_nd_it) const;
00205 
00206   private:
00207     node_iterator
00208     next_child(node_iterator, a_const_iterator, a_const_iterator,
00209            node_iterator, const access_traits&);
00210 
00211     /// Returns the const iterator associated with the just-after last element.
00212     virtual const_iterator
00213     end() const = 0;
00214 
00215     /// Returns the iterator associated with the just-after last element.
00216     virtual iterator
00217     end() = 0;
00218 
00219     /// Returns the node_const_iterator associated with the trie's root node.
00220     virtual node_const_iterator
00221     node_begin() const = 0;
00222 
00223     /// Returns the node_iterator associated with the trie's root node.
00224     virtual node_iterator
00225     node_begin() = 0;
00226 
00227     /// Returns the node_const_iterator associated with a just-after leaf node.
00228     virtual node_const_iterator
00229     node_end() const = 0;
00230 
00231     /// Returns the node_iterator associated with a just-after leaf node.
00232     virtual node_iterator
00233     node_end() = 0;
00234 
00235     /// Access to the cmp_fn object.
00236     virtual const access_traits&
00237     get_access_traits() const = 0;
00238   };
00239 
00240 #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp>
00241 
00242 #undef PB_DS_CLASS_C_DEC
00243 
00244 #define PB_DS_CLASS_C_DEC \
00245   trie_order_statistics_node_update<Node_CItr, Node_Itr, \
00246                     _ATraits, _Alloc>
00247 
00248   /// Functor updating ranks of entrees.
00249   template<typename Node_CItr,
00250        typename Node_Itr,
00251        typename _ATraits,
00252        typename _Alloc>
00253   class trie_order_statistics_node_update : private PB_DS_TRIE_POLICY_BASE
00254   {
00255   private:
00256     typedef PB_DS_TRIE_POLICY_BASE              base_type;
00257 
00258   public:
00259     typedef _ATraits                access_traits;
00260     typedef typename access_traits::const_iterator  a_const_iterator;
00261     typedef _Alloc                  allocator_type;
00262     typedef typename allocator_type::size_type      size_type;
00263     typedef typename base_type::key_type        key_type;
00264     typedef typename base_type::key_const_reference     key_const_reference;
00265 
00266     typedef size_type                   metadata_type;
00267     typedef Node_CItr                   node_const_iterator;
00268     typedef Node_Itr                    node_iterator;
00269     typedef typename node_const_iterator::value_type    const_iterator;
00270     typedef typename node_iterator::value_type      iterator;
00271 
00272     /// Finds an entry by __order. Returns a const_iterator to the
00273     /// entry with the __order order, or a const_iterator to the
00274     /// container object's end if order is at least the size of the
00275     /// container object.
00276     inline const_iterator
00277     find_by_order(size_type) const;
00278 
00279     /// Finds an entry by __order. Returns an iterator to the entry
00280     /// with the __order order, or an iterator to the container
00281     /// object's end if order is at least the size of the container
00282     /// object.
00283     inline iterator
00284     find_by_order(size_type);
00285 
00286     /// Returns the order of a key within a sequence. For exapmle, if
00287     /// r_key is the smallest key, this method will return 0; if r_key
00288     /// is a key between the smallest and next key, this method will
00289     /// return 1; if r_key is a key larger than the largest key, this
00290     /// method will return the size of r_c.
00291     inline size_type
00292     order_of_key(key_const_reference) const;
00293 
00294     /// Returns the order of a prefix within a sequence. For exapmle,
00295     /// if [b, e] is the smallest prefix, this method will return 0; if
00296     /// r_key is a key between the smallest and next key, this method
00297     /// will return 1; if r_key is a key larger than the largest key,
00298     /// this method will return the size of r_c.
00299     inline size_type
00300     order_of_prefix(a_const_iterator, a_const_iterator) const;
00301 
00302   protected:
00303     /// Updates the rank of a node through a node_iterator node_it;
00304     /// end_nd_it is the end node iterator.
00305     inline void
00306     operator()(node_iterator, node_const_iterator) const;
00307 
00308   private:
00309     typedef typename base_type::const_reference     const_reference;
00310     typedef typename base_type::const_pointer       const_pointer;
00311 
00312     typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
00313     typedef typename __rebind_m::other          __rebind_ma;
00314     typedef typename __rebind_ma::const_reference      metadata_const_reference;
00315     typedef typename __rebind_ma::reference         metadata_reference;
00316 
00317     /// Returns true if the container is empty.
00318     virtual bool
00319     empty() const = 0;
00320 
00321     /// Returns the iterator associated with the trie's first element.
00322     virtual iterator
00323     begin() = 0;
00324 
00325     /// Returns the iterator associated with the trie's
00326     /// just-after-last element.
00327     virtual iterator
00328     end() = 0;
00329 
00330     /// Returns the node_const_iterator associated with the trie's root node.
00331     virtual node_const_iterator
00332     node_begin() const = 0;
00333 
00334     /// Returns the node_iterator associated with the trie's root node.
00335     virtual node_iterator
00336     node_begin() = 0;
00337 
00338     /// Returns the node_const_iterator associated with a just-after
00339     /// leaf node.
00340     virtual node_const_iterator
00341     node_end() const = 0;
00342 
00343     /// Returns the node_iterator associated with a just-after leaf node.
00344     virtual node_iterator
00345     node_end() = 0;
00346 
00347     /// Access to the cmp_fn object.
00348     virtual access_traits&
00349     get_access_traits() = 0;
00350   };
00351 
00352 #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp>
00353 
00354 #undef PB_DS_CLASS_T_DEC
00355 #undef PB_DS_CLASS_C_DEC
00356 #undef PB_DS_TRIE_POLICY_BASE
00357 
00358 } // namespace __gnu_pbds
00359 
00360 #endif