// warranty.
/**
- * @file bin_search_tree_.hpp
- * Contains an implementation class for bin_search_tree_.
- */
-/*
- * This implementation uses an idea from the SGI STL (using a @a header node
- * which is needed for efficient iteration).
+ * @file bin_search_tree_/bin_search_tree_.hpp
+ * Contains an implementation class for binary search tree.
*/
#include <ext/pb_ds/exception.hpp>
+#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
#include <ext/pb_ds/detail/types_traits.hpp>
-#include <ext/pb_ds/detail/debug_map_base.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/tree_trace_base.hpp>
+#ifdef _GLIBCXX_DEBUG
+#include <ext/pb_ds/detail/debug_map_base.hpp>
+#endif
#include <utility>
#include <functional>
#include <debug/debug.h>
{
namespace detail
{
-
-#define PB_DS_CLASS_T_DEC \
- template<typename Key, typename Mapped, class Cmp_Fn, \
- class Node_And_It_Traits, class Allocator>
-
#ifdef PB_DS_DATA_TRUE_INDICATOR
-#define PB_DS_CLASS_NAME \
- bin_search_tree_data_
-#endif
+#define PB_DS_BIN_TREE_NAME bin_search_tree_map
+#endif
#ifdef PB_DS_DATA_FALSE_INDICATOR
-#define PB_DS_CLASS_NAME \
- bin_search_tree_no_data_
-#endif
-
-#define PB_DS_CLASS_C_DEC \
- PB_DS_CLASS_NAME< \
- Key, \
- Mapped, \
- Cmp_Fn, \
- Node_And_It_Traits, \
- Allocator>
-
-#define PB_DS_TYPES_TRAITS_C_DEC \
- types_traits< \
- Key, \
- Mapped, \
- Allocator, \
- false>
+#define PB_DS_BIN_TREE_NAME bin_search_tree_set
+#endif
-#ifdef _GLIBCXX_DEBUG
-#define PB_DS_DEBUG_MAP_BASE_C_DEC \
- debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
- typename Allocator::template rebind<Key>::other::const_reference>
-#endif
+#define PB_DS_CLASS_T_DEC \
+ template<typename Key, typename Mapped, typename Cmp_Fn, \
+ typename Node_And_It_Traits, typename _Alloc>
-#ifdef PB_DS_DATA_TRUE_INDICATOR
-#define PB_DS_V2F(X) (X).first
-#define PB_DS_V2S(X) (X).second
-#define PB_DS_EP2VP(X)& ((X)->m_value)
-#endif
+#define PB_DS_CLASS_C_DEC \
+ PB_DS_BIN_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>
-#ifdef PB_DS_DATA_FALSE_INDICATOR
-#define PB_DS_V2F(X) (X)
-#define PB_DS_V2S(X) Mapped_Data()
-#define PB_DS_EP2VP(X)& ((X)->m_value.first)
-#endif
+#define PB_DS_BIN_TREE_TRAITS_BASE \
+ types_traits<Key, Mapped, _Alloc, false>
+
+#ifdef _GLIBCXX_DEBUG
+#define PB_DS_DEBUG_MAP_BASE_C_DEC \
+ debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
+ typename _Alloc::template rebind<Key>::other::const_reference>
+#endif
#ifdef PB_DS_TREE_TRACE
-#define PB_DS_TREE_TRACE_BASE_C_DEC \
- tree_trace_base< \
- typename Node_And_It_Traits::const_node_iterator, \
- typename Node_And_It_Traits::node_iterator, \
- Cmp_Fn, \
- true, \
- Allocator>
-#endif
-
- /**
- * class description = "8i|\|4ree $34rc|-| 7r33 74813.">
- **/
- template<typename Key,
- typename Mapped,
- class Cmp_Fn,
- class Node_And_It_Traits,
- class Allocator>
- class PB_DS_CLASS_NAME :
+#define PB_DS_TREE_TRACE_BASE_C_DEC \
+ tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \
+ typename Node_And_It_Traits::node_iterator, \
+ Cmp_Fn, true, _Alloc>
+#endif
+
+
+ /*
+ * @brief Binary search tree (BST).
+ *
+ * This implementation uses an idea from the SGI STL (using a @a
+ * header node which is needed for efficient iteration).
+ */
+ template<typename Key, typename Mapped, typename Cmp_Fn,
+ typename Node_And_It_Traits, typename _Alloc>
+ class PB_DS_BIN_TREE_NAME :
#ifdef _GLIBCXX_DEBUG
public PB_DS_DEBUG_MAP_BASE_C_DEC,
-#endif
+#endif
#ifdef PB_DS_TREE_TRACE
public PB_DS_TREE_TRACE_BASE_C_DEC,
-#endif
+#endif
public Cmp_Fn,
- public PB_DS_TYPES_TRAITS_C_DEC,
+ public PB_DS_BIN_TREE_TRAITS_BASE,
public Node_And_It_Traits::node_update
{
+ typedef Node_And_It_Traits traits_type;
protected:
+ typedef PB_DS_BIN_TREE_TRAITS_BASE traits_base;
+
typedef
- typename Allocator::template rebind<
- typename Node_And_It_Traits::node>::other
+ typename _Alloc::template rebind<typename traits_type::node>::other
node_allocator;
- typedef typename node_allocator::value_type node;
-
- typedef typename node_allocator::pointer node_pointer;
+ typedef typename node_allocator::value_type node;
+ typedef typename node_allocator::pointer node_pointer;
- typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
-
- typedef
- typename Node_And_It_Traits::null_node_update_pointer
+ typedef typename traits_type::null_node_update_pointer
null_node_update_pointer;
private:
- typedef cond_dealtor< node, Allocator> cond_dealtor_t;
+ typedef cond_dealtor<node, _Alloc> cond_dealtor_t;
#ifdef _GLIBCXX_DEBUG
- typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
-#endif
+ typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
+#endif
public:
-
- typedef typename Allocator::size_type size_type;
-
- typedef typename Allocator::difference_type difference_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
- const_key_pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
- const_key_reference;
+ typedef typename _Alloc::size_type size_type;
+ typedef typename _Alloc::difference_type difference_type;
+ typedef typename traits_base::key_type key_type;
+ typedef typename traits_base::key_pointer key_pointer;
+ typedef typename traits_base::key_const_pointer key_const_pointer;
+ typedef typename traits_base::key_reference key_reference;
+ typedef typename traits_base::key_const_reference key_const_reference;
#ifdef PB_DS_DATA_TRUE_INDICATOR
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
- mapped_pointer;
+ typedef typename traits_base::mapped_type mapped_type;
+ typedef typename traits_base::mapped_pointer mapped_pointer;
+ typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
+ typedef typename traits_base::mapped_reference mapped_reference;
+ typedef typename traits_base::mapped_const_reference mapped_const_reference;
+#endif
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
- const_mapped_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
- mapped_reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
- const_mapped_reference;
-#endif
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
- const_reference;
-
- typedef
- typename Node_And_It_Traits::const_point_iterator
- const_point_iterator;
-
- typedef const_point_iterator const_iterator;
-
- typedef typename Node_And_It_Traits::point_iterator point_iterator;
+ typedef typename traits_base::value_type value_type;
+ typedef typename traits_base::pointer pointer;
+ typedef typename traits_base::const_pointer const_pointer;
+ typedef typename traits_base::reference reference;
+ typedef typename traits_base::const_reference const_reference;
+ typedef typename traits_type::point_const_iterator point_const_iterator;
- typedef point_iterator iterator;
+ typedef point_const_iterator const_iterator;
+ typedef typename traits_type::point_iterator point_iterator;
+ typedef point_iterator iterator;
- typedef
- typename Node_And_It_Traits::const_reverse_iterator
- const_reverse_iterator;
-
- typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
-
- typedef
- typename Node_And_It_Traits::const_node_iterator
- const_node_iterator;
+ typedef typename traits_type::const_reverse_iterator const_reverse_iterator;
- typedef typename Node_And_It_Traits::node_iterator node_iterator;
+ typedef typename traits_type::reverse_iterator reverse_iterator;
+ typedef typename traits_type::node_const_iterator node_const_iterator;
+ typedef typename traits_type::node_iterator node_iterator;
+ typedef typename traits_type::node_update node_update;
- typedef Cmp_Fn cmp_fn;
-
- typedef Allocator allocator_type;
-
- typedef typename Node_And_It_Traits::node_update node_update;
-
- public:
+ typedef Cmp_Fn cmp_fn;
+ typedef _Alloc allocator_type;
- PB_DS_CLASS_NAME();
+ PB_DS_BIN_TREE_NAME();
- PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
+ PB_DS_BIN_TREE_NAME(const Cmp_Fn&);
- PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update);
+ PB_DS_BIN_TREE_NAME(const Cmp_Fn&, const node_update&);
- PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
+ PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC&);
void
- swap(PB_DS_CLASS_C_DEC& other);
+ swap(PB_DS_CLASS_C_DEC&);
- ~PB_DS_CLASS_NAME();
+ ~PB_DS_BIN_TREE_NAME();
inline bool
empty() const;
inline size_type
max_size() const;
- Cmp_Fn&
+ Cmp_Fn&
get_cmp_fn();
- const Cmp_Fn&
+ const Cmp_Fn&
get_cmp_fn() const;
inline point_iterator
- lower_bound(const_key_reference r_key);
+ lower_bound(key_const_reference);
- inline const_point_iterator
- lower_bound(const_key_reference r_key) const;
+ inline point_const_iterator
+ lower_bound(key_const_reference) const;
inline point_iterator
- upper_bound(const_key_reference r_key);
+ upper_bound(key_const_reference);
- inline const_point_iterator
- upper_bound(const_key_reference r_key) const;
+ inline point_const_iterator
+ upper_bound(key_const_reference) const;
inline point_iterator
- find(const_key_reference r_key);
+ find(key_const_reference);
- inline const_point_iterator
- find(const_key_reference r_key) const;
+ inline point_const_iterator
+ find(key_const_reference) const;
inline iterator
begin();
inline const_reverse_iterator
rend() const;
- inline const_node_iterator
+ inline node_const_iterator
node_begin() const;
inline node_iterator
node_begin();
- inline const_node_iterator
+ inline node_const_iterator
node_end() const;
inline node_iterator
clear();
protected:
-
void
- value_swap(PB_DS_CLASS_C_DEC& other);
+ value_swap(PB_DS_CLASS_C_DEC&);
void
initialize_min_max();
inline iterator
- insert_imp_empty(const_reference r_value);
+ insert_imp_empty(const_reference);
inline iterator
- insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd);
+ insert_leaf_new(const_reference, node_pointer, bool);
inline node_pointer
- get_new_node_for_leaf_insert(const_reference r_val, false_type);
+ get_new_node_for_leaf_insert(const_reference, false_type);
inline node_pointer
- get_new_node_for_leaf_insert(const_reference r_val, true_type);
+ get_new_node_for_leaf_insert(const_reference, true_type);
inline void
- actual_erase_node(node_pointer p_nd);
+ actual_erase_node(node_pointer);
inline std::pair<node_pointer, bool>
- erase(node_pointer p_nd);
+ erase(node_pointer);
inline void
- update_min_max_for_erased_node(node_pointer p_nd);
+ update_min_max_for_erased_node(node_pointer);
static void
- clear_imp(node_pointer p_nd);
+ clear_imp(node_pointer);
- inline std::pair<
- point_iterator,
- bool>
- insert_leaf(const_reference r_value);
+ inline std::pair<point_iterator, bool>
+ insert_leaf(const_reference);
inline void
- rotate_left(node_pointer p_x);
+ rotate_left(node_pointer);
inline void
- rotate_right(node_pointer p_y);
+ rotate_right(node_pointer);
inline void
- rotate_parent(node_pointer p_nd);
+ rotate_parent(node_pointer);
inline void
- apply_update(node_pointer p_nd, null_node_update_pointer);
+ apply_update(node_pointer, null_node_update_pointer);
template<typename Node_Update_>
- inline void
- apply_update(node_pointer p_nd, Node_Update_* p_update);
+ inline void
+ apply_update(node_pointer, Node_Update_*);
inline void
- update_to_top(node_pointer p_nd, null_node_update_pointer);
+ update_to_top(node_pointer, null_node_update_pointer);
template<typename Node_Update_>
- inline void
- update_to_top(node_pointer p_nd, Node_Update_* p_update);
+ inline void
+ update_to_top(node_pointer, Node_Update_*);
bool
- join_prep(PB_DS_CLASS_C_DEC& other);
+ join_prep(PB_DS_CLASS_C_DEC&);
void
- join_finish(PB_DS_CLASS_C_DEC& other);
+ join_finish(PB_DS_CLASS_C_DEC&);
bool
- split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
+ split_prep(key_const_reference, PB_DS_CLASS_C_DEC&);
void
- split_finish(PB_DS_CLASS_C_DEC& other);
+ split_finish(PB_DS_CLASS_C_DEC&);
size_type
- recursive_count(node_pointer p_nd) const;
+ recursive_count(node_pointer) const;
#ifdef _GLIBCXX_DEBUG
void
- assert_valid(const char* file, int line) const;
+ assert_valid(const char*, int) const;
void
- structure_only_assert_valid(const char* file, int line) const;
+ structure_only_assert_valid(const char*, int) const;
void
- assert_node_consistent(const node_pointer p_nd,
- const char* file, int line) const;
-#endif
+ assert_node_consistent(const node_pointer, const char*, int) const;
+#endif
private:
#ifdef _GLIBCXX_DEBUG
void
- assert_iterators(const char* file, int line) const;
+ assert_iterators(const char*, int) const;
void
- assert_consistent_with_debug_base(const char* file, int line) const;
+ assert_consistent_with_debug_base(const char*, int) const;
void
- assert_node_consistent_with_left(const node_pointer p_nd,
- const char* file, int line) const;
+ assert_node_consistent_with_left(const node_pointer,
+ const char*, int) const;
void
- assert_node_consistent_with_right(const node_pointer p_nd,
- const char* file, int line) const;
+ assert_node_consistent_with_right(const node_pointer,
+ const char*, int) const;
void
- assert_consistent_with_debug_base(const node_pointer p_nd,
- const char* file, int line) const;
+ assert_consistent_with_debug_base(const node_pointer,
+ const char*, int) const;
void
- assert_min(const char* file, int line) const;
+ assert_min(const char*, int) const;
void
- assert_min_imp(const node_pointer p_nd,
- const char* file, int line) const;
+ assert_min_imp(const node_pointer, const char*, int) const;
void
- assert_max(const char* file, int line) const;
+ assert_max(const char*, int) const;
void
- assert_max_imp(const node_pointer p_nd,
- const char* file, int line) const;
+ assert_max_imp(const node_pointer, const char*, int) const;
void
- assert_size(const char* file, int line) const;
+ assert_size(const char*, int) const;
- typedef std::pair< const_pointer, const_pointer> node_consistent_t;
+ typedef std::pair<const_pointer, const_pointer> node_consistent_t;
node_consistent_t
- assert_node_consistent_(const node_pointer p_nd,
- const char* file, int line) const;
-#endif
+ assert_node_consistent_(const node_pointer, const char*, int) const;
+#endif
void
initialize();
node_pointer
- recursive_copy_node(const node_pointer p_nd);
+ recursive_copy_node(const node_pointer);
protected:
- node_pointer m_p_head;
-
- size_type m_size;
-
- static node_allocator s_node_allocator;
+ node_pointer m_p_head;
+ size_type m_size;
+ static node_allocator s_node_allocator;
};
#define PB_DS_STRUCT_ONLY_ASSERT_VALID(X) \
#undef PB_DS_STRUCT_ONLY_ASSERT_VALID
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_T_DEC
-#undef PB_DS_CLASS_NAME
-#undef PB_DS_TYPES_TRAITS_C_DEC
+#undef PB_DS_BIN_TREE_NAME
+#undef PB_DS_BIN_TREE_TRAITS_BASE
#undef PB_DS_DEBUG_MAP_BASE_C_DEC
#ifdef PB_DS_TREE_TRACE
#undef PB_DS_TREE_TRACE_BASE_C_DEC
-#endif
-
-#undef PB_DS_V2F
-#undef PB_DS_EP2VP
-#undef PB_DS_V2S
-
+#endif
} // namespace detail
} // namespace __gnu_pbds
projects / thirdparty / gcc.git / blobdiff