1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the terms 8 // of the GNU General Public License as published by the Free Software 9 // Foundation; either version 3, or (at your option) any later 10 // version. 11 12 // This library is distributed in the hope that it will be useful, but 13 // WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 // General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 27 28 // Permission to use, copy, modify, sell, and distribute this software 29 // is hereby granted without fee, provided that the above copyright 30 // notice appears in all copies, and that both that copyright notice 31 // and this permission notice appear in supporting documentation. None 32 // of the above authors, nor IBM Haifa Research Laboratories, make any 33 // representation about the suitability of this software for any 34 // purpose. It is provided "as is" without express or implied 35 // warranty. 36 37 /** 38 * @file trie_policy.hpp 39 * Contains trie-related policies. 40 */ 41 42 #ifndef PB_DS_TRIE_POLICY_HPP 43 #define PB_DS_TRIE_POLICY_HPP 44 45 #include <bits/c++config.h> 46 #include <string> 47 #include <ext/pb_ds/detail/type_utils.hpp> 48 #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp> 49 50 namespace __gnu_pbds 51 { 52 #define PB_DS_CLASS_T_DEC \ 53 template<typename String, typename String::value_type Min_E_Val, \ 54 typename String::value_type Max_E_Val, bool Reverse, \ 55 typename _Alloc> 56 57 #define PB_DS_CLASS_C_DEC \ 58 trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc> 59 60 /** 61 * Element access traits for string types. 62 * 63 * @tparam String String type. 64 * @tparam Min_E_Val Minimal element value. 65 * @tparam Max_E_Val Maximum element value. 66 * @tparam Reverse Reverse iteration should be used. 67 * Default: false. 68 * @tparam _Alloc Allocator type. 69 */ 70 template<typename String = std::string, 71 typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min, 72 typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max, 73 bool Reverse = false, 74 typename _Alloc = std::allocator<char> > 75 struct trie_string_access_traits 76 { 77 public: 78 typedef typename _Alloc::size_type size_type; 79 typedef String key_type; 80 typedef typename _Alloc::template rebind<key_type> __rebind_k; 81 typedef typename __rebind_k::other::const_reference key_const_reference; 82 83 enum 84 { 85 reverse = Reverse 86 }; 87 88 /// Element const iterator type. 89 typedef typename detail::__conditional_type<Reverse, \ 90 typename String::const_reverse_iterator, \ 91 typename String::const_iterator>::__type const_iterator; 92 93 /// Element type. 94 typedef typename std::iterator_traits<const_iterator>::value_type e_type; 95 96 enum 97 { 98 min_e_val = Min_E_Val, 99 max_e_val = Max_E_Val, 100 max_size = max_e_val - min_e_val + 1 101 }; 102 PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2); 103 104 /// Returns a const_iterator to the first element of 105 /// key_const_reference agumnet. 106 inline static const_iterator 107 begin(key_const_reference); 108 109 /// Returns a const_iterator to the after-last element of 110 /// key_const_reference argument. 111 inline static const_iterator 112 end(key_const_reference); 113 114 /// Maps an element to a position. 115 inline static size_type 116 e_pos(e_type e); 117 118 private: 119 inline static const_iterator 120 begin_imp(key_const_reference, detail::false_type); 121 122 inline static const_iterator 123 begin_imp(key_const_reference, detail::true_type); 124 125 inline static const_iterator 126 end_imp(key_const_reference, detail::false_type); 127 128 inline static const_iterator 129 end_imp(key_const_reference, detail::true_type); 130 131 static detail::integral_constant<int, Reverse> s_rev_ind; 132 }; 133 134 #include <ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp> 135 136 #undef PB_DS_CLASS_T_DEC 137 #undef PB_DS_CLASS_C_DEC 138 139 #define PB_DS_CLASS_T_DEC \ 140 template<typename Node_CItr,typename Node_Itr, \ 141 typename _ATraits, typename _Alloc> 142 143 #define PB_DS_CLASS_C_DEC \ 144 trie_prefix_search_node_update<Node_CItr, Node_Itr, \ 145 _ATraits,_Alloc> 146 147 #define PB_DS_TRIE_POLICY_BASE \ 148 detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc> 149 150 /// A node updator that allows tries to be searched for the range of 151 /// values that match a certain prefix. 152 template<typename Node_CItr, 153 typename Node_Itr, 154 typename _ATraits, 155 typename _Alloc> 156 class trie_prefix_search_node_update : private PB_DS_TRIE_POLICY_BASE 157 { 158 private: 159 typedef PB_DS_TRIE_POLICY_BASE base_type; 160 161 public: 162 typedef typename base_type::key_type key_type; 163 typedef typename base_type::key_const_reference key_const_reference; 164 165 /// Element access traits. 166 typedef _ATraits access_traits; 167 168 /// Const element iterator. 169 typedef typename access_traits::const_iterator a_const_iterator; 170 171 /// _Alloc type. 172 typedef _Alloc allocator_type; 173 174 /// Size type. 175 typedef typename allocator_type::size_type size_type; 176 typedef null_type metadata_type; 177 typedef Node_Itr node_iterator; 178 typedef Node_CItr node_const_iterator; 179 typedef typename node_iterator::value_type iterator; 180 typedef typename node_const_iterator::value_type const_iterator; 181 182 /// Finds the const iterator range corresponding to all values 183 /// whose prefixes match r_key. 184 std::pair<const_iterator, const_iterator> 185 prefix_range(key_const_reference) const; 186 187 /// Finds the iterator range corresponding to all values whose 188 /// prefixes match r_key. 189 std::pair<iterator, iterator> 190 prefix_range(key_const_reference); 191 192 /// Finds the const iterator range corresponding to all values 193 /// whose prefixes match [b, e). 194 std::pair<const_iterator, const_iterator> 195 prefix_range(a_const_iterator, a_const_iterator) const; 196 197 /// Finds the iterator range corresponding to all values whose 198 /// prefixes match [b, e). 199 std::pair<iterator, iterator> 200 prefix_range(a_const_iterator, a_const_iterator); 201 202 protected: 203 /// Called to update a node's metadata. 204 inline void 205 operator()(node_iterator node_it, node_const_iterator end_nd_it) const; 206 207 private: 208 node_iterator 209 next_child(node_iterator, a_const_iterator, a_const_iterator, 210 node_iterator, const access_traits&); 211 212 /// Returns the const iterator associated with the just-after last element. 213 virtual const_iterator 214 end() const = 0; 215 216 /// Returns the iterator associated with the just-after last element. 217 virtual iterator 218 end() = 0; 219 220 /// Returns the node_const_iterator associated with the trie's root node. 221 virtual node_const_iterator 222 node_begin() const = 0; 223 224 /// Returns the node_iterator associated with the trie's root node. 225 virtual node_iterator 226 node_begin() = 0; 227 228 /// Returns the node_const_iterator associated with a just-after leaf node. 229 virtual node_const_iterator 230 node_end() const = 0; 231 232 /// Returns the node_iterator associated with a just-after leaf node. 233 virtual node_iterator 234 node_end() = 0; 235 236 /// Access to the cmp_fn object. 237 virtual const access_traits& 238 get_access_traits() const = 0; 239 }; 240 241 #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp> 242 243 #undef PB_DS_CLASS_C_DEC 244 245 #define PB_DS_CLASS_C_DEC \ 246 trie_order_statistics_node_update<Node_CItr, Node_Itr, \ 247 _ATraits, _Alloc> 248 249 /// Functor updating ranks of entrees. 250 template<typename Node_CItr, 251 typename Node_Itr, 252 typename _ATraits, 253 typename _Alloc> 254 class trie_order_statistics_node_update : private PB_DS_TRIE_POLICY_BASE 255 { 256 private: 257 typedef PB_DS_TRIE_POLICY_BASE base_type; 258 259 public: 260 typedef _ATraits access_traits; 261 typedef typename access_traits::const_iterator a_const_iterator; 262 typedef _Alloc allocator_type; 263 typedef typename allocator_type::size_type size_type; 264 typedef typename base_type::key_type key_type; 265 typedef typename base_type::key_const_reference key_const_reference; 266 267 typedef size_type metadata_type; 268 typedef Node_CItr node_const_iterator; 269 typedef Node_Itr node_iterator; 270 typedef typename node_const_iterator::value_type const_iterator; 271 typedef typename node_iterator::value_type iterator; 272 273 /// Finds an entry by __order. Returns a const_iterator to the 274 /// entry with the __order order, or a const_iterator to the 275 /// container object's end if order is at least the size of the 276 /// container object. 277 inline const_iterator 278 find_by_order(size_type) const; 279 280 /// Finds an entry by __order. Returns an iterator to the entry 281 /// with the __order order, or an iterator to the container 282 /// object's end if order is at least the size of the container 283 /// object. 284 inline iterator 285 find_by_order(size_type); 286 287 /// Returns the order of a key within a sequence. For exapmle, if 288 /// r_key is the smallest key, this method will return 0; if r_key 289 /// is a key between the smallest and next key, this method will 290 /// return 1; if r_key is a key larger than the largest key, this 291 /// method will return the size of r_c. 292 inline size_type 293 order_of_key(key_const_reference) const; 294 295 /// Returns the order of a prefix within a sequence. For exapmle, 296 /// if [b, e] is the smallest prefix, this method will return 0; if 297 /// r_key is a key between the smallest and next key, this method 298 /// will return 1; if r_key is a key larger than the largest key, 299 /// this method will return the size of r_c. 300 inline size_type 301 order_of_prefix(a_const_iterator, a_const_iterator) const; 302 303 protected: 304 /// Updates the rank of a node through a node_iterator node_it; 305 /// end_nd_it is the end node iterator. 306 inline void 307 operator()(node_iterator, node_const_iterator) const; 308 309 private: 310 typedef typename base_type::const_reference const_reference; 311 typedef typename base_type::const_pointer const_pointer; 312 313 typedef typename _Alloc::template rebind<metadata_type> __rebind_m; 314 typedef typename __rebind_m::other __rebind_ma; 315 typedef typename __rebind_ma::const_reference metadata_const_reference; 316 typedef typename __rebind_ma::reference metadata_reference; 317 318 /// Returns true if the container is empty. 319 virtual bool 320 empty() const = 0; 321 322 /// Returns the iterator associated with the trie's first element. 323 virtual iterator 324 begin() = 0; 325 326 /// Returns the iterator associated with the trie's 327 /// just-after-last element. 328 virtual iterator 329 end() = 0; 330 331 /// Returns the node_const_iterator associated with the trie's root node. 332 virtual node_const_iterator 333 node_begin() const = 0; 334 335 /// Returns the node_iterator associated with the trie's root node. 336 virtual node_iterator 337 node_begin() = 0; 338 339 /// Returns the node_const_iterator associated with a just-after 340 /// leaf node. 341 virtual node_const_iterator 342 node_end() const = 0; 343 344 /// Returns the node_iterator associated with a just-after leaf node. 345 virtual node_iterator 346 node_end() = 0; 347 348 /// Access to the cmp_fn object. 349 virtual access_traits& 350 get_access_traits() = 0; 351 }; 352 353 #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp> 354 355 #undef PB_DS_CLASS_T_DEC 356 #undef PB_DS_CLASS_C_DEC 357 #undef PB_DS_TRIE_POLICY_BASE 358 359 } // namespace __gnu_pbds 360 361 #endif 362