iterator.hpp

/*
 * iterator.hpp
 *
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)

 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.

 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Created on: Apr 1, 2013
 * Author: Jan Travnicek
 */

#ifndef __ITERATOR_HPP_
#define __ITERATOR_HPP_

#include <iterator>
#include <functional>

namespace ext {

/**
 * \brief
 * Adaptor iterator to allow values to be moved from a set. Internaly calls const cast to dereference result of underlying set iterator.
 *
 * \tparam Iterator the adapted iterator
 */
template <class Iterator>
class set_move_iterator {
	/**
	 * \brief
	 * The value of the underlying iterator.
	 */
	Iterator current;

public:
	/**
	 * \brief
	 * The underlying iterator type.
	 */
	typedef Iterator iterator_type;

	/**
	 * \brief
	 * iterator_category is inherited.
	 */
	using iterator_category = typename std::iterator_traits < Iterator >::iterator_category;

	/**
	 * \brief
	 * The value type is the value_type of adapted iterator.
	 */
	typedef typename std::iterator_traits<Iterator>::value_type        value_type;

	/**
	 * \brief
	 * Reference type is rvalue reference to the value type.
	 */
	typedef value_type&& reference;

	/**
	 * \brief
	 * The pointer type is a pointer to the value_type.
	 */
	typedef value_type* pointer;

	/**
	 * \brief
	 * Difference_type is standard pointer difference type.
	 */
	using difference_type = std::ptrdiff_t;

	/**
	 * \brief
	 * Constructor of the set move iterator adaptor.
	 *
	 * \param it the underlying set iterator
	 */
	explicit set_move_iterator (Iterator it) : current(it) {
	}

	/**
	 * \brief
	 * Getter of the underlying set iterator.
	 *
	 * \return the underlying iterator
	 */
	iterator_type base() const {
		return current;
	}

	/**
	 * \brief
	 * Arrow operator using the const cast
	 *
	 * \return const casted pointer to the value pointed to by underlying set iterator
	 */
	pointer operator->() const {
		return & ( this->operator * ( ) );
	}

	/**
	 * \brief
	 * Dereference operator using the const cast
	 *
	 * \return rvalue reference to const casted value pointed to by underlying set iterator
	 */
	reference operator*() const {
		return std::move(const_cast<value_type&>(*current));
	}

	/**
	 * \brief
	 * Increment operator.
	 *
	 * Increments the underlying operator.
	 *
	 * \return the modified iterator
	 */
	set_move_iterator& operator++() {
		++current;
		return *this;
	}

	/**
	 * \brief
	 * Decrement operator.
	 *
	 * Decrements the underlying operator.
	 *
	 * \return the modified iterator
	 */
	set_move_iterator& operator--() {
		--current;
		return *this;
	}

	/**
	 * \brief
	 * Increment operator.
	 *
	 * Increments the underlying operator.
	 *
	 * \return the original iterator
	 */
	set_move_iterator operator++(int) {
		set_move_iterator temp = *this;
		++current;
		return temp;
	}

	/**
	 * \brief
	 * Decrement operator.
	 *
	 * Decrements the underlying operator.
	 *
	 * \return the original iterator
	 */
	set_move_iterator operator--(int) {
		set_move_iterator temp = *this;
		--current;
		return temp;
	}

	/**
	 * \brief
	 * Comparison of iterators for equality.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the two iterators underlying iterators are equal
	 */
	bool operator== (const set_move_iterator<Iterator>& other) {
		return this->current == other.current;
	}

	/**
	 * \brief
	 * Comparison of iterators for non-equality.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the two iterators underlying iterators are not equal
	 */
	bool operator!= (const set_move_iterator<Iterator>& other) {
		return ! ( *this == other );
	}

};

/**
 * \brief
 * Move from set iterator adaptor construction function.
 *
 * \tparam Iterator the type of iterator to adapt
 *
 * \param it iterator for adaptation
 *
 * \return adapted iterator
 */
template<class Iterator>
set_move_iterator<Iterator> make_set_move_iterator (Iterator it) {
	return set_move_iterator<Iterator>(it);
}

/**
 * \brief
 * Adaptor iterator to allow values to be moved from a map. Internaly calls reinterpret cast to dereference result of underlying map iterator.
 *
 * \tparam Iterator the adapted iterator
 * \tparam KeyType the key type of adapted map's iterator
 * \tparam ValueType the value type of adapted map's iterator
 */
template < class Iterator, class KeyType, class ValueType >
class map_move_iterator {
	/**
	 * \brief
	 * The value of the underlying iterator.
	 */
	Iterator current;

public:
	/**
	 * \brief
	 * The underlying iterator type.
	 */
	typedef Iterator iterator_type;

