#ifndef PB_DS_TAG_AND_TRAIT_HPP
#define PB_DS_TAG_AND_TRAIT_HPP
#include <ext/pb_ds/detail/type_utils.hpp>
namespace pb_ds
{
struct trivial_iterator_tag
{ };
typedef void trivial_iterator_difference_type;
struct basic_invalidation_guarantee
{ };
struct point_invalidation_guarantee : public basic_invalidation_guarantee
{ };
struct range_invalidation_guarantee : public point_invalidation_guarantee
{ };
struct null_mapped_type { };
struct container_tag
{ };
struct associative_container_tag : public container_tag { };
struct basic_hash_tag : public associative_container_tag { };
struct cc_hash_tag : public basic_hash_tag { };
struct gp_hash_tag : public basic_hash_tag { };
struct basic_tree_tag : public associative_container_tag { };
struct tree_tag : public basic_tree_tag { };
struct rb_tree_tag : public tree_tag { };
struct splay_tree_tag : public tree_tag { };
struct ov_tree_tag : public tree_tag { };
struct trie_tag : public basic_tree_tag { };
struct pat_trie_tag : public trie_tag { };
struct list_update_tag : public associative_container_tag { };
struct priority_queue_tag : public container_tag { };
struct pairing_heap_tag : public priority_queue_tag { };
struct binomial_heap_tag : public priority_queue_tag { };
struct rc_binomial_heap_tag : public priority_queue_tag { };
struct binary_heap_tag : public priority_queue_tag { };
struct thin_heap_tag : public priority_queue_tag { };
template<typename Tag>
struct container_traits_base;
template<>
struct container_traits_base<cc_hash_tag>
{
typedef cc_hash_tag container_category;
typedef point_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = false,
erase_can_throw = false,
split_join_can_throw = false,
reverse_iteration = false
};
};
template<>
struct container_traits_base<gp_hash_tag>
{
typedef gp_hash_tag container_category;
typedef basic_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = false,
erase_can_throw = false,
split_join_can_throw = false,
reverse_iteration = false
};
};
template<>
struct container_traits_base<rb_tree_tag>
{
typedef rb_tree_tag container_category;
typedef range_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = true,
erase_can_throw = false,
split_join_can_throw = false,
reverse_iteration = true
};
};
template<>
struct container_traits_base<splay_tree_tag>
{
typedef splay_tree_tag container_category;
typedef range_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = true,
erase_can_throw = false,
split_join_can_throw = false,
reverse_iteration = true
};
};
template<>
struct container_traits_base<ov_tree_tag>
{
typedef ov_tree_tag container_category;
typedef basic_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = true,
erase_can_throw = true,
split_join_can_throw = true,
reverse_iteration = false
};
};
template<>
struct container_traits_base<pat_trie_tag>
{
typedef pat_trie_tag container_category;
typedef range_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = true,
erase_can_throw = false,
split_join_can_throw = true,
reverse_iteration = true
};
};
template<>
struct container_traits_base<list_update_tag>
{
typedef list_update_tag container_category;
typedef point_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = false,
erase_can_throw = false,
split_join_can_throw = false,
reverse_iteration = false
};
};
template<>
struct container_traits_base<pairing_heap_tag>
{
typedef pairing_heap_tag container_category;
typedef point_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = false,
erase_can_throw = false,
split_join_can_throw = false,
reverse_iteration = false
};
};
template<>
struct container_traits_base<thin_heap_tag>
{
typedef thin_heap_tag container_category;
typedef point_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = false,
erase_can_throw = false,
split_join_can_throw = false,
reverse_iteration = false
};
};
template<>
struct container_traits_base<binomial_heap_tag>
{
typedef binomial_heap_tag container_category;
typedef point_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = false,
erase_can_throw = false,
split_join_can_throw = false,
reverse_iteration = false
};
};
template<>
struct container_traits_base<rc_binomial_heap_tag>
{
typedef rc_binomial_heap_tag container_category;
typedef point_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = false,
erase_can_throw = false,
split_join_can_throw = false,
reverse_iteration = false
};
};
template<>
struct container_traits_base<binary_heap_tag>
{
typedef binary_heap_tag container_category;
typedef basic_invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = false,
erase_can_throw = false,
split_join_can_throw = true,
reverse_iteration = false
};
};
template<typename Cntnr>
struct container_traits
: public container_traits_base<typename Cntnr::container_category>
{
typedef Cntnr container_type;
typedef typename Cntnr::container_category container_category;
typedef container_traits_base<container_category> base_type;
typedef typename base_type::invalidation_guarantee invalidation_guarantee;
enum
{
order_preserving = base_type::order_preserving,
erase_can_throw = base_type::erase_can_throw,
split_join_can_throw = base_type::split_join_can_throw,
reverse_iteration = base_type::reverse_iteration
};
};
}
#endif