spswap.c

/**************************************************************************
**
** Copyright (C) 1993 David E. Steward & Zbigniew Leyk, all rights reserved.
**
**			     Meschach Library
** 
** This Meschach Library is provided "as is" without any express 
** or implied warranty of any kind with respect to this software. 
** In particular the authors shall not be liable for any direct, 
** indirect, special, incidental or consequential damages arising 
** in any way from use of the software.
** 
** Everyone is granted permission to copy, modify and redistribute this
** Meschach Library, provided:
**  1.  All copies contain this copyright notice.
**  2.  All modified copies shall carry a notice stating who
**      made the last modification and the date of such modification.
**  3.  No charge is made for this software or works derived from it.  
**      This clause shall not be construed as constraining other software
**      distributed on the same medium as this software, nor is a
**      distribution fee considered a charge.
**
***************************************************************************/


/*
	Sparse matrix swap and permutation routines
	Modified Mon 09th Nov 1992, 08:50:54 PM
	to use Karen George's suggestion to use unordered rows
*/

static	char	rcsid[] = "$Id: spswap.c,v 1.3 1994/01/13 05:44:43 des Exp $";

#include	<stdio.h>
#include	<math.h>
#include        "sparse2.h"


#define	btos(x)	((x) ? "TRUE" : "FALSE")

/* scan_to -- updates scan (int) vectors to point to the last row in each
	column with row # <= max_row, if any */
#ifndef ANSI_C
void	scan_to(A, scan_row, scan_idx, col_list, max_row)
SPMAT	*A;
IVEC	*scan_row, *scan_idx, *col_list;
int	max_row;
#else
void	scan_to(SPMAT *A, IVEC *scan_row, IVEC *scan_idx, IVEC *col_list, 
		int max_row)
#endif
{
    int		col, idx, j_idx, row_num;
    SPROW	*r;
    row_elt	*e;

    if ( ! A || ! scan_row || ! scan_idx || ! col_list )
	error(E_NULL,"scan_to");
    if ( scan_row->dim != scan_idx->dim || scan_idx->dim != col_list->dim )
	error(E_SIZES,"scan_to");

    if ( max_row < 0 )
	return;

    if ( ! A->flag_col )
	sp_col_access(A);

    for ( j_idx = 0; j_idx < scan_row->dim; j_idx++ )
    {
	row_num = scan_row->ive[j_idx];
	idx = scan_idx->ive[j_idx];
	col = col_list->ive[j_idx];

	if ( col < 0 || col >= A->n )
	    error(E_BOUNDS,"scan_to");
	if ( row_num < 0 )
	{
	    idx = col;
	    continue;
	}
	r = &(A->row[row_num]);
	if ( idx < 0 )
	    error(E_INTERN,"scan_to");
	e = &(r->elt[idx]);
	if ( e->col != col )
	    error(E_INTERN,"scan_to");
	if ( idx < 0 )
	{
	    printf("scan_to: row_num = %d, idx = %d, col = %d\n",
		   row_num, idx, col);
	    error(E_INTERN,"scan_to");
	}
	/* if ( e->nxt_row <= max_row )
	    chase_col(A, col, &row_num, &idx, max_row); */
	while ( e->nxt_row >= 0 && e->nxt_row <= max_row )
	{
	    row_num = e->nxt_row;
	    idx = e->nxt_idx;
	    e = &(A->row[row_num].elt[idx]);
	}
	    
	/* printf("scan_to: computed j_idx = %d, row_num = %d, idx = %d\n",
	       j_idx, row_num, idx); */
	scan_row->ive[j_idx] = row_num;
	scan_idx->ive[j_idx] = idx;
    }
}

/* patch_col -- patches column access paths for fill-in */
#ifndef ANSI_C
void patch_col(A, col, old_row, old_idx, row_num, idx)
SPMAT	*A;
int	col, old_row, old_idx, row_num, idx;
#else
void patch_col(SPMAT *A, int col, int old_row, int old_idx, int row_num, 
	       int idx)
#endif
{
    SPROW	*r;
    row_elt	*e;
    
    if ( old_row >= 0 )
    {
	r = &(A->row[old_row]);
	old_idx = sprow_idx2(r,col,old_idx);
	e = &(r->elt[old_idx]);
	e->nxt_row = row_num;
	e->nxt_idx = idx;
    }
    else
    {
	A->start_row[col] = row_num;
	A->start_idx[col] = idx;
    }
}

/* chase_col -- chases column access path in column col, starting with
   row_num and idx, to find last row # in this column <= max_row
   -- row_num is returned; idx is also set by this routine
   -- assumes that the column access paths (possibly without the
   nxt_idx fields) are set up */
#ifndef ANSI_C
row_elt *chase_col(A, col, row_num, idx, max_row)
SPMAT	*A;
int	col, *row_num, *idx, max_row;
#else
row_elt *chase_col(const SPMAT *A, int col, int *row_num, int *idx, 
		   int max_row)
