3 // Copyright (C) 2005, 2006, 2007, 2009, 2011 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
37 * @file detail/standard_policies.hpp
38 * Contains standard policies for containers.
41 #ifndef PB_DS_STANDARD_POLICIES_HPP
42 #define PB_DS_STANDARD_POLICIES_HPP
45 #include <ext/pb_ds/hash_policy.hpp>
46 #include <ext/pb_ds/list_update_policy.hpp>
47 #include <ext/pb_ds/detail/branch_policy/null_node_metadata.hpp>
48 #include <ext/pb_ds/tree_policy.hpp>
49 #include <ext/pb_ds/trie_policy.hpp>
50 #include <ext/pb_ds/tag_and_trait.hpp>
51 #include <tr1/functional>
58 template<typename Key>
59 struct default_hash_fn
61 typedef std::tr1::hash<Key> type;
65 template<typename Key>
68 typedef std::equal_to<Key> type;
73 default_store_hash = false
76 /// default_comb_hash_fn
77 struct default_comb_hash_fn
79 typedef __gnu_pbds::direct_mask_range_hashing<> type;
82 /// default_resize_policy
83 template<typename Comb_Hash_Fn>
84 struct default_resize_policy
87 typedef typename Comb_Hash_Fn::size_type size_type;
89 typedef __gnu_pbds::direct_mask_range_hashing<size_type> default_fn;
90 typedef is_same<default_fn, Comb_Hash_Fn> same_type;
91 typedef __gnu_pbds::hash_exponential_size_policy<size_type> iftrue;
92 typedef __gnu_pbds::hash_prime_size_policy iffalse;
93 typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
94 typedef typename cond_type::__type size_policy_type;
96 typedef __gnu_pbds::hash_load_check_resize_trigger<false, size_type> trigger;
99 typedef __gnu_pbds::hash_standard_resize_policy<size_policy_type, trigger, false, size_type> type;
102 /// default_update_policy
103 struct default_update_policy
105 typedef __gnu_pbds::lu_move_to_front_policy<> type;
109 template<typename Comb_Probe_Fn>
110 struct default_probe_fn
113 typedef typename Comb_Probe_Fn::size_type size_type;
115 typedef __gnu_pbds::direct_mask_range_hashing<size_type> default_fn;
116 typedef is_same<default_fn, Comb_Probe_Fn> same_type;
117 typedef __gnu_pbds::linear_probe_fn<size_type> iftrue;
118 typedef __gnu_pbds::quadratic_probe_fn<size_type> iffalse;
119 typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
122 typedef typename cond_type::__type type;
125 /// default_trie_access_traits
126 template<typename Key>
127 struct default_trie_access_traits;
129 template<typename Char, typename Char_Traits>
130 struct default_trie_access_traits<std::basic_string<Char, Char_Traits, std::allocator<char> > >
133 typedef std::basic_string<Char, Char_Traits, std::allocator<char> > string_type;
136 typedef __gnu_pbds::trie_string_access_traits<string_type> type;
139 } // namespace detail
140 } // namespace __gnu_pbds
142 #endif // #ifndef PB_DS_STANDARD_POLICIES_HPP