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