old-autovect-branch/libstdc++-v3/include/ext/pb_assoc/detail/bin_search_tree_/find_iterators.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005 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
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  31
  32 // Permission to use, copy, modify, sell, and distribute this software
  33 // is hereby granted without fee, provided that the above copyright
  34 // notice appears in all copies, and that both that copyright notice and
  35 // this permission notice appear in supporting documentation. None of
  36 // the above authors, nor IBM Haifa Research Laboratories, make any
  37 // representation about the suitability of this software for any
  38 // purpose. It is provided "as is" without express or implied warranty.
  39
  40 /**
  41  * @file find_iterators.hpp
  42  * Contains an implementation class for bin_search_tree_.
  43  */
  44
  45 #define PB_ASSOC_CONST_IT_C_DEC \
  46         const_it_< \
  47                 Is_Forward_Iterator>
  48
  49 #define PB_ASSOC_CONST_ODIR_IT_C_DEC \
  50         const_it_< \
  51                 !Is_Forward_Iterator>
  52
  53 #define PB_ASSOC_IT_C_DEC \
  54         it_< \
  55                 Is_Forward_Iterator>
  56
  57 #define PB_ASSOC_ODIR_IT_C_DEC \
  58         it_< \
  59                 !Is_Forward_Iterator>
  60
  61 template<bool Is_Forward_Iterator>
  62 class const_it_
  63 {
  64
  65 public:
  66
  67   typedef std::bidirectional_iterator_tag iterator_category;
  68
  69   typedef typename Allocator::difference_type difference_type;
  70
  71   typedef mapped_value_type value_type;
  72
  73   typedef mapped_pointer pointer;
  74
  75   typedef const_mapped_pointer const_pointer;
  76
  77   typedef mapped_reference reference;
  78
  79   typedef const_mapped_reference const_reference;
  80
  81 public:
  82
  83   inline
  84   const_it_(const node_pointer p_nd = NULL) : m_p_nd(const_cast<node_pointer>(p_nd))
  85   { }
  86
  87   inline
  88   const_it_(const PB_ASSOC_CONST_ODIR_IT_C_DEC&
  89             r_other)
  90
  91     : m_p_nd(r_other.m_p_nd)
  92   { }
  93
  94   inline
  95   PB_ASSOC_CONST_IT_C_DEC&
  96   operator=(const PB_ASSOC_CONST_IT_C_DEC&
  97             r_other)
  98   {
  99     m_p_nd = r_other.m_p_nd;
 100
 101     return (*this);
 102   }
 103
 104   inline
 105   PB_ASSOC_CONST_IT_C_DEC&
 106   operator=(const PB_ASSOC_CONST_ODIR_IT_C_DEC&
 107             r_other)
 108   {
 109     m_p_nd = r_other.m_p_nd;
 110
 111     return (*this);
 112   }
 113
 114   inline const_pointer
 115   operator->() const
 116   {
 117     PB_ASSOC_DBG_ASSERT(m_p_nd != NULL);
 118
 119     return (&m_p_nd->m_value);
 120   }
 121
 122   inline const_reference
 123   operator*() const
 124   {
 125     PB_ASSOC_DBG_ASSERT(m_p_nd != NULL);
 126
 127     return (m_p_nd->m_value);
 128   }
 129
 130   inline bool
 131   operator==(const PB_ASSOC_CONST_IT_C_DEC
 132              &r_other) const
 133   {
 134     return (m_p_nd == r_other.m_p_nd);
 135   }
 136
 137   inline bool
 138   operator==(const PB_ASSOC_CONST_ODIR_IT_C_DEC
 139              &r_other) const
 140   {
 141     return (m_p_nd == r_other.m_p_nd);
 142   }
 143
 144   inline bool
 145   operator!=(const PB_ASSOC_CONST_IT_C_DEC&
 146              r_other) const
 147   {
 148     return (m_p_nd != r_other.m_p_nd);
 149   }
 150
 151   inline bool
 152   operator!=(const PB_ASSOC_CONST_ODIR_IT_C_DEC&
 153              r_other) const
 154   {
 155     return (m_p_nd != r_other.m_p_nd);
 156   }
 157
 158   inline PB_ASSOC_CONST_IT_C_DEC&
 159   operator++()
 160   {
 161     PB_ASSOC_DBG_ASSERT(m_p_nd != NULL);
 162
 163     inc(int_to_type<Is_Forward_Iterator>());
 164
 165     return (*this);
 166   }
 167
 168   inline PB_ASSOC_CONST_IT_C_DEC
 169   operator++(int)
 170   {
 171     PB_ASSOC_CONST_IT_C_DEC
 172       ret_it(m_p_nd);
 173
 174     operator++();
 175
 176     return (ret_it);
 177   }
 178
 179   inline PB_ASSOC_CONST_IT_C_DEC&
 180   operator--()
 181   {
 182     dec(int_to_type<Is_Forward_Iterator>());
 183
 184     return (*this);
 185   }
 186
 187   inline PB_ASSOC_CONST_IT_C_DEC
 188   operator--(int)
 189   {
 190     PB_ASSOC_CONST_IT_C_DEC
 191       ret_it(m_p_nd);
 192
 193     operator--();
 194
 195     return (ret_it);
 196   }
 197
 198 protected:
 199   inline void
 200   inc(int_to_type<false>)
 201   {
 202     dec(int_to_type<true>());
 203   }
 204
 205   void
 206   inc(int_to_type<true>)
 207   {
 208     if (m_p_nd->m_p_right != NULL)
 209       {
 210         m_p_nd = m_p_nd->m_p_right;
 211
 212         while (m_p_nd->m_p_left != NULL)
 213           m_p_nd = m_p_nd->m_p_left;
 214
 215         return;
 216       }
 217
 218     node_pointer p_y = m_p_nd->m_p_parent;
 219
 220     while (m_p_nd == p_y->m_p_right)
 221       {
 222         m_p_nd = p_y;
 223
 224         p_y = p_y->m_p_parent;
 225       }
 226
 227     if (m_p_nd->m_p_right != p_y)
 228       m_p_nd = p_y;
 229   }
 230
 231   inline void
 232   dec(int_to_type<false>)
 233   {
 234     inc(int_to_type<true>());
 235   }
 236
 237   void
 238   dec(int_to_type<true>)
 239   {
 240     if (m_p_nd->special_dec_check()&&
 241         m_p_nd->m_p_parent->m_p_parent == m_p_nd)
 242       {
 243         m_p_nd = m_p_nd->m_p_right;
 244
 245         return;
 246       }
 247
 248     if (m_p_nd->m_p_left != NULL)
 249       {
 250         node_pointer p_y = m_p_nd->m_p_left;
 251
 252         while (p_y->m_p_right != NULL)
 253           p_y = p_y->m_p_right;
 254
 255         m_p_nd = p_y;
 256
 257         return;
 258       }
 259
 260     node_pointer p_y = m_p_nd->m_p_parent;
 261
 262     while (m_p_nd == p_y->m_p_left)
 263       {
 264         m_p_nd = p_y;
 265
 266         p_y = p_y->m_p_parent;
 267       }
 268
 269     /*
 270      * This seems to correct an apparent bug in the SGI STL
 271      * implementation. */
 272     if (m_p_nd->m_p_left != p_y)
 273       m_p_nd = p_y;
 274   }
 275
 276   friend class PB_ASSOC_CLASS_C_DEC;
 277
 278 public:
 279   node_pointer m_p_nd;
 280 };
 281
 282 template<bool Is_Forward_Iterator>
 283 class it_ :
 284   public PB_ASSOC_CONST_IT_C_DEC
 285
 286 {
 287
 288 public:
 289
 290   inline
 291   it_(const node_pointer p_nd = NULL) : PB_ASSOC_CONST_IT_C_DEC((node_pointer)p_nd)
 292   { }
 293
 294   inline
 295   it_(const PB_ASSOC_ODIR_IT_C_DEC&
 296       r_other)
 297
 298     : PB_ASSOC_CONST_IT_C_DEC(
 299                               r_other.m_p_nd)
 300   { }
 301
 302   inline
 303   PB_ASSOC_IT_C_DEC&
 304   operator=(const PB_ASSOC_IT_C_DEC&
 305             r_other)
 306   {
 307     my_base_it::m_p_nd = r_other.m_p_nd;
 308
 309     return (*this);
 310   }
 311
 312   inline
 313   PB_ASSOC_IT_C_DEC&
 314   operator=(const PB_ASSOC_ODIR_IT_C_DEC&
 315             r_other)
 316   {
 317     my_base_it::m_p_nd = r_other.m_p_nd;
 318
 319     return (*this);
 320   }
 321
 322   inline pointer
 323   operator->()
 324   {
 325     PB_ASSOC_DBG_ASSERT(my_base_it::m_p_nd != NULL);
 326
 327     return (&my_base_it::m_p_nd->m_value);
 328   }
 329
 330   inline reference
 331   operator*()
 332   {
 333     PB_ASSOC_DBG_ASSERT(my_base_it::m_p_nd != NULL);
 334
 335     return (my_base_it::m_p_nd->m_value);
 336   }
 337
 338   inline PB_ASSOC_IT_C_DEC&
 339   operator++()
 340   {
 341     PB_ASSOC_CONST_IT_C_DEC::
 342       operator++();
 343
 344     return (*this);
 345   }
 346
 347   inline PB_ASSOC_IT_C_DEC
 348   operator++(int)
 349   {
 350     PB_ASSOC_IT_C_DEC
 351       ret_it(my_base_it::m_p_nd);
 352
 353     operator++();
 354
 355     return (ret_it);
 356   }
 357
 358   inline PB_ASSOC_IT_C_DEC&
 359   operator--()
 360   {
 361     PB_ASSOC_CONST_IT_C_DEC::
 362       operator--();
 363
 364     return (*this);
 365   }
 366
 367   inline PB_ASSOC_IT_C_DEC
 368   operator--(int)
 369   {
 370     PB_ASSOC_IT_C_DEC
 371       ret_it(my_base_it::m_p_nd);
 372
 373     operator--();
 374
 375     return (ret_it);
 376   }
 377
 378 protected:
 379   typedef PB_ASSOC_CONST_IT_C_DEC my_base_it;
 380
 381   friend class PB_ASSOC_CLASS_C_DEC;
 382 };
 383
 384 #undef PB_ASSOC_CONST_IT_C_DEC
 385
 386 #undef PB_ASSOC_CONST_ODIR_IT_C_DEC
 387
 388 #undef PB_ASSOC_IT_C_DEC
 389
 390 #undef PB_ASSOC_ODIR_IT_C_DEC
 391