RangeVector.impl.h

/******************************************************************************
 * File: RangeVector.impl.h
 * Date: 16.5.2018
 *****************************************************************************/

#include "Grinder.h"
#include "RangeVector.h"

template<typename ValType>
void RangeVector<ValType>::add(const range_type& range)
{
	// Find all ranges that overlap with the new one
	auto overlappingRanges = getOverlappingRanges(range);

	if (!overlappingRanges.empty())	// Some ranges overlap, so merge them
	{
		// Check if the new range is already completely contained
		for (const auto& it : overlappingRanges)
		{
			if (it->contains(range.first()) && it->contains(range.second()))
				return;
		}

		auto leftRange = *overlappingRanges.front();
		auto rightRange = *overlappingRanges.back();

		// Remove the existing ranges which overlap with the new range
		_ranges.erase(overlappingRanges.front(), std::next(overlappingRanges.back()));

		// Emplace the merged range
		_ranges.emplace(std::min(leftRange.first(), range.first()), std::max(rightRange.second(), range.second()));
	}
	else
		_ranges.emplace(range);

	// Merge adjacent ranges
	mergeAdjacent();
}

template<typename ValType>
void RangeVector<ValType>::add(const RangeVector<value_type>& other)
{
	for (const auto& range : other._ranges)
		add(range);
}

template<typename ValType>
void RangeVector<ValType>::remove(const range_type& range)
{
	// Find all ranges that overlap with the given one
	auto overlappingRanges = getOverlappingRanges(range);

	if (!overlappingRanges.empty())	// Some ranges overlap, so remove them
	{
		auto leftRange = *overlappingRanges.front();
		auto rightRange = *overlappingRanges.back();

		// Remove the existing ranges which overlap with the new range
		_ranges.erase(overlappingRanges.front(), std::next(overlappingRanges.back()));

		// Add cropped ranges if necessary
		if (leftRange.first() < range.first())
		{
			auto first = range.first();
			_ranges.emplace(leftRange.first(), --first);
		}

		if (rightRange.second() > range.second())
		{
			auto second = range.second();
			_ranges.emplace(++second, rightRange.second());
		}

		// Merge adjacent ranges
		mergeAdjacent();
	}
}

template<typename ValType>
void RangeVector<ValType>::remove(const RangeVector<value_type>& other)
{
	for (const auto& range : other._ranges)
		remove(range);
}

template<typename ValType>
void RangeVector<ValType>::offsetRanges(value_type offset)
{
	// Create new ranges offset by a certain amount
	std::list<range_type> ranges{_ranges.begin(), _ranges.end()};
	clear();	// Need to recreate the entire ranges set (as set entries can't be modified)

	for (auto& range : ranges)
	{
		range += offset;
		add(range);
	}
}

template<typename ValType>
bool RangeVector<ValType>::contains(value_type value) const
{
	// Perform a binary search on the ranges
	auto first = _ranges.cbegin();
	typename ranges_type::iterator it;
	typename ranges_type::difference_type count, step;

	count = std::distance(_ranges.cbegin(), _ranges.cend());

	while (count > 0)
	{
		it = first;
		step = count / 2;
		std::advance(it, step);

		if (it->contains(value))
			return true;

		if (it->first() < value)
		{
			first = ++it;
			count -= step + 1;
		}
		else
			count = step;
	}

	return false;
}

template<typename ValType>
bool RangeVector<ValType>::adjoins(const range_type& range) const
{
	// Check if one of the ranges overlaps or touches
	for (const auto& overlappingRange : _ranges)
	{
		if (rangesOverlap(range, overlappingRange))
			return true;

		auto overlappingNextSecond = overlappingRange.second();
		auto nextSecond = range.second();

		if (range.first() == ++overlappingNextSecond || ++nextSecond == overlappingRange.first())
			return true;
	}

	return false;
}

template<typename ValType>
auto RangeVector<ValType>::bounds() const
{
	std::pair<value_type, value_type> bounds{std::numeric_limits<value_type>::max(), std::numeric_limits<value_type>::min()};

	if (!_ranges.empty())
	{
		bounds.first = _ranges.cbegin()->first();
		bounds.second = _ranges.crbegin()->second();
	}

	return bounds;
}

template<typename ValType>
QString RangeVector<ValType>::toString() const
{
	QStringList ranges;

	for (const auto& range : _ranges)
		ranges << range.toString();

	return ranges.join(";");
}

template<typename ValType>
void RangeVector<ValType>::fromString(const QString& str)
{
	_ranges.clear();

	for (auto range : str.split(";", QString::SkipEmptyParts))
		_ranges.emplace(range_type{range});
}

template<typename ValType>
bool RangeVector<ValType>::rangesOverlap(const range_type& range, const range_type& overlappingRange) const
{
	return (range.contains(overlappingRange.first()) || range.contains(overlappingRange.second()) || (overlappingRange.contains(range.first()) && overlappingRange.contains(range.second())));
}

template<typename ValType>
auto RangeVector<ValType>::getOverlappingRanges(const range_type& range) const
{
	std::vector<decltype(_ranges.cbegin())> overlappingRanges;

	for (auto it = _ranges.cbegin(); it != _ranges.cend(); ++it)
	{
		if (rangesOverlap(range, *it))
			overlappingRanges.push_back(it);
	}

	return overlappingRanges;
}

template<typename ValType>
void RangeVector<ValType>::mergeAdjacent()
{
	if (_ranges.size() > 1)
	{
		auto it = _ranges.begin();
		auto itNext = std::next(it);

		while (itNext != _ranges.end())
		{
			auto nextValue = it->second();

			if (++nextValue == itNext->first())	// Ranges are adjacent, so merge them
			{
				auto newRange = std::make_pair(it->first(), itNext->second());

				// Remove the to-be-merged ranges
				_ranges.erase(it);
				_ranges.erase(itNext);

				// And emplace the merged one, updating the current iterator to point to the newly added element
				std::tie(it, std::ignore) = _ranges.emplace(newRange);
			}
			else
				++it;	// Just go to the next range

			itNext = std::next(it);
		}
	}
}