
#ifndef UTIL_RANGE_ADD_HPP_
#define UTIL_RANGE_ADD_HPP_

#include <algorithm>

namespace utility {

template <typename Container_>
void range_add (Container_& a_container,
		const typename Container_::value_type& a_from,
		const typename Container_::value_type& a_to)
{
	if (a_to < a_from)
	{
		return range_add(a_container, a_to, a_from);
	}
	else if (a_to == a_from)
	{
		return ;
	}

	typename Container_::iterator left = std::lower_bound(
			a_container. begin(), a_container. end(), a_from);
	if (left == a_container. end())
	{
		a_container. insert(a_container. end(), a_from);
		a_container. insert(a_container. end(), a_to);
		return ;
	}

	typename Container_::iterator right = std::upper_bound(
			a_container. begin(), a_container. end(), a_to);
	if (right == a_container. begin())
	{
		a_container. insert(a_container. begin(), a_to);
		a_container. insert(a_container. begin(), a_from);
		return ;
	}

	if (left == right)
	{
		if ((left - a_container. begin()) & 1)
		{
			// no operation
		}
		else
		{
			left = a_container. insert(left, a_to);
			a_container. insert(left, a_from);
		}

		return ;
	}

	if ((left - a_container. begin()) & 1)
	{
		if ((right - a_container. begin()) & 1)
		{
			// no operation
		}
		else
		{
			*left = a_to;
			std::advance(left, 1);
		}
	}
	else
	{
		if ((right - a_container. begin()) & 1)
		{
			std::advance(right, -1);
			*right = a_from;
		}
		else
		{
			*left = a_from;
			std::advance(left, 1);
			*left = a_to;
			std::advance(left, 1);
		}
	}

	a_container. erase(left, right);
}

} // namespace utility

#endif /* UTIL_RANGE_ADD_HPP_ */
