goldsborough · December 20, 2015 23:08
diff --git a/utility.cpp b/utility.cpp
 #ifndef UTILITY_HPP
 #define UTILITY_HPP

 #include "global.hpp"

 #include <algorithm>
 #include <chrono>
 #include <cmath>
 #include <ctime>
 #include <iterator>
 #include <numeric>
 #include <random>
 #include <type_traits>
 #include <utility>

 namespace Utility
 {

 template<typename Accumulator, typename Divisor, std::size_t N>
 class Average
 {
 public:
 	
 	template<typename... Args>
 	constexpr auto operator()(Args&&... args)
 	{
 		return _average(Accumulator(), std::forward<Args>(args)...);
 	}
 	
 private:
 	
 	constexpr auto _average(Accumulator sum)
 	{
 		return sum / static_cast<Divisor>(N);
 	}
 	
 	template<typename Head, typename... Tail>
 	constexpr auto _average(Accumulator sum, Head&& head, Tail&&... tail)
 	{
 		sum = sum + std::forward<Head>(head);
 		
 		return _average(sum, std::forward<Tail>(tail)...);
 	}
 };

 template<typename Accumulator = double, typename Divisor = double, typename... Args>
 constexpr auto average(Args&&... args)
 {
 	return Average<Accumulator, Divisor, sizeof...(args)>()(
 		std::forward<Args>(args)...
 	);
 }

 template<typename T, typename = void>
 struct is_iterator
 {
   static constexpr bool value = false;
 };

 template<typename T>
 struct is_iterator<T,
 	std::enable_if_t<
 		!std::is_same<
 			typename std::iterator_traits<T>::value_type,
 			void
 		>::value
 	>
 >
 {
   static constexpr bool value = true;
 };

 template<typename Iterator>
 std::enable_if_t<is_iterator<Iterator>::value, double>
 average(Iterator begin, Iterator end)
 {
 	auto value = std::accumulate(begin, end, 0.0);
 	
 	return value / std::distance(begin, end);
 }

 template<typename Sequence, typename T = double>
 auto average(const Sequence& sequence)
 {
 	using std::begin;
 	using std::end;
 	
 	auto first = begin(sequence);
 	auto last = end(sequence);

 	auto value = std::accumulate(first, last, T{});
 	
 	return value / std::distance(first, last);
 }

 template<
 	typename Iterator,
 	typename Predicate,
 	typename Greater
 >
 Iterator lower_bound_if(Iterator begin,
 						Iterator end,
 						Predicate predicate,
 						Greater greater)
 {
 	if (begin == end) return end;
 	
 	auto pivot = begin;
 	
 	std::advance(pivot, std::distance(begin, end)/2);
 	
 	if (predicate(*pivot) || greater(*pivot))
 	{
 		return lower_bound_if(begin, pivot, predicate, greater);
 	}
 	
 	else return lower_bound_if(++pivot, end, predicate, greater);
 }

 template<
 	typename Iterator,
 	typename Predicate,
 	typename Greater
 >
 Iterator upper_bound_if(Iterator begin,
 						Iterator end,
 						Predicate predicate,
 						Greater greater)
 {
 	if (begin == end) return end;
 	
 	auto pivot = begin;
 	
 	std::advance(pivot, std::distance(begin, end)/2);
 	
 	if (! predicate(*pivot) && greater(*pivot))
 	{
 		return upper_bound_if(begin, pivot, predicate, greater);
 	}
 	
 	else return upper_bound_if(++pivot, end, predicate, greater);
 }

 template<
 	typename Iterator,
 	typename Predicate,
 	typename Greater
 >
 std::pair<Iterator, Iterator> equal_range_if(Iterator begin,
 											 Iterator end,
 											 Predicate predicate,
 											 Greater greater)
 {
 	return {
 		lower_bound_if(begin, end, predicate, greater),
 		upper_bound_if(begin, end, predicate, greater)
 	};
 }
 	
 template<
 	typename Source,
 	typename Destination,
 	typename SourceIterator
 >
 auto translate_iterator(Source&& source,
 						SourceIterator source_iterator,
 						const Destination& destination)
 {
 	using std::begin;
 	
 	auto destination_iterator = begin(destination);
 	
 	auto distance = std::distance<SourceIterator>(begin(source),
 												  source_iterator);
 	
 	std::advance(destination_iterator, distance);
 	
 	return destination_iterator;
 }

 template<
 	typename Iterator,
 	typename Projection,
 	typename T,
 	typename U
 >
 Iterator find_similar(Iterator begin,
 					  Iterator end,
 					  Projection project,
 					  const T& target,
 					  const U& tolerance)
 {
 	for ( ; begin != end; ++begin)
 	{
 		if (std::abs(project(*begin) - target) < tolerance)
 		{
 			return begin;
 		}
 	}
 	
 	return end;
 }
 	
 template<typename Iterator, typename T, typename U>
 Iterator find_similar(Iterator begin,
 					  Iterator end,
 					  const T& target,
 					  const U& tolerance)
 {
 	for ( ; begin != end; ++begin)
 	{
 		if (std::abs(*begin - target) < tolerance)
 		{
 			return begin;
 		}
 	}
 	
 	return end;
 }

 template<typename Iterator, typename Source>
 auto index(Source&& source, Iterator iterator)
 {
 	using std::begin;

 	return std::distance(begin(source), iterator);
 }

 template<typename Iterator>
 Array median_filter(Iterator begin, Iterator end, std::size_t window)
 {
    Array filtered;
    
    filtered.reserve(std::distance(begin, end));
    
    // Start at middle so that
    // we overlap by one half left
    // and right and thus retain
    // the size of the array
    size_t middle = window / 2;
 	
    // first is the start() of the current
    // median filter window and i is
    // and iterator to check for positioning
    auto i = begin;
    
    // After this point the first iterator
    // start()s incrementing
    auto first_mid = begin + middle;
    
    // The end of the current median filter window
    auto last = first_mid + 1;
    
    // After this point the last iterator
    // stops incrementing
    auto last_mid = end - middle;
    
    // For odd windows the last iterator
    // stops incrementing earlier, because
    // for even windows the iterator start()s
    // at the right of the two middle values
    // and thus needs an extra incrementing
    if (window % 2) --last_mid;
    
    for( ; i != end; ++i)
    {
        // Current window
        Array temp(begin, last);
        
        std::sort(temp.begin(), temp.end());
        
        // This middle value cannot be precomputed
        // because the window size varies at the
        // begininning and end
        size_t middle = temp.size() / 2;
        
        double median = temp[middle];
 		
        if (temp.size() % 2 == 0)
        {
            median = (median + temp[middle - 1]) / 2;
        }
        
        filtered.emplace_back(median);
        
        // Start incrmenting first after first_mid
        if (i >= first_mid) ++begin;
        
        // Stop incrementing last after last_mid
        if (i < last_mid) ++last;
    }
    
    return filtered;
 }

 template<typename List, typename ListIterator>
 List extract_list(List& source, ListIterator first, ListIterator last)
 {
 	using std::begin;

 	List extracted;
 	
 	extracted.splice(begin(extracted), source, first, last);
 	
 	return extracted;
 }

 template<typename T>
 std::enable_if_t<std::is_integral<T>::value, T>
 random(T lower_bound, T upper_bound)
 {
 	static std::random_device seed;
 	
 	static std::mt19937_64 generator(seed());
 	
 	std::uniform_int_distribution<T> distribution(lower_bound, upper_bound);
 	
 	return distribution(generator);
 }

 template<typename T>
 std::enable_if_t<std::is_floating_point<T>::value, T>
 random(T lower_bound, T upper_bound)
 {
 	static std::random_device seed;
 	
 	static std::mt19937_64 generator(seed());
 	
 	std::uniform_real_distribution<T> distribution(lower_bound, upper_bound);
 	
 	return distribution(generator);
 }

 template<typename T>
 T random(T upper_bound)
 {
 	return random<T>(0, upper_bound);
 }

 template<typename ForwardIterator>
 std::enable_if_t<is_iterator<ForwardIterator>::value, ForwardIterator>
 random_iterator(ForwardIterator begin, ForwardIterator end)
 {
 	// upper_bound is inclusive, but don't want to include the end
 	auto offset = random(std::distance(begin, end) - 1);
 	
 	std::advance(begin, offset);
 	
 	return begin;
 }

 template<typename Iterator, typename Value>
 struct Position
 {
 	Position(const Iterator& iterator_, const Value& value_)
 	: iterator(iterator_)
 	, value(value_)
 	{ }

 	Iterator iterator;
 	
 	Value value;
 };

 template<typename Iterator, typename Projection, typename Compare>
 auto best(Iterator begin,
 		  Iterator end,
 		  Projection projection,
 		  Compare compare)
 {
 	using Output = decltype(projection(*begin));
 	
 	auto best_iterator = begin;

 	auto best_value = projection(*begin);
 	
 	for (++begin; begin != end; ++begin)
 	{
 		auto&& value = projection(*begin);
 		
 		if (compare(std::forward<Output>(value), best_value))
 		{
 			best_value = std::forward<Output>(value);
 			
 			best_iterator = begin;
 		}
 	}
 	
 	return Position<Iterator, Output>{best_iterator, best_value};
 }

 template<typename Iterator, typename Projection>
 auto maximum(Iterator begin, Iterator end, Projection projection)
 {
 	using Output = decltype(projection(*begin));

 	return best(begin, end, projection, std::greater<Output>());
 }

 template<typename Iterator, typename Projection>
 auto minimum(Iterator begin, Iterator end, Projection projection)
 {
 	using Output = decltype(projection(*begin));

 	return best(begin, end, projection, std::less<Output>());
 }

 template<typename T, typename U>
 auto truncate(const T& value, const U& factor)
 {
 	return value - (value % factor);
 }

 template<typename Container>
 auto front(Container&& container)
 {
 	using std::begin;
 	
 	return *begin(std::forward<Container>(container));
 }

 template<typename Container>
 auto back(Container&& container)
 {
 	using std::begin;
 	using std::end;
 	using std::prev;
 	
 	assert(begin(container) != end(container));
 	
 	return *prev(end(std::forward<Container>(container)));
 }

 template<typename SortedContainer, typename Iterator, typename Operation>
 auto modify(SortedContainer& container, Iterator iterator, Operation operation)
 {
 	assert(iterator != container.end());

 	auto modified = std::move(*iterator);
 	
 	operation(modified);
 	
 	iterator = container.erase(iterator);
 	
 	auto i = container.find(modified);
 	
 	if(i != container.end())
 	{
 	
 	}
 	
 	iterator = container.insert(iterator, modified);
 	
 	assert(*iterator == modified);
 	
 	return iterator;
 }

 template<typename SortedContainer, typename Operation>
 auto modify(SortedContainer& container, Operation operation)
 {
 	using std::begin;
 	using std::end;

 	for (auto i = begin(container), stop = end(container); i != stop; ++i)
 	{
 		i = modify(container, i, operation);
 	}
 }

 class Timer
 {
 public:

 	using clock_t = std::chrono::high_resolution_clock;
 	
 	Timer(bool deferred = false)
 	: _ended(true)
 	{
 		if (! deferred) start();
 	}
 	
 	~Timer()
 	{
 		if (! _ended) end();
 	}
 	
 	void start()
 	{
 		assert(_ended);
 	
 		_start_time = clock_t::now();
 		
 		_ended = false;
 	}
 	
 	template<typename Duration = std::chrono::microseconds>
 	void end(const std::string& message = std::string())
 	{
 		assert(! _ended);

 		auto elapsed = clock_t::now() - _start_time;
 		
 		auto cast = std::chrono::duration_cast<Duration>(elapsed);
 		
 		if (! message.empty()) std::clog << message << ": ";
 		
 		std::clog << cast.count() << "\n";
 		
 		_ended = true;
 	}
 	
 private:

 	clock_t::time_point _start_time;
 	
 	bool _ended;
 };

 }

 #endif /* UTILITY_HPP */
	#ifndef UTILITY_HPP
	#define UTILITY_HPP

	#include "global.hpp"

	#include <algorithm>
	#include <chrono>
	#include <cmath>
	#include <ctime>
	#include <iterator>
	#include <numeric>
	#include <random>
	#include <type_traits>
	#include <utility>

	namespace Utility
	{

	template<typename Accumulator, typename Divisor, std::size_t N>
	class Average
	{
	public:

	template<typename... Args>
	constexpr auto operator()(Args&&... args)
	{
	return _average(Accumulator(), std::forward<Args>(args)...);
	}

	private:

	constexpr auto _average(Accumulator sum)
	{
	return sum / static_cast<Divisor>(N);
	}

	template<typename Head, typename... Tail>
	constexpr auto _average(Accumulator sum, Head&& head, Tail&&... tail)
	{
	sum = sum + std::forward<Head>(head);

	return _average(sum, std::forward<Tail>(tail)...);
	}
	};

	template<typename Accumulator = double, typename Divisor = double, typename... Args>
	constexpr auto average(Args&&... args)
	{
	return Average<Accumulator, Divisor, sizeof...(args)>()(
	std::forward<Args>(args)...
	);
	}

	template<typename T, typename = void>
	struct is_iterator
	{
	static constexpr bool value = false;
	};

	template<typename T>
	struct is_iterator<T,
	std::enable_if_t<
	!std::is_same<
	typename std::iterator_traits<T>::value_type,
	void
	>::value
	>
	>
	{
	static constexpr bool value = true;
	};

	template<typename Iterator>
	std::enable_if_t<is_iterator<Iterator>::value, double>
	average(Iterator begin, Iterator end)
	{
	auto value = std::accumulate(begin, end, 0.0);

	return value / std::distance(begin, end);
	}

	template<typename Sequence, typename T = double>
	auto average(const Sequence& sequence)
	{
	using std::begin;
	using std::end;

	auto first = begin(sequence);
	auto last = end(sequence);

	auto value = std::accumulate(first, last, T{});

	return value / std::distance(first, last);
	}

	template<
	typename Iterator,
	typename Predicate,
	typename Greater
	>
	Iterator lower_bound_if(Iterator begin,
	Iterator end,
	Predicate predicate,
	Greater greater)
	{
	if (begin == end) return end;

	auto pivot = begin;

	std::advance(pivot, std::distance(begin, end)/2);

	if (predicate(pivot) \|\| greater(pivot))
	{
	return lower_bound_if(begin, pivot, predicate, greater);
	}

	else return lower_bound_if(++pivot, end, predicate, greater);
	}

	template<
	typename Iterator,
	typename Predicate,
	typename Greater
	>
	Iterator upper_bound_if(Iterator begin,
	Iterator end,
	Predicate predicate,
	Greater greater)
	{
	if (begin == end) return end;

	auto pivot = begin;

	std::advance(pivot, std::distance(begin, end)/2);

	if (! predicate(pivot) && greater(pivot))
	{
	return upper_bound_if(begin, pivot, predicate, greater);
	}

	else return upper_bound_if(++pivot, end, predicate, greater);
	}

	template<
	typename Iterator,
	typename Predicate,
	typename Greater
	>
	std::pair<Iterator, Iterator> equal_range_if(Iterator begin,
	Iterator end,
	Predicate predicate,
	Greater greater)
	{
	return {
	lower_bound_if(begin, end, predicate, greater),
	upper_bound_if(begin, end, predicate, greater)
	};
	}

	template<
	typename Source,
	typename Destination,
	typename SourceIterator
	>
	auto translate_iterator(Source&& source,
	SourceIterator source_iterator,
	const Destination& destination)
	{
	using std::begin;

	auto destination_iterator = begin(destination);

	auto distance = std::distance<SourceIterator>(begin(source),
	source_iterator);

	std::advance(destination_iterator, distance);

	return destination_iterator;
	}

	template<
	typename Iterator,
	typename Projection,
	typename T,
	typename U
	>
	Iterator find_similar(Iterator begin,
	Iterator end,
	Projection project,
	const T& target,
	const U& tolerance)
	{
	for ( ; begin != end; ++begin)
	{
	if (std::abs(project(*begin) - target) < tolerance)
	{
	return begin;
	}
	}

	return end;
	}

	template<typename Iterator, typename T, typename U>
	Iterator find_similar(Iterator begin,
	Iterator end,
	const T& target,
	const U& tolerance)
	{
	for ( ; begin != end; ++begin)
	{
	if (std::abs(*begin - target) < tolerance)
	{
	return begin;
	}
	}

	return end;
	}

	template<typename Iterator, typename Source>
	auto index(Source&& source, Iterator iterator)
	{
	using std::begin;

	return std::distance(begin(source), iterator);
	}

	template<typename Iterator>
	Array median_filter(Iterator begin, Iterator end, std::size_t window)
	{
	Array filtered;

	filtered.reserve(std::distance(begin, end));

	// Start at middle so that
	// we overlap by one half left
	// and right and thus retain
	// the size of the array
	size_t middle = window / 2;

	// first is the start() of the current
	// median filter window and i is
	// and iterator to check for positioning
	auto i = begin;

	// After this point the first iterator
	// start()s incrementing
	auto first_mid = begin + middle;

	// The end of the current median filter window
	auto last = first_mid + 1;

	// After this point the last iterator
	// stops incrementing
	auto last_mid = end - middle;

	// For odd windows the last iterator
	// stops incrementing earlier, because
	// for even windows the iterator start()s
	// at the right of the two middle values
	// and thus needs an extra incrementing
	if (window % 2) --last_mid;

	for( ; i != end; ++i)
	{
	// Current window
	Array temp(begin, last);

	std::sort(temp.begin(), temp.end());

	// This middle value cannot be precomputed
	// because the window size varies at the
	// begininning and end
	size_t middle = temp.size() / 2;

	double median = temp[middle];

	if (temp.size() % 2 == 0)
	{
	median = (median + temp[middle - 1]) / 2;
	}

	filtered.emplace_back(median);

	// Start incrmenting first after first_mid
	if (i >= first_mid) ++begin;

	// Stop incrementing last after last_mid
	if (i < last_mid) ++last;
	}

	return filtered;
	}

	template<typename List, typename ListIterator>
	List extract_list(List& source, ListIterator first, ListIterator last)
	{
	using std::begin;

	List extracted;

	extracted.splice(begin(extracted), source, first, last);

	return extracted;
	}

	template<typename T>
	std::enable_if_t<std::is_integral<T>::value, T>
	random(T lower_bound, T upper_bound)
	{
	static std::random_device seed;

	static std::mt19937_64 generator(seed());

	std::uniform_int_distribution<T> distribution(lower_bound, upper_bound);

	return distribution(generator);
	}

	template<typename T>
	std::enable_if_t<std::is_floating_point<T>::value, T>
	random(T lower_bound, T upper_bound)
	{
	static std::random_device seed;

	static std::mt19937_64 generator(seed());

	std::uniform_real_distribution<T> distribution(lower_bound, upper_bound);

	return distribution(generator);
	}

	template<typename T>
	T random(T upper_bound)
	{
	return random<T>(0, upper_bound);
	}

	template<typename ForwardIterator>
	std::enable_if_t<is_iterator<ForwardIterator>::value, ForwardIterator>
	random_iterator(ForwardIterator begin, ForwardIterator end)
	{
	// upper_bound is inclusive, but don't want to include the end
	auto offset = random(std::distance(begin, end) - 1);

	std::advance(begin, offset);

	return begin;
	}

	template<typename Iterator, typename Value>
	struct Position
	{
	Position(const Iterator& iterator_, const Value& value_)
	: iterator(iterator_)
	, value(value_)
	{ }

	Iterator iterator;

	Value value;
	};

	template<typename Iterator, typename Projection, typename Compare>
	auto best(Iterator begin,
	Iterator end,
	Projection projection,
	Compare compare)
	{
	using Output = decltype(projection(*begin));

	auto best_iterator = begin;

	auto best_value = projection(*begin);

	for (++begin; begin != end; ++begin)
	{
	auto&& value = projection(*begin);

	if (compare(std::forward<Output>(value), best_value))
	{
	best_value = std::forward<Output>(value);

	best_iterator = begin;
	}
	}

	return Position<Iterator, Output>{best_iterator, best_value};
	}

	template<typename Iterator, typename Projection>
	auto maximum(Iterator begin, Iterator end, Projection projection)
	{
	using Output = decltype(projection(*begin));

	return best(begin, end, projection, std::greater<Output>());
	}

	template<typename Iterator, typename Projection>
	auto minimum(Iterator begin, Iterator end, Projection projection)
	{
	using Output = decltype(projection(*begin));

	return best(begin, end, projection, std::less<Output>());
	}

	template<typename T, typename U>
	auto truncate(const T& value, const U& factor)
	{
	return value - (value % factor);
	}

	template<typename Container>
	auto front(Container&& container)
	{
	using std::begin;

	return *begin(std::forward<Container>(container));
	}

	template<typename Container>
	auto back(Container&& container)
	{
	using std::begin;
	using std::end;
	using std::prev;

	assert(begin(container) != end(container));

	return *prev(end(std::forward<Container>(container)));
	}

	template<typename SortedContainer, typename Iterator, typename Operation>
	auto modify(SortedContainer& container, Iterator iterator, Operation operation)
	{
	assert(iterator != container.end());

	auto modified = std::move(*iterator);

	operation(modified);

	iterator = container.erase(iterator);

	auto i = container.find(modified);

	if(i != container.end())
	{

	}

	iterator = container.insert(iterator, modified);

	assert(*iterator == modified);

	return iterator;
	}

	template<typename SortedContainer, typename Operation>
	auto modify(SortedContainer& container, Operation operation)
	{
	using std::begin;
	using std::end;

	for (auto i = begin(container), stop = end(container); i != stop; ++i)
	{
	i = modify(container, i, operation);
	}
	}

	class Timer
	{
	public:

	using clock_t = std::chrono::high_resolution_clock;

	Timer(bool deferred = false)
	: _ended(true)
	{
	if (! deferred) start();
	}

	~Timer()
	{
	if (! _ended) end();
	}

	void start()
	{
	assert(_ended);

	_start_time = clock_t::now();

	_ended = false;
	}

	template<typename Duration = std::chrono::microseconds>
	void end(const std::string& message = std::string())
	{
	assert(! _ended);

	auto elapsed = clock_t::now() - _start_time;

	auto cast = std::chrono::duration_cast<Duration>(elapsed);

	if (! message.empty()) std::clog << message << ": ";

	std::clog << cast.count() << "\n";

	_ended = true;
	}

	private:

	clock_t::time_point _start_time;

	bool _ended;
	};

	}

	#endif /* UTILITY_HPP */