/*

Copyright (C) 2005-2015 David Bateman

This file is part of Octave.

Octave 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.

Octave 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 Octave; see the file COPYING.  If not, see
<http://www.gnu.org/licenses/>.

*/

// This is the octave interface to ccolamd, which bore the copyright given
// in the help of the functions.

#ifdef HAVE_CONFIG_H
#  include <config.h>
#endif

#include <cstdlib>

#include <string>
#include <vector>

#include "ov.h"
#include "defun-dld.h"
#include "errwarn.h"
#include "pager.h"
#include "ov-re-mat.h"

#include "ov-re-sparse.h"
#include "ov-cx-sparse.h"

#include "oct-sparse.h"
#include "oct-locbuf.h"

#if defined (ENABLE_64)
#  define CCOLAMD_NAME(name) ccolamd_l ## name
#  define CSYMAMD_NAME(name) csymamd_l ## name
#else
#  define CCOLAMD_NAME(name) ccolamd ## name
#  define CSYMAMD_NAME(name) csymamd ## name
#endif

DEFUN_DLD (ccolamd, args, nargout,
           "-*- texinfo -*-\n\
@deftypefn  {} {@var{p} =} ccolamd (@var{S})\n\
@deftypefnx {} {@var{p} =} ccolamd (@var{S}, @var{knobs})\n\
@deftypefnx {} {@var{p} =} ccolamd (@var{S}, @var{knobs}, @var{cmember})\n\
@deftypefnx {} {[@var{p}, @var{stats}] =} ccolamd (@dots{})\n\
\n\
Constrained column approximate minimum degree permutation.\n\
\n\
@code{@var{p} = ccolamd (@var{S})} returns the column approximate minimum\n\
degree permutation vector for the sparse matrix @var{S}.  For a non-symmetric\n\
matrix @var{S}, @code{@var{S}(:, @var{p})} tends to have sparser\n\
LU@tie{}factors than @var{S}.\n\
@code{chol (@var{S}(:, @var{p})' * @var{S}(:, @var{p}))} also tends to be\n\
sparser than @code{chol (@var{S}' * @var{S})}.\n\
@code{@var{p} = ccolamd (@var{S}, 1)} optimizes the ordering for\n\
@code{lu (@var{S}(:, @var{p}))}.  The ordering is followed by a column\n\
elimination tree post-ordering.\n\
\n\
@var{knobs} is an optional 1-element to 5-element input vector, with a\n\
default value of @code{[0 10 10 1 0]} if not present or empty.  Entries not\n\
present are set to their defaults.\n\
\n\
@table @code\n\
@item @var{knobs}(1)\n\
if nonzero, the ordering is optimized for @code{lu (S(:, p))}.  It will be a\n\
poor ordering for @code{chol (@var{S}(:, @var{p})' * @var{S}(:, @var{p}))}.\n\
This is the most important knob for ccolamd.\n\
\n\
@item @var{knobs}(2)\n\
if @var{S} is m-by-n, rows with more than\n\
@code{max (16, @var{knobs}(2) * sqrt (n))} entries are ignored.\n\
\n\
@item @var{knobs}(3)\n\
columns with more than\n\
@code{max (16, @var{knobs}(3) * sqrt (min (@var{m}, @var{n})))} entries are\n\
ignored and ordered last in the output permutation\n\
(subject to the cmember constraints).\n\
\n\
@item @var{knobs}(4)\n\
if nonzero, aggressive absorption is performed.\n\
\n\
@item @var{knobs}(5)\n\
if nonzero, statistics and knobs are printed.\n\
\n\
@end table\n\
\n\
@var{cmember} is an optional vector of length @math{n}.  It defines the\n\
constraints on the column ordering.  If @code{@var{cmember}(j) = @var{c}},\n\
then column @var{j} is in constraint set @var{c} (@var{c} must be in the\n\
range 1 to n).  In the output permutation @var{p}, all columns in set 1\n\
appear first, followed by all columns in set 2, and so on.\n\
@code{@var{cmember} = ones (1,n)} if not present or empty.\n\
@code{ccolamd (@var{S}, [], 1 : n)} returns @code{1 : n}\n\
\n\
@code{@var{p} = ccolamd (@var{S})} is about the same as\n\
@code{@var{p} = colamd (@var{S})}.  @var{knobs} and its default values\n\
differ.  @code{colamd} always does aggressive absorption, and it finds an\n\
ordering suitable for both @code{lu (@var{S}(:, @var{p}))} and @code{chol\n\
(@var{S}(:, @var{p})' * @var{S}(:, @var{p}))}; it cannot optimize its\n\
ordering for @code{lu (@var{S}(:, @var{p}))} to the extent that\n\
@code{ccolamd (@var{S}, 1)} can.\n\
\n\
@var{stats} is an optional 20-element output vector that provides data\n\
about the ordering and the validity of the input matrix @var{S}.  Ordering\n\
statistics are in @code{@var{stats}(1 : 3)}.  @code{@var{stats}(1)} and\n\
@code{@var{stats}(2)} are the number of dense or empty rows and columns\n\
ignored by @sc{ccolamd} and @code{@var{stats}(3)} is the number of garbage\n\
collections performed on the internal data structure used by @sc{ccolamd}\n\
(roughly of size @code{2.2 * nnz (@var{S}) + 4 * @var{m} + 7 * @var{n}}\n\
integers).\n\
\n\
@code{@var{stats}(4 : 7)} provide information if CCOLAMD was able to\n\
continue.  The matrix is OK if @code{@var{stats}(4)} is zero, or 1 if\n\
invalid.  @code{@var{stats}(5)} is the rightmost column index that is\n\
unsorted or contains duplicate entries, or zero if no such column exists.\n\
@code{@var{stats}(6)} is the last seen duplicate or out-of-order row\n\
index in the column index given by @code{@var{stats}(5)}, or zero if no\n\
such row index exists.  @code{@var{stats}(7)} is the number of duplicate\n\
or out-of-order row indices.  @code{@var{stats}(8 : 20)} is always zero in\n\
the current version of @sc{ccolamd} (reserved for future use).\n\
\n\
The authors of the code itself are @nospell{S. Larimore, T. Davis}\n\
(Univ. of Florida) and @nospell{S. Rajamanickam} in collaboration with\n\
@nospell{J. Bilbert and E. Ng}.  Supported by the National Science Foundation\n\
@nospell{(DMS-9504974, DMS-9803599, CCR-0203270)}, and a grant from\n\
@nospell{Sandia} National Lab.\n\
See @url{http://www.cise.ufl.edu/research/sparse} for\n\
ccolamd, csymamd, amd, colamd, symamd, and other related orderings.\n\
@seealso{colamd, csymamd}\n\
@end deftypefn")
{
#ifdef HAVE_CCOLAMD

  int nargin = args.length ();

  if (nargin < 1 || nargin > 3)
    print_usage ();

  octave_value_list retval (nargout == 2 ? 2 : 1);
  int spumoni = 0;

  // Get knobs
  OCTAVE_LOCAL_BUFFER (double, knobs, CCOLAMD_KNOBS);
  CCOLAMD_NAME (_set_defaults) (knobs);

  // Check for user-passed knobs
  if (nargin > 1)
    {
      NDArray User_knobs = args(1).array_value ();
      int nel_User_knobs = User_knobs.numel ();

      if (nel_User_knobs > 0)
        knobs[CCOLAMD_LU] = (User_knobs(0) != 0);
      if (nel_User_knobs > 1)
        knobs[CCOLAMD_DENSE_ROW] = User_knobs(1);
      if (nel_User_knobs > 2)
        knobs[CCOLAMD_DENSE_COL] = User_knobs(2);
      if (nel_User_knobs > 3)
        knobs[CCOLAMD_AGGRESSIVE] = (User_knobs(3) != 0);
      if (nel_User_knobs > 4)
        spumoni = (User_knobs(4) != 0);

      // print knob settings if spumoni is set
      if (spumoni)
        {
          octave_stdout << "\nccolamd version " << CCOLAMD_MAIN_VERSION << "."
                        <<  CCOLAMD_SUB_VERSION << ", " << CCOLAMD_DATE
                        << ":\nknobs(1): " << User_knobs(0) << ", order for ";
          if (knobs[CCOLAMD_LU] != 0)
            octave_stdout << "lu (A)\n";
          else
            octave_stdout << "chol (A'*A)\n";

          if (knobs[CCOLAMD_DENSE_ROW] >= 0)
            octave_stdout << "knobs(2): " << User_knobs(1)
                          << ", rows with > max (16,"
                          << knobs[CCOLAMD_DENSE_ROW]
                          << "*sqrt (size(A,2)))"
                          << " entries removed\n";
          else
            octave_stdout << "knobs(2): " << User_knobs(1)
                          << ", no dense rows removed\n";

          if (knobs[CCOLAMD_DENSE_COL] >= 0)
            octave_stdout << "knobs(3): " << User_knobs(2)
                          << ", cols with > max (16,"
                          << knobs[CCOLAMD_DENSE_COL] << "*sqrt (size(A)))"
                          << " entries removed\n";
          else
            octave_stdout << "knobs(3): " << User_knobs(2)
                          << ", no dense columns removed\n";

          if (knobs[CCOLAMD_AGGRESSIVE] != 0)
            octave_stdout << "knobs(4): " << User_knobs(3)
                          << ", aggressive absorption: yes";
          else
            octave_stdout << "knobs(4): " << User_knobs(3)
                          << ", aggressive absorption: no";

          octave_stdout << "knobs(5): " << User_knobs(4)
                        << ", statistics and knobs printed\n";
        }
    }

  octave_idx_type n_row, n_col, nnz;
  octave_idx_type *ridx, *cidx;
  SparseComplexMatrix scm;
  SparseMatrix sm;

  if (args(0).is_sparse_type ())
    {
      if (args(0).is_complex_type ())
        {
          scm = args(0). sparse_complex_matrix_value ();
          n_row = scm.rows ();
          n_col = scm.cols ();
          nnz = scm.nnz ();
          ridx = scm.xridx ();
          cidx = scm.xcidx ();
        }
      else
        {
          sm = args(0).sparse_matrix_value ();

          n_row = sm.rows ();
          n_col = sm.cols ();
          nnz = sm.nnz ();
          ridx = sm.xridx ();
          cidx = sm.xcidx ();
        }
    }
  else
    {
      if (args(0).is_complex_type ())
        sm = SparseMatrix (real (args(0).complex_matrix_value ()));
      else
        sm = SparseMatrix (args(0).matrix_value ());

      n_row = sm.rows ();
      n_col = sm.cols ();
      nnz = sm.nnz ();
      ridx = sm.xridx ();
      cidx = sm.xcidx ();
    }

  // Allocate workspace for ccolamd
  OCTAVE_LOCAL_BUFFER (octave_idx_type, p, n_col+1);
  for (octave_idx_type i = 0; i < n_col+1; i++)
    p[i] = cidx[i];

  octave_idx_type Alen = CCOLAMD_NAME (_recommended) (nnz, n_row, n_col);
  OCTAVE_LOCAL_BUFFER (octave_idx_type, A, Alen);
  for (octave_idx_type i = 0; i < nnz; i++)
    A[i] = ridx[i];

  OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, CCOLAMD_STATS);

  if (nargin > 2)
    {
      NDArray in_cmember = args(2).array_value ();
      octave_idx_type cslen = in_cmember.numel ();
      OCTAVE_LOCAL_BUFFER (octave_idx_type, cmember, cslen);
      for (octave_idx_type i = 0; i < cslen; i++)
        // convert cmember from 1-based to 0-based
        cmember[i] = static_cast<octave_idx_type>(in_cmember(i) - 1);

      if (cslen != n_col)
        error ("ccolamd: CMEMBER must be of length equal to #cols of A");

      // Order the columns (destroys A)
      if (! CCOLAMD_NAME () (n_row, n_col, Alen, A, p, knobs, stats, cmember))
        {
          CCOLAMD_NAME (_report) (stats) ;

          error ("ccolamd: internal error!");
        }
    }
  else
    {
      // Order the columns (destroys A)
      if (! CCOLAMD_NAME () (n_row, n_col, Alen, A, p, knobs, stats, 0))
        {
          CCOLAMD_NAME (_report) (stats) ;

          error ("ccolamd: internal error!");
        }
    }

  // return the permutation vector
  NDArray out_perm (dim_vector (1, n_col));
  for (octave_idx_type i = 0; i < n_col; i++)
    out_perm(i) = p[i] + 1;

  retval(0) = out_perm;

  // print stats if spumoni > 0
  if (spumoni > 0)
    CCOLAMD_NAME (_report) (stats) ;

  // Return the stats vector
  if (nargout == 2)
    {
      NDArray out_stats (dim_vector (1, CCOLAMD_STATS));
      for (octave_idx_type i = 0 ; i < CCOLAMD_STATS ; i++)
        out_stats(i) = stats[i] ;
      retval(1) = out_stats;

      // fix stats (5) and (6), for 1-based information on
      // jumbled matrix.  note that this correction doesn't
      // occur if symamd returns FALSE
      out_stats (CCOLAMD_INFO1) ++ ;
      out_stats (CCOLAMD_INFO2) ++ ;
    }

  return retval;

