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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2010 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 = 0) : 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) == 0)
 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) == 0)
 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())? 0 :* 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 (0);
 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 (0);
 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 = 0) : 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