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