#ifndef SORT_ALGORITHM_CPP
#define SORT_ALGORITHM_CPP

#include <iostream>
#include <cstdint>
#include <utility>
#include "sort_algorithm.hpp"


//Class row

template <typename T>
row<T>::row():p(nullptr),n(0) {}

template<typename T>
row<T>::row(T* newP, uint32_t newN):p(newP),n(newN) {}

template<typename T>
row<T>::~row() {
	delete[] p;
}

template<typename T>
row<T>::row(const row<T>& object)::p(nullptr),n(object.n) {
	p=new T[n];
	for(uint32_t i=0;i <n;++i) {
		p[i]=object.p[i];
		}
	}

template<typename T>
row<T>& row<T>::operator=(const row<T>& other) {
	if(this==&other) {
		return this*;
	}
	delete[] p;
	n=other.n;
	if(n>0) {
		p=new T[n];
		for(uint32_t i=0; i<n;++i){
			p[i]=other.p[i];
		}
	}
	else {
		p=nullptr;
	}
	return *this;
}

template<typename T>
T& row<T>::operator[](uint32_t index){
	if(index>=n) {
		std::cout <<"SFALMA\n";
		exit(0);
	}
	return p[index];
}

template<typename T>
int row<T>::size() {
	return n;
}

template <typename U>
std::ostream& operator<<(std::ostream& outputStream, row<U>& r) {
		outputStream<<"[";
		for (uint32_t i=0; i<r.size();++i){
			outputStream<<r[i];
			if(i<r.size() - 1) {
				outputStream<<"\t";
		}
	}
	outputStream<<"]";
	return outputStream;
}

//Bubble Sort 
template<typename T>
void bubble_sort(row<T>& s){
	uint32_t n=s.size();
	for(uint32_t i=0;i<n;++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];
		uint32_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 i=0;i<n2;++i) {
		R[i]=s[mid+1 + i];
	}
	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(j<n1){
		s[++k]=L[++i];
	}
	while(j<n2) {
		s[k++] = R[j++];
	}

	delete[] L;
	delete[] R;
}

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

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

template<typename T>
void merge_sort(row<T>& s) {
	if(s.size()>1) {
		merge_sort_recrusive(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 - 1l
	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_recrusive(row<T>& s, int low,int high) {
	if (low<high) {
		int pi=partition(s, low, high);
		quick_sort_recrusive(s, low, pi-1);
		quick_sort_recrusive(s, pi+1, high);
	}
}

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

/*=============================
	ENUMERATON/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