iterator.hpp

Go to the documentation of this file.

 
#ifndef INCLUDE_KDTREE_ITERATOR_HPP
#define INCLUDE_KDTREE_ITERATOR_HPP
 
#include <iterator>
 
#include <kdtree++/node.hpp>
 
namespace KDTree
{
  template <typename _Val, typename _Ref, typename _Ptr>
    class _Iterator;
 
  template<typename _Val, typename _Ref, typename _Ptr>
    inline bool
    operator==(_Iterator<_Val, _Ref, _Ptr> const&,
               _Iterator<_Val, _Ref, _Ptr> const&);
 
  template<typename _Val>
    inline bool
    operator==(_Iterator<_Val, const _Val&, const _Val*> const&,
               _Iterator<_Val, _Val&, _Val*> const&);
 
  template<typename _Val>
    inline bool
    operator==(_Iterator<_Val, _Val&, _Val*> const&,
               _Iterator<_Val, const _Val&, const _Val*> const&);
 
  template<typename _Val, typename _Ref, typename _Ptr>
    inline bool
    operator!=(_Iterator<_Val, _Ref, _Ptr> const&,
               _Iterator<_Val, _Ref, _Ptr> const&);
 
  template<typename _Val>
    inline bool
    operator!=(_Iterator<_Val, const _Val&, const _Val*> const&,
               _Iterator<_Val, _Val&, _Val*> const&);
 
  template<typename _Val>
    inline bool
    operator!=(_Iterator<_Val, _Val&, _Val*> const&,
               _Iterator<_Val, const _Val&, const _Val*> const&);
 
  class _Base_iterator
  {
  protected:
    typedef _Node_base::_Base_const_ptr _Base_const_ptr;
    _Base_const_ptr _M_node;
 
    inline _Base_iterator(_Base_const_ptr const __N = NULL)
      : _M_node(__N) {}
    inline _Base_iterator(_Base_iterator const& __THAT)
      : _M_node(__THAT._M_node) {}
 
    inline void
    _M_increment()
    {
      if (_M_node->_M_right)
      {
            _M_node = _M_node->_M_right;
            while (_M_node->_M_left) _M_node = _M_node->_M_left;
      }
      else
        {
          _Base_const_ptr __p = _M_node->_M_parent;
          while (__p && _M_node == __p->_M_right)
            {
              _M_node = __p;
              __p = _M_node->_M_parent;
            }
          if (__p) // (__p) provide undetermined behavior on end()++ rather
                   // than a seg fault, similar to standard iterator.
            _M_node = __p;
        }
    }
 
    inline void
    _M_decrement()
    {
      if (!_M_node->_M_parent) // clearly identify the header node
        {
          _M_node = _M_node->_M_right;
        }
      else if (_M_node->_M_left)
        {
          _Base_const_ptr x = _M_node->_M_left;
          while (x->_M_right) x = x->_M_right;
          _M_node = x;
        }
      else
        {
          _Base_const_ptr __p = _M_node->_M_parent;
          while (__p && _M_node == __p->_M_left) // see below
            {
              _M_node = __p;
              __p = _M_node->_M_parent;
            }
          if (__p) // (__p) provide undetermined behavior on rend()++ rather
                   // than a seg fault, similar to standard iterator.
            _M_node = __p;
        }
    }
 
    template <size_t const __K, typename _Val, typename _Acc,
              typename _Dist, typename _Cmp, typename _Alloc>
      friend class KDTree;
  };
 
  template <typename _Val, typename _Ref, typename _Ptr>
    class _Iterator : protected _Base_iterator
    {
    public:
      typedef _Val value_type;
      typedef _Ref reference;
      typedef _Ptr pointer;
      typedef _Iterator<_Val, _Val&, _Val*> iterator;
      typedef _Iterator<_Val, _Val const&, _Val const*> const_iterator;
      typedef _Iterator<_Val, _Ref, _Ptr> _Self;
      typedef _Node<_Val> const* _Link_const_type;
      typedef std::bidirectional_iterator_tag iterator_category;
      typedef std::ptrdiff_t difference_type;
 
