#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#define LENGHT_STRING 255
using namespace std;
int rand_gen(int size){
return rand()%size;
}
class Key{
int key1;
unsigned char key2;
public:
Key(){
key1=0;
key2=0;
}
Key(Key* a_key){
key1=a_key->key1;
key2=a_key->key2;
}
Key(int a_key1, char a_key2){
key1=a_key1;
key2=a_key2;
}
friend ostream &operator<<(ostream &stream, Key key);
friend int operator<(Key key1, Key key2);
Key operator++(int i){
key2-=97;
key2++;
if(key2/26){
key1++;
key2=0;
}
key2+=97;
return *this;
}
Key operator=(Key op2){
key1=op2.key1;
key2=op2.key2;
return *this;
}
Key operator=(Key *op2){
key1=op2->key1;
key2=op2->key2;
return *this;
}
};
ostream &operator<<(ostream &stream, Key key){
stream<<key.key1<<key.key2;
}
int operator<(Key key1, Key key2){
if(key1.key1 != key2.key1)
return key1.key1 < key2.key1;
return key1.key2 < key2.key2;
}
class Row{
public:
Key *key;
char *value;
public:
Row (Key *a_key, char* a_value){
key=a_key;
value=a_value;
}
};
ostream &operator<<(ostream &stream, Row row){
stream<< *(row.key)<<": "<<(row.value)<<"\n";
}
int operator<(Row row1, Row row2){
return *row1.key<*row2.key;
}
class Table{
list<Row*> rows;
void Add(char* str){
Key *last_key;
last_key = new Key();
if(rows.size()){
Row* last_row=rows.back();
last_key=new Key(last_row->key);
}
(*last_key)++;
rows.push_back(new Row(last_key,str));
}
void LoadFromFile(char* filename){
int i,x,y,h,w;
double re,im;
ifstream in(filename);
if(!in)
exit(1);
while(in){
char *str= new char[LENGHT_STRING];
in.getline(str,LENGHT_STRING);
Add(str);
}
}
public:
Table(char* filename){
rows.clear();
LoadFromFile(filename);
}
void merge(int lb, int split, int ub){
list<Row*>::iterator left_i=rows.begin();
list<Row*>::iterator right_i=rows.begin();
int left=lb;
int right=split;
for(int i=0;i<lb;i++)
left_i++;
right_i=left_i;
for(int i=lb;i<split;i++)
right_i++;
list<Row*>::iterator initial_left = left_i;
list<Row*>::iterator initial_right = right_i;
list<Row*> temp;
list<Row*>::iterator temp_i=temp.begin();
while(left<split && right<ub){
if( (**left_i) < (**right_i)){
temp.push_back(*left_i);
left_i++;
left++;
}
else{
temp.push_back(*right_i);
right_i++;
right++;
}
}
while(left<split){
temp.push_back(*left_i);
left_i++;
left++;
}
while(right<ub){
temp.push_back(*right_i);
right_i++;
right++;
}
left_i=initial_left;
while(temp.size()){
rows.insert(rows.erase(left_i++),temp.front());
temp.erase(temp.begin());
}
}
void mergeSort(int lb, int ub) {
long split;
if (ub-lb>1) {
split = (lb + ub)/2;
mergeSort(lb, split);
mergeSort(split, ub);
merge(lb, split, ub);
}
}
void MergeSort(){
mergeSort(0,rows.size());
}
void OrderDesc(){
reverse(rows.begin(),rows.end());
}
void OrderRand(){
vector<Row*> rows2;
//list<Row*>::iterator b=rows.end();
rows2.insert(rows2.begin(),rows.begin(),rows.end());
random_shuffle(rows2.begin(),rows2.end());
rows.clear();
rows.insert(rows.begin(),rows2.begin(),rows2.end());
}
friend ostream &operator<<(ostream &stream, Table table);
};
ostream &operator<<(ostream &stream, Table table){
cout<<"===============================================================================\n";
list<Row*>::iterator p=table.rows.begin();
while(p!=table.rows.end()){
cout<<**p;
p++;
}
cout<<"===============================================================================\n";
}
void ShowMeTheMagic(char* fn){
Table table(fn);
cout<<"Initial table:\n";
cout<<table;
table.MergeSort();
cout<<"Table after sort:\n";
cout<<table;
cout<<"Table in reverse order:\n";
table.OrderDesc();
cout<<table;
table.MergeSort();
cout<<"Table after sort:\n";
cout<<table;
cout<<"Table in random order:\n";
table.OrderRand();
cout<<table;
table.MergeSort();
cout<<"Table after sort:\n";
cout<<table;
}
int main(){
ShowMeTheMagic("duck.txt");
ShowMeTheMagic("blinky.txt");
ShowMeTheMagic("test.txt");
system("pause");
}