libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005-2015 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