#ifndef SORT_ALGORITHMS_HPP
#define SORT_ALGORITHMS_HPP

#include <cstdint>
#include <utility>  // for std::swap

// forward declaration of container
template<typename T>
class row;

/* ===================
	BUBBLE SORT
=================== */

template<typename T>
void bubble_sort(row<T>& s)
{
	uint32_t n = s.size();

	for (uint32_t i=0; i<n-1; ++i)
		for (uint32_t j=0; j<n-i-1; ++j)
			if (s[j] > s[j+1])
				std::swap(s[j], s[j+1]);
}

/* =======================
	SELECTION SORT
=========================== */

template<typename T>
void selection_sort(row<T>& s)
{
	uint32_t n = s.size();

	for (uint32_t i=0; i<n-1;++i) {
		uint32_t min_idx = i;

		for (uint32_t  j=i+1; j<n; ++j)
			if (s[j] < s[min_idx])
				min_idx = j;

		std::swap(s[i], s[min_idx]);
	}
}

/* =========================
	INSERTION SORT
===========================*/
template<typename T>
void insertion_sort(row<T>& s)
{
	uint32_t n = s.size();

	for (uint32_t i=1; i<n; ++i){
		T key = s[i];
		int32_t j=i-1;

		while (j>= 0 && s[j] > key){
			s[j+1] = s[j];
			--j;
		}

		s[j+1] = key;
	}
}

/* ==================
	MERGE SORT
=====================*/

template<typename T>
void merge(row<T>& s, uint32_t left, uint32_t mid, uint32_t right)
{
	uint32_t n1 =mid - left+1;
	uint32_t n2 = right - mid;

	T* L = new T[n1];
	T* R = new T[n2];

	for (uint32_t i=0; i<n1; ++i)
		L[i] = s[left + i];

	for (uint32_t j=0; j<n2; ++j)
		R[j] = s[mid +1 +j];

	uint32_t i=0, j=0, k=left;

	while (i<n1 && j<n2){
		if(L[i] <= R[j])
			s[k++]=L[i++];
		else
			s[k++] = R[j++];
	}

	while(i<n1)
		s[k++]=L[i++];

	while(j<n2)
		s[k++] = R[j++];

	delete[] L;
	delete[] R;
}

template<typename T>
void merge_sort_recursive(row<T>& s, uint32_t left, uint32_t right)
{
	if(left < right) {
		uint32_t mid = left + (right - left)/2;

		merge_sort_recursive(s, left, mid);
		merge_sort_recursive(s, mid+1, right);
		merge(s, left, mid, right);
	}
}

template<typename T>
void merge_sort_recursive(row<T>& s)
{
	if( s.size()>1 )
		merge_sort_recursive(s, 0, s.size() -1);
}


/* ==================
	QUICK SORT
==================== */

template<typename T>
int partition(row<T>& s, int low, int high)
{
	T pivot = s[high];
	int i= low-1;

	for (int j=low; j<high; ++j){
		if(s[j]<pivot){
			++i;
			std::swap(s[i], s[j]);
		}
	}

	std::swap(s[i+1], s[high]);
	return i+1;
}

template<typename T>
void quick_sort_recursive(row<T>& s, int low, int high)
{
	if(low<high) {
		int pi = partition(s, low, high);

		quick_sort_recursive(s, low, pi-1);
		quick_sort_recursive(s, pi+1, high);
	}
}

template<typename T>
void quick_sort(row<T>& s)
{
	if(s.size()>1)
		quick_sort_recursive(s, 0, s.size() -1);
}

/* =================
	ENUMERATION SORT (RANK SORT)
================== */

template<typename T>
void enumeration_sort(row<T>& s)
{
	uint32_t n = s.size();

	if( n<= 1)
		return;

	T* temp = new T[n];

	for(uint32_t i=0; i<n; ++i) {

		uint32_t rank =0;

		for (uint32_t j=0; j<n; ++j){

			if(s[j]<s[i])
				++rank;

			//Handle duplicates safely
			if (s[j] == s[i] && j<i)
				++rank;
		}

		temp[rank] = s[i];
	}

	for (uint32_t i=0; i<n; ++i)
		s[i] = temp[i];

	delete[] temp;
}
#endif