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 54namespace 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 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 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 135 operator*() const 136 { return m_p_value; } 137 138 inline const_metadata_reference 139 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 152 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 167 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 182 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 197 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 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 259 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_ 264 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_ 280 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