#include <PmergeMe.hpp>

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sys/time.h>
#include <utility>

PmergeMe::PmergeMe() {}

PmergeMe::PmergeMe(const PmergeMe& other) {
	(void)other; // yeag...
}

static std::vector<size_t> generateJacobsthal(const size_t n) {
	std::vector<size_t> jacobsthal;

	jacobsthal.push_back(0);
	jacobsthal.push_back(1);
	while (jacobsthal.back() < n) {
		const size_t next = jacobsthal[jacobsthal.size() - 1] + 2 * jacobsthal[jacobsthal.size() - 2];
		jacobsthal.push_back(next);
	}

	return jacobsthal;
}

template <typename Container> Container fordJohnsonSortRange(const Container& input) {
	typedef typename Container::value_type ValueType;
	typedef std::pair<ValueType, ValueType> PairType;

	const size_t size = input.size();
	if (size <= 1)
		return input;

	std::vector<PairType> pairs;
	for (size_t i = 0; i + 1 < size; i += 2) {
		if (input[i] <= input[i + 1]) {
			pairs.push_back(std::make_pair(input[i], input[i + 1]));
		} else {
			pairs.push_back(std::make_pair(input[i + 1], input[i]));
		}
	}

	Container largerElements;
	for (size_t i = 0; i < pairs.size(); ++i)
		largerElements.push_back(pairs[i].second);

	largerElements = fordJohnsonSortRange(largerElements);

	if (pairs.empty())
		return largerElements;

	const typename Container::iterator firstUpper = std::upper_bound(largerElements.begin(), largerElements.end(), pairs[0].second);
	const typename Container::iterator firstPosition = std::upper_bound(largerElements.begin(), firstUpper, pairs[0].first);
	largerElements.insert(firstPosition, pairs[0].first);

	const std::vector<size_t> jacobsthal = generateJacobsthal(pairs.size());
	for (size_t i = 3; i < jacobsthal.size() && jacobsthal[i - 1] < pairs.size(); ++i) {
		const size_t start = jacobsthal[i - 1];
		const size_t end = std::min(jacobsthal[i] - 1, pairs.size() - 1);

		for (size_t idx = end; idx >= start; --idx) {
			const typename Container::iterator upper = std::upper_bound(largerElements.begin(), largerElements.end(), pairs[idx].second);
			const typename Container::iterator position = std::upper_bound(largerElements.begin(), upper, pairs[idx].first);
			largerElements.insert(position, pairs[idx].first);
		}
	}

	if (size % 2 == 1) {
		const typename Container::iterator position = std::upper_bound(largerElements.begin(), largerElements.end(), input[size - 1]);
		largerElements.insert(position, input[size - 1]);
	}

	return largerElements;
}
template <typename Container> void fordJohnsonSort(Container& container) { container = fordJohnsonSortRange(container); }

template std::vector<int> fordJohnsonSortRange<std::vector<int> >(const std::vector<int>&);
template std::deque<int> fordJohnsonSortRange<std::deque<int> >(const std::deque<int>&);

template void fordJohnsonSort<std::vector<int> >(std::vector<int>&);
template void fordJohnsonSort<std::deque<int> >(std::deque<int>&);

static double elapsedMicroseconds(const timespec& start, const timespec& end) { return (static_cast<double>(end.tv_sec - start.tv_sec) * 1000000 + static_cast<double>(end.tv_nsec - start.tv_nsec)) / 1000; }

static std::ostream& operator<<(std::ostream& stream, const std::vector<int>& vector) {
	for (size_t i = 0; i < vector.size(); ++i) {
		stream << vector[i];
		if (i + 1 < vector.size())
			stream << " ";
	}

	return stream; 
}

void PmergeMe::sort(std::vector<int>& vector, std::deque<int>& deque) {
	{
		std::cout << "Before: " << vector << std::endl;
		timespec start, end;

		clock_gettime(CLOCK_MONOTONIC, &start);
		fordJohnsonSort(vector);
		clock_gettime(CLOCK_MONOTONIC, &end);

		std::cout << "After: " << vector << std::endl;
		std::cout << "Time to process a range of " << vector.size() << " elements with std::vector : " << elapsedMicroseconds(start, end) << " us" << std::endl;
	}

	{
		timespec start, end;

		clock_gettime(CLOCK_MONOTONIC, &start);
		fordJohnsonSort(deque);
		clock_gettime(CLOCK_MONOTONIC, &end);

		std::cout << "Time to process a range of " << deque.size() << " elements with std::deque : " << elapsedMicroseconds(start, end) << " us" << std::endl;
	}
}

PmergeMe& PmergeMe::operator=(const PmergeMe& other) {
	if (this == &other)
		return *this;

	return *this;
}

PmergeMe::~PmergeMe() {}