CODEWITHSUNDEEP
c++algorithmmatrixdata-structuressparse-matrix
Andrei Gabor
Andrei Gabor

Reputation: 231

Sparse matrix compressed on rows in C++

I have to implement the CSR matrix data structure in C++ using 3 dynamic arrays (indexing starts at 0) and I've got stuck. So I have to implement 2 functions:

1) modify(int i, int j, TElem e) - modifies the value of (i,j) to e or adds if (if it does not exist) or deletes it if e is null.

2) element(int i, int j) const - returns the value found on (i,j)

I wanted to test my code in the next way:

Matrix m(4,4); m.print(); It will print:

Lines: 0 0 0 0 0

Columns:

Values:

(And this is fine)

Now if I want to modify: m.modify(1,1,5); //The element (1,1) will be set to 5

The output of m.print(); will be:

Lines: 0 1 1 1 1

Columns: 1

Values: 5 (which again is fine)

And now if I want to print m.element(1, 1) it will return 0 and m.element(0, 1) will return 5.

This is my implementation of element(int i, int j) :

    int currCol;
    for (int pos = this->lines[i]; pos < this->lines[i+1]; pos++) {
        currCol = this->columns[pos];
        if (currCol == j)
            return this->values[pos];
        else if (currCol > j)
            break;
    }
    return NULL_TELEM;

The constructor looks like this:

Matrix::Matrix(int nrLines, int nrCols) {
    if (nrLines <= 0 || nrCols <= 0)
        throw exception();
    this->nr_lines = nrLines;
    this->nr_columns = nrCols;
    this->values = new TElem[100];
    this->values_capacity = 1;
    this->values_size = 0; 
    this->lines = new int[nrLines + 1];
    this->columns = new TElem[100];
    this->columns_capacity = 1;
    this->columns_size = 0; 
    for (int i = 0; i <= nrLines; i++)
        this->lines[i] = NULL_TELEM;
}

This is the "modify" method:

TElem Matrix::modify(int i, int j, TElem e) {
    if (i < 0 || j < 0 || i >= this->nr_lines || j >= nr_columns)
        throw exception();
    int pos = this->lines[i];
    int currCol = 0;
    for (; pos < this->lines[i + 1]; i++) {
        currCol = this->columns[pos];
        if (currCol >= j)
            break;
    }
    if (currCol != j) {
        if (!(e == 0)) 
            add(pos, i, j, e);
    }
    else if (e == 0)
        remove(pos, i);
    else
        this->values[pos] = e;
    return NULL_TELEM;
}

And this is the inserting method:

void Matrix::add(int index, int line, int column, TElem value)
{
    this->columns_size++;
    this->values_size++;
    for (int i = this->columns_size; i >= index + 1; i--) {
        this->columns[i] = this->columns[i - 1];
        this->values[i] = this->values[i - 1];
    }
    this->columns[index] = column;
    this->values[index] = value;
    for (int i = line; i <= this->nr_lines; i++) //changed to i = line + 1;
        this->lines[i]++;
}

Can somebody help me, please? I can't figure out why this happens and I really need to finish this implementation these days.

It just can't pass the next test. And if I want to print the elements i have (4,0)=0 (4,1)=0 ... (4,8)=0 and (4,9)=3. Now this looks pretty weird why it happens.

void testModify() {
    cout << "Test modify" << endl;
    Matrix m(10, 10);
    for (int j = 0; j < m.nrColumns(); j++)
        m.modify(4, j, 3);
    for (int i = 0; i < m.nrLines(); i++)
        for (int j = 0; j < m.nrColumns(); j++)
            if (i == 4)
                assert(m.element(i, j) == 3);
                //cout << i << " " << j << ":" << m.element(i, j)<<'\n';
            else
                assert(m.element(i, j) == NULL_TELEM);
}

Upvotes: 0

Views: 380

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

When you call modify(1, 1, 5) with an empty matrix (all zeros), that results in a call to add(0, 1, 1, 5). That increments columns_size and values_size (both to 1), the for loop body will not execute, you update columns[0] to 1 and values[0] to 5, then increment all the lines values starting at element lines[1], setting them all to 1 (lines[0] will still be 0). But lines[1] should indicate the element we just added, so it should be 0, since the value is found using columns[0].

The for loop at the end of add should start at element line + 1.

Upvotes: 1

Related Questions