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