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