libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2007, 2009, 2010 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file ov_tree_map_/node_iterators.hpp 00038 * Contains an implementation class for ov_tree_. 00039 */ 00040 00041 #ifndef PB_DS_OV_TREE_NODE_ITERATORS_HPP 00042 #define PB_DS_OV_TREE_NODE_ITERATORS_HPP 00043 00044 #include <ext/pb_ds/tag_and_trait.hpp> 00045 #include <ext/pb_ds/detail/type_utils.hpp> 00046 #include <debug/debug.h> 00047 00048 namespace __gnu_pbds 00049 { 00050 namespace detail 00051 { 00052 #define PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC \ 00053 ov_tree_node_const_it_<Value_Type, Metadata_Type, _Alloc> 00054 00055 /// Const node reference. 00056 template<typename Value_Type, typename Metadata_Type, typename _Alloc> 00057 class ov_tree_node_const_it_ 00058 { 00059 00060 protected: 00061 typedef 00062 typename _Alloc::template rebind< 00063 Value_Type>::other::pointer 00064 pointer; 00065 00066 typedef 00067 typename _Alloc::template rebind< 00068 Value_Type>::other::const_pointer 00069 const_pointer; 00070 00071 typedef 00072 typename _Alloc::template rebind< 00073 Metadata_Type>::other::const_pointer 00074 const_metadata_pointer; 00075 00076 typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC this_type; 00077 00078 protected: 00079 00080 template<typename Ptr> 00081 inline static Ptr 00082 mid_pointer(Ptr p_begin, Ptr p_end) 00083 { 00084 _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin); 00085 return (p_begin + (p_end - p_begin) / 2); 00086 } 00087 00088 public: 00089 00090 typedef trivial_iterator_tag iterator_category; 00091 00092 typedef trivial_iterator_difference_type difference_type; 00093 00094 typedef 00095 typename _Alloc::template rebind< 00096 Value_Type>::other::const_pointer 00097 value_type; 00098 00099 typedef 00100 typename _Alloc::template rebind< 00101 typename remove_const< 00102 Value_Type>::type>::other::const_pointer 00103 reference; 00104 00105 typedef 00106 typename _Alloc::template rebind< 00107 typename remove_const< 00108 Value_Type>::type>::other::const_pointer 00109 const_reference; 00110 00111 typedef Metadata_Type metadata_type; 00112 00113 typedef 00114 typename _Alloc::template rebind< 00115 metadata_type>::other::const_reference 00116 metadata_const_reference; 00117 00118 public: 00119 inline 00120 ov_tree_node_const_it_(const_pointer p_nd = 0, const_pointer p_begin_nd = 0, const_pointer p_end_nd = 0, const_metadata_pointer p_metadata = 0) : 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) 00121 { } 00122 00123 inline const_reference 00124 operator*() const 00125 { return m_p_value; } 00126 00127 inline metadata_const_reference 00128 get_metadata() const 00129 { 00130 enum 00131 { 00132 has_metadata = !is_same<Metadata_Type, null_type>::value 00133 }; 00134 00135 PB_DS_STATIC_ASSERT(should_have_metadata, has_metadata); 00136 _GLIBCXX_DEBUG_ASSERT(m_p_metadata != 0); 00137 return *m_p_metadata; 00138 } 00139 00140 /// Returns the node iterator associated with the left node. 00141 inline this_type 00142 get_l_child() const 00143 { 00144 if (m_p_begin_value == m_p_value) 00145 return (this_type(m_p_begin_value, m_p_begin_value, m_p_begin_value)); 00146 00147 const_metadata_pointer p_begin_metadata = 00148 m_p_metadata - (m_p_value - m_p_begin_value); 00149 00150 return (this_type(mid_pointer(m_p_begin_value, m_p_value), 00151 m_p_begin_value, 00152 m_p_value, 00153 mid_pointer(p_begin_metadata, m_p_metadata))); 00154 } 00155 00156 /// Returns the node iterator associated with the right node. 00157 inline this_type 00158 get_r_child() const 00159 { 00160 if (m_p_value == m_p_end_value) 00161 return (this_type(m_p_end_value, m_p_end_value, m_p_end_value)); 00162 00163 const_metadata_pointer p_end_metadata = 00164 m_p_metadata + (m_p_end_value - m_p_value); 00165 00166 return (this_type(mid_pointer(m_p_value + 1, m_p_end_value), 00167 m_p_value + 1, 00168 m_p_end_value,(m_p_metadata == 0) ? 00169 0 : mid_pointer(m_p_metadata + 1, p_end_metadata))); 00170 } 00171 00172 inline bool 00173 operator==(const this_type& other) const 00174 { 00175 const bool is_end = m_p_begin_value == m_p_end_value; 00176 const bool is_other_end = other.m_p_begin_value == other.m_p_end_value; 00177 00178 if (is_end) 00179 return (is_other_end); 00180 00181 if (is_other_end) 00182 return (is_end); 00183 00184 return m_p_value == other.m_p_value; 00185 } 00186 00187 inline bool 00188 operator!=(const this_type& other) const 00189 { return !operator==(other); } 00190 00191 public: 00192 pointer m_p_value; 00193 pointer m_p_begin_value; 00194 pointer m_p_end_value; 00195 00196 const_metadata_pointer m_p_metadata; 00197 }; 00198 00199 #define PB_DS_OV_TREE_NODE_ITERATOR_C_DEC \ 00200 ov_tree_node_it_<Value_Type, Metadata_Type, _Alloc> 00201 00202 /// Node reference. 00203 template<typename Value_Type, typename Metadata_Type, typename _Alloc> 00204 class ov_tree_node_it_ : public PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC 00205 { 00206 private: 00207 typedef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC this_type; 00208 00209 typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC base_type; 00210 00211 typedef typename base_type::pointer pointer; 00212 00213 typedef typename base_type::const_pointer const_pointer; 00214 00215 typedef 00216 typename base_type::const_metadata_pointer 00217 const_metadata_pointer; 00218 00219 public: 00220 typedef trivial_iterator_tag iterator_category; 00221 00222 typedef trivial_iterator_difference_type difference_type; 00223 00224 typedef 00225 typename _Alloc::template rebind< 00226 Value_Type>::other::pointer 00227 value_type; 00228 00229 typedef 00230 typename _Alloc::template rebind< 00231 typename remove_const< 00232 Value_Type>::type>::other::pointer 00233 reference; 00234 00235 typedef 00236 typename _Alloc::template rebind< 00237 typename remove_const< 00238 Value_Type>::type>::other::pointer 00239 const_reference; 00240 00241 inline 00242 ov_tree_node_it_(const_pointer p_nd = 0, const_pointer p_begin_nd = 0, const_pointer p_end_nd = 0, const_metadata_pointer p_metadata = 0) : base_type(p_nd, p_begin_nd, p_end_nd, p_metadata) 00243 { } 00244 00245 /// Access. 00246 inline reference 00247 operator*() const 00248 { return reference(base_type::m_p_value); } 00249 00250 /// Returns the node reference associated with the left node. 00251 inline ov_tree_node_it_ 00252 get_l_child() const 00253 { 00254 if (base_type::m_p_begin_value == base_type::m_p_value) 00255 return (this_type(base_type::m_p_begin_value, base_type::m_p_begin_value, base_type::m_p_begin_value)); 00256 00257 const_metadata_pointer p_begin_metadata = 00258 base_type::m_p_metadata - (base_type::m_p_value - base_type::m_p_begin_value); 00259 00260 return (this_type(base_type::mid_pointer(base_type::m_p_begin_value, base_type::m_p_value), 00261 base_type::m_p_begin_value, 00262 base_type::m_p_value, 00263 base_type::mid_pointer(p_begin_metadata, base_type::m_p_metadata))); 00264 } 00265 00266 /// Returns the node reference associated with the right node. 00267 inline ov_tree_node_it_ 00268 get_r_child() const 00269 { 00270 if (base_type::m_p_value == base_type::m_p_end_value) 00271 return this_type(base_type::m_p_end_value, base_type::m_p_end_value, 00272 base_type::m_p_end_value); 00273 00274 const_metadata_pointer p_end_metadata = 00275 base_type::m_p_metadata + (base_type::m_p_end_value - base_type::m_p_value); 00276 00277 return (this_type(base_type::mid_pointer(base_type::m_p_value + 1, base_type::m_p_end_value), 00278 base_type::m_p_value + 1, 00279 base_type::m_p_end_value,(base_type::m_p_metadata == 0)? 00280 0 : base_type::mid_pointer(base_type::m_p_metadata + 1, p_end_metadata))); 00281 } 00282 00283 }; 00284 00285 #undef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC 00286 #undef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC 00287 00288 } // namespace detail 00289 } // namespace __gnu_pbds 00290 00291 #endif