ranged_probe_fn.hpp [plain text]
#ifndef PB_DS_RANGED_PROBE_FN_HPP
#define PB_DS_RANGED_PROBE_FN_HPP
#include <ext/pb_ds/detail/basic_types.hpp>
#include <utility>
#include <debug/debug.h>
namespace pb_ds
{
namespace detail
{
template<typename Key, typename Hash_Fn, typename Allocator,
typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash>
class ranged_probe_fn;
#define PB_DS_CLASS_T_DEC \
template<typename Key, typename Hash_Fn, typename Allocator, \
typename Comb_Probe_Fn, typename Probe_Fn>
#define PB_DS_CLASS_C_DEC \
ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, false>
template<typename Key, typename Hash_Fn, typename Allocator,
typename Comb_Probe_Fn, typename Probe_Fn>
class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn,
Probe_Fn, false>
: public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
{
protected:
typedef typename Allocator::size_type size_type;
typedef Comb_Probe_Fn comb_probe_fn_base;
typedef Hash_Fn hash_fn_base;
typedef Probe_Fn probe_fn_base;
typedef typename Allocator::template rebind<Key>::other key_allocator;
typedef typename key_allocator::const_reference const_key_reference;
ranged_probe_fn(size_type);
ranged_probe_fn(size_type, const Hash_Fn&);
ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&);
ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
const Probe_Fn&);
void
swap(PB_DS_CLASS_C_DEC&);
void
notify_resized(size_type);
inline size_type
operator()(const_key_reference) const;
inline size_type
operator()(const_key_reference, size_type, size_type) const;
};
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size)
{ Comb_Probe_Fn::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
: Hash_Fn(r_hash_fn)
{ Comb_Probe_Fn::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
const Comb_Probe_Fn& r_comb_probe_fn)
: Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
{ comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
const Comb_Probe_Fn& r_comb_probe_fn,
const Probe_Fn& r_probe_fn)
: Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
{ comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
comb_probe_fn_base::swap(other);
std::swap((Hash_Fn& )(*this), (Hash_Fn&)other);
}
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type size)
{ comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(const_key_reference r_key) const
{ return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); }
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(const_key_reference, size_type hash, size_type i) const
{
return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
}
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#define PB_DS_CLASS_T_DEC \
template<typename Key, typename Hash_Fn, typename Allocator, \
typename Comb_Probe_Fn, typename Probe_Fn>
#define PB_DS_CLASS_C_DEC \
ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, true>
template<typename Key, typename Hash_Fn, typename Allocator,
typename Comb_Probe_Fn, typename Probe_Fn>
class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn,
Probe_Fn, true>
: public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
{
protected:
typedef typename Allocator::size_type size_type;
typedef std::pair<size_type, size_type> comp_hash;
typedef Comb_Probe_Fn comb_probe_fn_base;
typedef Hash_Fn hash_fn_base;
typedef Probe_Fn probe_fn_base;
typedef typename Allocator::template rebind<Key>::other key_allocator;
typedef typename key_allocator::const_reference const_key_reference;
ranged_probe_fn(size_type);
ranged_probe_fn(size_type, const Hash_Fn&);
ranged_probe_fn(size_type, const Hash_Fn&,
const Comb_Probe_Fn&);
ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
const Probe_Fn&);
void
swap(PB_DS_CLASS_C_DEC&);
void
notify_resized(size_type);
inline comp_hash
operator()(const_key_reference) const;
inline size_type
operator()(const_key_reference, size_type, size_type) const;
inline size_type
operator()(const_key_reference, size_type) const;
};
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size)
{ Comb_Probe_Fn::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
: Hash_Fn(r_hash_fn)
{ Comb_Probe_Fn::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
const Comb_Probe_Fn& r_comb_probe_fn)
: Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
{ comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
const Comb_Probe_Fn& r_comb_probe_fn,
const Probe_Fn& r_probe_fn)
: Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
{ comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
comb_probe_fn_base::swap(other);
std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
}
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type size)
{ comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::comp_hash
PB_DS_CLASS_C_DEC::
operator()(const_key_reference r_key) const
{
const size_type hash = hash_fn_base::operator()(r_key);
return std::make_pair(comb_probe_fn_base::operator()(hash), hash);
}
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(const_key_reference, size_type hash, size_type i) const
{
return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
}
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()
#ifdef _GLIBCXX_DEBUG
(const_key_reference r_key, size_type hash) const
#else
(const_key_reference , size_type hash) const
#endif
{
_GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
return hash;
}
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
template<typename Key, typename Allocator, typename Comb_Probe_Fn>
class ranged_probe_fn<Key, null_hash_fn, Allocator, Comb_Probe_Fn,
null_probe_fn, false>
: public Comb_Probe_Fn, public null_hash_fn, public null_probe_fn
{
protected:
typedef typename Allocator::size_type size_type;
typedef Comb_Probe_Fn comb_probe_fn_base;
typedef typename Allocator::template rebind<Key>::other key_allocator;
typedef typename key_allocator::const_reference const_key_reference;
ranged_probe_fn(size_type size)
{ Comb_Probe_Fn::notify_resized(size); }
ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn)
: Comb_Probe_Fn(r_comb_probe_fn)
{ }
ranged_probe_fn(size_type, const null_hash_fn&,
const Comb_Probe_Fn& r_comb_probe_fn,
const null_probe_fn&)
: Comb_Probe_Fn(r_comb_probe_fn)
{ }
void
swap(ranged_probe_fn& other)
{ comb_probe_fn_base::swap(other); }
};
} }
#endif