1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file trie_policy.hpp 44169691Skan * Contains trie-related policies. 45169691Skan */ 46169691Skan 47169691Skan#ifndef PB_DS_TRIE_POLICY_HPP 48169691Skan#define PB_DS_TRIE_POLICY_HPP 49169691Skan 50169691Skan#include <string> 51169691Skan#include <ext/pb_ds/detail/type_utils.hpp> 52169691Skan#include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp> 53169691Skan 54169691Skannamespace pb_ds 55169691Skan{ 56169691Skan // A null node updator, indicating that no node updates are required. 57169691Skan template<typename Const_Node_Iterator, 58169691Skan typename Node_Iterator, 59169691Skan typename E_Access_Traits, 60169691Skan typename Allocator> 61169691Skan struct null_trie_node_update 62169691Skan { }; 63169691Skan 64169691Skan#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 65169691Skan typedef detail::static_assert_dumclass<sizeof(detail::static_assert<bool(E)>)> UNIQUE##_static_assert_type 66169691Skan 67169691Skan#define PB_DS_CLASS_T_DEC \ 68169691Skan template<typename String, typename String::value_type Min_E_Val, typename String::value_type Max_E_Val, bool Reverse, typename Allocator> 69169691Skan 70169691Skan#define PB_DS_CLASS_C_DEC \ 71169691Skan string_trie_e_access_traits<String, Min_E_Val,Max_E_Val,Reverse,Allocator> 72169691Skan 73169691Skan // Element access traits for string types. 74169691Skan template<typename String = std::string, 75169691Skan typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min, 76169691Skan typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max, 77169691Skan bool Reverse = false, 78169691Skan typename Allocator = std::allocator<char> > 79169691Skan struct string_trie_e_access_traits 80169691Skan { 81169691Skan public: 82169691Skan typedef typename Allocator::size_type size_type; 83169691Skan typedef String key_type; 84169691Skan typedef typename Allocator::template rebind<key_type>::other key_rebind; 85169691Skan typedef typename key_rebind::const_reference const_key_reference; 86169691Skan 87169691Skan enum 88169691Skan { 89169691Skan reverse = Reverse 90169691Skan }; 91169691Skan 92169691Skan // Element const iterator type. 93169691Skan typedef typename detail::__conditional_type<Reverse, typename String::const_reverse_iterator, typename String::const_iterator>::__type const_iterator; 94169691Skan 95169691Skan // Element type. 96169691Skan typedef typename std::iterator_traits<const_iterator>::value_type e_type; 97169691Skan 98169691Skan enum 99169691Skan { 100169691Skan min_e_val = Min_E_Val, 101169691Skan max_e_val = Max_E_Val, 102169691Skan max_size = max_e_val - min_e_val + 1 103169691Skan }; 104169691Skan PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2); 105169691Skan 106169691Skan // Returns a const_iterator to the first element of 107169691Skan // const_key_reference agumnet. 108169691Skan inline static const_iterator 109169691Skan begin(const_key_reference); 110169691Skan 111169691Skan // Returns a const_iterator to the after-last element of 112169691Skan // const_key_reference argument. 113169691Skan inline static const_iterator 114169691Skan end(const_key_reference); 115169691Skan 116169691Skan // Maps an element to a position. 117169691Skan inline static size_type 118169691Skan e_pos(e_type e); 119169691Skan 120169691Skan private: 121169691Skan 122169691Skan inline static const_iterator 123169691Skan begin_imp(const_key_reference, detail::false_type); 124169691Skan 125169691Skan inline static const_iterator 126169691Skan begin_imp(const_key_reference, detail::true_type); 127169691Skan 128169691Skan inline static const_iterator 129169691Skan end_imp(const_key_reference, detail::false_type); 130169691Skan 131169691Skan inline static const_iterator 132169691Skan end_imp(const_key_reference, detail::true_type); 133169691Skan 134169691Skan static detail::integral_constant<int, Reverse> s_rev_ind; 135169691Skan }; 136169691Skan 137169691Skan#include <ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp> 138169691Skan 139169691Skan#undef PB_DS_CLASS_T_DEC 140169691Skan#undef PB_DS_CLASS_C_DEC 141169691Skan 142169691Skan#define PB_DS_CLASS_T_DEC \ 143169691Skan template<typename Const_Node_Iterator,typename Node_Iterator,class E_Access_Traits, typename Allocator> 144169691Skan 145169691Skan#define PB_DS_CLASS_C_DEC \ 146169691Skan trie_prefix_search_node_update<Const_Node_Iterator, Node_Iterator, E_Access_Traits,Allocator> 147169691Skan 148169691Skan#define PB_DS_BASE_C_DEC \ 149169691Skan detail::trie_policy_base<Const_Node_Iterator,Node_Iterator,E_Access_Traits, Allocator> 150169691Skan 151169691Skan // A node updator that allows tries to be searched for the range of 152169691Skan // values that match a certain prefix. 153169691Skan template<typename Const_Node_Iterator, 154169691Skan typename Node_Iterator, 155169691Skan typename E_Access_Traits, 156169691Skan typename Allocator> 157169691Skan class trie_prefix_search_node_update : private PB_DS_BASE_C_DEC 158169691Skan { 159169691Skan private: 160169691Skan typedef PB_DS_BASE_C_DEC base_type; 161169691Skan 162169691Skan public: 163169691Skan typedef typename base_type::key_type key_type; 164169691Skan typedef typename base_type::const_key_reference const_key_reference; 165169691Skan 166169691Skan // Element access traits. 167169691Skan typedef E_Access_Traits e_access_traits; 168169691Skan 169169691Skan // Const element iterator. 170169691Skan typedef typename e_access_traits::const_iterator const_e_iterator; 171169691Skan 172169691Skan // Allocator type. 173169691Skan typedef Allocator allocator; 174169691Skan 175169691Skan // Size type. 176169691Skan typedef typename allocator::size_type size_type; 177169691Skan typedef detail::null_node_metadata metadata_type; 178169691Skan typedef Const_Node_Iterator const_node_iterator; 179169691Skan typedef Node_Iterator node_iterator; 180169691Skan typedef typename const_node_iterator::value_type const_iterator; 181169691Skan typedef typename node_iterator::value_type iterator; 182169691Skan 183169691Skan // Finds the const iterator range corresponding to all values 184169691Skan // whose prefixes match r_key. 185169691Skan std::pair<const_iterator, const_iterator> 186169691Skan prefix_range(const_key_reference) const; 187169691Skan 188169691Skan // Finds the iterator range corresponding to all values whose 189169691Skan // prefixes match r_key. 190169691Skan std::pair<iterator, iterator> 191169691Skan prefix_range(const_key_reference); 192169691Skan 193169691Skan // Finds the const iterator range corresponding to all values 194169691Skan // whose prefixes match [b, e). 195169691Skan std::pair<const_iterator, const_iterator> 196169691Skan prefix_range(const_e_iterator, const_e_iterator) const; 197169691Skan 198169691Skan // Finds the iterator range corresponding to all values whose 199169691Skan // prefixes match [b, e). 200169691Skan std::pair<iterator, iterator> 201169691Skan prefix_range(const_e_iterator, const_e_iterator); 202169691Skan 203169691Skan protected: 204169691Skan // Called to update a node's metadata. 205169691Skan inline void 206169691Skan operator()(node_iterator node_it, const_node_iterator end_nd_it) const; 207169691Skan 208169691Skan private: 209169691Skan // Returns the const iterator associated with the just-after last element. 210169691Skan virtual const_iterator 211169691Skan end() const = 0; 212169691Skan 213169691Skan // Returns the iterator associated with the just-after last element. 214169691Skan virtual iterator 215169691Skan end() = 0; 216169691Skan 217169691Skan // Returns the const_node_iterator associated with the trie's root node. 218169691Skan virtual const_node_iterator 219169691Skan node_begin() const = 0; 220169691Skan 221169691Skan // Returns the node_iterator associated with the trie's root node. 222169691Skan virtual node_iterator 223169691Skan node_begin() = 0; 224169691Skan 225169691Skan // Returns the const_node_iterator associated with a just-after leaf node. 226169691Skan virtual const_node_iterator 227169691Skan node_end() const = 0; 228169691Skan 229169691Skan // Returns the node_iterator associated with a just-after leaf node. 230169691Skan virtual node_iterator 231169691Skan node_end() = 0; 232169691Skan 233169691Skan // Access to the cmp_fn object. 234169691Skan virtual const e_access_traits& 235169691Skan get_e_access_traits() const = 0; 236169691Skan 237169691Skan node_iterator 238169691Skan next_child(node_iterator, const_e_iterator, const_e_iterator, 239169691Skan node_iterator, const e_access_traits&); 240169691Skan }; 241169691Skan 242169691Skan#include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp> 243169691Skan 244169691Skan#undef PB_DS_CLASS_C_DEC 245169691Skan 246169691Skan#define PB_DS_CLASS_C_DEC \ 247169691Skan trie_order_statistics_node_update<Const_Node_Iterator, Node_Iterator,E_Access_Traits, Allocator> 248169691Skan 249169691Skan // Functor updating ranks of entrees. 250169691Skan template<typename Const_Node_Iterator, 251169691Skan typename Node_Iterator, 252169691Skan typename E_Access_Traits, 253169691Skan typename Allocator> 254169691Skan class trie_order_statistics_node_update : private PB_DS_BASE_C_DEC 255169691Skan { 256169691Skan private: 257169691Skan typedef PB_DS_BASE_C_DEC base_type; 258169691Skan 259169691Skan public: 260169691Skan typedef E_Access_Traits e_access_traits; 261169691Skan typedef typename e_access_traits::const_iterator const_e_iterator; 262169691Skan typedef Allocator allocator; 263169691Skan typedef typename allocator::size_type size_type; 264169691Skan typedef typename base_type::key_type key_type; 265169691Skan typedef typename base_type::const_key_reference const_key_reference; 266169691Skan 267169691Skan typedef size_type metadata_type; 268169691Skan typedef Const_Node_Iterator const_node_iterator; 269169691Skan typedef Node_Iterator node_iterator; 270169691Skan typedef typename const_node_iterator::value_type const_iterator; 271169691Skan typedef typename node_iterator::value_type iterator; 272169691Skan 273169691Skan // Finds an entry by __order. Returns a const_iterator to the 274169691Skan // entry with the __order order, or a const_iterator to the 275169691Skan // container object's end if order is at least the size of the 276169691Skan // container object. 277169691Skan inline const_iterator 278169691Skan find_by_order(size_type) const; 279169691Skan 280169691Skan // Finds an entry by __order. Returns an iterator to the entry 281169691Skan // with the __order order, or an iterator to the container 282169691Skan // object's end if order is at least the size of the container 283169691Skan // object. 284169691Skan inline iterator 285169691Skan find_by_order(size_type); 286169691Skan 287169691Skan // Returns the order of a key within a sequence. For exapmle, if 288169691Skan // r_key is the smallest key, this method will return 0; if r_key 289169691Skan // is a key between the smallest and next key, this method will 290169691Skan // return 1; if r_key is a key larger than the largest key, this 291169691Skan // method will return the size of r_c. 292169691Skan inline size_type 293169691Skan order_of_key(const_key_reference) const; 294169691Skan 295169691Skan // Returns the order of a prefix within a sequence. For exapmle, 296169691Skan // if [b, e] is the smallest prefix, this method will return 0; if 297169691Skan // r_key is a key between the smallest and next key, this method 298169691Skan // will return 1; if r_key is a key larger than the largest key, 299169691Skan // this method will return the size of r_c. 300169691Skan inline size_type 301169691Skan order_of_prefix(const_e_iterator, const_e_iterator) const; 302169691Skan 303169691Skan private: 304169691Skan typedef typename base_type::const_reference const_reference; 305169691Skan typedef typename base_type::const_pointer const_pointer; 306169691Skan 307169691Skan typedef typename Allocator::template rebind<metadata_type>::other metadata_rebind; 308169691Skan typedef typename metadata_rebind::const_reference const_metadata_reference; 309169691Skan typedef typename metadata_rebind::reference metadata_reference; 310169691Skan 311169691Skan // Returns true if the container is empty. 312169691Skan virtual bool 313169691Skan empty() const = 0; 314169691Skan 315169691Skan // Returns the iterator associated with the trie's first element. 316169691Skan virtual iterator 317169691Skan begin() = 0; 318169691Skan 319169691Skan // Returns the iterator associated with the trie's 320169691Skan // just-after-last element. 321169691Skan virtual iterator 322169691Skan end() = 0; 323169691Skan 324169691Skan // Returns the const_node_iterator associated with the trie's root node. 325169691Skan virtual const_node_iterator 326169691Skan node_begin() const = 0; 327169691Skan 328169691Skan // Returns the node_iterator associated with the trie's root node. 329169691Skan virtual node_iterator 330169691Skan node_begin() = 0; 331169691Skan 332169691Skan // Returns the const_node_iterator associated with a just-after 333169691Skan // leaf node. 334169691Skan virtual const_node_iterator 335169691Skan node_end() const = 0; 336169691Skan 337169691Skan // Returns the node_iterator associated with a just-after leaf node. 338169691Skan virtual node_iterator 339169691Skan node_end() = 0; 340169691Skan 341169691Skan // Access to the cmp_fn object. 342169691Skan virtual e_access_traits& 343169691Skan get_e_access_traits() = 0; 344169691Skan 345169691Skan protected: 346169691Skan // Updates the rank of a node through a node_iterator node_it; 347169691Skan // end_nd_it is the end node iterator. 348169691Skan inline void 349169691Skan operator()(node_iterator, const_node_iterator) const; 350169691Skan 351169691Skan // Destructor. 352169691Skan virtual 353169691Skan ~trie_order_statistics_node_update(); 354169691Skan }; 355169691Skan 356169691Skan#include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp> 357169691Skan 358169691Skan#undef PB_DS_CLASS_T_DEC 359169691Skan#undef PB_DS_CLASS_C_DEC 360169691Skan#undef PB_DS_BASE_C_DEC 361169691Skan#undef PB_DS_STATIC_ASSERT 362169691Skan 363169691Skan} // namespace pb_ds 364169691Skan 365169691Skan#endif 366