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