#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");
}