#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE  25
typedef enum {head,entry} tagfield;
typedef struct MatrixNode *MatrixPointer;
	struct EntryNode {
			 int row;
			 int col;
			 int value;
	};
	struct MatrixNode {
			  MatrixPointer down;
			  MatrixPointer right;
			  tagfield tag;
			  union {
				MatrixPointer next;
				struct EntryNode entry;
			  } u;
	};
MatrixPointer HdNode[MAX_SIZE];
MatrixPointer mread(void);
void mwrite(MatrixPointer);
void merase(MatrixPointer *node);

int main()
{
    MatrixPointer a,b,c;
    a = mread();
    mwrite(a);
    merase(&a);
    if (!a)
      printf("The matrix has been erased.\n");
}

MatrixPointer mread(void)
{/* read in a matrix and set up its linked representation.
An auxilliary global array HdNode is used */
  int NumRows, NumCols,  NumEntries, NumHeads, i;
  int row, col, value, CurrentRow;
  MatrixPointer temp,last,node;

  printf("Enter the number of rows, columns and entries: ");
  scanf("%d,%d,%d",&NumRows, &NumCols, &NumEntries);
  NumHeads = (NumCols > NumRows) ? NumCols : NumRows;
  /* set up head node for the list of head nodes */
  node = (MatrixPointer)malloc(sizeof(struct MatrixNode));
  node->tag = entry;
  node->u.entry.row = NumRows;
  node->u.entry.col = NumCols;

  if (!NumHeads)
     node->right = node;
  else {
     /* initialize the head nodes */
     for (i = 0; i < NumHeads; i++) {
       temp = (MatrixPointer)malloc(sizeof(struct MatrixNode));
       HdNode[i] = temp;
       HdNode[i]->tag = head;
       HdNode[i]->right = temp;
       HdNode[i]->u.next = temp;
     }
     CurrentRow = 0;
     last = HdNode[0];
     for (i = 0; i < NumEntries; i++) {
       printf("Enter row, column and value: ");
       scanf("%d,%d,%d",&row,&col,&value);
       if (row > CurrentRow) {
	      last->right = HdNode[CurrentRow]; 
	      CurrentRow = row;
	      last = HdNode[row];
       }
       temp = (MatrixPointer)malloc(sizeof(struct MatrixNode));
       temp->tag = entry;
       temp->u.entry.row = row;
       temp->u.entry.col = col;
       temp->u.entry.value = value;
       last->right = temp;          /* link into row list */
       last = temp;
       HdNode[col]->u.next->down = temp;  /* link into column list */
       HdNode[col]->u.next = temp;
     }
     /*close last row */
     last->right = HdNode[CurrentRow];
     /* close all column lists */
     for (i = 0; i < NumCols; i++)
	    HdNode[i]->u.next->down = HdNode[i];
     /* link all head nodes together */
     for (i = 0; i < NumHeads-1; i++)
	    HdNode[i]->u.next = HdNode[i+1];
     HdNode[NumHeads-1]->u.next =  node;
     node->right = HdNode[0];
    }
    return node;
}

void mwrite(MatrixPointer node)
{
/* print out the matrix in row major form */
  int i;
  MatrixPointer temp;
  /* matrix dimensions */
  printf("\n\nNumRows = %d, NumCols = %d\n",node->u.entry.row,
	  node->u.entry.col);
  printf(" The matrix by row, column, and value: \n\n");
  for (i = 0; i < node->u.entry.row; i++)
  /* print out the entries in each row */
     for (temp = HdNode[i]->right; temp != HdNode[i]; temp = temp->right)
       printf("%5d%5d%5d\n",temp->u.entry.row,temp->u.entry.col,
	      temp->u.entry.value);
}

void merase(MatrixPointer *node)
{
/* erase the matrix, return the pointers to the heap */
   MatrixPointer x,y;
   int i, NumHeads;
   /* free the entry pointers by row */
   for (i = 0; i < (*node)->u.entry.row; i++) {
      y = HdNode[i]->right;
      while (y != HdNode[i]) {
	      x = y;
	      y = y->right;
	     free(x);
      }
    }
    /* determine the number of head nodes and free these pointers */
    NumHeads = ((*node)->u.entry.row > (*node)->u.entry.col) ?
	 (*node)->u.entry.row : (*node)->u.entry.col;
    for (i = 0; i < NumHeads; i++)
	    free(HdNode[i]);
    *node = NULL;
}