#include <iostream>
#include <vector>

using Matrix = std::vector<std::vector<double>>;

struct CRS
{
  std::vector<double> val;
  std::vector<int> colInd;
  std::vector<int> rowPtr;

  void print()
  {
    std::cout << "VAL: ";
    for(auto &value : val)
    {
      std::cout << value << " ";
    }
    std::cout << std::endl << std::endl;

    std::cout << "colInd: ";
    for(auto &value : colInd)
    {
      std::cout << value << " ";
    }
    std::cout << std::endl << std::endl;

    std::cout << "rowPtr: ";
    for(auto &value : rowPtr)
    {
      std::cout << value << " ";
    }
    std::cout << std::endl << std::endl;
  }
};

struct CCS
{
  std::vector<double> val;
  std::vector<int> rowInd;
  std::vector<int> colPtr;

    void print()
  {
    std::cout << "VAL: ";
    for(auto &value : val)
    {
      std::cout << value << " ";
    }
    std::cout << std::endl << std::endl;

    std::cout << "rowInd: ";
    for(auto &value : rowInd)
    {
      std::cout << value << " ";
    }
    std::cout << std::endl << std::endl;

    std::cout << "colPtr: ";
    for(auto &value : colPtr)
    {
      std::cout << value << " ";
    }
    std::cout << std::endl << std::endl;
  }
};

double getRandomDouble(double left, double right)
{
  return ((double)rand() / RAND_MAX) * (right-left) + left;
}

int getRandomInt(int left, int right)
{
  return (rand() % (right - left + 1)) + left;
}

CRS convertCRS(const Matrix& matrix)
{
  CRS crs;
  for(size_t i = 0; i < matrix.size(); ++i)
  {
    bool startedNew = false;
    for(size_t j = 0; j < matrix[i].size(); ++j)
    {
      if(matrix[i][j] != 0)
      {
        if(!startedNew)
        {
          startedNew = true;
          crs.rowPtr.push_back(crs.val.size() + 1);
        }
        crs.val.push_back(matrix[i][j]);
        crs.colInd.push_back(i + 1);
      }
    }
  }
  return crs;
}

CCS convertCCS(const Matrix& matrix)
{
  CCS ccs;
  size_t size = matrix.size();
  for(size_t j = 0; j < size; ++j)
  {
    bool startedNew = false;
    for(size_t i = 0; i < size; ++i)
    {
      if(matrix[i][j] != 0)
      {
        if(!startedNew)
        {
          startedNew = true;
          ccs.colPtr.push_back(ccs.val.size() + 1);
        }
        ccs.val.push_back(matrix[i][j]);
        ccs.rowInd.push_back(j + 1);
      }
    }
  }
  return ccs;
}

Matrix decompress(CCS& ccs)
{
  int size = ccs.rowInd.back();
  Matrix matrix(size, std::vector<double>(size, 0));
  for(int v_idx = 0; v_idx < ccs.val.size(); ++v_idx)
  {
    int column = 1;
    for(int i = 0; i < ccs.colPtr.size(); ++i)
    {
      if((v_idx + 1) > ccs.colPtr[i])
      {
        column = i;
      }
    }
    matrix[ccs.rowInd[v_idx]-1][column-1] = ccs.val[v_idx];
  }
  return matrix;
}

Matrix makeMatrix(size_t size, size_t numberOfRandomElements)
{
  Matrix matrix(size, std::vector<double>(size, 0));

  for(int i=0; i < size; ++i)
  {
    matrix[i][i] = getRandomDouble(1,2);
  }
  for(int i=0; i < numberOfRandomElements; ++i)
  {
    matrix[getRandomInt(0, size-1)][getRandomInt(0, size-1)] = getRandomDouble(0,1);
  }

  return matrix;
}

void printMatrix(Matrix const& matrix)
{
  for(auto &vec: matrix)
  {
    for(auto &el : vec)
    {
      std::cout << el << "\t\t";
    }
    std::cout << std::endl;
  }
}

int main(){
  srand(time(NULL));
  Matrix matrix = makeMatrix(5, 10);
  printMatrix(matrix);
  auto crs = convertCCS(matrix);
  auto m = decompress(crs);
  printMatrix(m);
  return 0;
}