/* 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() */