Goal: Implement matrix compression in the way we last discussed in the multidimensional arrays session $($with offset for each row$),$ as well as a function to retrieve an element from the compressed content. in C$++$

Briefly:

All non$-$zero elements $($and only them!$)$ from the matrix are placed in a linear array, with an "offset" calculated for the elements of each row.

The offset for the first row is always $0.$

The offset for each subsequent row is the smallest possible such that no element of this row coincides with any element of the previous rows.

The offset for each subsequent row is AT LEAST as much as that of the previous row.

A few examples:

$01000100//$ offset$=0$

$02000200//$ offset$=1$

$0003->0003//$ offset$=1$

$40054005//$ offset$=3$

$-------------$

$0124305$

$40054005//$ offset$=0$

$01000100//$ offset$=0$

$0003->0003//$ offset$=1$

$02000200//$ offset$=1$

$---------$

$41253$

$0200502005$

$6709067090$

$10300->10300$

$0008000080$

$1000410004$

$-----------------------$

$026759113804$

$6709067090$

$0200502005$

$00080->00080$

$1000410004$

$1030010300$

$-----------------------$

$672985110340$

For this, use the following implementation skeleton, and put whatever code you deem necessary in each place marked with FIXME. Modifying the existing part of the code is prohibited.

$//$ Contains everything needed for full$-$fledged work of a compressed matrix WITHOUT keeping a copy of the original.

struct SparseMatrix $\{$

$//$ FIXME

$\}$;

$//$ Allocates memory for the compressed representation $+$ any necessary auxiliary information,

$//$ performs the compression, and returns a structure containing all the data.

$//$ IMPORTANT: we cannot precompute how much memory will be needed for compression

$//=>$ for the purposes of this assignment, you can allocate an array of size numRowsnumCols, and populate it$.$

SparseMatrix makeSparse$($const int mat, const int numRows, const int numCols$)\{$

$//$ FIXME

$\}$

$//$ Returns the element at the given position in the original matrix.

int get$($const SparseMatrix& sm$,$ const int row, const int col$)\{$

$//$ FIXME: check if row and col are valid indices

return sm$.$data$[$sm$.$offsets$[$row$]+$ col$]$;

$\}$

$//$ Frees the memory allocated in makeSparse$()$ and stored in the member data of sm$.$

void freeSparse$($SparseMatrix& sm$)\{$

$//$ FIXME

$\}$

Tip: calculating the offsets and populating the linear array don't necessarily have to be separate steps :$)$

You can use the following two functions to test your solutions:

#include

int testEasy$($const int$*$ mat, const int numRows, const int numCols$)\{$

SparseMatrix sm $=$ makeSparse$($mat$,$ numRows, numCols$)$;

for $($int i $=0$; i $<$ numRows; $++$i$)\{$

for $($int j $=0$; i $<$ numCols; $++$j$)\{$

assert$($mat$[$i$][$j$]==0||$ mat$[$i$][$j$]==$ get$($sm$,$ i$,$ j$))$;

$\}$

$\}$

freeSparse$($sm$)$;

$\}$

int testHard$($const int$*$ mat, const int numRows, const int numCols$)\{$

SparseMatrix sm $=$ makeSparse$($mat$,$ numRows, numCols$)$;

for $($int i $=0$; i $<$ numRows; $++$i$)\{$

for $($int j $=0$; i $<$ numCols; $++$j$)\{$

$//$ Problem: if mat$[$i$][$j$]==0,$ in the compressed representation this hole might

$//$ have been filled by an element from a different row :$($

$//$ How can we distinguish them with as little additional information as possible, stored in the SparseMatrix object?

assert$($mat$[$i$][$j$]==$ get$($sm$,$ i$,$ j$))$;

$\}$

$\}$

freeSparse$($sm$)$;

$\}$