#include "BSprivate.h"

/*+ BSrows_2_inode - Put the row numbers into the efficient parallel structure

    Input Parameters:
.   A - the original sparse matrix
.   gnum - global numbering of the rows
.   l_perm - local permutation of the rows
.   l_iperm - inverse of the local permutation of the rows
.   perm_row - permuted index into the original sparse matrix
.   col_iA - i-node structure
.   col_cA - clique structure
.   key_arr - add to permutation (see BSperm_rows)
.   i_number - numbering of the i-nodes
.   i_distr - distribution of the numbering of the i-nodes
.   procinfo - the usual processor stuff

    Output Parameters:
.   col_iA - updated to contain row numbers from A

    Returns:
    int

 +*/

typedef	struct	__key_list {
	int	data;
	struct	__key_list	*next;
} key_list;
typedef	struct	__row_list {
	int	count;
	key_list	*list;
} row_list;

#include "BStree.h"

#define DROP_KEY_IN_TREE(tree,keyval,row_val,row_len,row_num_ptr) \
{ \
	int	found99, dummy99=0; \
	BStree_ptr	node_ptr99; \
	row_list	*row_list_ptr99; \
	key_list	*tptr99; \
	if (row_len[keyval] >= 1) { \
		MY_INSERT_TREE_NODE(tree,row_val[keyval],found99,node_ptr99,dummy99); \
		row_list_ptr99 = (row_list *) MY_GET_TREE_DATA(node_ptr99); \
		if (found99) { \
			row_list_ptr99->count++; \
		} else { \
			row_list_ptr99->count = 1; \
			row_list_ptr99->list = NULL; \
		} \
		tptr99 = &(row_num_ptr[keyval]); \
		tptr99->next = row_list_ptr99->list; \
		tptr99->data = keyval; \
		row_list_ptr99->list = tptr99; \
	} \
}

