#ifndef SPARSE_H
#define SPARSE_H

/*
 *  sparse.h -- sparse matrix package header file
 */

typedef struct sm_element_struct sm_element;
typedef struct sm_row_struct sm_row;
typedef struct sm_col_struct sm_col;
typedef struct sm_matrix_struct sm_matrix;

/*
 *  sparse matrix element
 */
struct sm_element_struct {
    int row_num;          /* row number of this element */
    int col_num;          /* column number of this element */
    sm_element *next_row; /* next row in this column */
    sm_element *prev_row; /* previous row in this column */
    sm_element *next_col; /* next column in this row */
    sm_element *prev_col; /* previous column in this row */
    char *user_word;      /* user-defined word */
};

/*
 *  row header
 */
struct sm_row_struct {
    int row_num;           /* the row number */
    int length;            /* number of elements in this row */
    int flag;              /* user-defined word */
    sm_element *first_col; /* first element in this row */
    sm_element *last_col;  /* last element in this row */
    sm_row *next_row;      /* next row (in sm_matrix linked list) */
    sm_row *prev_row;      /* previous row (in sm_matrix linked list) */
    char *user_word;       /* user-defined word */
};

/*
 *  column header
 */
struct sm_col_struct {
    int col_num;           /* the column number */
    int length;            /* number of elements in this column */
    int flag;              /* user-defined word */
    sm_element *first_row; /* first element in this column */
    sm_element *last_row;  /* last element in this column */
    sm_col *next_col;      /* next column (in sm_matrix linked list) */
    sm_col *prev_col;      /* prev column (in sm_matrix linked list) */
    char *user_word;       /* user-defined word */
};

/*
 *  A sparse matrix
 */
struct sm_matrix_struct {
    sm_row **rows;     /* pointer to row headers (by row #) */
    int rows_size;     /* alloc'ed size of above array */
    sm_col **cols;     /* pointer to column headers (by col #) */
    int cols_size;     /* alloc'ed size of above array */
    sm_row *first_row; /* first row (linked list of all rows) */
    sm_row *last_row;  /* last row (linked list of all rows) */
    int nrows;         /* number of rows */
    sm_col *first_col; /* first column (linked list of columns) */
    sm_col *last_col;  /* last column (linked list of columns) */
    int ncols;         /* number of columns */
    char *user_word;   /* user-defined word */
};

#define sm_get_col(A, colnum)                                         \
    (((colnum) >= 0 && (colnum) < (A)->cols_size) ? (A)->cols[colnum] \
                                                  : (sm_col *)0)

#define sm_get_row(A, rownum)                                         \
    (((rownum) >= 0 && (rownum) < (A)->rows_size) ? (A)->rows[rownum] \
                                                  : (sm_row *)0)

#define sm_foreach_row(A, prow) \
    for (prow = A->first_row; prow != 0; prow = prow->next_row)

#define sm_foreach_col(A, pcol) \
    for (pcol = A->first_col; pcol != 0; pcol = pcol->next_col)

#define sm_foreach_row_element(prow, p) \
    for (p = prow->first_col; p != 0; p = p->next_col)

/* matrix.c */
sm_matrix *sm_alloc();
void sm_free(sm_matrix *A);
sm_matrix *sm_dup(sm_matrix *A);
void sm_resize(sm_matrix *A, int row, int col);
sm_element *sm_insert(sm_matrix *A, int row, int col);
void sm_delrow(sm_matrix *A, int i);
void sm_delcol(sm_matrix *A, int i);
void sm_cleanup();

/* rows.c */
sm_row *sm_row_alloc();
void sm_row_free(sm_row *prow);
sm_row *sm_row_dup(sm_row *prow);
sm_element *sm_row_insert(sm_row *prow, int col);
void sm_row_remove(sm_row *prow, int col);
int sm_row_contains(sm_row *p1, sm_row *p2);
int sm_row_intersects(sm_row *p1, sm_row *p2);

/* cols.c */
sm_col *sm_col_alloc();
void sm_col_free(sm_col *pcol);
int sm_col_contains(sm_col *p1, sm_col *p2);
/* dominate.c */
int sm_row_dominance(sm_matrix *A);
int sm_col_dominance(sm_matrix *A, int *weight);

/* part.c */
int sm_block_partition(sm_matrix *A, sm_matrix **L, sm_matrix **R);

#endif
