/** \file
 * Defines interfaces for iterators as used by the KDTree class.
 *
 * \author Martin F. Krafft <libkdtree@pobox.madduck.net>
 */

#ifndef INCLUDE_KDTREE_ITERATOR_HPP
#define INCLUDE_KDTREE_ITERATOR_HPP

#include <iterator>

#include "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 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>
    bool
    operator==(_Iterator<_Val, _Ref, _Ptr> const& __X,
               _Iterator<_Val, _Ref, _Ptr> const& __Y)
    { return __X._M_node == __Y._M_node; }

  template<typename _Val>
    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>
    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>
    bool
    operator!=(_Iterator<_Val, _Ref, _Ptr> const& __X,
               _Iterator<_Val, _Ref, _Ptr> const& __Y)
    { return __X._M_node != __Y._M_node; }

  template<typename _Val>
    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>
    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.
 */