int BSrows_2_inode(BSspmat *A, BSnumbering *gnum, BSpermutation *l_perm,
	BSpermutation *l_iperm, BSsprow **perm_row, BSinode_list *col_iA,
	BScl_2_inode *col_cA, BSkey_arr *key_arr, BSnumbering *i_number,
	BSdistribution *i_distr, BSprocinfo *procinfo)
{
	BStree	tree;
	BStree_ptr	node_ptr;
	row_list	*row_list_ptr;
	key_list	*tptr;
	int	found, curkey;
	int	i, j, count;
	BSsprow *row;
	int	*col_ptr;
	int	row_gnum;
	int	*row_len, *row_num, *row_ind, *row_val, *row_inum, *row_size;
	key_list	*row_num_ptr;
	int	cl_ind, in_ind, clique_len, inode_len;
	BSinode *inode;
	int	cur_col, t_con, ind;
	int	done;
	int	curlen;

	/* set up the row sorting stuff, recall that we use i-node to simplify */
	MY_MALLOCN(row_len,(int *),sizeof(int)*(i_distr->max+1),2);
	MY_MALLOCN(row_ind,(int *),sizeof(int)*(i_distr->max+1),3);
	MY_MALLOCN(row_num_ptr,(key_list *),sizeof(key_list)*(i_distr->max+1),4);
	MY_MALLOCN(row_num,(int *),sizeof(int)*(i_distr->max+1),4);
	MY_MALLOCN(row_inum,(int *),sizeof(int)*(i_distr->max+1),5);
	MY_MALLOCN(row_val,(int *),sizeof(int)*(i_distr->max+1),6);
	MY_MALLOCN(row_size,(int *),sizeof(int)*(i_distr->max+1),7);
	MY_INIT_TREE(tree,sizeof(row_list));
	i = 0;
	for (count=0;count<=i_distr->max;count++) {
		row_inum[count] = i;
		row_ind[count] = 0;
		row_val[count] = key_arr->array[i_number->numbers[l_iperm->perm[i]]][0];
		row_size[count] = 
			i_distr->distribution[i_number->numbers[l_iperm->perm[i]]];
		row = perm_row[i];
		col_ptr = row->col;
		(*A->map->flocal2global)(1,&(l_iperm->perm[i]),&row_gnum,
			procinfo,A->map); CHKERRN(0);
		if(A->icc_storage) {
			row_len[count] = -1;
			for (j=0;j<row->length;j++) {
				if (row_gnum == col_ptr[j]) {
					row_len[count] = j+1;
					break;
				}
			}
		} else {
			row_len[count] = row->length;
		}
		DROP_KEY_IN_TREE(tree,count,row_val,row_len,row_num_ptr);
		i += row_size[count];
	}

	/* get the first list of row numbers */
	MY_FIRST_IN_TREE(tree,node_ptr);
	if (! IS_TREE_PTR_NULL(node_ptr)) {
		done = FALSE;
		row_list_ptr = (row_list *) MY_GET_TREE_DATA(node_ptr);
		tptr = row_list_ptr->list;
		curlen = row_list_ptr->count;
		for (i=0;i<curlen;i++) {
			row_num[i] = tptr->data;
			tptr = tptr->next;
		}
		curkey = row_val[row_num[0]];
		BSiheap_sort1(curlen,row_num,row_inum); CHKERRN(0);
	} else {
		done = TRUE;
	}
	/* end of getting row numbers */

	/* initialize the clique and inode indices */
	cl_ind = 0;
	in_ind = 0;
	clique_len = col_cA->d_mats[cl_ind].size;

	/* now, place column numbers into inode structure */
	/* we are doing 1 column/inode at a time */
	/* we are keeping the rows sorted by two keys: 1)next col #, 2)row # */
	/* row_num tells us what the sorted row number is and row_len */
	/* tells how many columns are left in the row and row_ind tells */
	/* us which col we are looking at within a row */
	/* the only thing which is REALLY moved during a sort is row_num */
	while (! done) {
		if (col_iA->length <= in_ind) {
			MY_SETERRCN(INODE_ERROR,"Too many inodes\n");
		}

		/* find the inode */
		inode = &(col_iA->list[in_ind]);
		inode_len = inode->num_cols;

		/* count the number of connections to the inode */
		cur_col = row_val[row_num[0]];
		t_con = row_size[row_num[0]];
		count = curlen; /* we get curlen from Msort_list */
		for (i=1;i<curlen;i++) {
			t_con+=row_size[row_num[i]];
		}
		inode->length = t_con;

		/* Are we local or global? */
		if (col_cA->proc[cl_ind] == procinfo->my_id) {
			/* put the first part of the values that are in the clique */
			/* nowhere, because we don't need indices for these values */
			/* put the rest of the values into the inode */
			if(A->icc_storage) {
				i = 0;
				t_con = 0;
				while (t_con < clique_len) {
					ind = row_num[i];
					/* just ignore this part */
					t_con += row_size[ind];
					row_ind[ind] += inode_len;
					row_len[ind] -= inode_len;
					if (row_len[ind] > 0) {
						row_val[ind] = 
							key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
							[row_ind[ind]];
					} else {
						row_val[ind] = INT_MAX;
					}
					i++;
				}
				inode->length -= t_con;
				/* allocate space in the inode */
				MY_MALLOCN(inode->row_num,(int *),sizeof(int)*inode->length,8);
				MY_MALLOCN(inode->nz,(FLOAT *),sizeof(FLOAT)*inode->length*
					inode_len,9);
				t_con = 0;
				for (i=i;i<count;i++) {
					ind = row_num[i];
					/* insert all of the row inode into this column inode */
					for (j=0;j<row_size[ind];j++) {
						inode->row_num[t_con] = row_inum[ind]+j;
						t_con++;
					}
					row_ind[ind] += inode_len;
					row_len[ind] -= inode_len;
					if (row_len[ind] > 0) {
						row_val[ind] = 
							key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
							[row_ind[ind]];
					} else {
						row_val[ind] = INT_MAX;
					}
				}
				clique_len -= inode_len;
			} else {
				/* allocate space in the inode */
				/* now the space allocated is a bit more than necessary (ILU) */
				MY_MALLOCN(inode->row_num,(int *),sizeof(int)*inode->length,8);
				MY_MALLOCN(inode->nz,(FLOAT *),sizeof(FLOAT)*inode->length*
					inode_len,9);
				t_con = 0;
				inode->below_diag = 0;
				for (i=0;i<count;i++) {
					ind = row_num[i];
					row_gnum = gnum->numbers[l_iperm->perm[row_inum[ind]]];
					if (row_gnum < col_cA->g_offset[cl_ind]) {
						inode->below_diag = t_con + row_size[ind];
					}
					if ((row_gnum >= col_cA->g_offset[cl_ind]) &
						(row_gnum <  col_cA->g_offset[cl_ind+1])) {
						/* don't put in diag entry into inode->row_num (ILU) */
						row_ind[ind] += inode_len;
						row_len[ind] -= inode_len;
						if (row_len[ind] > 0) {
							row_val[ind] = 
								key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
								[row_ind[ind]];
						} else {
							row_val[ind] = INT_MAX;
						}
						inode->length -= row_size[ind];
					} else {
						/* insert all of the row inode into this column inode */
						for (j=0;j<row_size[ind];j++) {
							inode->row_num[t_con] = row_inum[ind]+j;
							t_con++;
						}
						row_ind[ind] += inode_len;
						row_len[ind] -= inode_len;
						if (row_len[ind] > 0) {
							row_val[ind] = 
							key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
							[row_ind[ind]];
						} else {
							row_val[ind] = INT_MAX;
						}
					}
				}
				clique_len -= inode_len;
			}
		} else {
			/* allocate space in the inode */
			MY_MALLOCN(inode->row_num,(int *),sizeof(int)*inode->length,10);
			MY_MALLOCN(inode->nz,(FLOAT *),sizeof(FLOAT)*inode->length*
				inode_len,11);
			/* put all values into the inode, (no non-local cliques) */
			t_con = 0;
			inode->below_diag = 0;
			for (i=0;i<count;i++) {
				ind = row_num[i];
				row_gnum = gnum->numbers[l_iperm->perm[row_inum[ind]]];
				if (row_gnum < col_cA->g_offset[cl_ind]) {
					inode->below_diag = t_con + row_size[ind];
				}
				/* insert all of the row inode into this column inode */
				for (j=0;j<row_size[ind];j++) {
					inode->row_num[t_con] = row_inum[ind]+j;
					t_con++;
				}
				row_ind[ind] += inode_len;
				row_len[ind] -= inode_len;
				if (row_len[ind] > 0) {
					row_val[ind] = 
						key_arr->array[i_number->numbers[l_iperm->perm[row_inum[ind]]]]
						[row_ind[ind]];
				} else {
					row_val[ind] = INT_MAX;
				}
			}
		}
		/* get the next list of row numbers */
		/* free up the current list of row numbers */
		for (i=0;i<curlen;i++) {
			DROP_KEY_IN_TREE(tree,row_num[i],row_val,row_len,row_num_ptr);
		}
		MY_SEARCH_TREE(tree,curkey,found,node_ptr);
		MY_NEXT_IN_TREE(node_ptr);
		if (! IS_TREE_PTR_NULL(node_ptr)) {
			done = FALSE;
			row_list_ptr = (row_list *) MY_GET_TREE_DATA(node_ptr);
			tptr = row_list_ptr->list;
			curlen = row_list_ptr->count;
			for (i=0;i<curlen;i++) {
				row_num[i] = tptr->data;
				tptr = tptr->next;
			}
			curkey = row_val[row_num[0]];
			BSiheap_sort1(curlen,row_num,row_inum); CHKERRN(0);
		} else {
			done = TRUE;
		}
		/* end of getting row numbers */

		/* update clique/inode indices */
		in_ind++;
		if (in_ind >= col_cA->inode_index[cl_ind+1]) {
			cl_ind++;
			clique_len = col_cA->d_mats[cl_ind].size;
		}
	}

	/* free up sorting vectors */
	MY_FREE_TREE(tree);
	MY_FREEN(row_len);
	MY_FREEN(row_ind);
	MY_FREEN(row_num);
	MY_FREEN(row_num_ptr);
	MY_FREEN(row_inum);
	MY_FREEN(row_val);
	MY_FREEN(row_size);

	return(0);
}