libstdc++
ov_tree_map_/node_iterators.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 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 ov_tree_map_/node_iterators.hpp
00038  * Contains an implementation class for ov_tree_.
00039  */
00040 
00041 #ifndef PB_DS_OV_TREE_NODE_ITERATORS_HPP
00042 #define PB_DS_OV_TREE_NODE_ITERATORS_HPP
00043 
00044 #include <ext/pb_ds/tag_and_trait.hpp>
00045 #include <ext/pb_ds/detail/type_utils.hpp>
00046 #include <debug/debug.h>
00047 
00048 namespace __gnu_pbds
00049 {
00050   namespace detail
00051   {
00052 #define PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC \
00053     ov_tree_node_const_it_<Value_Type, Metadata_Type, _Alloc>
00054 
00055     /// Const node reference.
00056     template<typename Value_Type, typename Metadata_Type, typename _Alloc>
00057     class ov_tree_node_const_it_
00058     {
00059 
00060     protected:
00061       typedef
00062       typename _Alloc::template rebind<
00063       Value_Type>::other::pointer
00064       pointer;
00065 
00066       typedef
00067       typename _Alloc::template rebind<
00068     Value_Type>::other::const_pointer
00069       const_pointer;
00070 
00071       typedef
00072       typename _Alloc::template rebind<
00073     Metadata_Type>::other::const_pointer
00074       const_metadata_pointer;
00075 
00076       typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC this_type;
00077 
00078     protected:
00079 
00080       template<typename Ptr>
00081       inline static Ptr
00082       mid_pointer(Ptr p_begin, Ptr p_end)
00083       {
00084     _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
00085     return (p_begin + (p_end - p_begin) / 2);
00086       }
00087 
00088     public:
00089 
00090       typedef trivial_iterator_tag iterator_category;
00091 
00092       typedef trivial_iterator_difference_type difference_type;
00093 
00094       typedef
00095       typename _Alloc::template rebind<
00096     Value_Type>::other::const_pointer
00097       value_type;
00098 
00099       typedef
00100       typename _Alloc::template rebind<
00101     typename remove_const<
00102     Value_Type>::type>::other::const_pointer
00103       reference;
00104 
00105       typedef
00106       typename _Alloc::template rebind<
00107     typename remove_const<
00108     Value_Type>::type>::other::const_pointer
00109       const_reference;
00110 
00111       typedef Metadata_Type metadata_type;
00112 
00113       typedef
00114       typename _Alloc::template rebind<
00115     metadata_type>::other::const_reference
00116       metadata_const_reference;
00117 
00118     public:
00119       inline
00120       ov_tree_node_const_it_(const_pointer p_nd = 0,  const_pointer p_begin_nd = 0,  const_pointer p_end_nd = 0,  const_metadata_pointer p_metadata = 0) : m_p_value(const_cast<pointer>(p_nd)), m_p_begin_value(const_cast<pointer>(p_begin_nd)), m_p_end_value(const_cast<pointer>(p_end_nd)), m_p_metadata(p_metadata)
00121       { }
00122 
00123       inline const_reference
00124       operator*() const
00125       { return m_p_value; }
00126 
00127       inline metadata_const_reference
00128       get_metadata() const
00129       {
00130     enum
00131       {
00132         has_metadata = !is_same<Metadata_Type, null_type>::value
00133       };
00134 
00135     PB_DS_STATIC_ASSERT(should_have_metadata, has_metadata);
00136     _GLIBCXX_DEBUG_ASSERT(m_p_metadata != 0);
00137     return *m_p_metadata;
00138       }
00139 
00140       /// Returns the node iterator associated with the left node.
00141       inline this_type
00142       get_l_child() const
00143       {
00144     if (m_p_begin_value == m_p_value)
00145       return (this_type(m_p_begin_value, m_p_begin_value, m_p_begin_value));
00146 
00147     const_metadata_pointer p_begin_metadata =
00148       m_p_metadata - (m_p_value - m_p_begin_value);
00149 
00150     return (this_type(mid_pointer(m_p_begin_value, m_p_value),
00151               m_p_begin_value,
00152               m_p_value,
00153               mid_pointer(p_begin_metadata, m_p_metadata)));
00154       }
00155 
00156       /// Returns the node iterator associated with the right node.
00157       inline this_type
00158       get_r_child() const
00159       {
00160     if (m_p_value == m_p_end_value)
00161       return (this_type(m_p_end_value, m_p_end_value, m_p_end_value));
00162 
00163     const_metadata_pointer p_end_metadata =
00164       m_p_metadata + (m_p_end_value - m_p_value);
00165 
00166     return (this_type(mid_pointer(m_p_value + 1, m_p_end_value),
00167               m_p_value + 1,
00168               m_p_end_value,(m_p_metadata == 0) ?
00169               0 : mid_pointer(m_p_metadata + 1, p_end_metadata)));
00170       }
00171 
00172       inline bool
00173       operator==(const this_type& other) const
00174       {
00175     const bool is_end = m_p_begin_value == m_p_end_value;
00176     const bool is_other_end = other.m_p_begin_value == other.m_p_end_value;
00177 
00178     if (is_end)
00179       return (is_other_end);
00180 
00181     if (is_other_end)
00182       return (is_end);
00183 
00184     return m_p_value == other.m_p_value;
00185       }
00186 
00187       inline bool
00188       operator!=(const this_type& other) const
00189       { return !operator==(other); }
00190 
00191     public:
00192       pointer m_p_value;
00193       pointer m_p_begin_value;
00194       pointer m_p_end_value;
00195 
00196       const_metadata_pointer m_p_metadata;
00197     };
00198 
00199 #define PB_DS_OV_TREE_NODE_ITERATOR_C_DEC \
00200     ov_tree_node_it_<Value_Type, Metadata_Type, _Alloc>
00201 
00202     /// Node reference.
00203     template<typename Value_Type, typename Metadata_Type, typename _Alloc>
00204     class ov_tree_node_it_ : public PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
00205     {
00206     private:
00207       typedef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC this_type;
00208 
00209       typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC base_type;
00210 
00211       typedef typename base_type::pointer pointer;
00212 
00213       typedef typename base_type::const_pointer const_pointer;
00214 
00215       typedef
00216       typename base_type::const_metadata_pointer
00217       const_metadata_pointer;
00218 
00219     public:
00220       typedef trivial_iterator_tag iterator_category;
00221 
00222       typedef trivial_iterator_difference_type difference_type;
00223 
00224       typedef
00225       typename _Alloc::template rebind<
00226     Value_Type>::other::pointer
00227       value_type;
00228 
00229       typedef
00230       typename _Alloc::template rebind<
00231     typename remove_const<
00232     Value_Type>::type>::other::pointer
00233       reference;
00234 
00235       typedef
00236       typename _Alloc::template rebind<
00237     typename remove_const<
00238     Value_Type>::type>::other::pointer
00239       const_reference;
00240 
00241       inline
00242       ov_tree_node_it_(const_pointer p_nd = 0,  const_pointer p_begin_nd = 0,  const_pointer p_end_nd = 0,  const_metadata_pointer p_metadata = 0) : base_type(p_nd,  p_begin_nd,  p_end_nd,  p_metadata)
00243       { }
00244 
00245       /// Access.
00246       inline reference
00247       operator*() const
00248       { return reference(base_type::m_p_value); }
00249 
00250       /// Returns the node reference associated with the left node.
00251       inline ov_tree_node_it_
00252       get_l_child() const
00253       {
00254     if (base_type::m_p_begin_value == base_type::m_p_value)
00255       return (this_type(base_type::m_p_begin_value,  base_type::m_p_begin_value,  base_type::m_p_begin_value));
00256 
00257     const_metadata_pointer p_begin_metadata =
00258       base_type::m_p_metadata - (base_type::m_p_value - base_type::m_p_begin_value);
00259 
00260     return (this_type(base_type::mid_pointer(base_type::m_p_begin_value, base_type::m_p_value),
00261               base_type::m_p_begin_value,
00262               base_type::m_p_value,
00263               base_type::mid_pointer(p_begin_metadata, base_type::m_p_metadata)));
00264       }
00265 
00266       /// Returns the node reference associated with the right node.
00267       inline ov_tree_node_it_
00268       get_r_child() const
00269       {
00270     if (base_type::m_p_value == base_type::m_p_end_value)
00271       return this_type(base_type::m_p_end_value, base_type::m_p_end_value,  
00272                base_type::m_p_end_value);
00273 
00274     const_metadata_pointer p_end_metadata =
00275       base_type::m_p_metadata + (base_type::m_p_end_value - base_type::m_p_value);
00276 
00277     return (this_type(base_type::mid_pointer(base_type::m_p_value + 1, base_type::m_p_end_value),
00278               base_type::m_p_value + 1,
00279               base_type::m_p_end_value,(base_type::m_p_metadata == 0)?
00280               0 : base_type::mid_pointer(base_type::m_p_metadata + 1, p_end_metadata)));
00281       }
00282 
00283     };
00284 
00285 #undef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC
00286 #undef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
00287 
00288 } // namespace detail
00289 } // namespace __gnu_pbds
00290 
00291 #endif