#include <cstdlib>
#include <iostream>
using namespace std;

#define Size 128
typedef struct
{
	int row;
	int col;
	int value;
}MATRIX;

int com(const void *m1, const void *m2)
{
	if ((*(MATRIX *)m1).row != (*(MATRIX *)m2).row)
		return (*(MATRIX *)m1).row - (*(MATRIX *)m2).row;
	else
		return (*(MATRIX *)m1).col - (*(MATRIX *)m2).col;
}

class Matrix
{
private:
	int cmp(MATRIX m1, MATRIX m2)
	{
		if (m1.row != m2.row)
			return m1.row - m2.row;
		else
			return m1.col - m2.col;
	}

	void fast_transpose(MATRIX *m)
	{
		for (int i = 0 ; i <= m[0].value ; i++)
			m[i].col ^= m[i].row ^= m[i].col ^= m[i].row;
		qsort(m + 1, m[0].value, sizeof(MATRIX), com);
	}
public:
	bool change(int from[][Size], MATRIX *to, int row, int col)
	{
		to[0].row = row;
		to[0].col = col;
		to[0].value = 0;
		
		for (int i = 0 ; i < row ; i++)
			for (int j = 0 ; j < col ; j++)
			{
				if (from[i][j])
				{
					to[++to[0].value].row = i;
					to[to[0].value].col = j;
					to[to[0].value].value = from[i][j];
				}
			}
			
			return true;
	}
	
	bool mat_add(MATRIX *m1, MATRIX *m2, MATRIX *sum)
	{
		int i, j;
		int tmp;
		
		if (m1[0].col != m2[0].col || m1[0].row != m2[0].row)
			return false;
		
		sum[0].row = m1[0].row;
		sum[0].col = m1[0].col;
		sum[0].value = 0;
		for (i = j = 1 ; i <= m1[0].value && j <= m2[0].value;)
		{
			tmp = cmp(m1[i], m2[j]);
			if (tmp == 0 && m1[i].value + m2[j].value)
			{
				sum[++sum[0].value].col = m1[i].col;
				sum[sum[0].value].row = m1[i].row;
				sum[sum[0].value].value = m1[i].value + m2[j].value;
				i++;j++;
			}
			else if (tmp > 0)
			{
				sum[++sum[0].value].col = m2[j].col;
				sum[sum[0].value].row = m2[j].row;
				sum[sum[0].value].value = m2[j].value;
				j++;
			}
			else
			{
				sum[++sum[0].value].col = m1[i].col;
				sum[sum[0].value].row = m1[i].row;
				sum[sum[0].value].value = m1[i].value;
				i++;
			}
		}
		while (i <= m1[0].value)
		{
			sum[++sum[0].value].col = m1[i].col;
			sum[sum[0].value].row = m1[i].row;
			sum[sum[0].value].value = m1[i].value;
			i++;
		}
		while (j <= m2[0].value)
		{
			sum[++sum[0].value].col = m2[j].col;
			sum[sum[0].value].row = m2[j].row;
			sum[sum[0].value].value = m2[j].value;
			j++;
		}
		
		return true;
	}

	bool mat_mul(MATRIX *m1, MATRIX *m2, MATRIX *sum)
	{
		int i, j, r, c, row, tol;
		int row1[Size] = {1, 1}, row2[Size] = {1, 1};
		
		if (m1[0].col != m2[0].row)
			return false;

		fast_transpose(m2);
		sum[0].row = m1[0].row;
		sum[0].col = m2[0].row;
		sum[0].value = 0;
		row = m1[1].row;
		for (i = 2 ; i <= m1[0].value ; i++)
		{
			if (row != m1[i].row)
			{
				row1[++row1[0]] = i;
				row = m1[i].row;
			}
		}
		row1[++row1[0]] = m1[0].value + 1;
		row = m2[1].row;
		for (i = 2 ; i <= m2[0].value ; i++)
		{
			if (row != m2[i].row)
			{
				row2[++row2[0]] = i;
				row = m2[i].row;
			}
		}
		row2[++row2[0]] = m2[0].value + 1;

		for (i = 1 ; i < row1[0] ; i++)
		{
			for (j = 1 ; j <row2[0] ; j++)
			{
				tol = 0;
				for (r = row2[j], c = row1[i]; r < row2[j + 1] && c < row1[i + 1];)
				{
					if (m1[c].col < m2[r].col)
						c++;
					else if (m1[c].col == m2[r].col)
						tol += m1[c++].value * m2[r++].value;
					else
						r++;
				}
				if (tol)
				{
					sum[++sum[0].value].row = m1[row1[i]].row;
					sum[sum[0].value].col = m2[row2[j]].row;
					sum[sum[0].value].value = tol;
				}
			}
		}

		return true;
	}
	
	void display(MATRIX *to)
	{
		for (int i = 1 ; i <= to[0].value ; i++)
			cout << to[i].row << ' '
			<< to[i].col << ' '
			<< to[i].value << endl;
	}
};

int main(void)
{
	Matrix mat;
	MATRIX m[Size * Size];
	MATRIX n[Size * Size];
	MATRIX s[Size * Size];
	int a[Size][Size];
	
	for (int i = 0 ; i < 3 ; i++)
		for (int j = 0 ; j < 3 ; j++)
			a[i][j] = rand() % 4;
	mat.change(a, m, 3, 3);
	mat.display(m);
	cout << endl;

	for (i = 0 ; i < 3 ; i++)
		for (int j = 0 ; j < 3 ; j++)
			a[i][j] = rand() % 4;
	mat.change(a, n, 3, 3);
	mat.display(n);
	cout << endl;

	mat.mat_mul(m, n, s);
	mat.display(s);
	cout << endl;

	return 0;
}