	/**
	 * \brief
	 * iterator_category is inherited.
	 */
	using iterator_category = typename std::iterator_traits < Iterator >::iterator_category;

	/**
	 * \brief
	 * The value type is essentially the value_type of adapted iterator but constructed here to avoid consts.
	 */
	typedef typename std::pair < KeyType, ValueType >        value_type;

	/**
	 * \brief
	 * Reference type is rvalue reference to the value type.
	 */
	typedef value_type&& reference;

	/**
	 * \brief
	 * The pointer type is a pointer to the value_type.
	 */
	typedef value_type* pointer;

	/**
	 * \brief
	 * Difference_type is standard pointer difference type.
	 */
	using difference_type = std::ptrdiff_t;

	/**
	 * \brief
	 * Constructor of the set move iterator adaptor.
	 *
	 * \param it the underlying set iterator
	 */
	explicit map_move_iterator (Iterator it) : current(it) {
	}

	/**
	 * \brief
	 * Getter of the underlying set iterator.
	 *
	 * \return the underlying iterator
	 */
	iterator_type base() const {
		return current;
	}

	/**
	 * \brief
	 * Arrow operator using the reinterpret cast
	 *
	 * \return const casted pointer to the value pointed to by underlying set iterator
	 */
	pointer operator->() const {
		return & ( this->operator * ( ) );
	}

	/**
	 * \brief
	 * Dereference operator using the reinterpret cast
	 *
	 * \return rvalue reference to const casted value pointed to by underlying set iterator
	 */
	reference operator*() const {
		return std::move(reinterpret_cast < value_type & >(*current));
	}

	/**
	 * \brief
	 * Increment operator.
	 *
	 * Increments the underlying operator.
	 *
	 * \return the modified iterator
	 */
	map_move_iterator& operator++() {
		++current;
		return *this;
	}

	/**
	 * \brief
	 * Decrement operator.
	 *
	 * Decrements the underlying operator.
	 *
	 * \return the modified iterator
	 */
	map_move_iterator& operator--() {
		--current;
		return *this;
	}

	/**
	 * \brief
	 * Increment operator.
	 *
	 * Increments the underlying operator.
	 *
	 * \return the original iterator
	 */
	map_move_iterator operator++(int) {
		map_move_iterator temp = *this;
		++current;
		return temp;
	}

	/**
	 * \brief
	 * Decrement operator.
	 *
	 * Decrements the underlying operator.
	 *
	 * \return the original iterator
	 */
	map_move_iterator operator--(int) {
		map_move_iterator temp = *this;
		--current;
		return temp;
	}

	/**
	 * \brief
	 * Comparison of iterators for equality.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the two iterators underlying iterators are equal
	 */
	bool operator== (const map_move_iterator<Iterator, KeyType, ValueType>& other) {
		return this->current == other.current;
	}

	/**
	 * \brief
	 * Comparison of iterators for non-equality.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the two iterators underlying iterators are not equal
	 */
	bool operator!= (const map_move_iterator<Iterator, KeyType, ValueType>& other) {
		return ! ( *this == other );
	}

};

/**
 * \brief
 * Move from map iterator adaptor construction function.
 *
 * \tparam Iterator the type of iterator to adapt
 * \tparam KeyType the key type of adapted map's iterator
 * \tparam ValueType the value type of adapted map's iterator
 *
 * \param it iterator for adaptation
 *
 * \return adapted iterator
 */
template < class T, class R, class Iterator>
map_move_iterator<Iterator, T, R> make_map_move_iterator (Iterator it) {
	return map_move_iterator<Iterator, T, R>(it);
}

/**
 * \brief
 * Adaptor class to change begin and end behavior for rvalue qualified begin and end. This class takes ownership of the adapted instance by move construction.
 *
 * \tparam T the type of class having rvalue qualified begin and end methods
 */
template < class T >
class value_mover {
	/**
	 * \brief
	 * The adapted value.
	 */
	T m_Container;
public:
	/**
	 * \brief
	 * Constructor of the mover adaptor class.
	 */
	explicit value_mover ( T && param ) : m_Container ( std::move ( param ) ) {}

	/**
	 * \brief
	 * Begin method calls rvalue qualified begin on adapted value.
	 */
	auto begin ( ) {
		return std::move ( m_Container ).begin ( );
	}

