#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(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
   ==============================*/

  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