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 ov_tree_. 45 */ 46 47 #ifndef PB_DS_OV_TREE_NODE_ITERATORS_HPP 48 #define PB_DS_OV_TREE_NODE_ITERATORS_HPP 49 50 #include <ext/pb_ds/tag_and_trait.hpp> 51 #include <ext/pb_ds/detail/type_utils.hpp> 52 #include <debug/debug.h> 53 54 namespace pb_ds 55 { 56 namespace detail 57 { 58 #define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 59 typedef \ 60 static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> \ 61 UNIQUE##static_assert_type 62 63 #define PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC \ 64 ov_tree_node_const_it_<Value_Type, Metadata_Type, Allocator> 65 66 // Const node reference. 67 template<typename Value_Type, typename Metadata_Type, class Allocator> 68 class ov_tree_node_const_it_ 69 { 70 71 protected: 72 typedef 73 typename Allocator::template rebind< 74 Value_Type>::other::pointer 75 pointer; 76 77 typedef 78 typename Allocator::template rebind< 79 Value_Type>::other::const_pointer 80 const_pointer; 81 82 typedef 83 typename Allocator::template rebind< 84 Metadata_Type>::other::const_pointer 85 const_metadata_pointer; 86 87 typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC this_type; 88 89 protected: 90 91 template<typename Ptr> 92 inline static Ptr mid_pointer(Ptr p_begin,Ptr p_end)93 mid_pointer(Ptr p_begin, Ptr p_end) 94 { 95 _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin); 96 return (p_begin + (p_end - p_begin) / 2); 97 } 98 99 public: 100 101 typedef trivial_iterator_tag iterator_category; 102 103 typedef trivial_iterator_difference_type difference_type; 104 105 typedef 106 typename Allocator::template rebind< 107 Value_Type>::other::const_pointer 108 value_type; 109 110 typedef 111 typename Allocator::template rebind< 112 typename remove_const< 113 Value_Type>::type>::other::const_pointer 114 reference; 115 116 typedef 117 typename Allocator::template rebind< 118 typename remove_const< 119 Value_Type>::type>::other::const_pointer 120 const_reference; 121 122 typedef Metadata_Type metadata_type; 123 124 typedef 125 typename Allocator::template rebind< 126 metadata_type>::other::const_reference 127 const_metadata_reference; 128 129 public: 130 inline ov_tree_node_const_it_(const_pointer p_nd=NULL,const_pointer p_begin_nd=NULL,const_pointer p_end_nd=NULL,const_metadata_pointer p_metadata=NULL)131 ov_tree_node_const_it_(const_pointer p_nd = NULL, const_pointer p_begin_nd = NULL, const_pointer p_end_nd = NULL, const_metadata_pointer p_metadata = NULL) : m_p_value(const_cast<pointer>(p_nd)), m_p_begin_value(const_cast<pointer>(p_begin_nd)), m_p_end_value(const_cast<pointer>(p_end_nd)), m_p_metadata(p_metadata) 132 { } 133 134 inline const_reference operator *() const135 operator*() const 136 { return m_p_value; } 137 138 inline const_metadata_reference get_metadata() const139 get_metadata() const 140 { 141 enum 142 { 143 has_metadata = !is_same<Metadata_Type, null_node_metadata>::value 144 }; 145 146 PB_DS_STATIC_ASSERT(should_have_metadata, has_metadata); 147 _GLIBCXX_DEBUG_ASSERT(m_p_metadata != NULL); 148 return *m_p_metadata; 149 } 150 151 inline this_type get_l_child() const152 get_l_child() const 153 { 154 if (m_p_begin_value == m_p_value) 155 return (this_type(m_p_begin_value, m_p_begin_value, m_p_begin_value)); 156 157 const_metadata_pointer p_begin_metadata = 158 m_p_metadata - (m_p_value - m_p_begin_value); 159 160 return (this_type(mid_pointer(m_p_begin_value, m_p_value), 161 m_p_begin_value, 162 m_p_value, 163 mid_pointer(p_begin_metadata, m_p_metadata))); 164 } 165 166 inline this_type get_r_child() const167 get_r_child() const 168 { 169 if (m_p_value == m_p_end_value) 170 return (this_type(m_p_end_value, m_p_end_value, m_p_end_value)); 171 172 const_metadata_pointer p_end_metadata = 173 m_p_metadata + (m_p_end_value - m_p_value); 174 175 return (this_type(mid_pointer(m_p_value + 1, m_p_end_value), 176 m_p_value + 1, 177 m_p_end_value,(m_p_metadata == NULL) ? 178 NULL : mid_pointer(m_p_metadata + 1, p_end_metadata))); 179 } 180 181 inline bool operator ==(const this_type & other) const182 operator==(const this_type& other) const 183 { 184 const bool is_end = m_p_begin_value == m_p_end_value; 185 const bool is_other_end = other.m_p_begin_value == other.m_p_end_value; 186 187 if (is_end) 188 return (is_other_end); 189 190 if (is_other_end) 191 return (is_end); 192 193 return m_p_value == other.m_p_value; 194 } 195 196 inline bool operator !=(const this_type & other) const197 operator!=(const this_type& other) const 198 { return !operator==(other); } 199 200 public: 201 pointer m_p_value; 202 pointer m_p_begin_value; 203 pointer m_p_end_value; 204 205 const_metadata_pointer m_p_metadata; 206 }; 207 208 #define PB_DS_OV_TREE_NODE_ITERATOR_C_DEC \ 209 ov_tree_node_it_<Value_Type, Metadata_Type, Allocator> 210 211 // Node reference. 212 template<typename Value_Type, typename Metadata_Type, class Allocator> 213 class ov_tree_node_it_ : public PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC 214 { 215 216 private: 217 typedef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC this_type; 218 219 typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC base_type; 220 221 typedef typename base_type::pointer pointer; 222 223 typedef typename base_type::const_pointer const_pointer; 224 225 typedef 226 typename base_type::const_metadata_pointer 227 const_metadata_pointer; 228 229 public: 230 231 typedef trivial_iterator_tag iterator_category; 232 233 typedef trivial_iterator_difference_type difference_type; 234 235 typedef 236 typename Allocator::template rebind< 237 Value_Type>::other::pointer 238 value_type; 239 240 typedef 241 typename Allocator::template rebind< 242 typename remove_const< 243 Value_Type>::type>::other::pointer 244 reference; 245 246 typedef 247 typename Allocator::template rebind< 248 typename remove_const< 249 Value_Type>::type>::other::pointer 250 const_reference; 251 252 public: 253 inline ov_tree_node_it_(const_pointer p_nd=NULL,const_pointer p_begin_nd=NULL,const_pointer p_end_nd=NULL,const_metadata_pointer p_metadata=NULL)254 ov_tree_node_it_(const_pointer p_nd = NULL, const_pointer p_begin_nd = NULL, const_pointer p_end_nd = NULL, const_metadata_pointer p_metadata = NULL) : base_type( p_nd, p_begin_nd, p_end_nd, p_metadata) 255 { } 256 257 // Access. 258 inline reference operator *() const259 operator*() const 260 { return reference(base_type::m_p_value); } 261 262 // Returns the node reference associated with the left node. 263 inline ov_tree_node_it_ get_l_child() const264 get_l_child() const 265 { 266 if (base_type::m_p_begin_value == base_type::m_p_value) 267 return (this_type(base_type::m_p_begin_value, base_type::m_p_begin_value, base_type::m_p_begin_value)); 268 269 const_metadata_pointer p_begin_metadata = 270 base_type::m_p_metadata - (base_type::m_p_value - base_type::m_p_begin_value); 271 272 return (this_type(base_type::mid_pointer(base_type::m_p_begin_value, base_type::m_p_value), 273 base_type::m_p_begin_value, 274 base_type::m_p_value, 275 base_type::mid_pointer(p_begin_metadata, base_type::m_p_metadata))); 276 } 277 278 // Returns the node reference associated with the right node. 279 inline ov_tree_node_it_ get_r_child() const280 get_r_child() const 281 { 282 if (base_type::m_p_value == base_type::m_p_end_value) 283 return (this_type(base_type::m_p_end_value, base_type::m_p_end_value, base_type::m_p_end_value)); 284 285 const_metadata_pointer p_end_metadata = 286 base_type::m_p_metadata + (base_type::m_p_end_value - base_type::m_p_value); 287 288 return (this_type(base_type::mid_pointer(base_type::m_p_value + 1, base_type::m_p_end_value), 289 base_type::m_p_value + 1, 290 base_type::m_p_end_value,(base_type::m_p_metadata == NULL)? 291 NULL : base_type::mid_pointer(base_type::m_p_metadata + 1, p_end_metadata))); 292 } 293 294 }; 295 296 #undef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC 297 #undef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC 298 #undef PB_DS_STATIC_ASSERT 299 300 } // namespace detail 301 } // namespace pb_ds 302 303 #endif 304