/*
 *  Abstract vector based quick sort implementation
 *  Copyright (C) 2009 neverfear.org.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2, or (at your option)
 *  any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
 
 
 
#include <stdio.h>
#include <string>
#include <vector>
 
using namespace std;
 
#define ARRAY_SIZE(arr, typ) (sizeof(arr) / sizeof(typ))
 
// Abstract comparable template class
template <class X> class Comparable {
public:
	virtual int compareTo(X * x) = 0;
};
 
 
// Specific implementor of Comparable
// Note: std::string already has a comparison method but is implemented
// as such for a more polymorphic approach to sorting.
class ComparableString : public string, public Comparable<ComparableString> {
public:
	ComparableString(const char * s) : string(s) {}
 
	int compareTo(ComparableString * x) {
		return this->compare((string)*x);
	}
};
 
 
// Quick sort partitioner
template <class X> int partition(vector<X*> * list, int left, int right, int pivot) {
	int storeIndex = left;
	X * pivotValue = (*list)[pivot];
 
	(*list)[pivot] = (*list)[right];
	(*list)[right] = pivotValue;
 
	X * temp;
 
	for(int i = left; i < right; i++) {
		if ((*(*list)[i]).compareTo(pivotValue) < 0) {
 
			temp                = (*list)[storeIndex];
			(*list)[storeIndex] = (*list)[i];
			(*list)[i]          = temp;
			storeIndex++;
 
		}
	} 
	temp                = (*list)[right];
	(*list)[right]      = (*list)[storeIndex];
	(*list)[storeIndex] = temp;
 
	return storeIndex;
};
 
// Quick sort recursive caller
template <class X> int quicksort_recursive(vector<X*> * list, int left, int right) {
	if (right > left) {
		int pivot = partition(list, left, right, left);
		quicksort_recursive(list, left,      pivot - 1);
		quicksort_recursive(list, pivot + 1, right);
	}
	return 0;
}
 
// Simple interface to quick sort algorithm
template <class X> int quicksort(vector<X*> * list) {
	return quicksort_recursive(list, 0, (*list).size() - 1);
}
 
 
 
// Main entry point for testing purposes
 
int main(int argc, char ** argv) {
	ComparableString list[] = {
	    "This", "is", "the", "in-place", "partition",
        "algorithm", "It", "partitions", "the", "portion",
        "of", "the", "array", "between", "indexes",
        "left", "and", "right", "inclusively", "by",
        "moving", "all", "elements", "less", "than",
        "or", "equal", "to", "array", "to",
        "the", "beginning", "of", "the", "subarray",
        "leaving", "all", "the", "greater", "elements",
        "following", "them", "In", "the", "process",
        "it", "also", "finds", "the", "final",
        "position", "for", "the", "pivot", "element",
        "which", "it", "returns", "It", "temporarily",
        "moves", "the", "pivot", "element", "to",
        "the", "end", "of", "the", "subarray",
        "so", "that", "it", "doesn't", "get",
        "in", "the", "way", "Because", "it",
        "only", "uses", "exchanges", "the", "final",
        "list", "has", "the", "same", "elements",
        "as", "the", "original", "list", "Notice",
        "that", "an", "element", "may", "be",
        "exchanged", "multiple", "times", "before", "reaching",
        "its", "final", "place"
	};
 
	vector<ComparableString*> vlist;
	for(int i = 0; i < ARRAY_SIZE(list, ComparableString); i++) {
		vlist.push_back(&list[i]);
	}
 
	quicksort(&vlist);
 
	for(int i = 0; i < vlist.size(); i++) {
		printf("%03d='%s'\n", i, (*vlist[i]).c_str());
	}
	return 0;
}