/*Пример разреженной матрицы комплексного типа на двух списках 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;
}