libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp

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