#include <iostream>
#include <fstream>

#define NOT_DETERMINED 1

#define MAX(a,b) ((a)>(b)?(a):(b))

typedef enum VarType { vtInteger, vtDouble, vtComplex, vtCompMatrix };

using namespace std;

////////////////////////////////////////////////////////////////////////////////

class Variable
{
////////////////////////////////////////////////////////////////////////////////

protected:

    VarType type;
    bool    fiction;

////////////////////////////////////////////////////////////////////////////////

public:

    Variable()
    {
        fiction = false;
    }
    Variable(Variable * v1)
    {
    }
    virtual ~Variable()
    {
    }

////////////////////////////////////////////////////////////////////////////////

protected:

    virtual Variable * Create();
    virtual Variable * Copy(Variable * v);

    void ChooseOperands(Variable * p2, Variable ** op1, Variable ** op2);

////////////////////////////////////////////////////////////////////////////////

public:

    virtual void debug()
    {
        cout << "Variable!!1" << endl;
    }

    virtual int Add(Variable * op1);
    virtual int Sub(Variable * op1);
    virtual int Mul(Variable * op1);
    virtual int Div(Variable * op1);

    ////////////////////////////////////////////////////////////////////////////

    virtual int AddTo(Variable * op1);
    virtual int SubTo(Variable * op1);
    virtual int MulTo(Variable * op1);
    virtual int DivTo(Variable * op1);

    ////////////////////////////////////////////////////////////////////////////

    virtual int operator+(int p1);
    virtual int operator-(int p1);
    virtual int operator*(int p1);
    virtual int operator/(int p1);

    ////////////////////////////////////////////////////////////////////////////

    virtual double operator+(double p1);
    virtual double operator-(double p1);
    virtual double operator*(double p1);
    virtual double operator/(double p1);

    ////////////////////////////////////////////////////////////////////////////

    Variable & operator+(Variable & p1);
    Variable & operator-(Variable & p1);
    Variable & operator*(Variable & p1);
    Variable & operator/(Variable & p1);
    Variable & operator=(Variable & p1);

    ////////////////////////////////////////////////////////////////////////////

    VarType GetType()
    {
        return type;
    }

    void CheckFiction(Variable * op2)
    {
        if (op2->fiction)
            delete op2;
    }

    void SetFiction(bool fl)
    {
        fiction = fl;
    }

};

////////////////////////////////////////////////////////////////////////////////

class Integer: public Variable
{

////////////////////////////////////////////////////////////////////////////////

protected:

    int value;

////////////////////////////////////////////////////////////////////////////////

public:

    Integer()
    {
        type  = vtInteger;
        value = 0;
    }

    Integer(int nv)
    {
        type  = vtInteger;
        value = nv;
    }

    Integer(Integer * v1)
    {
        type  = vtInteger;
        value = v1->value;
    }

    virtual ~Integer()
    {
    }

    ////////////////////////////////////////////////////////////////////////////

    virtual Variable * Create()
    {
        return new Integer();
    }

    virtual Variable * Copy(Variable * v)
    {

        value = ((Integer *) v)->value;
        return this;
    }

    int GetValue()
    {
        return value;
    }

    int SetValue(int v1)
    {
        return value = v1;
    }

    ////////////////////////////////////////////////////////////////////////////

    virtual int Add(Variable * op1);
    virtual int Sub(Variable * op1);
    virtual int Mul(Variable * op1);
    virtual int Div(Variable * op1);
};

////////////////////////////////////////////////////////////////////////////////

class Double: public Variable
{

////////////////////////////////////////////////////////////////////////////////

protected:

    double value;

////////////////////////////////////////////////////////////////////////////////

public:

    Double()
    {
        type  = vtInteger;
        value = 0;
    }

    Double(double nv)
    {
        type  = vtDouble;
        value = nv;
    }

    Double(Double * v1)
    {
        type  = vtInteger;
        value = v1->value;
    }

