/* glpios04.c (operations on sparse vectors) */

/***********************************************************************

*  This code is part of GLPK (GNU Linear Programming Kit).

*

*  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,

*  2009, 2010 Andrew Makhorin, Department for Applied Informatics,

*  Moscow Aviation Institute, Moscow, Russia. All rights reserved.

*  E-mail: <mao@gnu.org>.

*

*  GLPK 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.

*

*  GLPK 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 GLPK. If not, see <http://www.gnu.org/licenses/>.

***********************************************************************/

#include "glpios.h"

/***********************************************************************

*  NAME

*

*  ios_create_vec - create sparse vector

*

*  SYNOPSIS

*

*  #include "glpios.h"

*  IOSVEC *ios_create_vec(int n);

*

*  DESCRIPTION

*

*  The routine ios_create_vec creates a sparse vector of dimension n,

*  which initially is a null vector.

*

*  RETURNS

*

*  The routine returns a pointer to the vector created. */

IOSVEC *ios_create_vec(int n)

{     IOSVEC *v;

      xassert(n >= 0);

      v = xmalloc(sizeof(IOSVEC));

      v->n = n;

      v->nnz = 0;

      v->pos = xcalloc(1+n, sizeof(int));

      memset(&v->pos[1], 0, n * sizeof(int));

      v->ind = xcalloc(1+n, sizeof(int));

      v->val = xcalloc(1+n, sizeof(double));

      return v;

}

/***********************************************************************

*  NAME

*

*  ios_check_vec - check that sparse vector has correct representation

*

*  SYNOPSIS

*

*  #include "glpios.h"

*  void ios_check_vec(IOSVEC *v);

*

*  DESCRIPTION

*

*  The routine ios_check_vec checks that a sparse vector specified by

*  the parameter v has correct representation.

*

*  NOTE

*

*  Complexity of this operation is O(n). */

void ios_check_vec(IOSVEC *v)

{     int j, k, nnz;

      xassert(v->n >= 0);

      nnz = 0;

      for (j = v->n; j >= 1; j--)

      {  k = v->pos[j];

         xassert(0 <= k && k <= v->nnz);

         if (k != 0)

         {  xassert(v->ind[k] == j);

            nnz++;

         }

      }

      xassert(v->nnz == nnz);

      return;

}

/***********************************************************************

*  NAME

*

*  ios_get_vj - retrieve component of sparse vector

*

*  SYNOPSIS

*

*  #include "glpios.h"

*  double ios_get_vj(IOSVEC *v, int j);

*

*  RETURNS

*

*  The routine ios_get_vj returns j-th component of a sparse vector

*  specified by the parameter v. */

double ios_get_vj(IOSVEC *v, int j)

{     int k;

      xassert(1 <= j && j <= v->n);

      k = v->pos[j];

      xassert(0 <= k && k <= v->nnz);

      return (k == 0 ? 0.0 : v->val[k]);

}

/***********************************************************************

*  NAME

*

*  ios_set_vj - set/change component of sparse vector

*

*  SYNOPSIS

*

*  #include "glpios.h"

*  void ios_set_vj(IOSVEC *v, int j, double val);

*

*  DESCRIPTION

*

*  The routine ios_set_vj assigns val to j-th component of a sparse

*  vector specified by the parameter v. */

void ios_set_vj(IOSVEC *v, int j, double val)

{     int k;

      xassert(1 <= j && j <= v->n);

      k = v->pos[j];

      if (val == 0.0)

      {  if (k != 0)

         {  /* remove j-th component */

            v->pos[j] = 0;

            if (k < v->nnz)

            {  v->pos[v->ind[v->nnz]] = k;

               v->ind[k] = v->ind[v->nnz];

               v->val[k] = v->val[v->nnz];

            }

            v->nnz--;

         }

      }

      else

      {  if (k == 0)

         {  /* create j-th component */

            k = ++(v->nnz);

            v->pos[j] = k;

            v->ind[k] = j;

         }

         v->val[k] = val;

      }

      return;

}

