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