intrusive/detail/tree_iterator.hpp

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga  2007-2013
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/intrusive for documentation.
0010 //
0011 /////////////////////////////////////////////////////////////////////////////
0012
0013 #ifndef BOOST_INTRUSIVE_TREE_ITERATOR_HPP
0014 #define BOOST_INTRUSIVE_TREE_ITERATOR_HPP
0015
0016 #ifndef BOOST_CONFIG_HPP
0017 #  include <boost/config.hpp>
0018 #endif
0019
0020 #if defined(BOOST_HAS_PRAGMA_ONCE)
0021 #  pragma once
0022 #endif
0023
0024 #include <boost/intrusive/detail/config_begin.hpp>
0025 #include <boost/intrusive/detail/workaround.hpp>
0026 #include <boost/intrusive/detail/std_fwd.hpp>
0027 #include <boost/intrusive/detail/iiterator.hpp>
0028 #include <boost/intrusive/detail/bstree_algorithms_base.hpp>
0029
0030 namespace boost {
0031 namespace intrusive {
0032
0033 /////////////////////////////////////////////////////////////////////////////
0034 //                                                                         //
0035 //                   Implementation of the tree iterator                   //
0036 //                                                                         //
0037 /////////////////////////////////////////////////////////////////////////////
0038
0039 // tree_iterator provides some basic functions for a
0040 // node oriented bidirectional iterator:
0041 template<class ValueTraits, bool IsConst>
0042 class tree_iterator
0043 {
0044    private:
0045    typedef iiterator< ValueTraits, IsConst
0046                     , std::bidirectional_iterator_tag>   types_t;
0047    typedef typename types_t::value_traits                value_traits;
0048    typedef typename types_t::node_traits                 node_traits;
0049    typedef typename types_t::node                        node;
0050    typedef typename types_t::node_ptr                    node_ptr;
0051    typedef typename types_t::const_value_traits_ptr      const_value_traits_ptr;
0052    typedef bstree_algorithms_base<node_traits>           node_algorithms;
0053
0054    static const bool stateful_value_traits = types_t::stateful_value_traits;
0055
0056    void unspecified_bool_type_func() const {}
0057    typedef void (tree_iterator::*unspecified_bool_type)() const;
0058    class nat;
0059    typedef typename
0060       detail::if_c< IsConst
0061                   , tree_iterator<value_traits, false>
0062                   , nat>::type                           nonconst_iterator;
0063
0064    public:
0065    typedef typename types_t::iterator_type::difference_type    difference_type;
0066    typedef typename types_t::iterator_type::value_type         value_type;
0067    typedef typename types_t::iterator_type::pointer            pointer;
0068    typedef typename types_t::iterator_type::reference          reference;
0069    typedef typename types_t::iterator_type::iterator_category  iterator_category;
0070
0071    BOOST_INTRUSIVE_FORCEINLINE tree_iterator()
0072    {}
0073
0074    BOOST_INTRUSIVE_FORCEINLINE explicit tree_iterator(node_ptr nodeptr, const_value_traits_ptr traits_ptr)
0075       : members_(nodeptr, traits_ptr)
0076    {}
0077
0078    BOOST_INTRUSIVE_FORCEINLINE tree_iterator(const tree_iterator &other)
0079       :  members_(other.pointed_node(), other.get_value_traits())
0080    {}
0081
0082    BOOST_INTRUSIVE_FORCEINLINE tree_iterator(const nonconst_iterator &other)
0083       :  members_(other.pointed_node(), other.get_value_traits())
0084    {}
0085
0086    BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(const tree_iterator &other)
0087    {  members_.nodeptr_ = other.members_.nodeptr_;  return *this;  }
0088
0089    BOOST_INTRUSIVE_FORCEINLINE tree_iterator &operator=(node_ptr nodeptr)
0090    {  members_.nodeptr_ = nodeptr;  return *this;  }
0091
0092    BOOST_INTRUSIVE_FORCEINLINE node_ptr pointed_node() const
0093    { return members_.nodeptr_; }
0094
0095    public:
0096    BOOST_INTRUSIVE_FORCEINLINE tree_iterator& operator++()
0097    {
0098       members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_);
0099       return *this;
0100    }
0101
0102    tree_iterator operator++(int)
0103    {
0104       tree_iterator result (*this);
0105       members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_);
0106       return result;
0107    }
0108
0109    BOOST_INTRUSIVE_FORCEINLINE tree_iterator& operator--()
0110    {
0111       members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_);
0112       return *this;
0113    }
0114
0115    tree_iterator operator--(int)
0116    {
0117       tree_iterator result (*this);
0118       members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_);
0119       return result;
0120    }
0121
0122    BOOST_INTRUSIVE_FORCEINLINE tree_iterator&  go_left()
0123    {
0124       members_.nodeptr_ = node_traits::get_left(members_.nodeptr_);
0125       return *this;
0126    }
0127
0128    BOOST_INTRUSIVE_FORCEINLINE tree_iterator&  go_right()
0129    {
0130       members_.nodeptr_ = node_traits::get_right(members_.nodeptr_);
0131       return *this;
0132    }
0133
0134    BOOST_INTRUSIVE_FORCEINLINE tree_iterator&  go_parent()
0135    {
0136       members_.nodeptr_ = node_traits::get_parent(members_.nodeptr_);
0137       return *this;
0138    }
0139
0140    BOOST_INTRUSIVE_FORCEINLINE operator unspecified_bool_type() const
0141    {  return members_.nodeptr_ ? &tree_iterator::unspecified_bool_type_func : 0;   }
0142
0143    BOOST_INTRUSIVE_FORCEINLINE bool operator! () const
0144    {  return !members_.nodeptr_;   }
0145
0146    BOOST_INTRUSIVE_FORCEINLINE friend bool operator== (const tree_iterator& l, const tree_iterator& r)
0147    { return l.pointed_node() == r.pointed_node(); }
0148
0149    BOOST_INTRUSIVE_FORCEINLINE friend bool operator!= (const tree_iterator& l, const tree_iterator& r)
0150    {  return !(l == r);   }
0151
0152    BOOST_INTRUSIVE_FORCEINLINE reference operator*() const
0153    {  return *operator->();   }
0154
0155    BOOST_INTRUSIVE_FORCEINLINE pointer operator->() const
0156    { return this->operator_arrow(detail::bool_<stateful_value_traits>()); }
0157
0158    BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr get_value_traits() const
0159    {  return members_.get_ptr();  }
0160
0161    tree_iterator end_iterator_from_it() const
0162    {
0163       return tree_iterator(node_algorithms::get_header(this->pointed_node()), this->get_value_traits());
0164    }
0165
0166    tree_iterator<value_traits, false> unconst() const
0167    {  return tree_iterator<value_traits, false>(this->pointed_node(), this->get_value_traits());   }
0168
0169    private:
0170    BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::false_) const
0171    { return ValueTraits::to_value_ptr(members_.nodeptr_); }
0172
0173    BOOST_INTRUSIVE_FORCEINLINE pointer operator_arrow(detail::true_) const
0174    { return this->get_value_traits()->to_value_ptr(members_.nodeptr_); }
0175
0176    iiterator_members<node_ptr, const_value_traits_ptr, stateful_value_traits> members_;
0177 };
0178
0179 } //namespace intrusive
0180 } //namespace boost
0181
0182 #include <boost/intrusive/detail/config_end.hpp>
0183
0184 #endif //BOOST_INTRUSIVE_TREE_ITERATOR_HPP