    virtual ~Double()
    {
    }

    ////////////////////////////////////////////////////////////////////////////

    virtual Variable * Create()
    {
        return new Double();
    }

    virtual Variable * Copy(Variable * v)
    {
        if (v->GetType() == vtDouble)
            value = ((Double *) v)->value;
        return this;
    }

    ////////////////////////////////////////////////////////////////////////////

    double GetValue()
    {
        return value;
    }

    double SetValue(double v1)
    {
        return value = v1;
    }

    ////////////////////////////////////////////////////////////////////////////

    virtual int Add(Variable * op1);
    virtual int Sub(Variable * op1);
    virtual int Mul(Variable * op1);
    virtual int Div(Variable * op1);
};

////////////////////////////////////////////////////////////////////////////////

class Complex: public Variable
{
////////////////////////////////////////////////////////////////////////////////

protected:

    double a;
    double b;

////////////////////////////////////////////////////////////////////////////////

public:

    Complex()
    {
        type = vtComplex;
        a = 0;
        b = 0;
    }

    Complex(double na, double nb)
    {
        type = vtComplex;
        a = na;
        b = nb;
    }

    Complex(Complex * v1)
    {
        type = vtComplex;
        a = v1->a;
        b = v1->b;
    }

    virtual ~Complex()
    {
    }

    ////////////////////////////////////////////////////////////////////////////

    virtual Complex * Create()
    {
        return new Complex();
    }

    virtual Complex * Copy(Variable * v)
    {
        a = ((Complex *) v)->a;
        b = ((Complex *) v)->b;
        return this;
    }

    ////////////////////////////////////////////////////////////////////////////

    virtual int Add(Variable * op1)
    {
        a += ((Complex *) op1)->a;
        b += ((Complex *) op1)->b;
        return 0;
    }

    virtual int Sub(Variable * op1)
    {
        a -= ((Complex *) op1)->a;
        b -= ((Complex *) op1)->b;
        return 0;
    }

    virtual int Mul(Variable * op1)
    {
        double a1 = a, b1 = b, a2 = ((Complex *) op1)->a, b2 = ((Complex *) op1)->b;
        a = (a1 * a2) - (b1 * b2);
        b = (a1 * b2) + (b1 * a2);
        return 0;
    }

    virtual int Div(Variable * op1)
    {
        double a1 = a, b1 = b, a2 = ((Complex *) op1)->a, b2 = ((Complex *) op1)->b;
        double d = (a2*a2 + b2*b2);
        a = (a1*a2 + b1*b2) / d;
        b = (a2*b1 - b2*a1) / d;
        return 0;
    }

    Complex & operator=(Variable & p1)
    {
        Variable::operator=(p1);
        return (* this);
    }

    ////////////////////////////////////////////////////////////////////////////

    double GetA()
    {
        return a;
    }

    double GetB()
    {
        return b;
    }

    void Clear()
    {
        a = 0;
        b = 0;
    }

    void SetA(double na)
    {
        a = na;
    }

    void SetB(double nb)
    {
        b = nb;
    }

    void SetAB(double na, double nb)
    {
        a = na;
        b = nb;
    }
};

////////////////////////////////////////////////////////////////////////////////

struct CompBlock
{
    unsigned nColumn;
    Complex value;
    CompBlock()
    {
        nColumn = 0;
    }
};

typedef CompBlock * pCompBlock;

////////////////////////////////////////////////////////////////////////////////

class CompMatrix: public Variable
{
////////////////////////////////////////////////////////////////////////////////

protected:

    CompBlock * * index;
    CompBlock * vector;
    unsigned m;
    unsigned n;
    unsigned curQty;
    unsigned maxQty;
    unsigned brQty;
    unsigned br[2];

////////////////////////////////////////////////////////////////////////////////

public:

    virtual void debug()
    {
        cout << "Matrix!!1" << endl;
    }


