// -*- C++ -*-
-// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+// Copyright (C) 2005-2020 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// warranty.
/**
- * @file tree_trace_base.hpp
+ * @file detail/tree_trace_base.hpp
* Contains tree-related policies.
*/
#ifdef PB_DS_TREE_TRACE
-#include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp>
-#include <ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp>
+#include <ext/pb_ds/detail/branch_policy/branch_policy.hpp>
+#include <ext/pb_ds/detail/branch_policy/null_node_metadata.hpp>
namespace __gnu_pbds
{
-
namespace detail
{
-
#ifdef PB_DS_TREE_TRACE
#define PB_DS_CLASS_T_DEC \
- template< \
- class Const_Node_Iterator, \
- class Node_Iterator, \
- class Cmp_Fn, \
- bool Node_Based, \
- class Allocator>
+ template<typename Node_CItr, typename Node_Itr, \
+ typename Cmp_Fn, bool Node_Based, typename _Alloc>
#define PB_DS_CLASS_C_DEC \
- tree_trace_base< \
- Const_Node_Iterator, \
- Node_Iterator, \
- Cmp_Fn, \
- Node_Based, \
- Allocator>
-
-#define PB_DS_BASE_C_DEC \
- basic_tree_policy_base< \
- Const_Node_Iterator, \
- Node_Iterator, \
- Allocator>
-
- template<typename Const_Node_Iterator,
- class Node_Iterator,
- class Cmp_Fn,
- bool Node_Based,
- class Allocator>
- class tree_trace_base : private PB_DS_BASE_C_DEC
+ tree_trace_base<Node_CItr, Node_Itr, Cmp_Fn, \
+ Node_Based, _Alloc>
+
+#define PB_DS_TRACE_BASE \
+ branch_policy<Node_CItr, Node_Itr, _Alloc>
+
+ /// Tracing base class.
+ template<typename Node_CItr, typename Node_Itr,
+ typename Cmp_Fn, bool Node_Based, typename _Alloc>
+ class tree_trace_base : private PB_DS_TRACE_BASE
{
public:
void
trace() const;
private:
- typedef PB_DS_BASE_C_DEC base_type;
-
- typedef Const_Node_Iterator const_node_iterator;
+ typedef PB_DS_TRACE_BASE base_type;
+ typedef Node_CItr node_const_iterator;
+ typedef typename _Alloc::size_type size_type;
- typedef typename Allocator::size_type size_type;
-
- private:
void
- trace_node(const_node_iterator nd_it, size_type level) const;
+ trace_node(node_const_iterator, size_type) const;
- virtual bool
+ _GLIBCXX_NODISCARD virtual bool
empty() const = 0;
- virtual const_node_iterator
+ virtual node_const_iterator
node_begin() const = 0;
- virtual const_node_iterator
+ virtual node_const_iterator
node_end() const = 0;
static void
- print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,true>);
+ print_node_pointer(Node_CItr, integral_constant<int,true>);
static void
- print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,false>);
+ print_node_pointer(Node_CItr, integral_constant<int,false>);
template<typename Metadata_>
static void
- trace_it_metadata(Const_Node_Iterator nd_it, type_to_type<Metadata_>);
+ trace_it_metadata(Node_CItr, type_to_type<Metadata_>);
static void
- trace_it_metadata(Const_Node_Iterator, type_to_type<null_node_metadata>);
+ trace_it_metadata(Node_CItr, type_to_type<null_type>);
};
PB_DS_CLASS_T_DEC
trace() const
{
if (empty())
- return;
-
+ return;
trace_node(node_begin(), 0);
}
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
- trace_node(const_node_iterator nd_it, size_type level) const
+ trace_node(node_const_iterator nd_it, size_type level) const
{
if (nd_it.get_r_child() != node_end())
- trace_node(nd_it.get_r_child(), level + 1);
+ trace_node(nd_it.get_r_child(), level + 1);
for (size_type i = 0; i < level; ++i)
- std::cerr << ' ';
+ std::cerr << ' ';
print_node_pointer(nd_it, integral_constant<int,Node_Based>());
std::cerr << base_type::extract_key(*(*nd_it));
- typedef
- type_to_type<
- typename const_node_iterator::metadata_type>
- m_type_ind_t;
+ typedef type_to_type<typename node_const_iterator::metadata_type>
+ m_type_ind_t;
trace_it_metadata(nd_it, m_type_ind_t());
std::cerr << std::endl;
if (nd_it.get_l_child() != node_end())
- trace_node(nd_it.get_l_child(), level + 1);
+ trace_node(nd_it.get_l_child(), level + 1);
}
PB_DS_CLASS_T_DEC
template<typename Metadata_>
void
PB_DS_CLASS_C_DEC::
- trace_it_metadata(Const_Node_Iterator nd_it, type_to_type<Metadata_>)
+ trace_it_metadata(Node_CItr nd_it, type_to_type<Metadata_>)
{
- std::cerr << " (" <<
- static_cast<unsigned long>(nd_it.get_metadata()) << ") ";
+ const unsigned long ul = static_cast<unsigned long>(nd_it.get_metadata());
+ std::cerr << " (" << ul << ") ";
}
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
- trace_it_metadata(Const_Node_Iterator, type_to_type<null_node_metadata>)
+ trace_it_metadata(Node_CItr, type_to_type<null_type>)
{ }
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
- print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,true>)
- {
- std::cerr << nd_it.m_p_nd << " ";
- }
+ print_node_pointer(Node_CItr nd_it, integral_constant<int,true>)
+ { std::cerr << nd_it.m_p_nd << " "; }
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
- print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,false>)
- {
- std::cerr <<* nd_it << " ";
- }
+ print_node_pointer(Node_CItr nd_it, integral_constant<int,false>)
+ { std::cerr << *nd_it << " "; }
#undef PB_DS_CLASS_T_DEC
-
#undef PB_DS_CLASS_C_DEC
-
-#undef PB_DS_BASE_C_DEC
-
+#undef PB_DS_TRACE_BASE
#endif // #ifdef PB_DS_TREE_TRACE
} // namespace detail
-
} // namespace __gnu_pbds
#endif // #ifdef PB_DS_TREE_TRACE
#endif // #ifndef PB_DS_TREE_TRACE_BASE_HPP
-