// This file is part of the ustl library, an STL implementation.
//
// Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
// This file is free software, distributed under the MIT License.
//
/// \file uiterator.h
/// \brief Contains various iterator adapters.
//

#ifndef UITERATOR_H_5BCA176C7214A30F2069E2614D2DC226
#define UITERATOR_H_5BCA176C7214A30F2069E2614D2DC226

#include "uassert.h"
#include "utypes.h"

namespace ustl {

//----------------------------------------------------------------------

/// \struct iterator_traits uiterator.h ustl.h
/// \brief Contains the type traits of \p Iterator
///
template <typename Iterator>
struct iterator_traits {
    typedef typename Iterator::value_type        value_type;
    typedef typename Iterator::difference_type   difference_type;
    typedef typename Iterator::pointer           pointer;
    typedef typename Iterator::reference         reference;
};

#ifndef DOXYGEN_SHOULD_SKIP_THIS

template <typename T>
struct iterator_traits<T*> {
    typedef T		value_type;
    typedef ptrdiff_t	difference_type;
    typedef const T*	const_pointer;
    typedef T*		pointer;
    typedef T&		reference;
};

template <typename T>
struct iterator_traits<const T*> {
    typedef T		value_type;
    typedef ptrdiff_t	difference_type;
    typedef const T*	const_pointer;
    typedef const T*	pointer;
    typedef const T&	reference;
};

template <>
struct iterator_traits<void*> {
    typedef uint8_t	value_type;
    typedef ptrdiff_t	difference_type;
    typedef const void*	const_pointer;
    typedef void*	pointer;
    typedef value_type&	reference;
};

template <>
struct iterator_traits<const void*> {
    typedef uint8_t		value_type;
    typedef ptrdiff_t		difference_type;
    typedef const void*		const_pointer;
    typedef const void*		pointer;
    typedef const value_type&	reference;
};

#endif

//----------------------------------------------------------------------

/// \class reverse_iterator uiterator.h ustl.h
/// \ingroup IteratorAdaptors
/// \brief Wraps \p Iterator to behave in an exactly opposite manner.
///
template <class Iterator>
class reverse_iterator {
public:
    typedef typename iterator_traits<Iterator>::value_type	value_type;
    typedef typename iterator_traits<Iterator>::difference_type	difference_type;
    typedef typename iterator_traits<Iterator>::pointer		pointer;
    typedef typename iterator_traits<Iterator>::reference	reference;
public:
    				reverse_iterator (void) : m_i() {}
    explicit			reverse_iterator (Iterator iter) : m_i (iter) {}
    inline bool			operator== (const reverse_iterator& iter) const { return (m_i == iter.m_i); }
    inline bool			operator< (const reverse_iterator& iter) const { return (iter.m_i < m_i); }
    inline Iterator		base (void) const { return (m_i); }
    inline reference		operator* (void) const { Iterator prev (m_i); --prev; return (*prev); }
    inline pointer		operator-> (void) const { return (&(operator*())); }
    inline reverse_iterator&	operator++ (void) { -- m_i; return (*this); }
    inline reverse_iterator&	operator-- (void) { ++ m_i; return (*this); }
    inline reverse_iterator	operator++ (int) { reverse_iterator prev (*this); -- m_i; return (prev); }
    inline reverse_iterator	operator-- (int) { reverse_iterator prev (*this); ++ m_i; return (prev); }
    inline reverse_iterator&	operator+= (size_t n) { m_i -= n; return (*this); }
    inline reverse_iterator&	operator-= (size_t n) { m_i += n; return (*this); }
    inline reverse_iterator	operator+ (size_t n) const { return (reverse_iterator (m_i - n)); }
    inline reverse_iterator	operator- (size_t n) const { return (reverse_iterator (m_i + n)); }
    inline reference		operator[] (uoff_t n) const { return (*(*this + n)); }
    inline difference_type	operator- (const reverse_iterator& i) const { return (distance (m_i, i.m_i)); }
protected:
    Iterator		m_i;
};

//----------------------------------------------------------------------

/// \class insert_iterator uiterator.h ustl.h
/// \ingroup IteratorAdaptors
/// \brief Calls insert on bound container for each assignment.
///
template <class Container>
class insert_iterator {
public:
    typedef typename Container::value_type	value_type;
    typedef typename Container::difference_type	difference_type;
    typedef typename Container::pointer		pointer;
    typedef typename Container::reference	reference;
    typedef typename Container::iterator	iterator;
public:
    explicit			insert_iterator (Container& ctr, iterator ip) : m_rCtr (ctr), m_ip (ip) {}
    inline insert_iterator&	operator= (typename Container::const_reference v)
    				    { m_ip = m_rCtr.insert (m_ip, v); return (*this); }
    inline insert_iterator&	operator* (void)  { return (*this); }
    inline insert_iterator&	operator++ (void) { ++ m_ip; return (*this); }
    inline insert_iterator	operator++ (int)  { insert_iterator prev (*this); ++ m_ip; return (*this); }
protected:
    Container&			m_rCtr;
    iterator			m_ip;
};

/// Returns the insert_iterator for \p ctr.
template <class Container>
inline insert_iterator<Container> inserter (Container& ctr, typename Container::iterator ip)
{
    return (insert_iterator<Container> (ctr, ip));
}

//----------------------------------------------------------------------

/// \class back_insert_iterator uiterator.h ustl.h
/// \ingroup IteratorAdaptors
/// \brief Calls push_back on bound container for each assignment.
///
template <class Container>
class back_insert_iterator {
public:
    typedef typename Container::value_type	value_type;
    typedef typename Container::difference_type	difference_type;
    typedef typename Container::pointer		pointer;
    typedef typename Container::reference	reference;
public:
    explicit				back_insert_iterator (Container& ctr) : m_rCtr (ctr) {}
    inline back_insert_iterator&	operator= (typename Container::const_reference v)
    					    { m_rCtr.push_back (v); return (*this); }
    inline back_insert_iterator&	operator* (void)  { return (*this); }
    inline back_insert_iterator&	operator++ (void) { return (*this); }
    inline back_insert_iterator		operator++ (int)  { return (*this); }
protected:
    Container&		m_rCtr;
};

/// Returns the back_insert_iterator for \p ctr.
template <class Container>
inline back_insert_iterator<Container> back_inserter (Container& ctr)
{
    return (back_insert_iterator<Container> (ctr));
}

//----------------------------------------------------------------------

/// \class index_iterate uiterator.h ustl.h
/// \ingroup IteratorAdaptors
///
/// \brief Allows iteration through an index container.
///
/// Converts an iterator into a container of uoff_t indexes to an
/// iterator of iterators into another container.
///
template <typename RandomAccessIterator, typename IndexIterator>
class index_iterate {
public:
    typedef RandomAccessIterator	value_type;
    typedef ptrdiff_t			difference_type;
    typedef RandomAccessIterator*	pointer;
    typedef RandomAccessIterator	reference;
public:
    				index_iterate (void) : m_Base(), m_i() {}
				index_iterate (RandomAccessIterator ibase, IndexIterator iindex) : m_Base (ibase), m_i (iindex) {}
    inline bool			operator== (const index_iterate& i) const { return (m_i == i.m_i); }
    inline bool			operator< (const index_iterate& i) const { return (m_i < i.m_i); }
    inline bool			operator== (const RandomAccessIterator& i) const { return (m_Base == i); }
    inline bool			operator< (const RandomAccessIterator& i) const { return (m_Base < i); }
    inline IndexIterator	base (void) const { return (m_i); }
    inline reference		operator* (void) const { return (advance(m_Base, *m_i)); }
    inline pointer		operator-> (void) const { return (&(operator*())); }
    inline index_iterate&	operator++ (void) { ++ m_i; return (*this); }
    inline index_iterate&	operator-- (void) { -- m_i; return (*this); }
    inline index_iterate	operator++ (int) { index_iterate prev (*this); ++ m_i; return (prev); }
    inline index_iterate	operator-- (int) { index_iterate prev (*this); -- m_i; return (prev); }
    inline index_iterate&	operator+= (size_t n) { m_i += n; return (*this); }
    inline index_iterate&	operator-= (size_t n) { m_i -= n; return (*this); }
    inline index_iterate	operator+ (size_t n) const { return (index_iterate (m_Base, m_i + n)); }
    inline index_iterate	operator- (size_t n) const { return (index_iterate (m_Base, m_i - n)); }
    inline reference		operator[] (uoff_t n) const { return (*(*this + n)); }
    inline difference_type	operator- (const index_iterate& i) const { return (distance (m_i, i.m_i)); }
private:
    RandomAccessIterator	m_Base;
    IndexIterator		m_i;
};

/// Returns an index_iterate for \p ibase over \p iindex.
template <typename RandomAccessIterator, typename IndexIterator>
inline index_iterate<RandomAccessIterator, IndexIterator> index_iterator (RandomAccessIterator ibase, IndexIterator iindex)
{
    return (index_iterate<RandomAccessIterator, IndexIterator> (ibase, iindex));
}

/// Converts the indexes in \p xc to iterators in \p ic of base \p ibase.
template <typename IndexContainer, typename IteratorContainer>
inline void indexv_to_iteratorv (typename IteratorContainer::value_type ibase, const IndexContainer& xc, IteratorContainer& ic)
{
    ic.resize (xc.size());
    copy_n (index_iterator (ibase, xc.begin()), xc.size(), ic.begin());
}

//----------------------------------------------------------------------

/// Converts the given const_iterator into an iterator.
///
template <typename Container>
inline typename Container::iterator unconst (typename Container::const_iterator i, Container& ctr)
{
    const Container& cctr = ctr;
    return (ctr.begin() + (i - cctr.begin()));
}

#ifndef DOXYGEN_SHOULD_SKIP_THIS

#define IBYI(Iter1, Iter2, Ctr1, Ctr2)	\
template <typename Container1, typename Container2>	\
inline typename Container2::Iter2 ibyi (typename Container1::Iter1 idx, Ctr1& ctr1, Ctr2& ctr2)	\
{							\
    assert (ctr1.size() == ctr2.size());		\
    return (ctr2.begin() + (idx - ctr1.begin()));	\
}

IBYI(const_iterator, const_iterator, const Container1, const Container2)
IBYI(iterator, iterator, Container1, Container2)
IBYI(const_iterator, iterator, const Container1, Container2)
IBYI(iterator, const_iterator, Container1, const Container2)

#else // DOXYGEN

#error This declaration is for doxygen only; it is not compiled.

/// Converts a const_iterator in one container into a const_iterator in another container.
template <typename Container1, typename Container2>
inline typename Container2::iterator ibyi (typename Container1::iterator idx, Container1& ctr1, Container2& ctr2) {}

#endif // DOXYGEN

//----------------------------------------------------------------------

} // namespace ustl

#endif