	/**
	 * \brief
	 * End method calls rvalue qualified end on adapted value.
	 */
	auto end ( ) {
		return std::move ( m_Container ).end ( );
	}
};

/**
 * \brief
 * Adaptor class to change begin and end behavior for rvalue qualified begin and end. This class keeps rvalue reference of the adapted instance.
 *
 * \tparam T the type of class having rvalue qualified begin and end methods
 */
template < class T >
class reference_mover {
	/**
	 * \brief
	 * The adapted value.
	 */
	T && m_Container;
public:
	/**
	 * \brief
	 * Constructor of the mover adaptor class.
	 */
	explicit reference_mover ( T && param ) : m_Container ( std::move ( param ) ) {}

	/**
	 * \brief
	 * Begin method calls rvalue qualified begin on adapted value.
	 */
	auto begin ( ) {
		return std::move ( m_Container ).begin ( );
	}

	/**
	 * \brief
	 * End method calls rvalue qualified end on adapted value.
	 */
	auto end ( ) {
		return std::move ( m_Container ).end ( );
	}
};

/**
 * \brief
 * Move adaptor construction function specialized to lvalue reference parameter.
 *
 * \tparam T the type of class having rvalue qualified begin and end methods
 *
 * \param container the instance of an adapted class
 *
 * \return class having begin, end, other related methods allowing move of values from the container
 */
template < class T >
reference_mover < T > make_mover ( T & param ) {
	return reference_mover < T > ( std::move ( param ) );
}

/**
 * \brief
 * Move adaptor construction function specialized to rvalue reference paramter.
 *
 * \tparam T the type of class having rvalue qualified begin and end methods
 *
 * \param container the instance of an adapted class
 *
 * \return class having begin, end, other related methods allowing move of values from the container
 */
template < class T >
value_mover < T > make_mover ( T && param ) {
	return value_mover < T > ( std::forward < T > ( param ) );
}

/**
 * \brief
 * Adaptor class to change begin and end behavior for reverse begin and reverse end and vise versa.
 *
 * \tparam T the type of class having rbegin and rend methods
 */
template < class T >
class reverser {
	/**
	 * \brief
	 * Reference holder for the adapted container. The reference will colaps to &, const & or
	 */
	T && m_Container;

public:
	/**
	 * \brief
	 * Constructor of the adaptor class based on the adapted container.
	 *
	 * \param container the adapted container
	 */
	explicit reverser ( T && container ) : m_Container ( std::forward < T && > ( container ) ) {
	}

	/**
	 * \brief
	 * Begin adaptor method to call rbegin.
	 *
	 * \return reverse begin iterator
	 */
	auto begin ( ) const {
		return m_Container.rbegin ( );
	}

	/**
	 * \brief
	 * End adaptor method to call rend.
	 *
	 * \return reverse end iterator
	 */
	auto end ( ) const {
		return m_Container.rend ( );
	}

};

/**
 * \brief
 * Reverese adaptor construction function.
 *
 * \tparam T the type of class having rbegin and rend methods
 *
 * \param container the instance of an adapted class
 *
 * \return class having begin, end, other related methods swaping reverse and not reverse iterator getters
 */
template < class T >
reverser < T > make_reverse ( T && container ) {
	return reverser < T > ( container );
}

/**
 * \brief
 * Adaptor iterator to additionally call second dereference on the iterator dereference result.
 *
 * \tparam Iterator the adapted iterator
 *
 */
template < class Iterator >
class dereferencing_iterator {
	/**
	 * \brief
	 * The value of the underlying iterator.
	 */
	Iterator m_base;

public:
	/**
	 * \brief
	 * The pointer type is the value of adapted iterator.
	 */
	using pointer = typename std::iterator_traits < Iterator >::value_type;

	/**
	 * \brief
	 * The value type is the value of adapted iterator without pointer.
	 */
	using value_type = typename std::conditional < std::is_const < typename std::remove_reference < typename std::iterator_traits < Iterator >::reference >::type >::value, typename std::add_const < typename std::remove_pointer < pointer >::type >::type, typename std::remove_pointer < pointer >::type >::type;

	/**
	 * \brief
	 * Difference_type is standard pointer difference type.
	 */
	using difference_type = std::ptrdiff_t;

	/**
	 * \brief
	 * Reference type is reference to the value type.
	 */
	using reference = value_type &;

	/**
	 * \brief
	 * iterator_category is inherited.
	 */
	using iterator_category = typename std::iterator_traits < Iterator >::iterator_category;

	/**
	 * \brief
	 * Constructor of the dereferencing iterator adaptor.
	 *
	 * \param base the underlying iterator
	 */
	explicit dereferencing_iterator ( Iterator base ) : m_base ( base ) {
	}

