map.hpp

/*
 * map.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 __MAP_HPP_
#define __MAP_HPP_

#include <map>
#include <ostream>
#include <sstream>
#include <utility>
#include <string>

#include "pair.hpp"

#include <extensions/compare.hpp>
#include <extensions/allocFix.hpp>
#include <extensions/range.hpp>

namespace ext {

/**
 * \brief
 * Class extending the map class from the standard library. Original reason is to allow printing of the container with overloaded operator <<.
 *
 * The class mimics the behavior of the map from the standatd library.
 *
 * \tparam T the type of keys inside the map
 * \tparam R the type of values inside the map
 * \tparam Cmp the comparator type used to order keys
 * \tparam Alloc the allocator of values of type T
 */
template < typename T, typename R, typename Cmp = std::less < >, typename Alloc = std::allocator < std::pair < const T, R > > >
class map : public std::map < T, R, Cmp, Alloc >, AllocFix < Alloc > {
public:
	/**
	 * Inherit constructors of the standard map
	 */
	using std::map< T, R, Cmp, Alloc >::map;

	/**
	 * Inherit operator = of the standard map
	 */
	using std::map< T, R, Cmp, Alloc >::operator =;
#ifndef __clang__

	/**
	 * Default constructor needed by g++ since it is not inherited
	 */
	map ( ) = default;

	/**
	 * Copy constructor needed by g++ since it is not inherited
	 */
	map ( const map & other ) = default;

	/**
	 * Move constructor needed by g++ since it is not inherited
	 */
	map ( map && other ) = default;

	/**
	 * Copy operator = needed by g++ since it is not inherited
	 */
	map & operator = ( map && other ) = default;

	/**
	 * Move operator = needed by g++ since it is not inherited
	 */
	map & operator = ( const map & other ) = default;
#endif
	/**
	 * Constructor from range of values.
	 *
	 * \tparam Iterator the type of range iterator
	 *
	 * \param range the source range
	 */
	template < class Iterator >
	explicit map ( const ext::iterator_range < Iterator > & range ) : map ( range.begin ( ), range.end ( ) ) {
	}

	/**
	 * \brief
	 * The iterator type is inheried.
	 */
	using iterator = typename std::map<T, R, Cmp, Alloc>::iterator;

	/**
	 * \brief
	 * Inherit all insert methods of the standard map.
	 */
	using std::map< T, R, Cmp, Alloc >::insert;

	/**
	 * \brief
	 * Insert variant with explicit key and value parameters.
	 *
	 * \param key the key
	 * \param value the value
	 *
	 * \return pair of iterator to inserted key-value pair and true if the value was inserted or false if the key already exited
	 */
	std::pair < iterator, bool > insert ( const T & key, const R & value ) {
		return insert ( std::make_pair ( key, value ) );
	}

	/**
	 * \brief
	 * Insert variant with explicit key and value parameters.
	 *
	 * \param key the key
	 * \param value the value
	 *
	 * \return pair of iterator to inserted key-value pair and true if the value was inserted or false if the key already exited
	 */
	std::pair < iterator, bool > insert ( const T & key, R && value ) {
		return insert ( std::make_pair ( key, std::move ( value ) ) );
	}

	/**
	 * \brief
	 * Insert variant with explicit key and value parameters.
	 *
	 * \param key the key
	 * \param value the value
	 *
	 * \return pair of iterator to inserted key-value pair and true if the value was inserted or false if the key already exited
	 */
	std::pair < iterator, bool > insert ( T && key, const R & value ) {
		return insert ( std::make_pair ( std::move ( key ), value ) );
	}

	/**
	 * \brief
	 * Insert variant with explicit key and value parameters.
	 *
	 * \param key the key
	 * \param value the value
	 *
	 * \return pair of iterator to inserted key-value pair and true if the value was inserted or false if the key already exited
	 */
	std::pair < iterator, bool > insert ( T && key, R && value ) {
		return insert ( std::make_pair ( std::move ( key ), std::move ( value ) ) );
	}

	using std::map< T, R, Cmp, Alloc >::at;

	R & at ( const T & key, R & defaultValue ) {
		auto value = this->find ( key );
		if ( value == end ( ) )
			return defaultValue;
		else
			return value->second;
	}

	const R & at ( const T & key, const R & defaultValue ) const {
		auto value = this->find ( key );
		if ( value == end ( ) )
			return defaultValue;
		else
			return value->second;
	}

	/**
	 * \brief
	 * Inherited behavior of begin for non-const instance.
	 *
	 * \return iterator the first element of map
	 */
	auto begin ( ) & {
		return std::map < T, R, Cmp, Alloc >::begin ( );
	}

	/**
	 * \brief
	 * Inherited behavior of begin for const instance.
	 *
	 * \return const_iterator the first element of map
	 */
	auto begin ( ) const & {
		return std::map < T, R, Cmp, Alloc >::begin ( );
	}

	/**
	 * \brief
	 * New variant of begin for rvalues.
	 *
	 * \return move_iterator the first element of map
	 */
	auto begin ( ) && {
		return make_map_move_iterator < T, R > ( this->begin ( ) );
	}

	/**
	 * \brief
	 * Inherited behavior of end for non-const instance.
	 *
	 * \return iterator to one after the last element of map
	 */
	auto end ( ) & {
		return std::map < T, R, Cmp, Alloc >::end ( );
	}

