// quicksort.cpp

//
// An elementary implementation of recursive, and also non-recursive (!)
// quicksort.
//

#define NDEBUG  // assertions disabled when NDEBUG defined

#include "cmpt_error.h"
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <ctime>     // time
#include <cstdlib>   // rand, srand

using namespace std;

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
	const int n = v.size();
	if (n == 0) return out << "{}";
	if (n == 1) return out << "{" << v[0] << "}";
	// v has at least 2 elements
	out << "{" << v[0];
	for(int i = 1; i < n; i++) {
		out << "," << v[i];
	}
	return out << "}";
}

// returns a new vector {0, 1, 2, ..., n}
vector<int> make_vec(int n) {
	assert(n >= 0);
	vector<int> result(n);
	for(int i = 0; i < n; i++) result[i] = i;
	return result;
}

vector<int> make_rand_vec(int n) {
	assert(n >= 0);
	vector<int> result = make_vec(n);
	random_shuffle(begin(result), end(result));
	return result;
}

// returns true iff v's elements in v in the range [being, end) are in
// ascending sorted order
bool is_sorted(const vector<int>& v, int begin, int end) {
	for(int i = begin+1; i < end; i++) {  // note that i starts at begin+1
		if (v[i-1] > v[i]) return false;
	}
	return true;
}

// returns true iff v's elements in v are in ascending sorted order
bool is_sorted(const vector<int>& v) {
	return is_sorted(v, 0, v.size());
}

// bool all_less_than(const vector<int>& v, int val, int begin, int end) {
// 	for(int i = begin; i < end; i++) {
// 		if (!(v[i] < val)) return false;
// 	}
// 	return true;
// }

bool all_less_than(const vector<int>& v, int val, int vbegin, int vend) {
	return all_of(begin(v)+vbegin, begin(v)+vend,
				  [val](int n){return n<val;});   // lambda expression
}

// bool all_greater_or_equal_than(const vector<int>& v, int val, int begin, int end) {
// 	for(int i = begin; i < end; i++) {
// 		if (!(v[i] >= val)) return false;
// 	}
// 	return true;
// }

bool all_greater_or_equal_than(const vector<int>& v, int val, int vbegin, int vend) {
	return all_of(begin(v)+vbegin, begin(v)+vend,
				  [val](int n){return n > val;});   // lambda expression
}

bool is_parititioned(const vector<int>& v, int ip, int begin, int end) {
	return all_less_than(v, v[ip], begin, ip)
	    && all_greater_or_equal_than(v, v[ip], ip+1, end);
}

// partitions v's [begin, end) using v[begin] as the pivot; not the most
// efficient implementation of this partition strategy (e.g. one of the swaps
// can essentially be factored out of the loop), but simple and
// straightforward
int partition1(vector<int>& v, int begin, int end) {
    const int pivot = v[begin];
    int ip = begin;  // ip is the location of the pivot
  
    for (int j = begin+1; j < end; j++) {
        if (v[j] < pivot) {
            swap(v[ip+1], v[j]);
            swap(v[ip], v[ip+1]);
            ip++;
        }
    }
    assert(is_parititioned(v, ip, begin, end));
    return ip; 
}

// partitions v's [begin, end) using v[begin] as the pivot; usually does fewer
// swaps than partition1
int partition2(vector<int>& v, int begin, int end) {
    const int pivot = v[begin];
    int ip = begin+1;  // ip refers to first non-partitioned value
  
    for (int j = begin+1; j < end; j++) {
        if (v[j] < pivot) {
            swap(v[ip], v[j]);
            ip++;
        }
    }
    swap(v[begin], v[ip-1]);
    assert(is_parititioned(v, ip, begin, end));
    return ip; 
}

// recursively sorts v[begin,end) using quicksort
void quicksort_rec(vector<int>& v, int begin, int end) {
	if (end - begin > 1) {
		const int p = partition2(v, begin, end);
		quicksort_rec(v, begin, p);
		quicksort_rec(v, p+1, end);
	}
	assert(is_sorted(v, begin, end));
}

void quicksort_rec(vector<int>& v) {
	quicksort_rec(v, 0, v.size());
}

