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 pat_trie_. 45 */ 46 47 #ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP 48 #define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP 49 50 #include <debug/debug.h> 51 52 namespace pb_ds 53 { 54 namespace detail 55 { 56 57 #define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC \ 58 pat_trie_const_node_it_< \ 59 Node, \ 60 Leaf, \ 61 Head, \ 62 Internal_Node, \ 63 Const_Iterator, \ 64 Iterator, \ 65 E_Access_Traits, \ 66 Allocator> 67 68 #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \ 69 pat_trie_node_it_< \ 70 Node, \ 71 Leaf, \ 72 Head, \ 73 Internal_Node, \ 74 Const_Iterator, \ 75 Iterator, \ 76 E_Access_Traits, \ 77 Allocator> 78 79 // Const node iterator. 80 template<typename Node, 81 class Leaf, 82 class Head, 83 class Internal_Node, 84 class Const_Iterator, 85 class Iterator, 86 class E_Access_Traits, 87 class Allocator> 88 class pat_trie_const_node_it_ 89 { 90 protected: 91 typedef 92 typename Allocator::template rebind< 93 Node>::other::pointer 94 node_pointer; 95 96 typedef 97 typename Allocator::template rebind< 98 Leaf>::other::const_pointer 99 const_leaf_pointer; 100 101 typedef 102 typename Allocator::template rebind< 103 Leaf>::other::pointer 104 leaf_pointer; 105 106 typedef 107 typename Allocator::template rebind< 108 Internal_Node>::other::pointer 109 internal_node_pointer; 110 111 typedef 112 typename Allocator::template rebind< 113 Internal_Node>::other::const_pointer 114 const_internal_node_pointer; 115 116 typedef 117 typename Allocator::template rebind< 118 E_Access_Traits>::other::const_pointer 119 const_e_access_traits_pointer; 120 121 private: 122 inline typename E_Access_Traits::const_iterator pref_begin() const123 pref_begin() const 124 { 125 if (m_p_nd->m_type == pat_trie_leaf_node_type) 126 return (m_p_traits->begin( 127 m_p_traits->extract_key( 128 static_cast<const_leaf_pointer>(m_p_nd)->value()))); 129 130 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 131 132 return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_b_it()); 133 } 134 135 inline typename E_Access_Traits::const_iterator pref_end() const136 pref_end() const 137 { 138 if (m_p_nd->m_type == pat_trie_leaf_node_type) 139 return (m_p_traits->end( 140 m_p_traits->extract_key( 141 static_cast<const_leaf_pointer>(m_p_nd)->value()))); 142 143 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 144 145 return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_e_it()); 146 } 147 148 public: 149 150 // Size type. 151 typedef typename Allocator::size_type size_type; 152 153 // Category. 154 typedef trivial_iterator_tag iterator_category; 155 156 // Difference type. 157 typedef trivial_iterator_difference_type difference_type; 158 159 // __Iterator's value type. 160 typedef Const_Iterator value_type; 161 162 // __Iterator's reference type. 163 typedef value_type reference; 164 165 // __Iterator's __const reference type. 166 typedef value_type const_reference; 167 168 // Element access traits. 169 typedef E_Access_Traits e_access_traits; 170 171 // A key's element __const iterator. 172 typedef typename e_access_traits::const_iterator const_e_iterator; 173 174 // Metadata type. 175 typedef typename Node::metadata_type metadata_type; 176 177 // Const metadata reference type. 178 typedef 179 typename Allocator::template rebind< 180 metadata_type>::other::const_reference 181 const_metadata_reference; 182 183 // Default constructor. 184 /* 185 inline 186 pat_trie_const_node_it_() 187 */ 188 inline pat_trie_const_node_it_(node_pointer p_nd=NULL,const_e_access_traits_pointer p_traits=NULL)189 pat_trie_const_node_it_(node_pointer p_nd = NULL, 190 const_e_access_traits_pointer p_traits = NULL) 191 : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits) 192 { } 193 194 // Subtree valid prefix. 195 inline std::pair<const_e_iterator, const_e_iterator> valid_prefix() const196 valid_prefix() const 197 { return std::make_pair(pref_begin(), pref_end()); } 198 199 // Const access; returns the __const iterator* associated with 200 // the current leaf. 201 inline const_reference operator *() const202 operator*() const 203 { 204 _GLIBCXX_DEBUG_ASSERT(num_children() == 0); 205 return Const_Iterator(m_p_nd); 206 } 207 208 // Metadata access. 209 inline const_metadata_reference get_metadata() const210 get_metadata() const 211 { return m_p_nd->get_metadata(); } 212 213 // Returns the number of children in the corresponding node. 214 inline size_type num_children() const215 num_children() const 216 { 217 if (m_p_nd->m_type == pat_trie_leaf_node_type) 218 return 0; 219 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 220 return std::distance(static_cast<internal_node_pointer>(m_p_nd)->begin(), static_cast<internal_node_pointer>(m_p_nd)->end()); 221 } 222 223 // Returns a __const node __iterator to the corresponding node's 224 // i-th child. 225 PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC get_child(size_type i) const226 get_child(size_type i) const 227 { 228 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 229 typename Internal_Node::iterator it = 230 static_cast<internal_node_pointer>(m_p_nd)->begin(); 231 232 std::advance(it, i); 233 return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits); 234 } 235 236 // Compares content to a different iterator object. 237 inline bool operator ==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC & other) const238 operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const 239 { return (m_p_nd == other.m_p_nd); } 240 241 // Compares content (negatively) to a different iterator object. 242 inline bool operator !=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC & other) const243 operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const 244 { return m_p_nd != other.m_p_nd; } 245 246 private: 247 248 friend class PB_DS_CLASS_C_DEC; 249 250 public: 251 node_pointer m_p_nd; 252 253 const_e_access_traits_pointer m_p_traits; 254 }; 255 256 // Node iterator. 257 template<typename Node, 258 class Leaf, 259 class Head, 260 class Internal_Node, 261 class Const_Iterator, 262 class Iterator, 263 class E_Access_Traits, 264 class Allocator> 265 class pat_trie_node_it_ : 266 public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC 267 268 { 269 private: 270 typedef 271 typename Allocator::template rebind< 272 Node>::other::pointer 273 node_pointer; 274 275 typedef Iterator iterator; 276 277 typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type; 278 279 typedef 280 typename base_type::const_e_access_traits_pointer 281 const_e_access_traits_pointer; 282 283 typedef typename base_type::internal_node_pointer internal_node_pointer; 284 285 public: 286 287 // Size type. 288 typedef 289 typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type 290 size_type; 291 292 // __Iterator's value type. 293 typedef Iterator value_type; 294 295 // __Iterator's reference type. 296 typedef value_type reference; 297 298 // __Iterator's __const reference type. 299 typedef value_type const_reference; 300 301 // Default constructor. 302 /* 303 inline 304 pat_trie_node_it_() ; 305 */ 306 307 inline pat_trie_node_it_(node_pointer p_nd=NULL,const_e_access_traits_pointer p_traits=NULL)308 pat_trie_node_it_(node_pointer p_nd = NULL, const_e_access_traits_pointer p_traits = NULL) : base_type(p_nd, p_traits) 309 { } 310 311 // Access; returns the iterator* associated with the current leaf. 312 inline reference operator *() const313 operator*() const 314 { 315 _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0); 316 return Iterator(base_type::m_p_nd); 317 318 } 319 320 // Returns a node __iterator to the corresponding node's i-th child. 321 PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC get_child(size_type i) const322 get_child(size_type i) const 323 { 324 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type); 325 326 typename Internal_Node::iterator it = 327 static_cast<internal_node_pointer>(base_type::m_p_nd)->begin(); 328 329 std::advance(it, i); 330 return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits); 331 } 332 333 private: 334 friend class PB_DS_CLASS_C_DEC; 335 }; 336 337 #undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC 338 #undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC 339 340 } // namespace detail 341 } // namespace pb_ds 342 343 #endif 344 345