libstdc++
point_iterators.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file bin_search_tree_/point_iterators.hpp
00038  * Contains an implementation class for bin_search_tree_.
00039  */
00040 
00041 #ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
00042 #define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
00043 
00044 #include <ext/pb_ds/tag_and_trait.hpp>
00045 #include <debug/debug.h>
00046 
00047 namespace __gnu_pbds
00048 {
00049   namespace detail
00050   {
00051 
00052 #define PB_DS_TREE_CONST_IT_C_DEC                   \
00053     bin_search_tree_const_it_<                      \
00054                         Node_Pointer,       \
00055                         Value_Type,     \
00056                         Pointer,        \
00057                         Const_Pointer,      \
00058                         Reference,      \
00059                         Const_Reference,    \
00060                         Is_Forward_Iterator,    \
00061                         _Alloc>
00062 
00063 #define PB_DS_TREE_CONST_ODIR_IT_C_DEC                  \
00064     bin_search_tree_const_it_<                      \
00065                         Node_Pointer,       \
00066                         Value_Type,     \
00067                         Pointer,        \
00068                         Const_Pointer,      \
00069                         Reference,      \
00070                         Const_Reference,    \
00071                         !Is_Forward_Iterator,   \
00072                         _Alloc>
00073 
00074 #define PB_DS_TREE_IT_C_DEC                     \
00075     bin_search_tree_it_<                        \
00076                         Node_Pointer,       \
00077                         Value_Type,     \
00078                         Pointer,        \
00079                         Const_Pointer,      \
00080                         Reference,      \
00081                         Const_Reference,    \
00082                         Is_Forward_Iterator,    \
00083                         _Alloc>
00084 
00085 #define PB_DS_TREE_ODIR_IT_C_DEC                    \
00086     bin_search_tree_it_<                        \
00087                             Node_Pointer,   \
00088                             Value_Type, \
00089                             Pointer,    \
00090                             Const_Pointer,  \
00091                             Reference,  \
00092                             Const_Reference, \
00093                             !Is_Forward_Iterator, \
00094                             _Alloc>
00095 
00096     /// Const iterator.
00097     template<typename Node_Pointer,
00098          typename Value_Type,
00099          typename Pointer,
00100          typename Const_Pointer,
00101          typename Reference,
00102          typename Const_Reference,
00103          bool Is_Forward_Iterator,
00104          typename _Alloc>
00105     class bin_search_tree_const_it_
00106     {
00107     public:
00108       typedef std::bidirectional_iterator_tag       iterator_category;
00109       typedef typename _Alloc::difference_type  difference_type;
00110       typedef Value_Type                value_type;
00111       typedef Pointer                   pointer;
00112       typedef Const_Pointer                 const_pointer;
00113       typedef Reference                 reference;
00114       typedef Const_Reference               const_reference;
00115 
00116       inline
00117       bin_search_tree_const_it_(const Node_Pointer p_nd = 0) 
00118       : m_p_nd(const_cast<Node_Pointer>(p_nd))
00119       { }
00120 
00121       inline
00122       bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 
00123       : m_p_nd(other.m_p_nd)
00124       { }
00125 
00126       inline
00127       PB_DS_TREE_CONST_IT_C_DEC& 
00128       operator=(const PB_DS_TREE_CONST_IT_C_DEC& other)
00129       {
00130     m_p_nd = other.m_p_nd;
00131     return *this;
00132       }
00133 
00134       inline
00135       PB_DS_TREE_CONST_IT_C_DEC& 
00136       operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
00137       {
00138     m_p_nd = other.m_p_nd;
00139     return *this;
00140       }
00141 
00142       inline const_pointer
00143       operator->() const
00144       {
00145     _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
00146     return &m_p_nd->m_value;
00147       }
00148 
00149       inline const_reference
00150       operator*() const
00151       {
00152     _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
00153     return m_p_nd->m_value;
00154       }
00155 
00156       inline bool
00157       operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const
00158       { return m_p_nd == other.m_p_nd; }
00159 
00160       inline bool
00161       operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const
00162       { return m_p_nd == other.m_p_nd; }
00163 
00164       inline bool
00165       operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const
00166       { return m_p_nd != other.m_p_nd; }
00167 
00168       inline bool
00169       operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const
00170       { return m_p_nd != other.m_p_nd; }
00171 
00172       inline PB_DS_TREE_CONST_IT_C_DEC& 
00173       operator++()
00174       {
00175     _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
00176     inc(integral_constant<int,Is_Forward_Iterator>());
00177     return *this;
00178       }
00179 
00180       inline PB_DS_TREE_CONST_IT_C_DEC
00181       operator++(int)
00182       {
00183     PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
00184     operator++();
00185     return ret_it;
00186       }
00187 
00188       inline PB_DS_TREE_CONST_IT_C_DEC& 
00189       operator--()
00190       {
00191     dec(integral_constant<int,Is_Forward_Iterator>());
00192     return *this;
00193       }
00194 
00195       inline PB_DS_TREE_CONST_IT_C_DEC
00196       operator--(int)
00197       {
00198     PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
00199     operator--();
00200     return ret_it;
00201       }
00202 
00203     protected:
00204       inline void
00205       inc(false_type)
00206       { dec(true_type()); }
00207 
00208       void
00209       inc(true_type)
00210       {
00211     if (m_p_nd->special()&& 
00212         m_p_nd->m_p_parent->m_p_parent == m_p_nd)
00213       {
00214         m_p_nd = m_p_nd->m_p_left;
00215         return;
00216       }
00217 
00218     if (m_p_nd->m_p_right != 0)
00219       {
00220         m_p_nd = m_p_nd->m_p_right;
00221         while (m_p_nd->m_p_left != 0)
00222           m_p_nd = m_p_nd->m_p_left;
00223         return;
00224       }
00225 
00226     Node_Pointer p_y = m_p_nd->m_p_parent;
00227     while (m_p_nd == p_y->m_p_right)
00228       {
00229         m_p_nd = p_y;
00230         p_y = p_y->m_p_parent;
00231       }
00232 
00233     if (m_p_nd->m_p_right != p_y)
00234       m_p_nd = p_y;
00235       }
00236 
00237       inline void
00238       dec(false_type)
00239       { inc(true_type()); }
00240 
00241       void
00242       dec(true_type)
00243       {
00244     if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
00245       {
00246         m_p_nd = m_p_nd->m_p_right;
00247         return;
00248       }
00249 
00250     if (m_p_nd->m_p_left != 0)
00251       {
00252         Node_Pointer p_y = m_p_nd->m_p_left;
00253         while (p_y->m_p_right != 0)
00254           p_y = p_y->m_p_right;
00255         m_p_nd = p_y;
00256         return;
00257       }
00258 
00259     Node_Pointer p_y = m_p_nd->m_p_parent;
00260     while (m_p_nd == p_y->m_p_left)
00261       {
00262         m_p_nd = p_y;
00263         p_y = p_y->m_p_parent;
00264       }
00265     if (m_p_nd->m_p_left != p_y)
00266       m_p_nd = p_y;
00267       }
00268 
00269     public:
00270       Node_Pointer m_p_nd;
00271     };
00272 
00273     /// Iterator.
00274     template<typename Node_Pointer,
00275          typename Value_Type,
00276          typename Pointer,
00277          typename Const_Pointer,
00278          typename Reference,
00279          typename Const_Reference,
00280          bool Is_Forward_Iterator,
00281          typename _Alloc>
00282     class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC
00283     {
00284     public:
00285       inline
00286       bin_search_tree_it_(const Node_Pointer p_nd = 0) 
00287       : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
00288       { }
00289 
00290       inline
00291       bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other) 
00292       : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd)
00293       { }
00294 
00295       inline
00296       PB_DS_TREE_IT_C_DEC& 
00297       operator=(const PB_DS_TREE_IT_C_DEC& other)
00298       {
00299     base_it_type::m_p_nd = other.m_p_nd;
00300     return *this;
00301       }
00302 
00303       inline
00304       PB_DS_TREE_IT_C_DEC& 
00305       operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other)
00306       {
00307     base_it_type::m_p_nd = other.m_p_nd;
00308     return *this;
00309       }
00310 
00311       inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer
00312       operator->() const
00313       {
00314     _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
00315     return &base_it_type::m_p_nd->m_value;
00316       }
00317 
00318       inline typename PB_DS_TREE_CONST_IT_C_DEC::reference
00319       operator*() const
00320       {
00321     _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
00322     return base_it_type::m_p_nd->m_value;
00323       }
00324 
00325       inline PB_DS_TREE_IT_C_DEC& 
00326       operator++()
00327       {
00328     PB_DS_TREE_CONST_IT_C_DEC:: operator++();
00329     return *this;
00330       }
00331 
00332       inline PB_DS_TREE_IT_C_DEC
00333       operator++(int)
00334       {
00335     PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
00336     operator++();
00337     return ret_it;
00338       }
00339 
00340       inline PB_DS_TREE_IT_C_DEC& 
00341       operator--()
00342       {
00343     PB_DS_TREE_CONST_IT_C_DEC:: operator--();
00344     return *this;
00345       }
00346 
00347       inline PB_DS_TREE_IT_C_DEC
00348       operator--(int)
00349       {
00350     PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
00351     operator--();
00352     return ret_it;
00353       }
00354 
00355     protected:
00356       typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type;
00357     };
00358 
00359 #undef PB_DS_TREE_CONST_IT_C_DEC
00360 #undef PB_DS_TREE_CONST_ODIR_IT_C_DEC
00361 #undef PB_DS_TREE_IT_C_DEC
00362 #undef PB_DS_TREE_ODIR_IT_C_DEC
00363 
00364   } // namespace detail
00365 } // namespace __gnu_pbds
00366 
00367 #endif