libstdc++
tree_trace_base.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10 
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26 
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
34 // warranty.
35 
36 /**
37  * @file tree_trace_base.hpp
38  * Contains tree-related policies.
39  */
40 
41 #ifndef PB_DS_TREE_TRACE_BASE_HPP
42 #define PB_DS_TREE_TRACE_BASE_HPP
43 
44 #ifdef PB_DS_TREE_TRACE
45 
46 #include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp>
47 #include <ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp>
48 
49 namespace __gnu_pbds
50 {
51 
52  namespace detail
53  {
54 
55 #ifdef PB_DS_TREE_TRACE
56 
57 #define PB_DS_CLASS_T_DEC \
58  template< \
59  class Const_Node_Iterator, \
60  class Node_Iterator, \
61  class Cmp_Fn, \
62  bool Node_Based, \
63  class Allocator>
64 
65 #define PB_DS_CLASS_C_DEC \
66  tree_trace_base< \
67  Const_Node_Iterator, \
68  Node_Iterator, \
69  Cmp_Fn, \
70  Node_Based, \
71  Allocator>
72 
73 #define PB_DS_BASE_C_DEC \
74  basic_tree_policy_base< \
75  Const_Node_Iterator, \
76  Node_Iterator, \
77  Allocator>
78 
79  template<typename Const_Node_Iterator,
80  class Node_Iterator,
81  class Cmp_Fn,
82  bool Node_Based,
83  class Allocator>
84  class tree_trace_base : private PB_DS_BASE_C_DEC
85  {
86  public:
87  void
88  trace() const;
89 
90  private:
91  typedef PB_DS_BASE_C_DEC base_type;
92 
93  typedef Const_Node_Iterator const_node_iterator;
94 
95  typedef typename Allocator::size_type size_type;
96 
97  private:
98  void
99  trace_node(const_node_iterator nd_it, size_type level) const;
100 
101  virtual bool
102  empty() const = 0;
103 
104  virtual const_node_iterator
105  node_begin() const = 0;
106 
107  virtual const_node_iterator
108  node_end() const = 0;
109 
110  static void
111  print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,true>);
112 
113  static void
114  print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,false>);
115 
116  template<typename Metadata_>
117  static void
118  trace_it_metadata(Const_Node_Iterator nd_it, type_to_type<Metadata_>);
119 
120  static void
121  trace_it_metadata(Const_Node_Iterator, type_to_type<null_node_metadata>);
122  };
123 
124  PB_DS_CLASS_T_DEC
125  void
126  PB_DS_CLASS_C_DEC::
127  trace() const
128  {
129  if (empty())
130  return;
131 
132  trace_node(node_begin(), 0);
133  }
134 
135  PB_DS_CLASS_T_DEC
136  void
137  PB_DS_CLASS_C_DEC::
138  trace_node(const_node_iterator nd_it, size_type level) const
139  {
140  if (nd_it.get_r_child() != node_end())
141  trace_node(nd_it.get_r_child(), level + 1);
142 
143  for (size_type i = 0; i < level; ++i)
144  std::cerr << ' ';
145 
146  print_node_pointer(nd_it, integral_constant<int,Node_Based>());
147  std::cerr << base_type::extract_key(*(*nd_it));
148 
149  typedef
150  type_to_type<
151  typename const_node_iterator::metadata_type>
152  m_type_ind_t;
153 
154  trace_it_metadata(nd_it, m_type_ind_t());
155 
156  std::cerr << std::endl;
157 
158  if (nd_it.get_l_child() != node_end())
159  trace_node(nd_it.get_l_child(), level + 1);
160  }
161 
162  PB_DS_CLASS_T_DEC
163  template<typename Metadata_>
164  void
165  PB_DS_CLASS_C_DEC::
166  trace_it_metadata(Const_Node_Iterator nd_it, type_to_type<Metadata_>)
167  {
168  std::cerr << " (" <<
169  static_cast<unsigned long>(nd_it.get_metadata()) << ") ";
170  }
171 
172  PB_DS_CLASS_T_DEC
173  void
174  PB_DS_CLASS_C_DEC::
175  trace_it_metadata(Const_Node_Iterator, type_to_type<null_node_metadata>)
176  { }
177 
178  PB_DS_CLASS_T_DEC
179  void
180  PB_DS_CLASS_C_DEC::
181  print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,true>)
182  {
183  std::cerr << nd_it.m_p_nd << " ";
184  }
185 
186  PB_DS_CLASS_T_DEC
187  void
188  PB_DS_CLASS_C_DEC::
189  print_node_pointer(Const_Node_Iterator nd_it, integral_constant<int,false>)
190  {
191  std::cerr <<* nd_it << " ";
192  }
193 
194 #undef PB_DS_CLASS_T_DEC
195 
196 #undef PB_DS_CLASS_C_DEC
197 
198 #undef PB_DS_BASE_C_DEC
199 
200 #endif // #ifdef PB_DS_TREE_TRACE
201 
202  } // namespace detail
203 
204 } // namespace __gnu_pbds
205 
206 #endif // #ifdef PB_DS_TREE_TRACE
207 
208 #endif // #ifndef PB_DS_TREE_TRACE_BASE_HPP
209 
basic_ostream< _CharT, _Traits > & endl(basic_ostream< _CharT, _Traits > &__os)
Write a newline and flush the stream.
Definition: ostream:543
ostream cerr
Linked to standard output.