libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2007, 2009 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 <string> 00045 #include <ext/pb_ds/detail/type_utils.hpp> 00046 #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp> 00047 00048 namespace __gnu_pbds 00049 { 00050 // A null node updator, indicating that no node updates are required. 00051 template<typename Const_Node_Iterator, 00052 typename Node_Iterator, 00053 typename E_Access_Traits, 00054 typename Allocator> 00055 struct null_trie_node_update 00056 { }; 00057 00058 #define PB_DS_CLASS_T_DEC \ 00059 template<typename String, typename String::value_type Min_E_Val, typename String::value_type Max_E_Val, bool Reverse, typename Allocator> 00060 00061 #define PB_DS_CLASS_C_DEC \ 00062 string_trie_e_access_traits<String, Min_E_Val,Max_E_Val,Reverse,Allocator> 00063 00064 // Element access traits for string types. 00065 template<typename String = std::string, 00066 typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min, 00067 typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max, 00068 bool Reverse = false, 00069 typename Allocator = std::allocator<char> > 00070 struct string_trie_e_access_traits 00071 { 00072 public: 00073 typedef typename Allocator::size_type size_type; 00074 typedef String key_type; 00075 typedef typename Allocator::template rebind<key_type>::other key_rebind; 00076 typedef typename key_rebind::const_reference const_key_reference; 00077 00078 enum 00079 { 00080 reverse = Reverse 00081 }; 00082 00083 // Element const iterator type. 00084 typedef typename detail::__conditional_type<Reverse, typename String::const_reverse_iterator, typename String::const_iterator>::__type const_iterator; 00085 00086 // Element type. 00087 typedef typename std::iterator_traits<const_iterator>::value_type e_type; 00088 00089 enum 00090 { 00091 min_e_val = Min_E_Val, 00092 max_e_val = Max_E_Val, 00093 max_size = max_e_val - min_e_val + 1 00094 }; 00095 PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2); 00096 00097 // Returns a const_iterator to the first element of 00098 // const_key_reference agumnet. 00099 inline static const_iterator 00100 begin(const_key_reference); 00101 00102 // Returns a const_iterator to the after-last element of 00103 // const_key_reference argument. 00104 inline static const_iterator 00105 end(const_key_reference); 00106 00107 // Maps an element to a position. 00108 inline static size_type 00109 e_pos(e_type e); 00110 00111 private: 00112 00113 inline static const_iterator 00114 begin_imp(const_key_reference, detail::false_type); 00115 00116 inline static const_iterator 00117 begin_imp(const_key_reference, detail::true_type); 00118 00119 inline static const_iterator 00120 end_imp(const_key_reference, detail::false_type); 00121 00122 inline static const_iterator 00123 end_imp(const_key_reference, detail::true_type); 00124 00125 static detail::integral_constant<int, Reverse> s_rev_ind; 00126 }; 00127 00128 #include <ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp> 00129 00130 #undef PB_DS_CLASS_T_DEC 00131 #undef PB_DS_CLASS_C_DEC 00132 00133 #define PB_DS_CLASS_T_DEC \ 00134 template<typename Const_Node_Iterator,typename Node_Iterator,class E_Access_Traits, typename Allocator> 00135 00136 #define PB_DS_CLASS_C_DEC \ 00137 trie_prefix_search_node_update<Const_Node_Iterator, Node_Iterator, E_Access_Traits,Allocator> 00138 00139 #define PB_DS_BASE_C_DEC \ 00140 detail::trie_policy_base<Const_Node_Iterator,Node_Iterator,E_Access_Traits, Allocator> 00141 00142 // A node updator that allows tries to be searched for the range of 00143 // values that match a certain prefix. 00144 template<typename Const_Node_Iterator, 00145 typename Node_Iterator, 00146 typename E_Access_Traits, 00147 typename Allocator> 00148 class trie_prefix_search_node_update : private PB_DS_BASE_C_DEC 00149 { 00150 private: 00151 typedef PB_DS_BASE_C_DEC base_type; 00152 00153 public: 00154 typedef typename base_type::key_type key_type; 00155 typedef typename base_type::const_key_reference const_key_reference; 00156 00157 // Element access traits. 00158 typedef E_Access_Traits e_access_traits; 00159 00160 // Const element iterator. 00161 typedef typename e_access_traits::const_iterator const_e_iterator; 00162 00163 // Allocator type. 00164 typedef Allocator allocator_type; 00165 00166 // Size type. 00167 typedef typename allocator_type::size_type size_type; 00168 typedef detail::null_node_metadata metadata_type; 00169 typedef Const_Node_Iterator const_node_iterator; 00170 typedef Node_Iterator node_iterator; 00171 typedef typename const_node_iterator::value_type const_iterator; 00172 typedef typename node_iterator::value_type iterator; 00173 00174 // Finds the const iterator range corresponding to all values 00175 // whose prefixes match r_key. 00176 std::pair<const_iterator, const_iterator> 00177 prefix_range(const_key_reference) const; 00178 00179 // Finds the iterator range corresponding to all values whose 00180 // prefixes match r_key. 00181 std::pair<iterator, iterator> 00182 prefix_range(const_key_reference); 00183 00184 // Finds the const iterator range corresponding to all values 00185 // whose prefixes match [b, e). 00186 std::pair<const_iterator, const_iterator> 00187 prefix_range(const_e_iterator, const_e_iterator) const; 00188 00189 // Finds the iterator range corresponding to all values whose 00190 // prefixes match [b, e). 00191 std::pair<iterator, iterator> 00192 prefix_range(const_e_iterator, const_e_iterator); 00193 00194 protected: 00195 // Called to update a node's metadata. 00196 inline void 00197 operator()(node_iterator node_it, const_node_iterator end_nd_it) const; 00198 00199 private: 00200 // Returns the const iterator associated with the just-after last element. 00201 virtual const_iterator 00202 end() const = 0; 00203 00204 // Returns the iterator associated with the just-after last element. 00205 virtual iterator 00206 end() = 0; 00207 00208 // Returns the const_node_iterator associated with the trie's root node. 00209 virtual const_node_iterator 00210 node_begin() const = 0; 00211 00212 // Returns the node_iterator associated with the trie's root node. 00213 virtual node_iterator 00214 node_begin() = 0; 00215 00216 // Returns the const_node_iterator associated with a just-after leaf node. 00217 virtual const_node_iterator 00218 node_end() const = 0; 00219 00220 // Returns the node_iterator associated with a just-after leaf node. 00221 virtual node_iterator 00222 node_end() = 0; 00223 00224 // Access to the cmp_fn object. 00225 virtual const e_access_traits& 00226 get_e_access_traits() const = 0; 00227 00228 node_iterator 00229 next_child(node_iterator, const_e_iterator, const_e_iterator, 00230 node_iterator, const e_access_traits&); 00231 }; 00232 00233 #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp> 00234 00235 #undef PB_DS_CLASS_C_DEC 00236 00237 #define PB_DS_CLASS_C_DEC \ 00238 trie_order_statistics_node_update<Const_Node_Iterator, Node_Iterator,E_Access_Traits, Allocator> 00239 00240 // Functor updating ranks of entrees. 00241 template<typename Const_Node_Iterator, 00242 typename Node_Iterator, 00243 typename E_Access_Traits, 00244 typename Allocator> 00245 class trie_order_statistics_node_update : private PB_DS_BASE_C_DEC 00246 { 00247 private: 00248 typedef PB_DS_BASE_C_DEC base_type; 00249 00250 public: 00251 typedef E_Access_Traits e_access_traits; 00252 typedef typename e_access_traits::const_iterator const_e_iterator; 00253 typedef Allocator allocator_type; 00254 typedef typename allocator_type::size_type size_type; 00255 typedef typename base_type::key_type key_type; 00256 typedef typename base_type::const_key_reference const_key_reference; 00257 00258 typedef size_type metadata_type; 00259 typedef Const_Node_Iterator const_node_iterator; 00260 typedef Node_Iterator node_iterator; 00261 typedef typename const_node_iterator::value_type const_iterator; 00262 typedef typename node_iterator::value_type iterator; 00263 00264 // Finds an entry by __order. Returns a const_iterator to the 00265 // entry with the __order order, or a const_iterator to the 00266 // container object's end if order is at least the size of the 00267 // container object. 00268 inline const_iterator 00269 find_by_order(size_type) const; 00270 00271 // Finds an entry by __order. Returns an iterator to the entry 00272 // with the __order order, or an iterator to the container 00273 // object's end if order is at least the size of the container 00274 // object. 00275 inline iterator 00276 find_by_order(size_type); 00277 00278 // Returns the order of a key within a sequence. For exapmle, if 00279 // r_key is the smallest key, this method will return 0; if r_key 00280 // is a key between the smallest and next key, this method will 00281 // return 1; if r_key is a key larger than the largest key, this 00282 // method will return the size of r_c. 00283 inline size_type 00284 order_of_key(const_key_reference) const; 00285 00286 // Returns the order of a prefix within a sequence. For exapmle, 00287 // if [b, e] is the smallest prefix, this method will return 0; if 00288 // r_key is a key between the smallest and next key, this method 00289 // will return 1; if r_key is a key larger than the largest key, 00290 // this method will return the size of r_c. 00291 inline size_type 00292 order_of_prefix(const_e_iterator, const_e_iterator) const; 00293 00294 private: 00295 typedef typename base_type::const_reference const_reference; 00296 typedef typename base_type::const_pointer const_pointer; 00297 00298 typedef typename Allocator::template rebind<metadata_type>::other metadata_rebind; 00299 typedef typename metadata_rebind::const_reference const_metadata_reference; 00300 typedef typename metadata_rebind::reference metadata_reference; 00301 00302 // Returns true if the container is empty. 00303 virtual bool 00304 empty() const = 0; 00305 00306 // Returns the iterator associated with the trie's first element. 00307 virtual iterator 00308 begin() = 0; 00309 00310 // Returns the iterator associated with the trie's 00311 // just-after-last element. 00312 virtual iterator 00313 end() = 0; 00314 00315 // Returns the const_node_iterator associated with the trie's root node. 00316 virtual const_node_iterator 00317 node_begin() const = 0; 00318 00319 // Returns the node_iterator associated with the trie's root node. 00320 virtual node_iterator 00321 node_begin() = 0; 00322 00323 // Returns the const_node_iterator associated with a just-after 00324 // leaf node. 00325 virtual const_node_iterator 00326 node_end() const = 0; 00327 00328 // Returns the node_iterator associated with a just-after leaf node. 00329 virtual node_iterator 00330 node_end() = 0; 00331 00332 // Access to the cmp_fn object. 00333 virtual e_access_traits& 00334 get_e_access_traits() = 0; 00335 00336 protected: 00337 // Updates the rank of a node through a node_iterator node_it; 00338 // end_nd_it is the end node iterator. 00339 inline void 00340 operator()(node_iterator, const_node_iterator) const; 00341 00342 // Destructor. 00343 virtual 00344 ~trie_order_statistics_node_update(); 00345 }; 00346 00347 #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp> 00348 00349 #undef PB_DS_CLASS_T_DEC 00350 #undef PB_DS_CLASS_C_DEC 00351 #undef PB_DS_BASE_C_DEC 00352 00353 } // namespace __gnu_pbds 00354 00355 #endif