/*Пример разреженной матрицы комплексного типа на двух списках std:list с 
индексацией по столбцам и загрузкой из текстового файла
сделал Shiz at 03:01 28.04.2008*/

#include <list>
#include <stack>
#include <iostream>
#include <fstream>
#include <complex>

using namespace std;

//ломает постоянно писать такую длинную штуку. поэтому будем писать просто T
#define T complex<double>

class matrix{
  
  //структура одного элемента-ячейки, храним номер строки и значение
  struct cell{
    unsigned int row;
    T* value;
    
    cell(unsigned int a_row, T* a_value){
      row=a_row;
      value=a_value;
    }
    
  };
  
  //структура одного столбца, храним номер стоблца, 
  //итератор на первый элемент столбца из списка элементов
  //и число элементов в столбце
  struct col{
    unsigned int num;
    list<cell>::iterator begin;
    int size;
    
    col(unsigned int a_num, list<cell>::iterator a_begin, int a_size){
      num   = a_num;
      begin = a_begin;
      size  = a_size;
    }
  };
  
  //создаем списки
  list <col>  cols;
  list <cell> cells;
  
  public: 
    
  //загружаем матрицу из файла
  void LoadMatrix(char* filename){//имхо, единтвенное место где что-то от си осталось
    int i,x,y;
    double re,im;
    //объявляем поток на чление
    ifstream in(filename);
    for(in>>i; i>0;i--){
      //читаем
      in>>x>>y>>re>>im;
      //добавляем в матрицу
      Add(x,y,new T(re,im));
    }
    
  };
  
    
    
  void Add(int a_col, int a_row, T* a_value){
    //если есть ненулевой элемент - то уходим
    if(Get(a_col,a_row)!=T(0,0)) return;
    
    
    if(!cols.empty()){
      
      list<col>::iterator p = cols.begin();
      //перебираем столбцы пока не найдем требуемый
      while(p!=cols.end() && (*p).num<a_col){
        p++;
      }
      
      if((*p).num==a_col){
        //столбец уже существует, добавляем ячейку
        cell c(a_row, a_value);
        list<cell>::iterator p_cell;
        
        //находим элемент, чей номер строки больше чем у вставляемого
        p_cell=(*p).begin;
        int i=(*p).size;
        
        while(i && a_row>(*p_cell).row){
          i--;
          p_cell++;
        }

        //вставляем перед ним элемент
        cells.insert(p_cell, c);
        
        // если вставляем перед первым элементом то сдвигаем итератор
        if(p_cell==(*p).begin)
          (*p).begin--;
          
        (*p).size++;
      }
      else{
        //создаем ячейку и пихаем ее в конец списка
        cell c(a_row, a_value);
        cells.push_front(c) ;
        //столбец не существует, создаем его и пихаем перед текущим
        col cl(a_col, cells.begin(), 1);
        cols.insert(p, cl);
      }
    }
    else{
      //список столбцов пуст, а значит список ячеек тоже
      cell c(a_row, a_value);
      cells.push_back(c) ;
      //столбец не существует, создаем его и пихаем в список
      col cl(a_col, cells.begin(), 1);
      cols.push_back(cl);
    }
    

    
  }
  

  T Get(int a_col, int a_row){
    list<col>::iterator p = cols.begin();
    //перебираем столбцы пока не найдем требуемый или пока не кончится список
    while(p!=cols.end() && (*p).num<a_col){
      p++;
    } 
  
    //если нашли столбец
    if((*p).num==a_col){
      list<cell>::iterator p_cells = (*p).begin;
      //перебираем строки
      for(int i=(*p).size;i;i--){
        if((*p_cells).row==a_row)//нашли столбец
          return *(*p_cells).value;
        *p_cells++;
      }
    }

    return *new T(0,0);

  }

  unsigned int GetNumElements(){
    return cells.size();
  }

  unsigned int GetNumCols(){
    return cols.size();
  }

  
  //выводим информацию о столбцах
  void print_cols(){
    list<col>::iterator p;
    p=cols.begin();
    
    while(p!=cols.end()){
      cout<<endl<<"Col #"<<(*p).num<<endl
      <<"  Size: "<<(*p).size<<endl
      <<"  Begin row: "<<(*(*p).begin).row<<endl;
      
      p++;
    }
    
    cout<<endl;
  }

  //выводим в столбик инфу о всех столбцах и строках
  void print_all(){
    list<col>::iterator p_col;
    list<cell>::iterator p_cell;
    p_col=cols.begin();
    
    for(p_col=cols.begin();p_col!=cols.end();p_col++){
      p_cell=(*p_col).begin;
      for(int i=(*p_col).size;i;i--){
        cout<<"("<<(*p_col).num<<","<<(*p_cell).row<<") -> "<<*(*p_cell).value<<endl;
        p_cell++;
      }
    }
  }

  void Task(){
    //вывести произведение элементов столбца, в котором ненулевых элементов, больше чем в остальных
    //если число элементов совпадает у нескольких столбцов, то обработать предпоследний

    list<col>::iterator p;
    //создаем стек итераторов
    stack<list<col>::iterator> stk;
    
    
    p=cols.begin();
    int max_size=0;//максимальный размер столбца
    
    //перебираем столбцы
    while(p!=cols.end()){
      
      if((*p).size > max_size){
        //встретили столбец, у которого размер больше маесимального
        if(!stk.empty())
          stack<list<col>::iterator> stk;//если стек непуст то удаляем его куда подальше=))
        
        stk.push(p);//пихаем итератор в стек
        max_size=(*p).size;
      }

      if((*p).size == max_size){
        //если размер столбца равен максимальному, то пихаем итератор в стек
        stk.push(p);
      }

      p++;
    }
    
    //если в стеке больше одного элемента, то удаляем верхний, ибо нам нужен предпоследний
    if(stk.size()>1)
      stk.pop();
    
    //извлекаем последний элемент
    p = stk.top();

    T result(1,0);
    list<cell>::iterator p_cell;
    
    p_cell=(*p).begin;
    //перебираем элементы столбца, попутно их перемножая
    for(int i=(*p).size;i;i--){
      result*=*((*p_cell).value);
      p_cell++;
    }
    
    cout<<endl<<"Task:"<<endl
              <<"  Col #"<<(*p).num   << endl
              <<"  Size: "<<(*p).size << endl
              <<"  Produce elements: "<<result<<endl;
  }
};

int main(){
  
  matrix M;
  
  M.LoadMatrix("m.txt");
  
  cout<<"Number"<<endl<<"  of cols: "<<M.GetNumCols()<<endl<<"  of elements: "<<M.GetNumElements()<<endl;

  M.print_cols();
  M.print_all();

  M.Task();

  int i;
  cin>>i;

}