    CompMatrix();
    CompMatrix(int m0, int n0, int mq0);
    virtual ~CompMatrix();

    void Init(int m0, int n0, int mq0);

    Complex & GetValue();
    Complex & SetValue();
    CompMatrix & operator[](unsigned p1);

    virtual Variable * Create();
    virtual Variable * Copy(Variable * p1);
    virtual int Mul(Variable * op1);

    void Print()
    {
        for (unsigned i=0; i<m; i++)
        {
            cout << "|";
            for (int j=0; j<n; j++)
                cout << "(" << (* this)[i][j].GetValue().GetA() << ", " << (* this)[i][j].GetValue().GetB() << ")";
            cout << "|" << endl;
        };
        cout << endl;
    }

    void PrintI()
    {
        for (unsigned i=0; i<m; i++)
            cout << index[i] << " | ";
        cout << endl;
    }

    void ReadFromFile(char * fn);

    Variable & operator=(Variable & p1)
    {
        return Variable::operator=(p1);
    }

    unsigned GetM()
    {
        return m;
    }

    unsigned GetN()
    {
        return n;
    }

    unsigned GetMaxQty()
    {
        return maxQty;
    }

    unsigned GetCurQty()
    {
        return curQty;
    }

    CompBlock * * GetIndex()
    {
        return index;
    }

    CompBlock * GetVector()
    {
        return vector;
    }

////////////////////////////////////////////////////////////////////////////////

protected:

    void ResetBrackets()
    {
        brQty = 0;
        br[0] = 0;
        br[1] = 0;
    }

};

////////////////////////////////////////////////////////////////////////////////

class VirtualArray
{
////////////////////////////////////////////////////////////////////////////////

protected:

    VirtualArray * next;
    Complex      value;
    int          position;

////////////////////////////////////////////////////////////////////////////////

public:

    VirtualArray()
    {
        next     = NULL;
        position = 0;
    }
    VirtualArray(Complex v, int p)
    {
        //Complex
    }

    ////////////////////////////////////////////////////////////////////////////

    int Add(Complex v, int p)
    {
        if (position != p)
        {
            if (next)
                next->Add(v, p);
            else
                next = new VirtualArray(v, p);
        }
        else
        {
            value.Copy(&v);
        }
        return 0;
    }

    void Clear()
    {
    }

    Complex & operator[](int p)
    {
        return value;
    }
};

////////////////////////////////////////////////////////////////////////////////

Variable * Variable::Create()
{
    return new Variable();
}

Variable * Variable::Copy(Variable * v)
{
    return this;
}

void Variable::ChooseOperands(Variable * p2, Variable ** op1, Variable ** op2)
{
    if (fiction)
    {
        (* op1) = this;
        (* op2) = p2;
    }
    else
    {
        (* op1) = (Create())->Copy(this);
        (* op1)->SetFiction(true);
        (* op2) = p2;
    }
}

////////////////////////////////////////////////////////////////////////////////

int Variable::Add(Variable * op1)
{
    return NOT_DETERMINED;
}

int Variable::Sub(Variable * op1)
{
    return NOT_DETERMINED;
}

int Variable::Mul(Variable * op1)
{
    return NOT_DETERMINED;
}

int Variable::Div(Variable * op1)
{
    return NOT_DETERMINED;
}

////////////////////////////////////////////////////////////////////////////////

int Variable::AddTo(Variable * op1)
{
    return NOT_DETERMINED;
}

int Variable::SubTo(Variable * op1)
{
    return NOT_DETERMINED;
}

int Variable::MulTo(Variable * op1)
{
    return NOT_DETERMINED;
}

int Variable::DivTo(Variable * op1)
{
    return NOT_DETERMINED;
}

////////////////////////////////////////////////////////////////////////////////

int Variable::operator+(int p1)
{
    return 0;
}

int Variable::operator-(int p1)
{
    return 0;
}

int Variable::operator*(int p1)
{
    return 0;
}

