mingw/lib/gcc/mingw32/4.3.3/include/c++/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 #include <debug/debug.h>
  51
  52 namespace __gnu_pbds
  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
 154       pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)
 155       { }
 156
 157       inline
 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&
 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&
 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
 179       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
 186       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
 193       operator==(const PB_DS_CONST_IT_C_DEC& other) const
 194       { return (m_p_nd == other.m_p_nd); }
 195
 196       inline bool
 197       operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
 198       { return (m_p_nd == other.m_p_nd); }
 199
 200       inline bool
 201       operator!=(const PB_DS_CONST_IT_C_DEC& other) const
 202       { return (m_p_nd != other.m_p_nd); }
 203
 204       inline bool
 205       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&
 209       operator++()
 210       {
 211         inc(integral_constant<int,Is_Forward_Iterator>());
 212         return *this;
 213       }
 214
 215       inline PB_DS_CONST_IT_C_DEC
 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&
 224       operator--()
 225       {
 226         dec(integral_constant<int,Is_Forward_Iterator>());
 227         return *this;
 228       }
 229
 230       inline PB_DS_CONST_IT_C_DEC
 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
 240       inc(false_type)
 241       { dec(true_type()); }
 242
 243       void
 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
 269       dec(false_type)
 270       { inc(true_type()); }
 271
 272       void
 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
 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
 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
 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
 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
 406       pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)
 407       { }
 408
 409       inline
 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&
 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&
 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
 430       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
 438       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&
 445       operator++()
 446       {
 447         PB_DS_CONST_IT_C_DEC::
 448           operator++();
 449         return *this;
 450       }
 451
 452       inline PB_DS_IT_C_DEC
 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&
 461       operator--()
 462       {
 463         PB_DS_CONST_IT_C_DEC::operator--();
 464         return *this;
 465       }
 466
 467       inline PB_DS_IT_C_DEC
 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 __gnu_pbds
 488
 489 #endif
 490