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 point_iterators.hpp 38 * Contains an implementation class for bin_search_tree_. 39 */ 40 41 #ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP 42 #define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP 43 44 #include <debug/debug.h> 45 46 namespace __gnu_pbds 47 { 48 namespace detail 49 { 50 51 #define PB_DS_CONST_IT_C_DEC \ 52 pat_trie_const_it_< \ 53 Type_Traits, \ 54 Node, \ 55 Leaf, \ 56 Head, \ 57 Internal_Node, \ 58 Is_Forward_Iterator, \ 59 Allocator> 60 61 #define PB_DS_CONST_ODIR_IT_C_DEC \ 62 pat_trie_const_it_< \ 63 Type_Traits, \ 64 Node, \ 65 Leaf, \ 66 Head, \ 67 Internal_Node, \ 68 !Is_Forward_Iterator, \ 69 Allocator> 70 71 #define PB_DS_IT_C_DEC \ 72 pat_trie_it_< \ 73 Type_Traits, \ 74 Node, \ 75 Leaf, \ 76 Head, \ 77 Internal_Node, \ 78 Is_Forward_Iterator, \ 79 Allocator> 80 81 #define PB_DS_ODIR_IT_C_DEC \ 82 pat_trie_it_< \ 83 Type_Traits, \ 84 Node, \ 85 Leaf, \ 86 Head, \ 87 Internal_Node, \ 88 !Is_Forward_Iterator, \ 89 Allocator> 90 91 92 // Const iterator. 93 template<typename Type_Traits, 94 class Node, 95 class Leaf, 96 class Head, 97 class Internal_Node, 98 bool Is_Forward_Iterator, 99 class Allocator> 100 class pat_trie_const_it_ 101 { 102 103 private: 104 typedef 105 typename Allocator::template rebind< 106 Node>::other::pointer 107 node_pointer; 108 109 typedef 110 typename Allocator::template rebind< 111 Leaf>::other::const_pointer 112 const_leaf_pointer; 113 114 typedef 115 typename Allocator::template rebind< 116 Leaf>::other::pointer 117 leaf_pointer; 118 119 typedef 120 typename Allocator::template rebind< 121 Head>::other::pointer 122 head_pointer; 123 124 typedef 125 typename Allocator::template rebind< 126 Internal_Node>::other::pointer 127 internal_node_pointer; 128 129 public: 130 131 typedef std::bidirectional_iterator_tag iterator_category; 132 133 typedef typename Allocator::difference_type difference_type; 134 135 typedef typename Type_Traits::value_type value_type; 136 137 typedef typename Type_Traits::pointer pointer; 138 139 typedef typename Type_Traits::const_pointer const_pointer; 140 141 typedef typename Type_Traits::reference reference; 142 143 typedef typename Type_Traits::const_reference const_reference; 144 145 public: 146 147 inline 148 pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd) 149 { } 150 151 inline 152 pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other) 153 : m_p_nd(other.m_p_nd) 154 { } 155 156 inline 157 PB_DS_CONST_IT_C_DEC& 158 operator=(const PB_DS_CONST_IT_C_DEC& other) 159 { 160 m_p_nd = other.m_p_nd; 161 return *this; 162 } 163 164 inline 165 PB_DS_CONST_IT_C_DEC& 166 operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other) 167 { 168 m_p_nd = other.m_p_nd; 169 return *this; 170 } 171 172 inline const_pointer 173 operator->() const 174 { 175 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type); 176 return &static_cast<leaf_pointer>(m_p_nd)->value(); 177 } 178 179 inline const_reference 180 operator*() const 181 { 182 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type); 183 return static_cast<leaf_pointer>(m_p_nd)->value(); 184 } 185 186 inline bool 187 operator==(const PB_DS_CONST_IT_C_DEC& other) const 188 { return (m_p_nd == other.m_p_nd); } 189 190 inline bool 191 operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const 192 { return (m_p_nd == other.m_p_nd); } 193 194 inline bool 195 operator!=(const PB_DS_CONST_IT_C_DEC& other) const 196 { return (m_p_nd != other.m_p_nd); } 197 198 inline bool 199 operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const 200 { return (m_p_nd != other.m_p_nd); } 201 202 inline PB_DS_CONST_IT_C_DEC& 203 operator++() 204 { 205 inc(integral_constant<int,Is_Forward_Iterator>()); 206 return *this; 207 } 208 209 inline PB_DS_CONST_IT_C_DEC 210 operator++(int) 211 { 212 PB_DS_CONST_IT_C_DEC ret_it(m_p_nd); 213 operator++(); 214 return ret_it; 215 } 216 217 inline PB_DS_CONST_IT_C_DEC& 218 operator--() 219 { 220 dec(integral_constant<int,Is_Forward_Iterator>()); 221 return *this; 222 } 223 224 inline PB_DS_CONST_IT_C_DEC 225 operator--(int) 226 { 227 PB_DS_CONST_IT_C_DEC ret_it(m_p_nd); 228 operator--(); 229 return ret_it; 230 } 231 232 protected: 233 inline void 234 inc(false_type) 235 { dec(true_type()); } 236 237 void 238 inc(true_type) 239 { 240 if (m_p_nd->m_type == pat_trie_head_node_type) 241 { 242 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min; 243 return; 244 } 245 246 node_pointer p_y = m_p_nd->m_p_parent; 247 while (p_y->m_type != pat_trie_head_node_type && 248 get_larger_sibling(m_p_nd) == NULL) 249 { 250 m_p_nd = p_y; 251 p_y = p_y->m_p_parent; 252 } 253 254 if (p_y->m_type == pat_trie_head_node_type) 255 { 256 m_p_nd = p_y; 257 return; 258 } 259 m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd)); 260 } 261 262 inline void 263 dec(false_type) 264 { inc(true_type()); } 265 266 void 267 dec(true_type) 268 { 269 if (m_p_nd->m_type == pat_trie_head_node_type) 270 { 271 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max; 272 return; 273 } 274 275 node_pointer p_y = m_p_nd->m_p_parent; 276 while (p_y->m_type != pat_trie_head_node_type && 277 get_smaller_sibling(m_p_nd) == NULL) 278 { 279 m_p_nd = p_y; 280 p_y = p_y->m_p_parent; 281 } 282 283 if (p_y->m_type == pat_trie_head_node_type) 284 { 285 m_p_nd = p_y; 286 return; 287 } 288 m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd)); 289 } 290 291 inline static node_pointer 292 get_larger_sibling(node_pointer p_nd) 293 { 294 internal_node_pointer p_parent = 295 static_cast<internal_node_pointer>(p_nd->m_p_parent); 296 297 typename Internal_Node::iterator it = p_parent->begin(); 298 while (*it != p_nd) 299 ++it; 300 301 typename Internal_Node::iterator next_it = it; 302 ++next_it; 303 return ((next_it == p_parent->end())? NULL :* next_it); 304 } 305 306 inline static node_pointer 307 get_smaller_sibling(node_pointer p_nd) 308 { 309 internal_node_pointer p_parent = 310 static_cast<internal_node_pointer>(p_nd->m_p_parent); 311 312 typename Internal_Node::iterator it = p_parent->begin(); 313 314 if (*it == p_nd) 315 return (NULL); 316 typename Internal_Node::iterator prev_it; 317 do 318 { 319 prev_it = it; 320 ++it; 321 if (*it == p_nd) 322 return (*prev_it); 323 } 324 while (true); 325 326 _GLIBCXX_DEBUG_ASSERT(false); 327 return (NULL); 328 } 329 330 inline static leaf_pointer 331 leftmost_descendant(node_pointer p_nd) 332 { 333 if (p_nd->m_type == pat_trie_leaf_node_type) 334 return static_cast<leaf_pointer>(p_nd); 335 return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant(); 336 } 337 338 inline static leaf_pointer 339 rightmost_descendant(node_pointer p_nd) 340 { 341 if (p_nd->m_type == pat_trie_leaf_node_type) 342 return static_cast<leaf_pointer>(p_nd); 343 return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant(); 344 } 345 346 public: 347 node_pointer m_p_nd; 348 }; 349 350 // Iterator. 351 template<typename Type_Traits, 352 class Node, 353 class Leaf, 354 class Head, 355 class Internal_Node, 356 bool Is_Forward_Iterator, 357 class Allocator> 358 class pat_trie_it_ : 359 public PB_DS_CONST_IT_C_DEC 360 361 { 362 private: 363 typedef 364 typename Allocator::template rebind< 365 Node>::other::pointer 366 node_pointer; 367 368 typedef 369 typename Allocator::template rebind< 370 Leaf>::other::const_pointer 371 const_leaf_pointer; 372 373 typedef 374 typename Allocator::template rebind< 375 Leaf>::other::pointer 376 leaf_pointer; 377 378 typedef 379 typename Allocator::template rebind< 380 Head>::other::pointer 381 head_pointer; 382 383 typedef 384 typename Allocator::template rebind< 385 Internal_Node>::other::pointer 386 internal_node_pointer; 387 388 public: 389 typedef typename Type_Traits::value_type value_type; 390 391 typedef typename Type_Traits::const_pointer const_pointer; 392 393 typedef typename Type_Traits::pointer pointer; 394 395 typedef typename Type_Traits::const_reference const_reference; 396 397 typedef typename Type_Traits::reference reference; 398 399 inline 400 pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd) 401 { } 402 403 inline 404 pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd) 405 { } 406 407 inline 408 PB_DS_IT_C_DEC& 409 operator=(const PB_DS_IT_C_DEC& other) 410 { 411 base_it_type::m_p_nd = other.m_p_nd; 412 return *this; 413 } 414 415 inline 416 PB_DS_IT_C_DEC& 417 operator=(const PB_DS_ODIR_IT_C_DEC& other) 418 { 419 base_it_type::m_p_nd = other.m_p_nd; 420 return *this; 421 } 422 423 inline pointer 424 operator->() const 425 { 426 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type); 427 428 return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value(); 429 } 430 431 inline reference 432 operator*() const 433 { 434 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type); 435 return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value(); 436 } 437 438 inline PB_DS_IT_C_DEC& 439 operator++() 440 { 441 PB_DS_CONST_IT_C_DEC:: 442 operator++(); 443 return *this; 444 } 445 446 inline PB_DS_IT_C_DEC 447 operator++(int) 448 { 449 PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd); 450 operator++(); 451 return ret_it; 452 } 453 454 inline PB_DS_IT_C_DEC& 455 operator--() 456 { 457 PB_DS_CONST_IT_C_DEC::operator--(); 458 return *this; 459 } 460 461 inline PB_DS_IT_C_DEC 462 operator--(int) 463 { 464 PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd); 465 operator--(); 466 return ret_it; 467 } 468 469 protected: 470 typedef PB_DS_CONST_IT_C_DEC base_it_type; 471 472 friend class PB_DS_CLASS_C_DEC; 473 }; 474 475 #undef PB_DS_CONST_IT_C_DEC 476 #undef PB_DS_CONST_ODIR_IT_C_DEC 477 #undef PB_DS_IT_C_DEC 478 #undef PB_DS_ODIR_IT_C_DEC 479 480 } // namespace detail 481 } // namespace __gnu_pbds 482 483 #endif 484 485
