1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file trie_policy.hpp 44 * Contains trie-related policies. 45 */ 46 47#ifndef PB_DS_TRIE_POLICY_HPP 48#define PB_DS_TRIE_POLICY_HPP 49 50#include <string> 51#include <ext/pb_ds/detail/type_utils.hpp> 52#include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp> 53 54namespace pb_ds 55{ 56 // A null node updator, indicating that no node updates are required. 57 template<typename Const_Node_Iterator, 58 typename Node_Iterator, 59 typename E_Access_Traits, 60 typename Allocator> 61 struct null_trie_node_update 62 { }; 63 64#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 65 typedef detail::static_assert_dumclass<sizeof(detail::static_assert<bool(E)>)> UNIQUE##_static_assert_type 66 67#define PB_DS_CLASS_T_DEC \ 68 template<typename String, typename String::value_type Min_E_Val, typename String::value_type Max_E_Val, bool Reverse, typename Allocator> 69 70#define PB_DS_CLASS_C_DEC \ 71 string_trie_e_access_traits<String, Min_E_Val,Max_E_Val,Reverse,Allocator> 72 73 // Element access traits for string types. 74 template<typename String = std::string, 75 typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min, 76 typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max, 77 bool Reverse = false, 78 typename Allocator = std::allocator<char> > 79 struct string_trie_e_access_traits 80 { 81 public: 82 typedef typename Allocator::size_type size_type; 83 typedef String key_type; 84 typedef typename Allocator::template rebind<key_type>::other key_rebind; 85 typedef typename key_rebind::const_reference const_key_reference; 86 87 enum 88 { 89 reverse = Reverse 90 }; 91 92 // Element const iterator type. 93 typedef typename detail::__conditional_type<Reverse, typename String::const_reverse_iterator, typename String::const_iterator>::__type const_iterator; 94 95 // Element type. 96 typedef typename std::iterator_traits<const_iterator>::value_type e_type; 97 98 enum 99 { 100 min_e_val = Min_E_Val, 101 max_e_val = Max_E_Val, 102 max_size = max_e_val - min_e_val + 1 103 }; 104 PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2); 105 106 // Returns a const_iterator to the first element of 107 // const_key_reference agumnet. 108 inline static const_iterator 109 begin(const_key_reference); 110 111 // Returns a const_iterator to the after-last element of 112 // const_key_reference argument. 113 inline static const_iterator 114 end(const_key_reference); 115 116 // Maps an element to a position. 117 inline static size_type 118 e_pos(e_type e); 119 120 private: 121 122 inline static const_iterator 123 begin_imp(const_key_reference, detail::false_type); 124 125 inline static const_iterator 126 begin_imp(const_key_reference, detail::true_type); 127 128 inline static const_iterator 129 end_imp(const_key_reference, detail::false_type); 130 131 inline static const_iterator 132 end_imp(const_key_reference, detail::true_type); 133 134 static detail::integral_constant<int, Reverse> s_rev_ind; 135 }; 136 137#include <ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp> 138 139#undef PB_DS_CLASS_T_DEC 140#undef PB_DS_CLASS_C_DEC 141 142#define PB_DS_CLASS_T_DEC \ 143 template<typename Const_Node_Iterator,typename Node_Iterator,class E_Access_Traits, typename Allocator> 144 145#define PB_DS_CLASS_C_DEC \ 146 trie_prefix_search_node_update<Const_Node_Iterator, Node_Iterator, E_Access_Traits,Allocator> 147 148#define PB_DS_BASE_C_DEC \ 149 detail::trie_policy_base<Const_Node_Iterator,Node_Iterator,E_Access_Traits, Allocator> 150 151 // A node updator that allows tries to be searched for the range of 152 // values that match a certain prefix. 153 template<typename Const_Node_Iterator, 154 typename Node_Iterator, 155 typename E_Access_Traits, 156 typename Allocator> 157 class trie_prefix_search_node_update : private PB_DS_BASE_C_DEC 158 { 159 private: 160 typedef PB_DS_BASE_C_DEC base_type; 161 162 public: 163 typedef typename base_type::key_type key_type; 164 typedef typename base_type::const_key_reference const_key_reference; 165 166 // Element access traits. 167 typedef E_Access_Traits e_access_traits; 168 169 // Const element iterator. 170 typedef typename e_access_traits::const_iterator const_e_iterator; 171 172 // Allocator type. 173 typedef Allocator allocator; 174 175 // Size type. 176 typedef typename allocator::size_type size_type; 177 typedef detail::null_node_metadata metadata_type; 178 typedef Const_Node_Iterator const_node_iterator; 179 typedef Node_Iterator node_iterator; 180 typedef typename const_node_iterator::value_type const_iterator; 181 typedef typename node_iterator::value_type iterator; 182 183 // Finds the const iterator range corresponding to all values 184 // whose prefixes match r_key. 185 std::pair<const_iterator, const_iterator> 186 prefix_range(const_key_reference) const; 187 188 // Finds the iterator range corresponding to all values whose 189 // prefixes match r_key. 190 std::pair<iterator, iterator> 191 prefix_range(const_key_reference); 192 193 // Finds the const iterator range corresponding to all values 194 // whose prefixes match [b, e). 195 std::pair<const_iterator, const_iterator> 196 prefix_range(const_e_iterator, const_e_iterator) const; 197 198 // Finds the iterator range corresponding to all values whose 199 // prefixes match [b, e). 200 std::pair<iterator, iterator> 201 prefix_range(const_e_iterator, const_e_iterator); 202 203 protected: 204 // Called to update a node's metadata. 205 inline void 206 operator()(node_iterator node_it, const_node_iterator end_nd_it) const; 207 208 private: 209 // Returns the const iterator associated with the just-after last element. 210 virtual const_iterator 211 end() const = 0; 212 213 // Returns the iterator associated with the just-after last element. 214 virtual iterator 215 end() = 0; 216 217 // Returns the const_node_iterator associated with the trie's root node. 218 virtual const_node_iterator 219 node_begin() const = 0; 220 221 // Returns the node_iterator associated with the trie's root node. 222 virtual node_iterator 223 node_begin() = 0; 224 225 // Returns the const_node_iterator associated with a just-after leaf node. 226 virtual const_node_iterator 227 node_end() const = 0; 228 229 // Returns the node_iterator associated with a just-after leaf node. 230 virtual node_iterator 231 node_end() = 0; 232 233 // Access to the cmp_fn object. 234 virtual const e_access_traits& 235 get_e_access_traits() const = 0; 236 237 node_iterator 238 next_child(node_iterator, const_e_iterator, const_e_iterator, 239 node_iterator, const e_access_traits&); 240 }; 241 242#include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp> 243 244#undef PB_DS_CLASS_C_DEC 245 246#define PB_DS_CLASS_C_DEC \ 247 trie_order_statistics_node_update<Const_Node_Iterator, Node_Iterator,E_Access_Traits, Allocator> 248 249 // Functor updating ranks of entrees. 250 template<typename Const_Node_Iterator, 251 typename Node_Iterator, 252 typename E_Access_Traits, 253 typename Allocator> 254 class trie_order_statistics_node_update : private PB_DS_BASE_C_DEC 255 { 256 private: 257 typedef PB_DS_BASE_C_DEC base_type; 258 259 public: 260 typedef E_Access_Traits e_access_traits; 261 typedef typename e_access_traits::const_iterator const_e_iterator; 262 typedef Allocator allocator; 263 typedef typename allocator::size_type size_type; 264 typedef typename base_type::key_type key_type; 265 typedef typename base_type::const_key_reference const_key_reference; 266 267 typedef size_type metadata_type; 268 typedef Const_Node_Iterator const_node_iterator; 269 typedef Node_Iterator node_iterator; 270 typedef typename const_node_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(const_key_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(const_e_iterator, const_e_iterator) const; 302 303 private: 304 typedef typename base_type::const_reference const_reference; 305 typedef typename base_type::const_pointer const_pointer; 306 307 typedef typename Allocator::template rebind<metadata_type>::other metadata_rebind; 308 typedef typename metadata_rebind::const_reference const_metadata_reference; 309 typedef typename metadata_rebind::reference metadata_reference; 310 311 // Returns true if the container is empty. 312 virtual bool 313 empty() const = 0; 314 315 // Returns the iterator associated with the trie's first element. 316 virtual iterator 317 begin() = 0; 318 319 // Returns the iterator associated with the trie's 320 // just-after-last element. 321 virtual iterator 322 end() = 0; 323 324 // Returns the const_node_iterator associated with the trie's root node. 325 virtual const_node_iterator 326 node_begin() const = 0; 327 328 // Returns the node_iterator associated with the trie's root node. 329 virtual node_iterator 330 node_begin() = 0; 331 332 // Returns the const_node_iterator associated with a just-after 333 // leaf node. 334 virtual const_node_iterator 335 node_end() const = 0; 336 337 // Returns the node_iterator associated with a just-after leaf node. 338 virtual node_iterator 339 node_end() = 0; 340 341 // Access to the cmp_fn object. 342 virtual e_access_traits& 343 get_e_access_traits() = 0; 344 345 protected: 346 // Updates the rank of a node through a node_iterator node_it; 347 // end_nd_it is the end node iterator. 348 inline void 349 operator()(node_iterator, const_node_iterator) const; 350 351 // Destructor. 352 virtual 353 ~trie_order_statistics_node_update(); 354 }; 355 356#include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp> 357 358#undef PB_DS_CLASS_T_DEC 359#undef PB_DS_CLASS_C_DEC 360#undef PB_DS_BASE_C_DEC 361#undef PB_DS_STATIC_ASSERT 362 363} // namespace pb_ds 364 365#endif 366