libstdc++
tree_trace_base.hpp
Go to the documentation of this file.
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