tree_trace_base.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041 #ifndef PB_DS_TREE_TRACE_BASE_HPP
00042 #define PB_DS_TREE_TRACE_BASE_HPP
00043
00044 #ifdef PB_DS_TREE_TRACE
00045
00046 #include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp>
00047 #include <ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp>
00048
00049 namespace __gnu_pbds
00050 {
00051
00052 namespace detail
00053 {
00054
00055 #ifdef PB_DS_TREE_TRACE
00056
00057 #define PB_DS_CLASS_T_DEC \
00058 template< \
00059 class Const_Node_Iterator, \
00060 class Node_Iterator, \
00061 class Cmp_Fn, \
00062 bool Node_Based, \
00063 class Allocator>
00064
00065 #define PB_DS_CLASS_C_DEC \
00066 tree_trace_base< \
00067 Const_Node_Iterator, \
00068 Node_Iterator, \
00069 Cmp_Fn, \
00070 Node_Based, \
00071 Allocator>
00072
00073 #define PB_DS_BASE_C_DEC \
00074 basic_tree_policy_base< \
00075 Const_Node_Iterator, \
00076 Node_Iterator, \
00077 Allocator>
00078
00079 template<typename Const_Node_Iterator,
00080 class Node_Iterator,
00081 class Cmp_Fn,
00082 bool Node_Based,
00083 class Allocator>
00084 class tree_trace_base : private PB_DS_BASE_C_DEC
00085 {
00086 public:
00087 void
00088 trace() const;
00089
00090 private:
00091 typedef PB_DS_BASE_C_DEC base_type;
00092
00093 typedef Const_Node_Iterator const_node_iterator;
00094
00095 typedef typename Allocator::size_type size_type;
00096
00097 private:
00098 void
00099 trace_node(const_node_iterator nd_it, size_type level) const;
00100
00101 virtual bool
00102 empty() const = 0;
00103
00104 virtual const_node_iterator
00105 node_begin() const = 0;
00106
00107 virtual const_node_iterator
00108 node_end() const = 0;
00109
00110 static void
00111 print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,true>);
00112
00113 static void
00114 print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,false>);
00115
00116 template<typename Metadata_>
00117 static void
00118 trace_it_metadata(Const_Node_Iterator nd_it, type_to_type<Metadata_>);
00119
00120 static void
00121 trace_it_metadata(Const_Node_Iterator, type_to_type<null_node_metadata>);
00122 };
00123
00124 PB_DS_CLASS_T_DEC
00125 void
00126 PB_DS_CLASS_C_DEC::
00127 trace() const
00128 {
00129 if (empty())
00130 return;
00131
00132 trace_node(node_begin(), 0);
00133 }
00134
00135 PB_DS_CLASS_T_DEC
00136 void
00137 PB_DS_CLASS_C_DEC::
00138 trace_node(const_node_iterator nd_it, size_type level) const
00139 {
00140 if (nd_it.get_r_child() != node_end())
00141 trace_node(nd_it.get_r_child(), level + 1);
00142
00143 for (size_type i = 0; i < level; ++i)
00144 std::cerr << ' ';
00145
00146 print_node_pointer(nd_it, integral_constant<int,Node_Based>());
00147 std::cerr << base_type::extract_key(*(*nd_it));
00148
00149 typedef
00150 type_to_type<
00151 typename const_node_iterator::metadata_type>
00152 m_type_ind_t;
00153
00154 trace_it_metadata(nd_it, m_type_ind_t());
00155
00156 std::cerr << std::endl;
00157
00158 if (nd_it.get_l_child() != node_end())
00159 trace_node(nd_it.get_l_child(), level + 1);
00160 }
00161
00162 PB_DS_CLASS_T_DEC
00163 template<typename Metadata_>
00164 void
00165 PB_DS_CLASS_C_DEC::
00166 trace_it_metadata(Const_Node_Iterator nd_it, type_to_type<Metadata_>)
00167 {
00168 std::cerr << " (" <<
00169 static_cast<unsigned long>(nd_it.get_metadata()) << ") ";
00170 }
00171
00172 PB_DS_CLASS_T_DEC
00173 void
00174 PB_DS_CLASS_C_DEC::
00175 trace_it_metadata(Const_Node_Iterator, type_to_type<null_node_metadata>)
00176 { }
00177
00178 PB_DS_CLASS_T_DEC
00179 void
00180 PB_DS_CLASS_C_DEC::
00181 print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,true>)
00182 {
00183 std::cerr << nd_it.m_p_nd << " ";
00184 }
00185
00186 PB_DS_CLASS_T_DEC
00187 void
00188 PB_DS_CLASS_C_DEC::
00189 print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,false>)
00190 {
00191 std::cerr <<* nd_it << " ";
00192 }
00193
00194 #undef PB_DS_CLASS_T_DEC
00195
00196 #undef PB_DS_CLASS_C_DEC
00197
00198 #undef PB_DS_BASE_C_DEC
00199
00200 #endif // #ifdef PB_DS_TREE_TRACE
00201
00202 }
00203
00204 }
00205
00206 #endif // #ifdef PB_DS_TREE_TRACE
00207
00208 #endif // #ifndef PB_DS_TREE_TRACE_BASE_HPP
00209