libstdc++
bin_search_tree_/node_iterators.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009, 2010 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 bin_search_tree_/node_iterators.hpp
38  * Contains an implementation class for bin_search_tree_.
39  */
40 
41 #ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP
42 #define PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP
43 
45 
46 namespace __gnu_pbds
47 {
48  namespace detail
49  {
50 #define PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC \
51  bin_search_tree_const_node_it_<Node, Const_Iterator, Iterator, _Alloc>
52 
53  /// Const node iterator.
54  template<typename Node,
55  class Const_Iterator,
56  class Iterator,
57  typename _Alloc>
59  {
60  private:
61  typedef
62  typename _Alloc::template rebind<
63  Node>::other::pointer
64  node_pointer;
65 
66  public:
67  /// Category.
69 
70  /// Difference type.
72 
73  /// Iterator's value type.
74  typedef Const_Iterator value_type;
75 
76  /// Iterator's reference type.
77  typedef Const_Iterator reference;
78 
79  /// Iterator's __const reference type.
80  typedef Const_Iterator const_reference;
81 
82  /// Metadata type.
83  typedef typename Node::metadata_type metadata_type;
84 
85  /// Const metadata reference type.
86  typedef
87  typename _Alloc::template rebind<metadata_type>::other::const_reference
89 
90 
91  bin_search_tree_const_node_it_(const node_pointer p_nd = 0)
92  : m_p_nd(const_cast<node_pointer>(p_nd))
93  { }
94 
95  /// Access.
97  operator*() const
98  { return Const_Iterator(m_p_nd); }
99 
100  /// Metadata access.
102  get_metadata() const
103  { return m_p_nd->get_metadata(); }
104 
105  /// Returns the __const node iterator associated with the left node.
106  PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
107  get_l_child() const
108  { return PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_left); }
109 
110  /// Returns the __const node iterator associated with the right node.
111  PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
112  get_r_child() const
113  { return PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_right); }
114 
115  /// Compares to a different iterator object.
116  bool
117  operator==(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const
118  { return m_p_nd == other.m_p_nd; }
119 
120  /// Compares (negatively) to a different iterator object.
121  bool
122  operator!=(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const
123  { return m_p_nd != other.m_p_nd; }
124 
125  node_pointer m_p_nd;
126  };
127 
128 #define PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC \
129  bin_search_tree_node_it_<Node, Const_Iterator, Iterator, _Alloc>
130 
131  /// Node iterator.
132  template<typename Node,
133  class Const_Iterator,
134  class Iterator,
135  typename _Alloc>
137  : public PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
138  {
139  private:
140  typedef
141  typename _Alloc::template rebind<
142  Node>::other::pointer
143  node_pointer;
144 
145  public:
146  /// Iterator's value type.
147  typedef Iterator value_type;
148 
149  /// Iterator's reference type.
150  typedef Iterator reference;
151 
152  /// Iterator's __const reference type.
153  typedef Iterator const_reference;
154 
155  inline
156  bin_search_tree_node_it_(const node_pointer p_nd = 0)
157  : PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(const_cast<node_pointer>(p_nd))
158  { }
159 
160  /// Access.
161  Iterator
162  operator*() const
163  { return Iterator(PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd); }
164 
165  /// Returns the node iterator associated with the left node.
166  PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
167  get_l_child() const
168  {
169  return PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC(
170  PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_left);
171  }
172 
173  /// Returns the node iterator associated with the right node.
174  PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
175  get_r_child() const
176  {
177  return PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC(
178  PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_right);
179  }
180 
181  };
182 
183 #undef PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
184 #undef PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
185 
186  } // namespace detail
187 } // namespace __gnu_pbds
188 
189 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP