libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file tree_trace_base.hpp 00038 * Contains tree-related policies. 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 } // namespace detail 00203 00204 } // namespace __gnu_pbds 00205 00206 #endif // #ifdef PB_DS_TREE_TRACE 00207 00208 #endif // #ifndef PB_DS_TREE_TRACE_BASE_HPP 00209