/***********************************************************************

*  NAME

*

*  ios_clear_vec - set all components of sparse vector to zero

*

*  SYNOPSIS

*

*  #include "glpios.h"

*  void ios_clear_vec(IOSVEC *v);

*

*  DESCRIPTION

*

*  The routine ios_clear_vec sets all components of a sparse vector

*  specified by the parameter v to zero. */

void ios_clear_vec(IOSVEC *v)

{     int k;

      for (k = 1; k <= v->nnz; k++)

         v->pos[v->ind[k]] = 0;

      v->nnz = 0;

      return;

}

/***********************************************************************

*  NAME

*

*  ios_clean_vec - remove zero or small components from sparse vector

*

*  SYNOPSIS

*

*  #include "glpios.h"

*  void ios_clean_vec(IOSVEC *v, double eps);

*

*  DESCRIPTION

*

*  The routine ios_clean_vec removes zero components and components

*  whose magnitude is less than eps from a sparse vector specified by

*  the parameter v. If eps is 0.0, only zero components are removed. */

void ios_clean_vec(IOSVEC *v, double eps)

{     int k, nnz;

      nnz = 0;

      for (k = 1; k <= v->nnz; k++)

      {  if (fabs(v->val[k]) == 0.0 || fabs(v->val[k]) < eps)

         {  /* remove component */

            v->pos[v->ind[k]] = 0;

         }

         else

         {  /* keep component */

            nnz++;

            v->pos[v->ind[k]] = nnz;

            v->ind[nnz] = v->ind[k];

            v->val[nnz] = v->val[k];

         }

      }

      v->nnz = nnz;

      return;

}

/***********************************************************************

*  NAME

*

*  ios_copy_vec - copy sparse vector (x := y)

*

*  SYNOPSIS

*

*  #include "glpios.h"

*  void ios_copy_vec(IOSVEC *x, IOSVEC *y);

*

*  DESCRIPTION

*

*  The routine ios_copy_vec copies a sparse vector specified by the

*  parameter y to a sparse vector specified by the parameter x. */

void ios_copy_vec(IOSVEC *x, IOSVEC *y)

{     int j;

      xassert(x != y);

      xassert(x->n == y->n);

      ios_clear_vec(x);

      x->nnz = y->nnz;

      memcpy(&x->ind[1], &y->ind[1], x->nnz * sizeof(int));

      memcpy(&x->val[1], &y->val[1], x->nnz * sizeof(double));

      for (j = 1; j <= x->nnz; j++)

         x->pos[x->ind[j]] = j;

      return;

}

/***********************************************************************

*  NAME

*

*  ios_linear_comb - compute linear combination (x := x + a * y)

*

*  SYNOPSIS

*

*  #include "glpios.h"

*  void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y);

*

*  DESCRIPTION

*

*  The routine ios_linear_comb computes the linear combination

*

*     x := x + a * y,

*

*  where x and y are sparse vectors, a is a scalar. */

void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y)

{     int j, k;

      double xj, yj;

      xassert(x != y);

      xassert(x->n == y->n);

      for (k = 1; k <= y->nnz; k++)

      {  j = y->ind[k];

         xj = ios_get_vj(x, j);

         yj = y->val[k];

         ios_set_vj(x, j, xj + a * yj);

      }

      return;

}

/***********************************************************************

*  NAME

*

*  ios_delete_vec - delete sparse vector

*

*  SYNOPSIS

*

*  #include "glpios.h"

*  void ios_delete_vec(IOSVEC *v);

*

*  DESCRIPTION

*

*  The routine ios_delete_vec deletes a sparse vector specified by the

*  parameter v freeing all the memory allocated to this object. */

void ios_delete_vec(IOSVEC *v)

{     /* delete sparse vector */

      xfree(v->pos);

      xfree(v->ind);

      xfree(v->val);

      xfree(v);

      return;

}

/* eof */