	/**
	 * Cast constructor from dereferencing iterator adapting compatible iterator.
	 *
	 * \tparam Iter the underlying iterator type of dereference iterator
	 *
	 * \param iter the casted dereferencing iterator
	 */
	template < class Iter >
	dereferencing_iterator ( const dereferencing_iterator < Iter > & iter ) : m_base ( iter.base ( ) ) {
	}

	/**
	 * \brief
	 * Dereference operator doing extra dereference.
	 *
	 * \return the value pointed to by result of dereference of the underlying iterator
	 */
	reference operator * ( ) const {
		return * * m_base;
	}

	/**
	 * \brief
	 * Arrow operator doing extra dereference.
	 *
	 * \return dereference of the underlying iterator
	 */
	pointer operator -> ( ) const {
		return * m_base;
	}

	/**
	 * \brief
	 * Increment operator.
	 *
	 * Increments the underlying operator.
	 *
	 * \return the modified iterator
	 */
	dereferencing_iterator < Iterator > & operator ++ ( ) {
		++ m_base;
		return * this;
	}

	/**
	 * \brief
	 * Increment operator.
	 *
	 * Increments the underlying operator.
	 *
	 * \return the original iterator
	 */
	dereferencing_iterator < Iterator > operator ++ ( int ) {
		auto tmp = * this;
		++ m_base;
		return tmp;
	}

	/**
	 * \brief
	 * Decrement operator.
	 *
	 * Decrements the underlying operator.
	 *
	 * \return the modified iterator
	 */
	dereferencing_iterator < Iterator > & operator -- ( ) {
		-- m_base;
		return * this;
	}

	/**
	 * \brief
	 * Decrement operator.
	 *
	 * Decrements the underlying operator.
	 *
	 * \return the original iterator
	 */
	dereferencing_iterator < Iterator > operator -- ( int ) {
		auto tmp = * this;
		-- m_base;
		return tmp;
	}

	/**
	 * \brief
	 * Shifs the iterator by \p distance.
	 *
	 * \param distance the distance to shift by
	 *
	 * \return the modified iterator
	 */
	dereferencing_iterator < Iterator > & operator += ( int distance ) {
		m_base += distance;
		return *this;
	}

	/**
	 * \brief
	 * Creates a new iterator and shifs it by \p distance.
	 *
	 * \param distance the distance to shift by
	 *
	 * \return the new iterator
	 */
	dereferencing_iterator < Iterator > operator + ( int distance ) const {
		auto res = * this;
		res += distance;
		return res;
	}

	/**
	 * \brief
	 * Shifs the iterator back by \p distance.
	 *
	 * \param distance the distance to shift by
	 *
	 * \return the modified iterator
	 */
	dereferencing_iterator < Iterator > & operator -= ( int distance ) {
		m_base -= distance;
		return *this;
	}

	/**
	 * \brief
	 * Creates a new iterator and shifs it back by \p distance.
	 *
	 * \param distance the distance to shift by
	 *
	 * \return the new iterator
	 */
	dereferencing_iterator < Iterator > operator - ( int distance ) const {
		auto res = * this;
		res -= distance;
		return res;
	}

	/**
	 * \brief
	 * Array subscript operator.
	 *
	 * Additionaly dereferences the result of subscript of the underlying iterator.
	 *
	 * \param index the subscript index
	 *
	 * \return the value pointed to by pointer at position given by \p index
	 */
	reference operator [ ] ( int index ) const {
		return * ( m_base [ index ] );
	}

	/**
	 * \brief
	 * Distance of two iterators computation operator.
	 *
	 * \param other the other iterator
	 *
	 * \return the distance between this and the other iterator
	 */
	difference_type operator - ( const dereferencing_iterator < Iterator > & other ) {
		return m_base - other.m_base;
	}

	/**
	 * \brief
	 * Comparison of iterators for equality.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the two iterators underlying iterators are equal
	 */
	bool operator == ( const dereferencing_iterator < Iterator > & other ) const {
		return this->m_base == other.m_base;
	}

	/**
	 * \brief
	 * Comparison of iterators for non-equality.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the two iterators underlying iterators are not equal
	 */
	bool operator != ( const dereferencing_iterator < Iterator > & other ) const {
		return ! ( * this == other );
	}

	/**
	 * \brief
	 * Less than comparison of iterators.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the underlying iterator of this is less than the underlying iterator of the other one
	 */
	bool operator < ( const dereferencing_iterator < Iterator > & other ) const {
		return this->m_base < other.m_base;
	}

