#include <iostream>
using namespace std;

class Element
{
public:
    int i;
    int j;
    int x;
};

class Sparse
{
private:
    int m;
    int n;
    int num;
    Element *ele;

public:
    Sparse(int m, int n, int num)
    {
        this->m = m;
        this->n = n;
        this->num = num;
        ele = new Element[this->num];
    }

    ~Sparse()
    {
        delete[] ele;
    }

    Sparse operator+(Sparse &s);
    Sparse transpose();
    Sparse multiply(Sparse &s);

    friend istream & operator>>(istream &is, Sparse &s);
    friend ostream & operator<<(ostream &os, Sparse &s);
};

Sparse Sparse::operator+(Sparse &s)
{
    int i, j, k;
    if (m != s.m || n != s.n)
        return Sparse(0, 0, 0);

    Sparse *sum = new Sparse(m, n, num + s.num);
    i = j = k = 0;

    while (i < num && j < s.num)
    {
        if (ele[i].i < s.ele[j].i)
            sum->ele[k++] = ele[i++];
        else if (ele[i].i > s.ele[j].i)
            sum->ele[k++] = s.ele[j++];
        else
        {
            if (ele[i].j < s.ele[j].j)
                sum->ele[k++] = ele[i++];
            else if (ele[i].j > s.ele[j].j)
                sum->ele[k++] = s.ele[j++];
            else
            {
                sum->ele[k] = ele[i];
                sum->ele[k++].x = ele[i++].x + s.ele[j++].x;
            }
        }
    }

    for (; i < num; i++) sum->ele[k++] = ele[i];
    for (; j < s.num; j++) sum->ele[k++] = s.ele[j];

    sum->num = k;
    return *sum;
}

Sparse Sparse::transpose()
{
    Sparse *result = new Sparse(n, m, num);
    int *rowTerms = new int[n]{0};
    int *rowPosition = new int[n]{0};

    for (int i = 0; i < num; i++)
        rowTerms[ele[i].j]++;

    rowPosition[0] = 0;
    for (int i = 1; i < n; i++)
        rowPosition[i] = rowPosition[i-1] + rowTerms[i-1];

    for (int i = 0; i < num; i++)
    {
        int j = rowPosition[ele[i].j]++;
        result->ele[j].i = ele[i].j;
        result->ele[j].j = ele[i].i;
        result->ele[j].x = ele[i].x;
    }

    delete[] rowTerms;
    delete[] rowPosition;
    return *result;
}

Sparse Sparse::multiply(Sparse &s)
{
    if (n != s.m)
        return Sparse(0, 0, 0);

    Sparse *result = new Sparse(m, s.n, m * s.n);
    int *rowTerms = new int[m]{0};
    int *colTerms = new int[s.n]{0};
    int k = 0;

    for (int i = 0; i < num; i++)
        rowTerms[ele[i].i]++;

    for (int i = 0; i < s.num; i++)
        colTerms[s.ele[i].j]++;

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < s.n; j++)
        {
            int sum = 0;
            int p1 = 0, p2 = 0;
            while (p1 < num && p2 < s.num)
            {
                if (ele[p1].i != i)
                    p1++;
                else if (s.ele[p2].j != j)
                    p2++;
                else if (ele[p1].j < s.ele[p2].i)
                    p1++;
                else if (ele[p1].j > s.ele[p2].i)
                    p2++;
                else
                    sum += ele[p1++].x * s.ele[p2++].x;
            }
            if (sum != 0)
            {
                result->ele[k].i = i;
                result->ele[k].j = j;
                result->ele[k].x = sum;
                k++;
            }
        }
    }

    result->num = k;
    delete[] rowTerms;
    delete[] colTerms;
    return *result;
}

istream & operator>>(istream &is, Sparse &s)
{
    cout << "Enter non-zero elements";
    for (int i = 0; i < s.num; i++)
        cin >> s.ele[i].i >> s.ele[i].j >> s.ele[i].x;
    return is;
}

ostream & operator<<(ostream &os, Sparse &s)
{
    int k = 0;
    for (int i = 0; i < s.m; i++)
    {
        for (int j = 0; j < s.n; j++)
        {
            if (k < s.num && s.ele[k].i == i && s.ele[k].j == j)
                cout << s.ele[k++].x << " ";
            else
                cout << "0 ";
        }
        cout << endl;
    }
    return os;
}

int main()
{
    Sparse s1(3, 3, 3);
    Sparse s2(3, 3, 3);

    cin >> s1;
    cin >> s2;

    cout << "First Matrix" << endl << s1;
    cout << "Second Matrix" << endl << s2;

    Sparse sum = s1 + s2;
    cout << "Sum Matrix" << endl << sum;

    Sparse trans = s1.transpose();
    cout << "Transpose of First Matrix" << endl << trans;

    Sparse prod = s1.multiply(s2);
    cout << "Product Matrix" << endl << prod;

    return 0;
}
in the above code why are we doing this
class Element
{
public:
    int i;
    int j;
    int x;
};

class Sparse
{
private:
    int m;
    int n;
    int num;
    Element *ele;