int Variable::operator/(int p1)
{
    return 0;
}


////////////////////////////////////////////////////////////////////////////////

double Variable::operator+(double p1)
{
    return 0;
}

double Variable::operator-(double p1)
{
    return 0;
}

double Variable::operator*(double p1)
{
    return 0;
}

double Variable::operator/(double p1)
{
    return 0;
}

////////////////////////////////////////////////////////////////////////////////

Variable & Variable::operator+(Variable & p1)
{
    Variable * op1 = NULL, * op2 = NULL;
    ChooseOperands(&p1, &op1, &op2);
    if (op1->Add(op2) == NOT_DETERMINED)
        op2->AddTo(op1);
    CheckFiction(op2);
    return (* op1);
}

Variable & Variable::operator-(Variable & p1)
{
    Variable * op1 = NULL, * op2 = NULL;
    ChooseOperands(&p1, &op1, &op2);
    if (op1->Sub(op2) == NOT_DETERMINED)
        op2->SubTo(op1);
    CheckFiction(op2);
    return (* op1);
}

Variable & Variable::operator*(Variable & p1)
{
    Variable * op1 = NULL, * op2 = NULL;
    ChooseOperands(&p1, &op1, &op2);
    if (op1->Mul(op2) == NOT_DETERMINED)
        op2->MulTo(op1);
    CheckFiction(op2);
    return (* op1);
}

Variable & Variable::operator/(Variable & p1)
{
    Variable * op1 = NULL, * op2 = NULL;
    ChooseOperands(&p1, &op1, &op2);
    if (op1->Div(op2) == NOT_DETERMINED)
        op2->DivTo(op1);
    CheckFiction(op2);
    return (* op1);
}

Variable & Variable::operator=(Variable & p1)
{
    Copy(&p1);
    CheckFiction(&p1);
    return (* this);
}

////////////////////////////////////////////////////////////////////////////////

int Integer::Add(Variable * op1)
{
    switch (op1->GetType())
    {
        case vtInteger:
            value += ((Integer *) op1)->GetValue();
        break;
        case vtDouble:
            value += (int) ((Double *) op1)->GetValue();
        break;
        default:
            return NOT_DETERMINED;
    }
    return 0;
}

int Integer::Sub(Variable * op1)
{
    switch (op1->GetType())
    {
        case vtInteger:
            value -= ((Integer *) op1)->GetValue();
        break;
        case vtDouble:
            value -= (int) ((Double *) op1)->GetValue();
        break;
        default:
            return NOT_DETERMINED;
    }
    return 0;
}

int Integer::Mul(Variable * op1)
{
    switch (op1->GetType())
    {
        case vtInteger:
            value *= ((Integer *) op1)->GetValue();
        break;
        case vtDouble:
            value *= (int) ((Double *) op1)->GetValue();
        break;
        default:
            return NOT_DETERMINED;
    }
    return 0;
}

int Integer::Div(Variable * op1)
{
    switch (op1->GetType())
    {
        case vtInteger:
            value /= ((Integer *) op1)->GetValue();
        break;
        case vtDouble:
            value /= (int) ((Double *) op1)->GetValue();
        break;
        default:
            return NOT_DETERMINED;
    }
    return 0;
}

////////////////////////////////////////////////////////////////////////////////


int Double::Add(Variable * op1)
{
    switch (op1->GetType())
    {
        case vtInteger:
            value += ((Integer *) op1)->GetValue();
        break;
        case vtDouble:
            value += ((Double *) op1)->GetValue();
        break;
        default:
            return NOT_DETERMINED;
    }
    return 0;
}

int Double::Sub(Variable * op1)
{
    switch (op1->GetType())
    {
        case vtInteger:
            value -= ((Integer *) op1)->GetValue();
        break;
        case vtDouble:
            value -= ((Double *) op1)->GetValue();
        break;
        default:
            return NOT_DETERMINED;
    }
    return 0;
}

