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