      inline _Iterator()
        : _Base_iterator() {}
      inline _Iterator(_Link_const_type const __N)
        : _Base_iterator(__N) {}
      inline _Iterator(iterator const& __THAT)
        : _Base_iterator(__THAT) {}
 
      _Link_const_type get_raw_node() const
      {
         return _Link_const_type(_M_node);
      }
 
      reference
      operator*() const
      {
        return _Link_const_type(_M_node)->_M_value;
      }
 
      pointer
      operator->() const
      {
        return &(operator*());
      }
 
      _Self
      operator++()
      {
        _M_increment();
        return *this;
      }
 
      _Self
      operator++(int)
      {
        _Self ret = *this;
        _M_increment();
        return ret;
      }
 
      _Self&
      operator--()
      {
        _M_decrement();
        return *this;
      }
 
      _Self
      operator--(int)
      {
        _Self ret = *this;
        _M_decrement();
        return ret;
      }
 
      friend bool
      operator== <>(_Iterator<_Val, _Ref, _Ptr> const&,
                    _Iterator<_Val, _Ref, _Ptr> const&);
 
      friend bool
      operator== <>(_Iterator<_Val, const _Val&, const _Val*> const&,
                    _Iterator<_Val, _Val&, _Val*> const&);
 
      friend bool
      operator== <>(_Iterator<_Val, _Val&, _Val*> const&,
                    _Iterator<_Val, const _Val&, const _Val*> const&);
 
      friend bool
      operator!= <>(_Iterator<_Val, _Ref, _Ptr> const&,
                    _Iterator<_Val, _Ref, _Ptr> const&);
 
      friend bool
      operator!= <>(_Iterator<_Val, const _Val&, const _Val*> const&,
                    _Iterator<_Val, _Val&, _Val*> const&);
 
      friend bool
      operator!= <>(_Iterator<_Val, _Val&, _Val*> const&,
                    _Iterator<_Val, const _Val&, const _Val*> const&);
    };
 
  template<typename _Val, typename _Ref, typename _Ptr>
    inline bool
    operator==(_Iterator<_Val, _Ref, _Ptr> const& __X,
               _Iterator<_Val, _Ref, _Ptr> const& __Y)
    { return __X._M_node == __Y._M_node; }
 
  template<typename _Val>
    inline bool
    operator==(_Iterator<_Val, const _Val&, const _Val*> const& __X,
               _Iterator<_Val, _Val&, _Val*> const& __Y)
    { return __X._M_node == __Y._M_node; }
 
  template<typename _Val>
    inline bool
    operator==(_Iterator<_Val, _Val&, _Val*> const& __X,
               _Iterator<_Val, const _Val&, const _Val*> const& __Y)
    { return __X._M_node == __Y._M_node; }
 
  template<typename _Val, typename _Ref, typename _Ptr>
    inline bool
    operator!=(_Iterator<_Val, _Ref, _Ptr> const& __X,
               _Iterator<_Val, _Ref, _Ptr> const& __Y)
    { return __X._M_node != __Y._M_node; }
 
  template<typename _Val>
    inline bool
    operator!=(_Iterator<_Val, const _Val&, const _Val*> const& __X,
               _Iterator<_Val, _Val&, _Val*> const& __Y)
    { return __X._M_node != __Y._M_node; }
 
  template<typename _Val>
    inline bool
    operator!=(_Iterator<_Val, _Val&, _Val*> const& __X,
               _Iterator<_Val, const _Val&, const _Val*> const& __Y)
    { return __X._M_node != __Y._M_node; }
 
} // namespace KDTree
 
#endif // include guard
 
/* COPYRIGHT --
 *
 * This file is part of libkdtree++, a C++ template KD-Tree sorting container.
 * libkdtree++ is (c) 2004-2007 Martin F. Krafft <libkdtree@pobox.madduck.net>
 * and Sylvain Bougerel <sylvain.bougerel.devel@gmail.com> distributed under the
 * terms of the Artistic License 2.0. See the ./COPYING file in the source tree
 * root for more information.
 *
 * THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES
 * OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */