1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License 17 // along with this library; see the file COPYING. If not, write to 18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19 // MA 02111-1307, USA. 20 21 // As a special exception, you may use this file as part of a free 22 // software library without restriction. Specifically, if other files 23 // instantiate templates or use macros or inline functions from this 24 // file, or you compile this file and link it with other files to 25 // produce an executable, this file does not by itself cause the 26 // resulting executable to be covered by the GNU General Public 27 // License. This exception does not however invalidate any other 28 // reasons why the executable file might be covered by the GNU General 29 // Public License. 30 31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33 // Permission to use, copy, modify, sell, and distribute this software 34 // is hereby granted without fee, provided that the above copyright 35 // notice appears in all copies, and that both that copyright notice 36 // and this permission notice appear in supporting documentation. None 37 // of the above authors, nor IBM Haifa Research Laboratories, make any 38 // representation about the suitability of this software for any 39 // purpose. It is provided "as is" without express or implied 40 // warranty. 41 42 /** 43 * @file node_iterators.hpp 44 * Contains an implementation class for bin_search_tree_. 45 */ 46 47 #ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP 48 #define PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP 49 50 #include <ext/pb_ds/tag_and_trait.hpp> 51 52 namespace pb_ds 53 { 54 namespace detail 55 { 56 57 #define PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC \ 58 bin_search_tree_const_node_it_< \ 59 Node, \ 60 Const_Iterator, \ 61 Iterator, \ 62 Allocator> 63 64 // Const node iterator. 65 template<typename Node, 66 class Const_Iterator, 67 class Iterator, 68 class Allocator> 69 class bin_search_tree_const_node_it_ 70 { 71 private: 72 73 private: 74 typedef 75 typename Allocator::template rebind< 76 Node>::other::pointer 77 node_pointer; 78 79 public: 80 81 // Category. 82 typedef trivial_iterator_tag iterator_category; 83 84 // Difference type. 85 typedef trivial_iterator_difference_type difference_type; 86 87 // __Iterator's value type. 88 typedef Const_Iterator value_type; 89 90 // __Iterator's reference type. 91 typedef Const_Iterator reference; 92 93 // __Iterator's __const reference type. 94 typedef Const_Iterator const_reference; 95 96 // Metadata type. 97 typedef typename Node::metadata_type metadata_type; 98 99 // Const metadata reference type. 100 typedef 101 typename Allocator::template rebind< 102 metadata_type>::other::const_reference 103 const_metadata_reference; 104 105 public: 106 107 // Default constructor. 108 /* 109 inline 110 bin_search_tree_const_node_it_() 111 */ 112 113 inline bin_search_tree_const_node_it_(const node_pointer p_nd=NULL)114 bin_search_tree_const_node_it_(const node_pointer p_nd = NULL) : m_p_nd(const_cast<node_pointer>(p_nd)) 115 { } 116 117 // Access. 118 inline const_reference operator *() const119 operator*() const 120 { 121 return (Const_Iterator(m_p_nd)); 122 } 123 124 // Metadata access. 125 inline const_metadata_reference get_metadata() const126 get_metadata() const 127 { 128 return (m_p_nd->get_metadata()); 129 } 130 131 // Returns the __const node iterator associated with the left node. 132 inline PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC get_l_child() const133 get_l_child() const 134 { 135 return (PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_left)); 136 } 137 138 // Returns the __const node iterator associated with the right node. 139 inline PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC get_r_child() const140 get_r_child() const 141 { 142 return (PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_right)); 143 } 144 145 // Compares to a different iterator object. 146 inline bool operator ==(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC & other) const147 operator==(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const 148 { 149 return (m_p_nd == other.m_p_nd); 150 } 151 152 // Compares (negatively) to a different iterator object. 153 inline bool operator !=(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC & other) const154 operator!=(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const 155 { 156 return (m_p_nd != other.m_p_nd); 157 } 158 159 public: 160 node_pointer m_p_nd; 161 }; 162 163 #define PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC \ 164 bin_search_tree_node_it_< \ 165 Node, \ 166 Const_Iterator, \ 167 Iterator, \ 168 Allocator> 169 170 // Node iterator. 171 template<typename Node, 172 class Const_Iterator, 173 class Iterator, 174 class Allocator> 175 class bin_search_tree_node_it_ : 176 public PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC 177 178 { 179 180 private: 181 typedef 182 typename Allocator::template rebind< 183 Node>::other::pointer 184 node_pointer; 185 186 public: 187 188 // __Iterator's value type. 189 typedef Iterator value_type; 190 191 // __Iterator's reference type. 192 typedef Iterator reference; 193 194 // __Iterator's __const reference type. 195 typedef Iterator const_reference; 196 197 public: 198 199 // Default constructor. 200 /* 201 inline 202 bin_search_tree_node_it_(); 203 */ 204 205 inline bin_search_tree_node_it_(const node_pointer p_nd=NULL)206 bin_search_tree_node_it_(const node_pointer p_nd = NULL) : PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC( 207 const_cast<node_pointer>(p_nd)) 208 { } 209 210 // Access. 211 inline Iterator operator *() const212 operator*() const 213 { 214 return (Iterator(PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd)); 215 } 216 217 // Returns the node iterator associated with the left node. 218 inline PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC get_l_child() const219 get_l_child() const 220 { 221 return (PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC( 222 PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_left)); 223 } 224 225 // Returns the node iterator associated with the right node. 226 inline PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC get_r_child() const227 get_r_child() const 228 { 229 return (PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC( 230 PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_right)); 231 } 232 233 }; 234 235 #undef PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC 236 237 #undef PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC 238 239 } // namespace detail 240 } // namespace pb_ds 241 242 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP 243 244