/**
* ΤΕΙ ΗΠΕΙΡΟΥ
* ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΕ
* ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ
* 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();
}
Comments