int Double::Mul(Variable * op1)
{
    switch (op1->GetType())
    {
        case vtInteger:
            value *= ((Integer *) op1)->GetValue();
        break;
        case vtDouble:
            value *= ((Double *) op1)->GetValue();
        break;
        default:
            return NOT_DETERMINED;
    }
    return 0;
}

int Double::Div(Variable * op1)
{
    switch (op1->GetType())
    {
        case vtInteger:
            value /= ((Integer *) op1)->GetValue();
        break;
        case vtDouble:
            value /= ((Double *) op1)->GetValue();
        break;
        default:
            return NOT_DETERMINED;
    }
    return 0;
}

////////////////////////////////////////////////////////////////////////////////

CompMatrix::CompMatrix()
{
    type   = vtCompMatrix;
    index  = NULL;
    vector = NULL;
    m = 0;
    n = 0;
    maxQty = 0;
    curQty = 0;
    brQty  = 0;
    br[0]  = 0;
    br[1]  = 0;
}

CompMatrix::CompMatrix(int m0, int n0, int mq0)
{
    CompMatrix::CompMatrix();
    Init(m0, n0, mq0);
}

CompMatrix::~CompMatrix()
{
    if (index)
        delete[] index;
    if (vector)
        delete[] vector;
}

////////////////////////////////////////////////////////////////////////////////

void  CompMatrix::Init(int m0, int n0, int mq0)
{
    if (vector)
        delete[] vector;
    if (index)
        delete[] index;
    m = m0;
    n = n0;
    maxQty = mq0;
    index  = new pCompBlock[m];
    memset(index, 0, sizeof(pCompBlock)*m);
    vector = new CompBlock[maxQty];
}

////////////////////////////////////////////////////////////////////////////////

Complex & CompMatrix::GetValue()
{
    static Complex Blank;
    unsigned m0 = br[0], n0 = br[1];

    ResetBrackets();
    CompBlock * cp = index[m0];

    CompBlock * nextBlock = NULL;
    unsigned rowLen = 0;


    for (unsigned i=m0+1; i<m; i++)
        if (index[i])
        {
            nextBlock = index[i];
            break;
        }

    if (nextBlock)
        rowLen = unsigned(nextBlock - cp);
    else
        rowLen = curQty - unsigned(cp - vector);

    if (cp)
    {
        for (unsigned i=0; i<rowLen; i++)
            if (cp[i].nColumn == n0)
                return  cp[i].value;
    }
    Blank.Clear();
    return Blank;
}

////////////////////////////////////////////////////////////////////////////////

Complex & CompMatrix::SetValue()
{

    static Complex Blank;
    unsigned m0 = br[0], n0 = br[1];
    ResetBrackets();

    CompBlock * newBlock  = index[m0];
    CompBlock * nextBlock = NULL;
    unsigned rowLen = 0;

    for (unsigned i=m0+1; i<m; i++)
        if (index[i])
        {
            nextBlock = index[i];
            break;
        }

    if (newBlock)
    {
        if (nextBlock)
            rowLen = unsigned(nextBlock - newBlock);

        for (unsigned i=0; i<rowLen; i++)
            if (newBlock[i].nColumn == n0)
                return newBlock->value;

        if (curQty < maxQty)
        {
            memcpy(newBlock + 1, newBlock, ((curQty - (vector - newBlock) + 1) * sizeof(CompBlock)));
            for (unsigned i=m0+1; i<m; i++)
                if (index[i])
                    index[i]++;
            newBlock->nColumn = n0;
            newBlock->value.Clear();
            curQty++;
            return newBlock->value;
        }
        else
        {
            Blank.Clear();
            return Blank;
        }
    }
    else
    {
        if (curQty < maxQty)
        {
            if (nextBlock)
            {
                index[m0] = nextBlock;
                memcpy(nextBlock + 1, nextBlock, ((curQty - m0 +1 ) * sizeof(CompBlock)));
                index[m0]->value.Clear();
                for (unsigned i=m0+1; i<m; i++)
                    if (index[i])
                        index[i]++;
                curQty++;
                return index[m0]->value;
            }
            else
            {
                index[m0] = vector + curQty;
                vector[curQty].nColumn = n0;
                return vector[curQty++].value;
            }
        }
        else
        {
            Blank.Clear();
            return Blank;
        }
    }
}

