/* ========================================================================== */
  /* === UMFPACK_triplet_to_col =============================================== */
  /* ========================================================================== */
  
  /* -------------------------------------------------------------------------- */
  /* UMFPACK Copyright (c) Timothy A. Davis, CISE,                              */
  /* Univ. of Florida.  All Rights Reserved.  See ../Doc/License for License.   */
  /* web: http://www.cise.ufl.edu/research/sparse/umfpack                       */
  /* -------------------------------------------------------------------------- */
  
  /*
      User callable.  Converts triplet input to column-oriented form.  Duplicate
      entries may exist (they are summed in the output).  The columns of the
      column-oriented form are in sorted order.  The input is not modified.
      Returns 1 if OK, 0 if an error occurred.  See umfpack_triplet_to_col.h for
      details.
  
      If Map is present (a non-NULL pointer to an Int array of size nz), then on
      output it holds the position of the triplets in the column-form matrix.
      That is, suppose p = Map [k], and the k-th triplet is i=Ti[k], j=Tj[k], and
      aij=Tx[k].  Then i=Ai[p], and aij will have been summed into Ax[p].  Also,
      Ap[j] <= p < Ap[j+1].  The Map array is not computed if it is (Int *) NULL.
  
      Dynamic memory usage:
  
  	If numerical values are present, then one (two for complex version)
  	workspace of size (nz+1)*sizeof(double) is allocated via UMF_malloc.
  	Next, 4 calls to UMF_malloc are made to obtain workspace of size
  	((nz+1) + (n_row+1) + n_row + MAX (n_row,n_col)) * sizeof(Int).  All of
  	this workspace (4 to 6 objects) are free'd via UMF_free on return.
  
  	For the complex version, additional space is allocated.
  
  	An extra array of size nz*sizeof(Int) is allocated if Map is present.
  */
  
  #include "umf_internal.h"
  #include "umf_malloc.h"
  #include "umf_free.h"
  #include "umf_triplet.h"
  
  #ifndef NDEBUG
  PRIVATE Int init_count ;
  #endif
  
  /* ========================================================================== */
  
  GLOBAL Int UMFPACK_triplet_to_col
  (
      Int n_row,
      Int n_col,
      Int nz,
      const Int Ti [ ],		/* size nz */
      const Int Tj [ ],		/* size nz */
      const double Tx [ ],	/* size nz */
  #ifdef COMPLEX
      const double Tz [ ],	/* size nz */
  #endif
      Int Ap [ ],			/* size n_col + 1 */
      Int Ai [ ],			/* size nz */
      double Ax [ ]		/* size nz */
  #ifdef COMPLEX
      , double Az [ ]		/* size nz */
  #endif
      , Int Map [ ]		/* size nz */
  )
  {
  
      /* ---------------------------------------------------------------------- */
      /* local variables */
      /* ---------------------------------------------------------------------- */
  
      Int *RowCount, *Rp, *Rj, *W, nn, do_values, do_map, *Map2, status ;
      double *Rx ;
  #ifdef COMPLEX
      double *Rz ;
      Int split ;
  #endif
  
  #ifndef NDEBUG
      UMF_dump_start ( ) ;
      init_count = UMF_malloc_count ;
  #endif
  
      /* ---------------------------------------------------------------------- */
      /* check inputs */
      /* ---------------------------------------------------------------------- */
  
      if (!Ai || !Ap || !Ti || !Tj)
      {
  	return (UMFPACK_ERROR_argument_missing) ;
      }
  
      if (n_row <= 0 || n_col <= 0)		/* must be > 0 */
      {
  	return (UMFPACK_ERROR_n_nonpositive) ;
      }
  
      if (nz < 0)		/* nz must be >= 0 (singular matrices are OK) */
      {
  	return (UMFPACK_ERROR_invalid_matrix) ;
      }
  
      nn = MAX (n_row, n_col) ;
  
      /* ---------------------------------------------------------------------- */
      /* allocate workspace */
      /* ---------------------------------------------------------------------- */
  
      Rx = (double *) NULL ;
  
      do_values = Ax && Tx ;
  
      if (do_values)
      {
  #ifdef COMPLEX
  	Rx = (double *) UMF_malloc (2*nz+2, sizeof (double)) ;
  	split = SPLIT (Tz) && SPLIT (Az) ;
  	if (split)
  	{
  	    Rz = Rx + nz ;
  	}
  	else
  	{
  	    Rz = (double *) NULL ;
  	}
  #else
  	Rx = (double *) UMF_malloc (nz+1, sizeof (double)) ;
  #endif
  	if (!Rx)
  	{
  	    DEBUGm4 (("out of memory: triplet work 
  ")) ;
  	    ASSERT (UMF_malloc_count == init_count) ;
  	    return (UMFPACK_ERROR_out_of_memory) ;
  	}
      }
  
      do_map = (Map != (Int *) NULL) ;
      Map2 = (Int *) NULL ;
      if (do_map)
      {
  	DEBUG0 (("Do map:
  ")) ;
  	Map2 = (Int *) UMF_malloc (nz+1, sizeof (Int)) ;
  	if (!Map2)
  	{
  	    DEBUGm4 (("out of memory: triplet map
  ")) ;
  	    (void) UMF_free ((void *) Rx) ;
  	    ASSERT (UMF_malloc_count == init_count) ;
  	    return (UMFPACK_ERROR_out_of_memory) ;
  	}
      }
  
      Rj = (Int *) UMF_malloc (nz+1, sizeof (Int)) ;
      Rp = (Int *) UMF_malloc (n_row+1, sizeof (Int)) ;
      RowCount = (Int *) UMF_malloc (n_row, sizeof (Int)) ;
      W = (Int *) UMF_malloc (nn, sizeof (Int)) ;
      if (!Rj || !Rp || !RowCount || !W)
      {
  	DEBUGm4 (("out of memory: triplet work (int)
  ")) ;
  	(void) UMF_free ((void *) Rx) ;
  	(void) UMF_free ((void *) Map2) ;
  	(void) UMF_free ((void *) Rp) ;
  	(void) UMF_free ((void *) Rj) ;
  	(void) UMF_free ((void *) RowCount) ;
  	(void) UMF_free ((void *) W) ;
  	ASSERT (UMF_malloc_count == init_count) ;
  	return (UMFPACK_ERROR_out_of_memory) ;
      }
  
      ASSERT (UMF_malloc_count == init_count + 4 +
  	(Rx != (double *) NULL) + do_map) ;
  
      /* ---------------------------------------------------------------------- */
      /* convert from triplet to column form */
      /* ---------------------------------------------------------------------- */
  
      if (do_map)
      {
  	if (do_values)
  	{
  	    status = UMF_triplet_map_x (n_row, n_col, nz, Ti, Tj, Ap, Ai, Rp,
  		Rj, W, RowCount, Tx, Ax, Rx
  #ifdef COMPLEX
  		, Tz, Az, Rz
  #endif
  		, Map, Map2) ;
  	}
  	else
  	{
  	    status = UMF_triplet_map_nox (n_row, n_col, nz, Ti, Tj, Ap, Ai, Rp,
  		Rj, W, RowCount, Map, Map2) ;
  	}
      }
      else
      {
  	if (do_values)
  	{
  	    status = UMF_triplet_nomap_x (n_row, n_col, nz, Ti, Tj, Ap, Ai, Rp,
  		Rj, W, RowCount , Tx, Ax, Rx
  #ifdef COMPLEX
  		, Tz, Az, Rz
  #endif
  		) ;
  	}
  	else
  	{
  	    status = UMF_triplet_nomap_nox (n_row, n_col, nz, Ti, Tj, Ap, Ai,
  		Rp, Rj, W, RowCount) ;
  	}
      }
  
      /* ---------------------------------------------------------------------- */
      /* free the workspace */
      /* ---------------------------------------------------------------------- */
  
      (void) UMF_free ((void *) Rx) ;
      (void) UMF_free ((void *) Map2) ;
      (void) UMF_free ((void *) Rp) ;
      (void) UMF_free ((void *) Rj) ;
      (void) UMF_free ((void *) RowCount) ;
      (void) UMF_free ((void *) W) ;
      ASSERT (UMF_malloc_count == init_count) ;
  
      return (status) ;
  }