libstdc++
|
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