libstdc++
tree_trace_base.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2014 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 detail/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 
48 
49 namespace __gnu_pbds
50 {
51  namespace detail
52  {
53 #ifdef PB_DS_TREE_TRACE
54 
55 #define PB_DS_CLASS_T_DEC \
56  template<typename Node_CItr, typename Node_Itr, \
57  typename Cmp_Fn, bool Node_Based, typename _Alloc>
58 
59 #define PB_DS_CLASS_C_DEC \
60  tree_trace_base<Node_CItr, Node_Itr, Cmp_Fn, \
61  Node_Based, _Alloc>
62 
63 #define PB_DS_TRACE_BASE \
64  branch_policy<Node_CItr, Node_Itr, _Alloc>
65 
66  /// Tracing base class.
67  template<typename Node_CItr, typename Node_Itr,
68  typename Cmp_Fn, bool Node_Based, typename _Alloc>
69  class tree_trace_base : private PB_DS_TRACE_BASE
70  {
71  public:
72  void
73  trace() const;
74 
75  private:
76  typedef PB_DS_TRACE_BASE base_type;
77  typedef Node_CItr node_const_iterator;
78  typedef typename _Alloc::size_type size_type;
79 
80  void
81  trace_node(node_const_iterator, size_type) const;
82 
83  virtual bool
84  empty() const = 0;
85 
86  virtual node_const_iterator
87  node_begin() const = 0;
88 
89  virtual node_const_iterator
90  node_end() const = 0;
91 
92  static void
93  print_node_pointer(Node_CItr, integral_constant<int,true>);
94 
95  static void
96  print_node_pointer(Node_CItr, integral_constant<int,false>);
97 
98  template<typename Metadata_>
99  static void
100  trace_it_metadata(Node_CItr, type_to_type<Metadata_>);
101 
102  static void
103  trace_it_metadata(Node_CItr, type_to_type<null_type>);
104  };
105 
106  PB_DS_CLASS_T_DEC
107  void
108  PB_DS_CLASS_C_DEC::
109  trace() const
110  {
111  if (empty())
112  return;
113  trace_node(node_begin(), 0);
114  }
115 
116  PB_DS_CLASS_T_DEC
117  void
118  PB_DS_CLASS_C_DEC::
119  trace_node(node_const_iterator nd_it, size_type level) const
120  {
121  if (nd_it.get_r_child() != node_end())
122  trace_node(nd_it.get_r_child(), level + 1);
123 
124  for (size_type i = 0; i < level; ++i)
125  std::cerr << ' ';
126 
127  print_node_pointer(nd_it, integral_constant<int,Node_Based>());
128  std::cerr << base_type::extract_key(*(*nd_it));
129 
130  typedef type_to_type<typename node_const_iterator::metadata_type>
131  m_type_ind_t;
132 
133  trace_it_metadata(nd_it, m_type_ind_t());
134 
135  std::cerr << std::endl;
136 
137  if (nd_it.get_l_child() != node_end())
138  trace_node(nd_it.get_l_child(), level + 1);
139  }
140 
141  PB_DS_CLASS_T_DEC
142  template<typename Metadata_>
143  void
144  PB_DS_CLASS_C_DEC::
145  trace_it_metadata(Node_CItr nd_it, type_to_type<Metadata_>)
146  {
147  const unsigned long ul = static_cast<unsigned long>(nd_it.get_metadata());
148  std::cerr << " (" << ul << ") ";
149  }
150 
151  PB_DS_CLASS_T_DEC
152  void
153  PB_DS_CLASS_C_DEC::
154  trace_it_metadata(Node_CItr, type_to_type<null_type>)
155  { }
156 
157  PB_DS_CLASS_T_DEC
158  void
159  PB_DS_CLASS_C_DEC::
160  print_node_pointer(Node_CItr nd_it, integral_constant<int,true>)
161  { std::cerr << nd_it.m_p_nd << " "; }
162 
163  PB_DS_CLASS_T_DEC
164  void
165  PB_DS_CLASS_C_DEC::
166  print_node_pointer(Node_CItr nd_it, integral_constant<int,false>)
167  { std::cerr << *nd_it << " "; }
168 
169 #undef PB_DS_CLASS_T_DEC
170 #undef PB_DS_CLASS_C_DEC
171 #undef PB_DS_TRACE_BASE
172 #endif // #ifdef PB_DS_TREE_TRACE
173 
174  } // namespace detail
175 } // namespace __gnu_pbds
176 
177 #endif // #ifdef PB_DS_TREE_TRACE
178 
179 #endif // #ifndef PB_DS_TREE_TRACE_BASE_HPP
GNU extensions for policy-based data structures for public use.