/**
 * ΤΕΙ ΗΠΕΙΡΟΥ
 * ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΕ
 * ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ
 * 2015-2016
 * ΓΚΟΓΚΟΣ ΧΡΗΣΤΟΣ
 *
 * Αρχικός κώδικας : http://pastebin.com/REK6nTAJ
 */

#include <iostream>
#include <string>
#include <random>
#include <algorithm>
#include <list>
#include <chrono>

using namespace std;
using namespace chrono;

mt19937 mt;
uniform_int_distribution<int> uni1(0, 5000);
uniform_int_distribution<int> uni2(0, 25);


// Δομή "πελάτης" :
struct customer
{
	string name;
	int balance;

	bool operator<(customer other) // Δημιουργία συνάρτησης σύγκρισης του αντικειμένου
	{
		return name < other.name;
	}
};


string generate_random_name(int k)
{
	string name { }; // Δημιουργία ενός *αρχικά* κενού String ονόματος. ( String name = ""; )

	string letters_en("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); // Εδώ βάζει όλα τα γράμματα της αλφαβήτου από τα οποία θα διαλέγει 1 κάθε φορά.

	for (int j = 0; j < k; j++)
	{
		// Δημιουργία ενός τυχαίου *χαρακτήρα* :
		char c { letters_en[uni2(mt)] }; // Ίδιο με :  char c = letters_en[ uni2(mt) ]; - Εδώ διαλέγει ένα από τα 25 γράμματα του string.
		name += c; // Προσθήκη του νέου χαρακτήρα στο String του ονόματος
	}

	return name;
}





/**
 * ######################################################################
 * ΣΤΑΤΙΚΗ ΑΝΑΠΑΡΑΣΤΑΣΗ ΓΡΑΜΜΙΚΗΣ ΛΙΣΤΑΣ (ΑΡΧΗ)
 * ######################################################################
 */

const int MAX = 50000;

template<class T>
struct static_list
{
	T elements[MAX];
	int size = 0;
};



// επιστροφή του στοιχείου που βρίσκεται στη θέση i
template<class T>
T access(static_list<T>& static_list, int i)
{
	if (i < 0 || i >= static_list.size)
		throw -1;
	else
		return static_list.elements[i];
}



// προσθήκη στοιχείου στο τέλος της λίστας
template<class T>
void push_back(static_list<T>& static_list, T x)
{
	if (static_list.size == MAX)
		return;

	static_list.elements[static_list.size] = x;
	static_list.size++;
}




// προσθήκη στοιχείου στη θέση i, ολίσθηση δεξιά των υπόλοιπων στοιχείων
template<class T>
void insert(static_list<T>& static_list, int i, T x)
{
	if (static_list.size == MAX)
		return;

	if (i < 0 || i >= static_list.size)
		return;

	for (int k = static_list.size; k > i; k--)
	{
		static_list.elements[k] = static_list.elements[k - 1];
	}

	static_list.elements[i] = x;
	static_list.size++;
}




// διαγραφή στοιχείου στη θέση i, αριστερή ολίσθηση των υπόλοιπων στοιχείων
template<class T>
void delete_item(static_list<T>& static_list, int i)
{
	if (i < 0 || i >= static_list.size)
		return;

	for (int k = i; k < static_list.size; k++)
	{
		static_list.elements[k] = static_list.elements[k + 1];
	}

	static_list.size--;
}



// δημιουργία δεδομένων στατικής λίστας
void generate_data_static_list(static_list<customer>& static_list, int N)
{

	for (int i = 0; i < N; i++)
	{
		customer c;
		c.name = generate_random_name(10);
		c.balance = uni1(mt);
		push_back(static_list, c);
	}

}



// εκτύπωση στατικής λίστας
void print_customers_static_list(static_list<customer>& static_list, int k)
{
	for (int i = 0; i < k; i++)
	{
		customer cu = access(static_list, i);
		cout << cu.name << " - " << cu.balance << endl;
	}

	cout << "SIZE " << static_list.size << endl;

}






void total_balance_static_list(static_list<customer>& static_list, char c)
{
	// ερώτημα 1α
}

void add_extra_customers_static_list(static_list<customer>& static_list, char c)
{
	// ερώτημα 1β
}




void remove_customers_static_list(static_list<customer>& static_list, char c)
{
	int i = 0;

	while (i < static_list.size)
	{
		customer cu = access(static_list, i);

		if (cu.name.at(0) == c)
			delete_item(static_list, i);
		else
			i++;
	}

}


void test_static_list()
{
	mt = *(new mt19937(1940));

	cout << "Testing static list" << endl;
	cout << "########################################################" << endl;

	high_resolution_clock::time_point t1 = high_resolution_clock::now();
	struct static_list<customer> static_list;

	generate_data_static_list(static_list, 40000);

	high_resolution_clock::time_point t2 = high_resolution_clock::now();
	print_customers_static_list(static_list, 20);

	auto duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;



	t1 = high_resolution_clock::now();
	total_balance_static_list(static_list, 'A');
	t2 = high_resolution_clock::now();

	duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;



	t1 = high_resolution_clock::now();
	add_extra_customers_static_list(static_list, 'A');
	t2 = high_resolution_clock::now();

	print_customers_static_list(static_list, 20);
	duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;

	t1 = high_resolution_clock::now();
	remove_customers_static_list(static_list, 'B');
	t2 = high_resolution_clock::now();

	print_customers_static_list(static_list, 20);
	duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;


	cout << "########################################################" << endl;
}


/**
 * ######################################################################
 * ΓΡΑΜΜΙΚΗ ΛΙΣΤΑ (ΤΕΛΟΣ)
 * ######################################################################
 */





/**
 * ######################################################################
 * ΣΥΝΔΕΔΕΜΕΝΗ ΛΙΣΤΑ (ΑΡΧΗ)
 * ######################################################################
 */

template<class T>
struct node
{
	T data;
	struct node<T>* next = NULL;
};


template<class T>
struct linked_list
{
	struct node<T>* head = NULL;
	int size = 0;
};


// επιστροφή του στοιχείου που βρίσκεται στη θέση i
template<class T>
struct node<T>* access(linked_list<T>& linked_list, int i)
{
	if (i < 0 || i >= linked_list.size)
		return NULL;

	struct node<T>* current = linked_list.head;

	for (int k = 0; k < i; k++)
	{
		current = current->next;
	}

	return current;
}



// προσθήκη στοιχείου στο τέλος της λίστας
template<class T>
void push_back(linked_list<T>& linked_list, T x)
{
	struct node<T>* new_node, *current;

	new_node = new node<T>();
	new_node->data = x;
	new_node->next = NULL;
	current = linked_list.head;

	if (current == NULL)
	{
		linked_list.head = new_node;
		linked_list.size++;
	}

	else
	{
		while (current->next != NULL)
		{
			current = current->next;
		}

		current->next = new_node;
		linked_list.size++;
	}


}



void print_customers_linked_list(linked_list<customer>& linked_list, int k)
{
	for (int i = 0; i < k; i++)
	{
		struct node<customer>* node = access(linked_list, i);
		customer cu = node->data;
		cout << cu.name << " - " << cu.balance << endl;
	}

	cout << "SIZE " << linked_list.size << endl;
}





void generate_data_linked_list(linked_list<customer>& linked_list, int N)
{
	for (int i = 0; i < N; i++)
	{
		customer c;
		c.name = generate_random_name(10);
		c.balance = uni1(mt);
		push_back(linked_list, c);
	}

}



void total_balance_linked_list(linked_list<customer>& linked_list, char c)
{
	struct node<customer>* ptr;
	ptr = linked_list.head;
	int i = 0;
	int sum = 0;

	while (ptr != NULL)
	{
		customer cu = ptr->data;
		if (cu.name.at(0) == c)
			sum += cu.balance;
		ptr = ptr->next;
		i++;
	}

	cout << "Total balance for customers having name starting with character  " << c << " is " << sum << endl;

}




void add_extra_customers_linked_list(linked_list<customer>& linked_list, char c)
{
	struct node<customer>* ptr;
	ptr = linked_list.head;

	while (ptr != NULL)
	{
		customer cu = ptr->data;

		if (cu.name.at(0) == c)
		{
			customer ncu;
			ncu.name = cu.name;
			reverse(ncu.name.begin(), ncu.name.end());
			ncu.balance = cu.balance;

			struct node<customer>* new_node = new node<customer>();
			new_node->data = ncu;
			new_node->next = ptr->next;
			ptr->next = new_node;
			linked_list.size++;
			ptr = new_node->next;
		}

		else
			ptr = ptr->next;
	}


}




void remove_customers_linked_list(linked_list<customer>& linked_list, char c)
{
	// ερώτημα 2
}




void test_linked_list()
{
	mt = *(new mt19937(1940));

	cout << "Testing linked list" << endl;
	cout << "########################################################" << endl;

	struct linked_list<customer> linked_list;
	high_resolution_clock::time_point t1 = high_resolution_clock::now();
	generate_data_linked_list(linked_list, 40000);
	high_resolution_clock::time_point t2 = high_resolution_clock::now();
	print_customers_linked_list(linked_list, 20);
	auto duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;


	t1 = high_resolution_clock::now();
	total_balance_linked_list(linked_list, 'A');
	t2 = high_resolution_clock::now();
	duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;


	t1 = high_resolution_clock::now();
	add_extra_customers_linked_list(linked_list, 'A');
	t2 = high_resolution_clock::now();
	print_customers_linked_list(linked_list, 20);
	duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;

	t1 = high_resolution_clock::now();
	remove_customers_linked_list(linked_list, 'B');
	t2 = high_resolution_clock::now();
	print_customers_linked_list(linked_list, 20);
	duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;


	cout << "########################################################" << endl;
}

/**
 * ######################################################################
 * ΣΥΝΔΕΔΕΜΕΝΗ ΛΙΣΤΑ (ΤΕΛΟΣ)
 * ######################################################################
 */





/**
 * ######################################################################
 * ΛΙΣΤΑ STL (ΑΡΧΗ)
 * ######################################################################
 */


void generate_data_stl_list(list<customer>& stl_list, int N)
{
	for (int i = 0; i < N; i++)
	{
		customer c;
		c.name = generate_random_name(10);
		c.balance = uni1(mt);
		stl_list.push_back(c);
	}

}

void print_customers_stl_list(list<customer>& stl_list, int k)
{

	list<customer>::iterator i;
	int c = 0;

	for (i = stl_list.begin(); c < k && i != stl_list.end(); i++)
	{
		customer cu = *i;
		cout << cu.name << " - " << cu.balance << endl;
		c++;
	}

	cout << "SIZE " << stl_list.size() << endl;

}

void total_balance_stl_list(list<customer>& stl_list, char c)
{
	list<customer>::iterator i;
	int sum = 0;

	for (i = stl_list.begin(); i != stl_list.end(); i++)
	{
		customer cu = *i;
		if (cu.name.at(0) == c)
			sum += cu.balance;
	}

	cout << "Total balance for customers having name starting with character  " << c << " is " << sum << endl;
}




void add_extra_customers_stl_list(list<customer>& stl_list, char c)
{
	// ερώτημα 3
}



void remove_customers_stl_list(list<customer>& stl_list, char c)
{
	list<customer>::iterator i = stl_list.begin();

	while (i != stl_list.end())
	{
		customer cu = *i;

		if (cu.name.at(0) == c)
		{
			i = stl_list.erase(i);
		}

		else
			i++;
	}

}



void test_stl_list()
{
	// STL ΛΙΣΤΑ
	mt = *(new mt19937(1940));
	cout << "Testing stl list" << endl;
	cout << "########################################################" << endl;

	high_resolution_clock::time_point t1 = high_resolution_clock::now();
	list<customer> stl_list;
	generate_data_stl_list(stl_list, 40000);
	high_resolution_clock::time_point t2 = high_resolution_clock::now();
	print_customers_stl_list(stl_list, 20);
	auto duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;


	t1 = high_resolution_clock::now();
	total_balance_stl_list(stl_list, 'A');
	t2 = high_resolution_clock::now();
	duration = duration_cast<microseconds>( t2 - t1 ).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;

	t1 = high_resolution_clock::now();
	add_extra_customers_stl_list(stl_list, 'A');
	t2 = high_resolution_clock::now();
	print_customers_stl_list(stl_list, 20);
	duration = duration_cast<microseconds>(t2 - t1).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;

	t1 = high_resolution_clock::now();
	remove_customers_stl_list(stl_list, 'B');
	t2 = high_resolution_clock::now();
	print_customers_stl_list(stl_list, 20);
	duration = duration_cast<microseconds>(t2 - t1).count();
	cout << "Time elapsed: " << duration << "microseconds" << endl;

	cout << "########################################################" << endl;

}

/**
 * ######################################################################
 * ΛΙΣΤΑ STL (ΤΕΛΟΣ)
 * ######################################################################
 */





int main(int argc, char **argv)
{
	test_static_list();
	test_linked_list();
	test_stl_list();
}