void test_quicksort_rec1() {
	cout << "\ntest_quicksort_rec1 ...\n";
	vector<int> v = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
	random_shuffle(begin(v), end(v));
	cout << " start: " << v << "\n";
	quicksort_rec(v);
	cout << "sorted: " << v << "\n";
}

void test_quicksort_rec2() {
	cout << "\ntest_quicksort_rec2 ... ";
	for(int n = 0; n <= 100; n++) {
		auto v = make_vec(n);
		quicksort_rec(v);
	}

	for(int n = 1000; n <= 50000; n += 1000) {
		auto v = make_vec(n);
		quicksort_rec(v);
	}
	cout << "all test_quicksort_rec2 tests passed\n";
}

////////////////////////////////////////////////////////////////////////////

// a Range refers to a [begin, end) sub-vector within another vector; the type
// of begin and end are size_t (an integer type) to match the type of vector
// indices
struct Range {
	size_t begin;
	size_t end;

	bool is_done() const { return end - begin <= 1; }
}; 

// quicksort without recursion
void quicksort_iter(vector<int>& v) {
	vector<Range> stack;
	stack.push_back(Range{0, v.size()});

	while (!stack.empty()) {
		// get the next range of v to process
		Range rng = stack.back();
		stack.pop_back();

		// if the range isn't done (i.e. has more than 1 element), then
		// partition it
		if (!rng.is_done()) {
			// ip is of size_t to match the type in Range
			const size_t ip = partition2(v, rng.begin, rng.end);
			stack.push_back(Range{rng.begin, ip});
			stack.push_back(Range{ip+1, rng.end});

			// The order in which items are removed from the stack doesn't
			// matter, e.g. if you uncomment the following line the sorting
			// still works.

			// random_shuffle(begin(stack), end(stack));
		}
	} // while
	assert(is_sorted(v, 0, v.size()));
} // quicksort_iter

void test_quicksort_iter1() {
	cout << "\ntest_quicksort_iter1 ...\n";
	auto v = make_rand_vec(15);
	cout << " start: " << v << "\n";
	quicksort_rec(v);
	cout << "sorted: " << v << "\n";
}

void test_quicksort_iter2() {
	cout << "\ntest_quicksort_iter2 ... ";
	for(int n = 0; n <= 100; n++) {
		auto v = make_vec(n);
		quicksort_iter(v);
	}

	for(int n = 1000; n <= 50000; n += 1000) {
		auto v = make_vec(n);
		quicksort_iter(v);
	}
	cout << "all test_quicksort_iter2 tests passed\n";
}

void test_std_sort2() {
	cout << "\ntest_std_sort2 ... ";
	for(int n = 0; n <= 100; n++) {
		auto v = make_vec(n);
		sort(begin(v), end(v));
	}

	for(int n = 1000; n <= 50000; n += 1000) {
		auto v = make_vec(n);
		sort(begin(v), end(v));
	}
	cout << "all test_std_sort2 tests passed\n";
}

int main() {
	srand(unsigned(std::time(0))); // seed random number generator
	// test_partition1();
	// test_quicksort_rec1();

	// recursive quicksort does more assertion checks than iterative
	// quicksort, so if they are left in recursive quicksort is slower than
	// non-recursive quicksort; removing all assertions shows that the timings
	// are practically equal

	// test_quicksort_rec2();  
	// 23.12, 22.79, 23.18 (assertions on, partition1, -O3)
    // 10.22, 10.17, 10.13 (assertions off, partition1, -O3)
    // 7.59, 7.72, 7.60    (assertions off, partition2, -O3)
    // 7.74, 7.66, 7.75    (assertions off, partition2, const ip, -O3)

	// test_quicksort_iter1(); 
	test_quicksort_iter2(); 
	// 15.19, 15.10, 15.30 (assertions on, partition1, -O3)
	// 10.03, 10.12, 10.06 (assertions off, partition1, -O3)
	// 7.66, 7.61, 7.63    (assertions off, partition2, -O3)
	// 6.80, 6.76, 6.80    (assertions off, partition2, const ip, -O3)
	
	// The performance of std::sort() shows there is still improvements that
	// can be made to to our quicksort.
	//	
	// test_std_sort2(); // 0.01, 0.01, 0.01
} // main