ZBP1-1.cpp

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <list>

#define DICTIONARY_PATH "/cygdrive/d/files/gdrive/Uczelnia/ZBP/lab1/lab1-1/lab1.dic"

//#define VERBOSE
//#define READ_TEST_DATA

using namespace std;

void printStringVector(vector<string*> &v);
void printStringList(list<string*> &v);
int stringCompareQsort(const void * a, const void * b);
int stringCompareSort(string *lhs, string *rhs);
void freeDictionary(vector<string*> &v);
double runQsort(vector<string*> dictionary);
double runSort(vector<string*> dictionary);
double runStableSort(vector<string*> dictionary);
double runListSort(list<string*> dictionary);
vector<string*> loadDictionary();
vector<string*> readDictionaryFromFile();

int main() {
	vector<string*> dictionary = loadDictionary();
	srand(unsigned(time(0)));
	random_shuffle(dictionary.begin(), dictionary.end());

	cout << "-- QSort" << endl;
	cout << runQsort(vector<string*>(dictionary)) << endl;
	cout << "-- Sort" << endl;
	cout << runSort(vector<string*>(dictionary)) << endl;
	cout << "-- Stable sort" << endl;
	cout << runStableSort(vector<string*>(dictionary)) << endl;
	cout << "-- list.sort()" << endl;
	cout << runListSort(list<string*>(dictionary.begin(), dictionary.end()))
			<< endl;

#ifdef VERBOSE
	cout << "-- Original" << endl;
	printStringVector(dictionary);
#endif

	cout << "-- Free memory" << endl;
	freeDictionary(dictionary);

	return 0;
}

double runQsort(vector<string*> dictionary) {
	clock_t begin = clock();

	qsort(&dictionary[0], dictionary.size(), sizeof(dictionary[0]),
			stringCompareQsort);

	double duration = double(clock() - begin) / CLOCKS_PER_SEC;

#ifdef VERBOSE
	printStringVector(dictionary);
#endif

	return duration;
}

double runSort(vector<string*> dictionary) {
	clock_t begin = clock();

	sort(dictionary.begin(), dictionary.end(), stringCompareSort);

	double duration = double(clock() - begin) / CLOCKS_PER_SEC;

#ifdef VERBOSE
	printStringVector(dictionary);
#endif

	return duration;
}

double runStableSort(vector<string*> dictionary) {
	clock_t begin = clock();

	stable_sort(dictionary.begin(), dictionary.end(), stringCompareSort);

	double duration = double(clock() - begin) / CLOCKS_PER_SEC;

#ifdef VERBOSE
	printStringVector(dictionary);
#endif

	return duration;
}

double runListSort(list<string*> dictionary) {
	clock_t begin = clock();

	dictionary.sort(stringCompareSort);

	double duration = double(clock() - begin) / CLOCKS_PER_SEC;

#ifdef VERBOSE
	printStringList(dictionary);
#endif

	return duration;
}

void printStringVector(vector<string*> &v) {
	for (vector<string*>::iterator it = v.begin(); it != v.end(); it++) {
		cout << **it << endl;
	}
}

void printStringList(list<string*> &v) {
	for (list<string*>::iterator it = v.begin(); it != v.end(); it++) {
		cout << **it << endl;
	}
}

int stringCompareQsort(const void *a, const void * b) {
	string* lhs = *(string**) a;
	string* rhs = *(string**) b;

	return lhs->compare(*rhs);
}

int stringCompareSort(string *lhs, string *rhs) {
	return *lhs < *rhs;
}

void freeDictionary(vector<string*> &v) {
	for (vector<string*>::iterator it = v.begin(); it != v.end(); it++) {
		delete *it;
	}
}

vector<string*> loadDictionary() {
#ifdef READ_TEST_DATA
	vector<string*> dictionary;

	dictionary.push_back(new string("aa"));
	dictionary.push_back(new string("a"));
	dictionary.push_back(new string("b"));
	dictionary.push_back(new string("0"));
	dictionary.push_back(new string("a"));

	return dictionary;
#else
	return readDictionaryFromFile();
#endif
}

vector<string*> readDictionaryFromFile() {
	vector<string*> dictionary;

	ifstream input(DICTIONARY_PATH);

	int i = 0;

	for (string line; getline(input, line); i++) {
		dictionary.push_back(new string(line));
	}

	return dictionary;
}