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