CompMatrix & CompMatrix::operator[](unsigned p1)
{
    if (brQty < 2)
        br[brQty++] = p1;
    else
        ResetBrackets();
    return (* this);
}

////////////////////////////////////////////////////////////////////////////////

Variable * CompMatrix::Create()
{
    return new CompMatrix;
}

Variable * CompMatrix::Copy(Variable * p1)
{
    CompMatrix * cm1 = (CompMatrix *) p1;
    type = vtCompMatrix;
    Init(cm1->GetM(), cm1->GetN(), cm1->GetMaxQty());
    for (unsigned i=0; i<m; i++)
        if ((cm1->GetIndex())[i])
            index[i] = vector + ((cm1->GetIndex())[i] - cm1->GetVector());
    memcpy(vector, cm1->GetVector(), sizeof(CompBlock) * maxQty);
    curQty = cm1->GetCurQty();
    brQty  = 0;
    br[0]  = 0;
    br[1]  = 0;
    return (Variable *) this;
}

////////////////////////////////////////////////////////////////////////////////

int CompMatrix::Mul(Variable * op1)
{


    if (op1->GetType() == vtCompMatrix)
    {
        CompMatrix * cm1 = (CompMatrix *) op1;
        if (n == cm1->GetM())
        {
            CompMatrix * ncm = new CompMatrix(m, cm1->GetN(), MAX(maxQty, cm1->GetMaxQty()));
            for (unsigned i=0; i<m; i++)
            {
                for (unsigned j=0; j<cm1->GetN(); j++)
                {
                    Complex nc;
                    nc.SetAB(0, 0);

                    for (unsigned x=0; x<n; x++)
                    {
                        Complex c1 = (* this)[i][x].GetValue();
                        Complex c2 = (* cm1)[x][j].GetValue();
                        nc = nc + c1 * c2;
                    }


                    if (nc.GetA() || nc.GetB())
                        (* ncm)[i][j].SetValue() = nc;
                }
            }
            Copy(ncm);
            return 0;
        }
        else
            return 2;
    }
    else
        return NOT_DETERMINED;
}

////////////////////////////////////////////////////////////////////////////////

void CompMatrix::ReadFromFile(char * fn)
{
    ifstream inFile(fn);
    int rc = 0, cc = 0, mq = 0;
    inFile >> rc >> cc >> mq;
    Init(rc, cc, mq);
    for (int i=0; i<rc; i++)
    {
        for (int j=0; j<cc; j++)
        {
            double na = 0, nb = 0;
            char str[32];
            inFile >> na >> nb >> str;
            if ((na!=0) || (nb!=0))
                (* this)[i][j].SetValue().SetAB(na, nb);
        }
    }
}

////////////////////////////////////////////////////////////////////////////////

int main()
{
    CompMatrix cm1, cm2, cm3;
    unsigned nzc = 0;

    cm1.ReadFromFile("matrix");
    cm2.ReadFromFile("vector");

    cout << "Matrix: " << endl;
    cm1.Print();
    cout << "Vector: " << endl;
    cm2.Print();

    cm3 = cm1 * cm2;

    cout << "Matrix * Vector:" << endl;
    cm3.Print();

    for (unsigned i=0; i<cm3.GetM(); i++)
        for (unsigned j=0; j<cm3.GetN(); j++)
            if (cm3[i][j].GetValue().GetA() || cm3[i][j].GetValue().GetB())
                nzc++;

    cout << "Count of non-zero elements: " << nzc;

    getchar();

    return 0;
}