#ifndef PB_DS_HASH_POLICY_HPP
#define PB_DS_HASH_POLICY_HPP
#include <algorithm>
#include <vector>
#include <cmath>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp>
#include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp>
#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp>
namespace pb_ds
{
struct null_hash_fn
{ };
struct null_probe_fn
{ };
#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type>
template<typename Size_Type = size_t>
class linear_probe_fn
{
public:
typedef Size_Type size_type;
void
swap(PB_DS_CLASS_C_DEC& other);
protected:
inline size_type
operator()(size_type i) const;
};
#include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp>
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type>
template<typename Size_Type = size_t>
class quadratic_probe_fn
{
public:
typedef Size_Type size_type;
void
swap(PB_DS_CLASS_C_DEC& other);
protected:
inline size_type
operator()(size_type i) const;
};
#include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp>
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type>
template<typename Size_Type = size_t>
class direct_mask_range_hashing
: public detail::mask_based_range_hashing<Size_Type>
{
private:
typedef detail::mask_based_range_hashing<Size_Type> mask_based_base;
public:
typedef Size_Type size_type;
void
swap(PB_DS_CLASS_C_DEC& other);
protected:
void
notify_resized(size_type size);
inline size_type
operator()(size_type hash) const;
};
#include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp>
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type>
template<typename Size_Type = size_t>
class direct_mod_range_hashing
: public detail::mod_based_range_hashing<Size_Type>
{
public:
typedef Size_Type size_type;
void
swap(PB_DS_CLASS_C_DEC& other);
protected:
void
notify_resized(size_type size);
inline size_type
operator()(size_type hash) const;
private:
typedef detail::mod_based_range_hashing<size_type> mod_based_base;
};
#include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp>
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
#define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type>
#define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access>
template<bool External_Load_Access = false, typename Size_Type = size_t>
class hash_load_check_resize_trigger : private PB_DS_SIZE_BASE_C_DEC
{
public:
typedef Size_Type size_type;
enum
{
external_load_access = External_Load_Access
};
hash_load_check_resize_trigger(float load_min = 0.125,
float load_max = 0.5);
void
swap(hash_load_check_resize_trigger& other);
virtual
~hash_load_check_resize_trigger();
inline std::pair<float, float>
get_loads() const;
void
set_loads(std::pair<float, float> load_pair);
protected:
inline void
notify_insert_search_start();
inline void
notify_insert_search_collision();
inline void
notify_insert_search_end();
inline void
notify_find_search_start();
inline void
notify_find_search_collision();
inline void
notify_find_search_end();
inline void
notify_erase_search_start();
inline void
notify_erase_search_collision();
inline void
notify_erase_search_end();
inline void
notify_inserted(size_type num_entries);
inline void
notify_erased(size_type num_entries);
void
notify_cleared();
void
notify_resized(size_type new_size);
void
notify_externally_resized(size_type new_size);
inline bool
is_resize_needed() const;
inline bool
is_grow_needed(size_type size, size_type num_entries) const;
private:
virtual void
do_resize(size_type new_size);
typedef PB_DS_SIZE_BASE_C_DEC size_base;
#ifdef _GLIBCXX_DEBUG
void
assert_valid() const;
#endif
float m_load_min;
float m_load_max;
size_type m_next_shrink_size;
size_type m_next_grow_size;
bool m_resize_needed;
};
#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_SIZE_BASE_C_DEC
#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
#define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type>
template<bool External_Load_Access = false, typename Size_Type = size_t>
class cc_hash_max_collision_check_resize_trigger
{
public:
typedef Size_Type size_type;
enum
{
external_load_access = External_Load_Access
};
cc_hash_max_collision_check_resize_trigger(float load = 0.5);
void
swap(PB_DS_CLASS_C_DEC& other);
inline float
get_load() const;
void
set_load(float load);
protected:
inline void
notify_insert_search_start();
inline void
notify_insert_search_collision();
inline void
notify_insert_search_end();
inline void
notify_find_search_start();
inline void
notify_find_search_collision();
inline void
notify_find_search_end();
inline void
notify_erase_search_start();
inline void
notify_erase_search_collision();
inline void
notify_erase_search_end();
inline void
notify_inserted(size_type num_entries);
inline void
notify_erased(size_type num_entries);
void
notify_cleared();
void
notify_resized(size_type new_size);
void
notify_externally_resized(size_type new_size);
inline bool
is_resize_needed() const;
inline bool
is_grow_needed(size_type size, size_type num_entries) const;
private:
void
calc_max_num_coll();
inline void
calc_resize_needed();
float m_load;
size_type m_size;
size_type m_num_col;
size_type m_max_col;
bool m_resize_needed;
};
#include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp>
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type>
template<typename Size_Type = size_t>
class hash_exponential_size_policy
{
public:
typedef Size_Type size_type;
hash_exponential_size_policy(size_type start_size = 8,
size_type grow_factor = 2);
void
swap(PB_DS_CLASS_C_DEC& other);
protected:
size_type
get_nearest_larger_size(size_type size) const;
size_type
get_nearest_smaller_size(size_type size) const;
private:
size_type m_start_size;
size_type m_grow_factor;
};
#include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp>
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#define PB_DS_CLASS_T_DEC
#define PB_DS_CLASS_C_DEC hash_prime_size_policy
class hash_prime_size_policy
{
public:
typedef size_t size_type;
hash_prime_size_policy(size_type start_size = 8);
inline void
swap(PB_DS_CLASS_C_DEC& other);
protected:
size_type
get_nearest_larger_size(size_type size) const;
size_type
get_nearest_smaller_size(size_type size) const;
private:
size_type m_start_size;
};
#include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp>
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type>
#define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type>
template<typename Size_Policy = hash_exponential_size_policy<>,
typename Trigger_Policy = hash_load_check_resize_trigger<>,
bool External_Size_Access = false,
typename Size_Type = size_t>
class hash_standard_resize_policy
: public Size_Policy, public Trigger_Policy
{
public:
typedef Size_Type size_type;
typedef Trigger_Policy trigger_policy;
typedef Size_Policy size_policy;
enum
{
external_size_access = External_Size_Access
};
hash_standard_resize_policy();
hash_standard_resize_policy(const Size_Policy& r_size_policy);
hash_standard_resize_policy(const Size_Policy& r_size_policy,
const Trigger_Policy& r_trigger_policy);
virtual
~hash_standard_resize_policy();
inline void
swap(PB_DS_CLASS_C_DEC& other);
Size_Policy&
get_size_policy();
const Size_Policy&
get_size_policy() const;
Trigger_Policy&
get_trigger_policy();
const Trigger_Policy&
get_trigger_policy() const;
inline size_type
get_actual_size() const;
void
resize(size_type suggested_new_size);
protected:
inline void
notify_insert_search_start();
inline void
notify_insert_search_collision();
inline void
notify_insert_search_end();
inline void
notify_find_search_start();
inline void
notify_find_search_collision();
inline void
notify_find_search_end();
inline void
notify_erase_search_start();
inline void
notify_erase_search_collision();
inline void
notify_erase_search_end();
inline void
notify_inserted(size_type num_e);
inline void
notify_erased(size_type num_e);
void
notify_cleared();
void
notify_resized(size_type new_size);
inline bool
is_resize_needed() const;
size_type
get_new_size(size_type size, size_type num_used_e) const;
private:
virtual void
do_resize(size_type new_size);
typedef Trigger_Policy trigger_policy_base;
typedef Size_Policy size_policy_base;
size_type m_size;
};
#include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp>
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
}
#endif