1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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 3, 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// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27// Permission to use, copy, modify, sell, and distribute this software 28// is hereby granted without fee, provided that the above copyright 29// notice appears in all copies, and that both that copyright notice 30// and this permission notice appear in supporting documentation. None 31// of the above authors, nor IBM Haifa Research Laboratories, make any 32// representation about the suitability of this software for any 33// purpose. It is provided "as is" without express or implied 34// warranty. 35 36/** 37 * @file node_iterators.hpp 38 * Contains an implementation class for pat_trie_. 39 */ 40 41#ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP 42#define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP 43 44#include <debug/debug.h> 45 46namespace __gnu_pbds 47{ 48 namespace detail 49 { 50 51#define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC \ 52 pat_trie_const_node_it_< \ 53 Node, \ 54 Leaf, \ 55 Head, \ 56 Internal_Node, \ 57 Const_Iterator, \ 58 Iterator, \ 59 E_Access_Traits, \ 60 Allocator> 61 62#define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \ 63 pat_trie_node_it_< \ 64 Node, \ 65 Leaf, \ 66 Head, \ 67 Internal_Node, \ 68 Const_Iterator, \ 69 Iterator, \ 70 E_Access_Traits, \ 71 Allocator> 72 73 // Const node iterator. 74 template<typename Node, 75 class Leaf, 76 class Head, 77 class Internal_Node, 78 class Const_Iterator, 79 class Iterator, 80 class E_Access_Traits, 81 class Allocator> 82 class pat_trie_const_node_it_ 83 { 84 protected: 85 typedef 86 typename Allocator::template rebind< 87 Node>::other::pointer 88 node_pointer; 89 90 typedef 91 typename Allocator::template rebind< 92 Leaf>::other::const_pointer 93 const_leaf_pointer; 94 95 typedef 96 typename Allocator::template rebind< 97 Leaf>::other::pointer 98 leaf_pointer; 99 100 typedef 101 typename Allocator::template rebind< 102 Internal_Node>::other::pointer 103 internal_node_pointer; 104 105 typedef 106 typename Allocator::template rebind< 107 Internal_Node>::other::const_pointer 108 const_internal_node_pointer; 109 110 typedef 111 typename Allocator::template rebind< 112 E_Access_Traits>::other::const_pointer 113 const_e_access_traits_pointer; 114 115 private: 116 inline typename E_Access_Traits::const_iterator 117 pref_begin() const 118 { 119 if (m_p_nd->m_type == pat_trie_leaf_node_type) 120 return (m_p_traits->begin( 121 m_p_traits->extract_key( 122 static_cast<const_leaf_pointer>(m_p_nd)->value()))); 123 124 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 125 126 return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_b_it()); 127 } 128 129 inline typename E_Access_Traits::const_iterator 130 pref_end() const 131 { 132 if (m_p_nd->m_type == pat_trie_leaf_node_type) 133 return (m_p_traits->end( 134 m_p_traits->extract_key( 135 static_cast<const_leaf_pointer>(m_p_nd)->value()))); 136 137 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 138 139 return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_e_it()); 140 } 141 142 public: 143 144 // Size type. 145 typedef typename Allocator::size_type size_type; 146 147 // Category. 148 typedef trivial_iterator_tag iterator_category; 149 150 // Difference type. 151 typedef trivial_iterator_difference_type difference_type; 152 153 // __Iterator's value type. 154 typedef Const_Iterator value_type; 155 156 // __Iterator's reference type. 157 typedef value_type reference; 158 159 // __Iterator's __const reference type. 160 typedef value_type const_reference; 161 162 // Element access traits. 163 typedef E_Access_Traits e_access_traits; 164 165 // A key's element __const iterator. 166 typedef typename e_access_traits::const_iterator const_e_iterator; 167 168 // Metadata type. 169 typedef typename Node::metadata_type metadata_type; 170 171 // Const metadata reference type. 172 typedef 173 typename Allocator::template rebind< 174 metadata_type>::other::const_reference 175 const_metadata_reference; 176 177 // Default constructor. 178 /* 179 inline 180 pat_trie_const_node_it_() 181 */ 182 inline 183 pat_trie_const_node_it_(node_pointer p_nd = NULL, 184 const_e_access_traits_pointer p_traits = NULL) 185 : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits) 186 { } 187 188 // Subtree valid prefix. 189 inline std::pair<const_e_iterator, const_e_iterator> 190 valid_prefix() const 191 { return std::make_pair(pref_begin(), pref_end()); } 192 193 // Const access; returns the __const iterator* associated with 194 // the current leaf. 195 inline const_reference 196 operator*() const 197 { 198 _GLIBCXX_DEBUG_ASSERT(num_children() == 0); 199 return Const_Iterator(m_p_nd); 200 } 201 202 // Metadata access. 203 inline const_metadata_reference 204 get_metadata() const 205 { return m_p_nd->get_metadata(); } 206 207 // Returns the number of children in the corresponding node. 208 inline size_type 209 num_children() const 210 { 211 if (m_p_nd->m_type == pat_trie_leaf_node_type) 212 return 0; 213 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 214 return std::distance(static_cast<internal_node_pointer>(m_p_nd)->begin(), static_cast<internal_node_pointer>(m_p_nd)->end()); 215 } 216 217 // Returns a __const node __iterator to the corresponding node's 218 // i-th child. 219 PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC 220 get_child(size_type i) const 221 { 222 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 223 typename Internal_Node::iterator it = 224 static_cast<internal_node_pointer>(m_p_nd)->begin(); 225 226 std::advance(it, i); 227 return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits); 228 } 229 230 // Compares content to a different iterator object. 231 inline bool 232 operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const 233 { return (m_p_nd == other.m_p_nd); } 234 235 // Compares content (negatively) to a different iterator object. 236 inline bool 237 operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const 238 { return m_p_nd != other.m_p_nd; } 239 240 private: 241 242 friend class PB_DS_CLASS_C_DEC; 243 244 public: 245 node_pointer m_p_nd; 246 247 const_e_access_traits_pointer m_p_traits; 248 }; 249 250 // Node iterator. 251 template<typename Node, 252 class Leaf, 253 class Head, 254 class Internal_Node, 255 class Const_Iterator, 256 class Iterator, 257 class E_Access_Traits, 258 class Allocator> 259 class pat_trie_node_it_ : 260 public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC 261 262 { 263 private: 264 typedef 265 typename Allocator::template rebind< 266 Node>::other::pointer 267 node_pointer; 268 269 typedef Iterator iterator; 270 271 typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type; 272 273 typedef 274 typename base_type::const_e_access_traits_pointer 275 const_e_access_traits_pointer; 276 277 typedef typename base_type::internal_node_pointer internal_node_pointer; 278 279 public: 280 281 // Size type. 282 typedef 283 typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type 284 size_type; 285 286 // __Iterator's value type. 287 typedef Iterator value_type; 288 289 // __Iterator's reference type. 290 typedef value_type reference; 291 292 // __Iterator's __const reference type. 293 typedef value_type const_reference; 294 295 // Default constructor. 296 /* 297 inline 298 pat_trie_node_it_() ; 299 */ 300 301 inline 302 pat_trie_node_it_(node_pointer p_nd = NULL, const_e_access_traits_pointer p_traits = NULL) : base_type(p_nd, p_traits) 303 { } 304 305 // Access; returns the iterator* associated with the current leaf. 306 inline reference 307 operator*() const 308 { 309 _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0); 310 return Iterator(base_type::m_p_nd); 311 312 } 313 314 // Returns a node __iterator to the corresponding node's i-th child. 315 PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC 316 get_child(size_type i) const 317 { 318 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type); 319 320 typename Internal_Node::iterator it = 321 static_cast<internal_node_pointer>(base_type::m_p_nd)->begin(); 322 323 std::advance(it, i); 324 return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits); 325 } 326 327 private: 328 friend class PB_DS_CLASS_C_DEC; 329 }; 330 331#undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC 332#undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC 333 334 } // namespace detail 335} // namespace __gnu_pbds 336 337#endif 338 339