#else
  err_disabled_feature ("ccolamd", "CCOLAMD");
#endif
}

DEFUN_DLD (csymamd, args, nargout,
           "-*- texinfo -*-\n\
@deftypefn  {} {@var{p} =} csymamd (@var{S})\n\
@deftypefnx {} {@var{p} =} csymamd (@var{S}, @var{knobs})\n\
@deftypefnx {} {@var{p} =} csymamd (@var{S}, @var{knobs}, @var{cmember})\n\
@deftypefnx {} {[@var{p}, @var{stats}] =} csymamd (@dots{})\n\
\n\
For a symmetric positive definite matrix @var{S}, return the permutation\n\
vector @var{p} such that @code{@var{S}(@var{p},@var{p})} tends to have a\n\
sparser Cholesky@tie{}factor than @var{S}.\n\
\n\
Sometimes @code{csymamd} works well for symmetric indefinite matrices too. \n\
The matrix @var{S} is assumed to be symmetric; only the strictly lower\n\
triangular part is referenced.  @var{S} must be square.  The ordering is\n\
followed by an elimination tree post-ordering.\n\
\n\
@var{knobs} is an optional 1-element to 3-element input vector, with a\n\
default value of @code{[10 1 0]}.  Entries not present are set to their\n\
defaults.\n\
\n\
@table @code\n\
@item @var{knobs}(1)\n\
If @var{S} is n-by-n, then rows and columns with more than\n\
@code{max(16,@var{knobs}(1)*sqrt(n))} entries are ignored, and ordered\n\
last in the output permutation (subject to the cmember constraints).\n\
\n\
@item @var{knobs}(2)\n\
If nonzero, aggressive absorption is performed.\n\
\n\
@item @var{knobs}(3)\n\
If nonzero, statistics and knobs are printed.\n\
\n\
@end table\n\
\n\
@var{cmember} is an optional vector of length n. It defines the constraints\n\
on the ordering.  If @code{@var{cmember}(j) = @var{S}}, then row/column j is\n\
in constraint set @var{c} (@var{c} must be in the range 1 to n).  In the\n\
output permutation @var{p}, rows/columns in set 1 appear first, followed\n\
by all rows/columns in set 2, and so on.  @code{@var{cmember} = ones (1,n)}\n\
if not present or empty.  @code{csymamd (@var{S},[],1:n)} returns @code{1:n}.\n\
\n\
@code{@var{p} = csymamd (@var{S})} is about the same as\n\
@code{@var{p} = symamd (@var{S})}.  @var{knobs} and its default values\n\
differ.\n\
\n\
@code{@var{stats}(4:7)} provide information if CCOLAMD was able to\n\
continue.  The matrix is OK if @code{@var{stats}(4)} is zero, or 1 if\n\
invalid.  @code{@var{stats}(5)} is the rightmost column index that is\n\
unsorted or contains duplicate entries, or zero if no such column exists.\n\
@code{@var{stats}(6)} is the last seen duplicate or out-of-order row\n\
index in the column index given by @code{@var{stats}(5)}, or zero if no\n\
such row index exists.  @code{@var{stats}(7)} is the number of duplicate\n\
or out-of-order row indices.  @code{@var{stats}(8:20)} is always zero in\n\
the current version of @sc{ccolamd} (reserved for future use).\n\
\n\
The authors of the code itself are @nospell{S. Larimore, T. Davis}\n\
(Univ. of Florida) and @nospell{S. Rajamanickam} in collaboration with\n\
@nospell{J. Bilbert and E. Ng}.  Supported by the National Science Foundation\n\
@nospell{(DMS-9504974, DMS-9803599, CCR-0203270)}, and a grant from\n\
@nospell{Sandia} National Lab.\n\
See @url{http://www.cise.ufl.edu/research/sparse} for\n\
ccolamd, csymamd, amd, colamd, symamd, and other related orderings.\n\
@seealso{symamd, ccolamd}\n\
@end deftypefn")
{
#if defined (HAVE_CCOLAMD)

  int nargin = args.length ();

  if (nargin < 1 || nargin > 3)
    print_usage ();

  octave_value_list retval (nargout == 2 ? 2 : 1);
  int spumoni = 0;

  // Get knobs
  OCTAVE_LOCAL_BUFFER (double, knobs, CCOLAMD_KNOBS);
  CCOLAMD_NAME (_set_defaults) (knobs);

  // Check for user-passed knobs
  if (nargin > 1)
    {
      NDArray User_knobs = args(1).array_value ();
      int nel_User_knobs = User_knobs.numel ();

      if (nel_User_knobs > 0)
        knobs[CCOLAMD_DENSE_ROW] = User_knobs(0);
      if (nel_User_knobs > 0)
        knobs[CCOLAMD_AGGRESSIVE] = User_knobs(1);
      if (nel_User_knobs > 1)
        spumoni = static_cast<int> (User_knobs(2));

      // print knob settings if spumoni is set
      if (spumoni)
        {
          octave_stdout << "\ncsymamd version " << CCOLAMD_MAIN_VERSION
                        << "." << CCOLAMD_SUB_VERSION
                        << ", " << CCOLAMD_DATE << "\n";

          if (knobs[CCOLAMD_DENSE_ROW] >= 0)
            octave_stdout << "knobs(1): " << User_knobs(0)
                          << ", rows/cols with > max (16,"
                          << knobs[CCOLAMD_DENSE_ROW]
                          << "*sqrt (size(A,2)))"
                          << " entries removed\n";
          else
            octave_stdout << "knobs(1): " << User_knobs(0)
                          << ", no dense rows/cols removed\n";

          if (knobs[CCOLAMD_AGGRESSIVE] != 0)
            octave_stdout << "knobs(2): " << User_knobs(1)
                          << ", aggressive absorption: yes";
          else
            octave_stdout << "knobs(2): " << User_knobs(1)
                          << ", aggressive absorption: no";


          octave_stdout << "knobs(3): " << User_knobs(2)
                        << ", statistics and knobs printed\n";
        }
    }

  octave_idx_type n_row, n_col;
  octave_idx_type *ridx, *cidx;
  SparseMatrix sm;
  SparseComplexMatrix scm;

  if (args(0).is_sparse_type ())
    {
      if (args(0).is_complex_type ())
        {
          scm = args(0).sparse_complex_matrix_value ();
          n_row = scm.rows ();
          n_col = scm.cols ();
          ridx = scm.xridx ();
          cidx = scm.xcidx ();
        }
      else
        {
          sm = args(0).sparse_matrix_value ();
          n_row = sm.rows ();
          n_col = sm.cols ();
          ridx = sm.xridx ();
          cidx = sm.xcidx ();
        }
    }
  else
    {
      if (args(0).is_complex_type ())
        sm = SparseMatrix (real (args(0).complex_matrix_value ()));
      else
        sm = SparseMatrix (args(0).matrix_value ());

      n_row = sm.rows ();
      n_col = sm.cols ();
      ridx = sm.xridx ();
      cidx = sm.xcidx ();
    }

  if (n_row != n_col)
    err_square_matrix_required ("csymamd", "S");

  // Allocate workspace for symamd
  OCTAVE_LOCAL_BUFFER (octave_idx_type, perm, n_col+1);
  OCTAVE_LOCAL_BUFFER (octave_idx_type, stats, CCOLAMD_STATS);

  if (nargin > 2)
    {
      NDArray in_cmember = args(2).array_value ();
      octave_idx_type cslen = in_cmember.numel ();
      OCTAVE_LOCAL_BUFFER (octave_idx_type, cmember, cslen);
      for (octave_idx_type i = 0; i < cslen; i++)
        // convert cmember from 1-based to 0-based
        cmember[i] = static_cast<octave_idx_type>(in_cmember(i) - 1);

      if (cslen != n_col)
        error ("csymamd: CMEMBER must be of length equal to #cols of A");

      if (! CSYMAMD_NAME () (n_col, ridx, cidx, perm, knobs, stats,
                             &calloc, &free, cmember, -1))
        {
          CSYMAMD_NAME (_report) (stats) ;

          error ("csymamd: internal error!") ;
        }
    }
  else
    {
      if (! CSYMAMD_NAME () (n_col, ridx, cidx, perm, knobs, stats,
                            &calloc, &free, 0, -1))
        {
          CSYMAMD_NAME (_report) (stats) ;

          error ("csymamd: internal error!") ;
        }
    }

  // return the permutation vector
  NDArray out_perm (dim_vector (1, n_col));
  for (octave_idx_type i = 0; i < n_col; i++)
    out_perm(i) = perm[i] + 1;

  retval(0) = out_perm;

  // print stats if spumoni > 0
  if (spumoni > 0)
    CSYMAMD_NAME (_report) (stats) ;

  // Return the stats vector
  if (nargout == 2)
    {
      NDArray out_stats (dim_vector (1, CCOLAMD_STATS));
      for (octave_idx_type i = 0 ; i < CCOLAMD_STATS ; i++)
        out_stats(i) = stats[i] ;
      retval(1) = out_stats;

      // fix stats (5) and (6), for 1-based information on
      // jumbled matrix.  note that this correction doesn't
      // occur if symamd returns FALSE
      out_stats (CCOLAMD_INFO1) ++ ;
      out_stats (CCOLAMD_INFO2) ++ ;
    }

  return retval;

#else
  err_disabled_feature ("csymamd", "CCOLAMD");
#endif
}