#endif
{
    int		old_idx, old_row, tmp_idx, tmp_row;
    SPROW	*r;
    row_elt	*e;
    
    if ( col < 0 || col >= A->n )
	error(E_BOUNDS,"chase_col");
    tmp_row = *row_num;
    if ( tmp_row < 0 )
    {
	if ( A->start_row[col] > max_row )
	{
	    tmp_row = -1;
	    tmp_idx = col;
	    return (row_elt *)NULL;
	}
	else
	{
	    tmp_row = A->start_row[col];
	    tmp_idx = A->start_idx[col];
	}
    }
    else
	tmp_idx = *idx;
    
    old_row = tmp_row;
    old_idx = tmp_idx;
    while ( tmp_row >= 0 && tmp_row < max_row )
    {
	r = &(A->row[tmp_row]);
	/* tmp_idx = sprow_idx2(r,col,tmp_idx); */
	if ( tmp_idx < 0 || tmp_idx >= r->len ||
	     r->elt[tmp_idx].col != col )
	{
#ifdef DEBUG
	    printf("chase_col:error: col = %d, row # = %d, idx = %d\n",
		   col, tmp_row, tmp_idx);
	    printf("chase_col:error: old_row = %d, old_idx = %d\n",
		   old_row, old_idx);
	    printf("chase_col:error: A =\n");
	    sp_dump(stdout,A);
#endif
	    error(E_INTERN,"chase_col");
	}
	e = &(r->elt[tmp_idx]);
	old_row = tmp_row;
	old_idx = tmp_idx;
	tmp_row = e->nxt_row;
	tmp_idx = e->nxt_idx;
    }
    if ( old_row > max_row )
    {
	old_row = -1;
	old_idx = col;
	e = (row_elt *)NULL;
    }
    else if ( tmp_row <= max_row && tmp_row >= 0 )
    {
	old_row = tmp_row;
	old_idx = tmp_idx;
    }

    *row_num = old_row;
    if ( old_row >= 0 )
	*idx = old_idx;
    else
	*idx = col;

    return e;
}

/* chase_past -- as for chase_col except that we want the first
	row whose row # >= min_row; -1 indicates no such row */
#ifndef ANSI_C
row_elt *chase_past(A, col, row_num, idx, min_row)
SPMAT	*A;
int	col, *row_num, *idx, min_row;
#else
row_elt *chase_past(const SPMAT *A, int col, int *row_num, int *idx, 
		    int min_row)
#endif
{
    SPROW	*r;
    row_elt	*e;
    int		tmp_idx, tmp_row;

    tmp_row = *row_num;
    tmp_idx = *idx;
    chase_col(A,col,&tmp_row,&tmp_idx,min_row);
    if ( tmp_row < 0 )	/* use A->start_row[..] etc. */
    {
	if ( A->start_row[col] < 0 )
	    tmp_row = -1;
	else
	{
	    tmp_row = A->start_row[col];
	    tmp_idx = A->start_idx[col];
	}
    }
    else if ( tmp_row < min_row )
    {
	r = &(A->row[tmp_row]);
	if ( tmp_idx < 0 || tmp_idx >= r->len ||
	     r->elt[tmp_idx].col != col )
	    error(E_INTERN,"chase_past");
	tmp_row = r->elt[tmp_idx].nxt_row;
	tmp_idx = r->elt[tmp_idx].nxt_idx;
    }

    *row_num = tmp_row;
    *idx = tmp_idx;
    if ( tmp_row < 0 )
	e = (row_elt *)NULL;
    else
    {
	if ( tmp_idx < 0 || tmp_idx >= A->row[tmp_row].len ||
	     A->row[tmp_row].elt[tmp_idx].col != col )
	    error(E_INTERN,"bump_col");
	e = &(A->row[tmp_row].elt[tmp_idx]);
    }

    return e;
}

/* bump_col -- move along to next nonzero entry in column col after row_num
	-- update row_num and idx */
#ifndef ANSI_C
row_elt *bump_col(A, col, row_num, idx)
SPMAT	*A;
int	col, *row_num, *idx;
#else
row_elt *bump_col(const SPMAT *A, int col, int *row_num, int *idx)
#endif
{
    SPROW	*r;
    row_elt	*e;
    int		tmp_row, tmp_idx;

    tmp_row = *row_num;
    tmp_idx = *idx;
    /* printf("bump_col: col = %d, row# = %d, idx = %d\n",
	   col, *row_num, *idx); */
    if ( tmp_row < 0 )
    {
	tmp_row = A->start_row[col];
	tmp_idx = A->start_idx[col];
    }
    else
    {
	r = &(A->row[tmp_row]);
	if ( tmp_idx < 0 || tmp_idx >= r->len ||
	     r->elt[tmp_idx].col != col )
	    error(E_INTERN,"bump_col");
	e = &(r->elt[tmp_idx]);
	tmp_row = e->nxt_row;
	tmp_idx = e->nxt_idx;
    }
    if ( tmp_row < 0 )
    {
	e = (row_elt *)NULL;
	tmp_idx = col;
    }
    else
    {
	if ( tmp_idx < 0 || tmp_idx >= A->row[tmp_row].len ||
	     A->row[tmp_row].elt[tmp_idx].col != col )
	    error(E_INTERN,"bump_col");
	e = &(A->row[tmp_row].elt[tmp_idx]);
    }
    *row_num = tmp_row;
    *idx = tmp_idx;

    return e;
}