	/**
	 * \brief
	 * Greater than comparison of iterators.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the underlying iterator of this is greater than the underlying iterator of the other one
	 */
	bool operator > ( const dereferencing_iterator < Iterator > & other ) const {
		return other < * this;
	}

	/**
	 * \brief
	 * Less than or equal comparison of iterators.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the underlying iterator of this is less than or equal to the underlying iterator of the other one
	 */
	bool operator <= ( const dereferencing_iterator < Iterator > & other ) const {
		return ! ( * this > other );
	}

	/**
	 * \brief
	 * Greater than or equal comparison of iterators.
	 *
	 * \param other the other iterator
	 *
	 * \return true if the underlying iterator of this is greater than or equal to the underlying iterator of the other one
	 */
	bool operator >= ( const dereferencing_iterator < Iterator > & other ) const {
		return ! ( * this < other );
	}

	/**
	 * \brief
	 * The underlying iterator getter.
	 *
	 * \return the underlying iterator
	 */
	Iterator base ( ) const {
		return m_base;
	}

};

/**
 * \brief
 * Dereferencing adaptor construction function.
 *
 * \tparam T the type of iterator to adapt
 *
 * \param iter source iterator for inner dereferencing
 *
 * \return adapted iterator
 */
template < class Iterator >
dereferencing_iterator < Iterator > dereferencer ( Iterator iter ) {
	return dereferencing_iterator < Iterator > ( iter );
}

/**
 * \brief
 * False case type trait detecting the template parameter T is not an iterator.
 *
 * The class has a field value set to false.
 */
template < typename T >
struct is_iterator : std::false_type {};

/**
 * \brief
 * True case type trait detecting the template parameter T is an iterator.
 *
 * The class has a field value set to true.
 */
template < typename T >
struct is_iterator<typename std::iterator_traits<T>> : std::true_type {};

/**
 * \brief
 * Implementation of retract function specific to input iterators.
 *
 * \tparam Iterator the type of retracted iterator
 * \tparam Distance the type of distance to retract
 *
 * \param i the retracted iterator
 * \param n the distance to retract
 */
template < typename InputIterator, typename Distance >
inline constexpr void retractInternal ( InputIterator & i, Distance n, std::input_iterator_tag ) {
	assert ( n <= 0 );
	while ( n ++ )
		++ i;
}

/**
 * \brief
 * Implementation of retract function specific to bidrectional iterators.
 *
 * \tparam Iterator the type of retracted iterator
 * \tparam Distance the type of distance to retract
 *
 * \param i the retracted iterator
 * \param n the distance to retract
 */
template < typename BidirectionalIterator, typename Distance >
inline constexpr void retractInternal ( BidirectionalIterator & i, Distance n, std::bidirectional_iterator_tag ) {
	if ( n > 0)
		while ( n -- )
			-- i;
	else
		while ( n ++ )
			++ i;
}

/**
 * \brief
 * Implementation of retract function specific to random access iterators.
 *
 * \tparam Iterator the type of retracted iterator
 * \tparam Distance the type of distance to retract
 *
 * \param i the retracted iterator
 * \param n the distance to retract
 */
template < typename RandomAccessIterator, typename Distance >
inline constexpr void retractInternal ( RandomAccessIterator & i, Distance n, std::random_access_iterator_tag ) {
	i -= n;
}

/**
 * \brief
 * \brief A generalization of pointer arithmetic.
 *
 * \tparam Iterator the type of retracted iterator
 * \tparam Distance the type of distance to retract
 *
 * \param i An instance of some iterator.
 * \param n The \a delta by which to change \p i.
 *
 * For random access and bidirectional iterators, \p n may be positive, in which case \p i is decremented.
 * For random access, bidirectional, and input iterators, \p n may be negative, in which case \p i is incremented.
 *
 * For random access iterators, this uses their \c + and \c - operations and are constant time. For other %iterator classes they are linear time.
 */
template < typename Iterator, typename Distance >
inline constexpr void retract ( Iterator & i, Distance n ) {
	typename std::iterator_traits < Iterator >::difference_type d = n;
	retractInternal ( i, d, std::__iterator_category ( i ) );
}

/**
 * Generalization of begin for universaly referenced containers.
 *
 * \param cont the container to call begin on
 *
 * \result the begin move iterator
 */
template < class Container >
auto begin ( Container && cont ) -> decltype ( std::forward ( cont ).begin ( ) ) {
	return std::forward ( cont ).begin ( );
}

/**
 * Generalization of end for universaly referenced containers.
 *
 * \param cont the container to call end on
 *
 * \result the end move iterator
 */
template < class Container >