C++ Upper Triangular Matrix Bracket Operator

Question

I've hit a road block with a certain project of mine. I want to create an Upper Triangle Matrix (all elements below the diagonal are zero) that allocates only the memory necessary to hold the nonzero elements. The problem that I'm having is indexing into this matrix. I would rather not have to redesign the matrix, but if that is the only solution, then I can accept it. As a side note, the Vector is my own implementation, not the stl Vector.

So far I have the class declared as follows:

template <class T>
class UMatrix : public AbstractMatrix<T>
{
  private:
    Vector<T>* m_data;
    int m_size;
  public:
    //lots of member functions
};

The constructor of the Upper Triangle Matrix:

template <class T>
UMatrix<T>(const int size)
{
  m_size = size;

  if(size < 1)
    throw(RangeErr(size));

  m_data = new Vector<T> [size];
  for(int i = 0; i < size; i++)
  {
    Vector<T> init(i + 1);
    m_data[i] = init;
  }
}

And the code that I'm having trouble with:

template <class T>
Vector<T>& operator[] (const int index)
{
  if(m_data != NULL && index >= 0 && index < m_rows)
  {
    // Insert dark magic here
  }
  else
  {
    throw(RangeErr(index));
  }
}

This results in an array of staggered vectors, each vector being 1 length larger than the previous.

I am attempting to implement the bracket operator such that UMatrix[a][b] accesses row a, column b of the true Upper Triangular Matrix. This means that UMatrix[a][b] == 0 when a > b.

The bracket operator is also a virtual function from the abstract base class, and must return a Vector&. Also, this implementation must use the bracket operator, not the function () operator, so that it is compatible with previously written code. I am aware that it would be simpler to use a dense matrix, but I am limited to only necessary memory usage.

My first attempt involved using one vector for storage, similar to a 1d array matrix. However, the bracket operator is also seemingly impossible to write for that implementation as well.

My question: is it even possible to implement this bracket operator?

Answer 1

Well, I don't know if this is accepted solution since you have not provided anything about Vector class. You can create another class let's call it SparseVector<U>, where you will have the code like this

virtual U& operator[](int i) {
    if(m_data != nullptr) {
        if(m_nnzb <= i && i <= m_nnze) {
            return m_data[i - m_nnzb];
        }
    }
    throw std::runtime_error("bad index: in SparseVector::operator[]");
}

Here the idea of this implementation. This is a vector of size m_size where we store only non-zero elements in range from m_nnzb to m_nnze. And we use this class for subscript operator in matrix class. Here is the full code with small example.

#include <iostream>
#include <exception>
#include <stdexcept>

/* vector interface */
template<typename T>
class IVector {
public:
    virtual T& operator[](int i) = 0;
};

/* matrix interface */
template<typename T>
class IMatrix {
public:
    virtual IVector<T>& operator[](int i) = 0;
};

/* implementation for upper triangular matrix */
template<typename T>
class UpperMatrix : public IMatrix<T> {
public:
    /* implementation for sparse vector */
    template<typename U>
    class SparseVector : public IVector<U> {
    public:
        SparseVector() {
            m_size = m_nnzb = m_nnze = 0;
            m_data = nullptr;
        }
        SparseVector(int size, int b, int e) {
            m_size = size;
            m_nnzb = b;
            m_nnze = e;
            m_data = new U[e - b];
        }
        SparseVector(const SparseVector<U>& other) {
            m_size = other.m_size;
            m_nnzb = other.m_nnzb;
            m_nnze = other.m_nnze;
            m_data = new U[m_nnze - m_nnzb];
            for(int i = 0; i < m_nnze - m_nnzb; ++i) {
                m_data[i] = other.m_data[i];
            }
        }
        virtual U& operator[](int i) {
            if(m_data != nullptr) {
                if(m_nnzb <= i && i <= m_nnze) {
                    return m_data[i - m_nnzb];
                }
            }
            throw std::runtime_error("bad index: in SparseVector::operator[]");
        }
    protected:
        int m_size;
        int m_nnzb;
        int m_nnze;
        U*  m_data;
    };
    UpperMatrix(int n) {
        m_size = n;
        m_data = new SparseVector<T>[n];
        for(int i = 0; i < n; ++i) {
            m_data[i] = SparseVector<T>(n, i, n);
        }
    }
    virtual IVector<T>& operator[](int i) {
        if(i < m_size && m_data != nullptr) {
            return m_data[i];
        }
        throw std::runtime_error("bad index in UpperMatrix::operator[]");
    }
protected:
    int              m_size;
    SparseVector<T>* m_data;
};

int main(int argc, char** argv) {
    UpperMatrix<int> m1(3);
    /* correct index */
    for(int i = 0; i < 3; ++i) {
        for(int j = i; j < 3; ++j) {
            m1[i][j] = i + j;
        }
    }
    for(int i = 0; i < 3; ++i) {
        for(int j = i; j < 3; ++j) {
            std::cout << m1[i][j] << " ";
        }
        std::cout << std::endl;
    }
    /* incorrect index */
    try {
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                m1[i][j] = i + j;
            }
        }
    } catch(const std::exception& ex) {
        std::cout << "error occured: " << ex.what() << std::endl;
    }
}

Answer 2

The professor changed the project specifications to allow for the parenthesis operator overload. This is the best method available to solve this problem.