	/**
	 * \brief
	 * Inherited behavior of end for const instance.
	 *
	 * \return const_iterator to one after the last element of map
	 */
	auto end ( ) const & {
		return std::map < T, R, Cmp, Alloc >::end ( );
	}

	/**
	 * \brief
	 * New variant of end for rvalues.
	 *
	 * \return move_iterator to one after the last element of map
	 */
	auto end ( ) && {
		return make_map_move_iterator < T, R > ( this->end ( ) );
	}

	/**
	 * \brief
	 * Make range of non-const begin to end iterators.
	 *
	 * \return full range over container values
	 */
	auto range ( ) & {
		auto endIter = end ( );
		auto beginIter = begin ( );
		return ext::iterator_range < decltype ( endIter ) > ( beginIter, endIter );
	}

	/**
	 * \brief
	 * Make range of non-const begin to end iterators.
	 *
	 * \return full range over container values
	 */
	auto range ( ) const & {
		auto endIter = end ( );
		auto beginIter = begin ( );
		return ext::iterator_range < decltype ( endIter ) > ( beginIter, endIter );
	}

	/**
	 * \brief
	 * Make range of move begin to end iterators.
	 *
	 * \return full range over container values
	 */
	auto range ( ) && {
		auto endIter = std::move ( * this ).end ( );
		auto beginIter = std::move ( * this ).begin ( );
		return ext::iterator_range < decltype ( endIter ) > ( beginIter, endIter );
	}

	/**
	 * \brief
	 * Make range of elements with key equal to the @p key.
	 *
	 * \tparam K the key used in the query
	 *
	 * \param key the value used in the query
	 *
	 * \return selected range of elements
	 */
	template < class K >
	auto equal_range ( K && key ) const & {
		auto res = std::map < T, R, Cmp, Alloc >::equal_range ( std::forward < K > ( key ) );
		return ext::iterator_range < decltype ( res.first ) > ( res.first, res.second );
	}

	/**
	 * \brief
	 * Make range of elements with key equal to the @p key.
	 *
	 * \tparam K the key used in the query
	 *
	 * \param key the value used in the query
	 *
	 * \return selected range of elements
	 */
	template < class K >
	auto equal_range ( K && key ) & {
		auto res = std::map < T, R, Cmp, Alloc >::equal_range ( std::forward < K > ( key ) );
		return ext::iterator_range < decltype ( res.first ) > ( res.first, res.second );
	}

	/**
	 * \brief
	 * Make range of elements with key equal to the @p key.
	 *
	 * \tparam K the key used in the query
	 *
	 * \param key the value used in the query
	 *
	 * \return selected range of elements
	 */
	template < class K >
	auto equal_range ( K && key ) && {
		auto res = std::map < T, R, Cmp, Alloc >::equal_range ( std::forward < K > ( key ) );
		return ext::make_iterator_range ( make_map_move_iterator < T, R > ( res.first ), make_map_move_iterator < T, R > ( res.second ) );
	}
};

/**
 * \brief
 * Operator to print the map to the output stream.
 *
 * \param out the output stream
 * \param map the map to print
 *
 * \tparam T the type of keys inside the map
 * \tparam R the type of values inside the map
 * \tparam Ts ... remaining unimportant template parameters of the map
 *
 * \return the output stream from the \p out
 */
template< class T, class R, class ... Ts >
std::ostream& operator<<(std::ostream& out, const ext::map<T, R, Ts ... >& map) {
	out << "{";

	bool first = true;
	for(const std::pair<const T, R>& item : map) {
		if(!first) out << ", ";
		first = false;
		out << "(" << item.first << ", " << item.second << ")";
	}

	out << "}";
	return out;
}

/**
 * \brief
 * Specialisation of the compare structure implementing the three-way comparison.
 *
 * \tparam T the type of keys inside the map
 * \tparam R the type of values inside the map
 * \tparam Ts ... remaining unimportant template parameters of the map
 */
template < class T, class R, class ... Ts >
struct compare < ext::map < T, R, Ts ... > > {

	/**
	 * \brief
	 * Implementation of the three-way comparison.
	 *
	 * \param first the left operand of the comparison
	 * \param second the right operand of the comparison
	 *
	 * \return negative value of left < right, positive value if left > right, zero if left == right
	 */
	int operator ( ) ( const ext::map < T, R, Ts ... > & first, const ext::map < T, R, Ts ... > & second) const {
		if(first.size() < second.size()) return -1;
		if(first.size() > second.size()) return 1;

		static compare < typename std::decay < T >::type > compT;
		static compare < typename std::decay < R >::type > compR;
		for(auto iterF = first.begin(), iterS = second.begin(); iterF != first.end(); ++iterF, ++iterS) {
			int res = compT(iterF->first, iterS->first);
			if(res == 0) res = compR(iterF->second, iterS->second);
			if(res != 0) return res;
		}
		return 0;
	}
};

/**
 * \brief
 * Overload of to_string function.
 *
 * \param value the map to be converted to string
 *
 * \tparam T the type of values inside the map
 * \tparam Ts ... remaining unimportant template parameters of the map
 *
 * \return string representation
 */
template < class T, class R, class ... Ts >
std::string to_string ( const ext::map < T, R, Ts ... > & value ) {
	std::stringstream ss;
	ss << value;
	return ss.str();
}

} /* namespace ext */

#endif /* __MAP_HPP_ */