/* spcompress.c

 * 

 * Copyright (C) 2012-2014, 2016 Patrick Alken

 * 

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 3 of the License, or (at

 * your option) any later version.

 * 

 * This program is distributed in the hope that it will be useful, but

 * WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * General Public License for more details.

 * 

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

 */

#include <config.h>

#include <stdlib.h>

#include <math.h>

#include <gsl/gsl_math.h>

#include <gsl/gsl_errno.h>

#include <gsl/gsl_spmatrix.h>

/*

gsl_spmatrix_ccs()

  Create a sparse matrix in compressed column format

Inputs: T - sparse matrix in triplet format

Return: pointer to new matrix (should be freed when finished with it)

*/

gsl_spmatrix *

gsl_spmatrix_ccs(const gsl_spmatrix *T)

{

  if (!GSL_SPMATRIX_ISTRIPLET(T))

    {

      GSL_ERROR_NULL("matrix must be in triplet format", GSL_EINVAL);

    }

  else

    {

      const size_t *Tj; /* column indices of triplet matrix */

      size_t *Cp;       /* column pointers of compressed column matrix */

      size_t *w;        /* copy of column pointers */

      gsl_spmatrix *m;

      size_t n;

      m = gsl_spmatrix_alloc_nzmax(T->size1, T->size2, T->nz,

                                   GSL_SPMATRIX_CCS);

      if (!m)

        return NULL;

      Tj = T->p;

      Cp = m->p;

      /* initialize column pointers to 0 */

      for (n = 0; n < m->size2 + 1; ++n)

        Cp[n] = 0;

      /*

       * compute the number of elements in each column:

       * Cp[j] = # non-zero elements in column j

       */

      for (n = 0; n < T->nz; ++n)

        Cp[Tj[n]]++;

      /* compute column pointers: p[j] = p[j-1] + nnz[j-1] */

      gsl_spmatrix_cumsum(m->size2, Cp);

      /* make a copy of the column pointers */

      w = m->work_sze;

      for (n = 0; n < m->size2; ++n)

        w[n] = Cp[n];

      /* transfer data from triplet format to CCS */

      for (n = 0; n < T->nz; ++n)

        {

          size_t k = w[Tj[n]]++;

          m->i[k] = T->i[n];

          m->data[k] = T->data[n];

        }

      m->nz = T->nz;

      return m;

    }

}

gsl_spmatrix *

gsl_spmatrix_compcol(const gsl_spmatrix *T)

{

  return gsl_spmatrix_ccs(T);

}

/*

gsl_spmatrix_crs()

  Create a sparse matrix in compressed row format

Inputs: T - sparse matrix in triplet format

Return: pointer to new matrix (should be freed when finished with it)

*/

gsl_spmatrix *

gsl_spmatrix_crs(const gsl_spmatrix *T)

{

  if (!GSL_SPMATRIX_ISTRIPLET(T))

    {

      GSL_ERROR_NULL("matrix must be in triplet format", GSL_EINVAL);

    }

  else

    {

      const size_t *Ti; /* row indices of triplet matrix */

      size_t *Cp;       /* row pointers of compressed row matrix */

      size_t *w;        /* copy of column pointers */

      gsl_spmatrix *m;

      size_t n;

      m = gsl_spmatrix_alloc_nzmax(T->size1, T->size2, T->nz,

                                   GSL_SPMATRIX_CRS);

      if (!m)

        return NULL;

      Ti = T->i;

      Cp = m->p;

      /* initialize row pointers to 0 */

      for (n = 0; n < m->size1 + 1; ++n)

        Cp[n] = 0;

      /*

       * compute the number of elements in each row:

       * Cp[i] = # non-zero elements in row i

       */

      for (n = 0; n < T->nz; ++n)

        Cp[Ti[n]]++;

      /* compute row pointers: p[i] = p[i-1] + nnz[i-1] */

      gsl_spmatrix_cumsum(m->size1, Cp);

      /* make a copy of the row pointers */

      w = m->work_sze;

      for (n = 0; n < m->size1; ++n)

        w[n] = Cp[n];

      /* transfer data from triplet format to CRS */

      for (n = 0; n < T->nz; ++n)

        {

          size_t k = w[Ti[n]]++;

          m->i[k] = T->p[n];

          m->data[k] = T->data[n];

        }

      m->nz = T->nz;

      return m;

    }

}

/*

gsl_spmatrix_cumsum()

Compute the cumulative sum:

p[j] = Sum_{k=0...j-1} c[k]

0 <= j < n + 1

Alternatively,

p[0] = 0

p[j] = p[j - 1] + c[j - 1]

Inputs: n - length of input array

        c - (input/output) array of size n + 1

            on input, contains the n values c[k]

            on output, contains the n + 1 values p[j]

Return: success or error

*/

void

gsl_spmatrix_cumsum(const size_t n, size_t *c)

{

  size_t sum = 0;

  size_t k;

  for (k = 0; k < n; ++k)

    {

      size_t ck = c[k];

      c[k] = sum;

      sum += ck;

    }

  c[n] = sum;

} /* gsl_spmatrix_cumsum() */