/* This is the sample sparse.c file that implements functions defined in the
        sparse.h file and those called from p2_1.c.
ENTRY * make_node (int r, int c, int v)         // sparse.h
ROOT * make_root (void)                         // sparse.h
void show_list (ROOT *M, FILE *F)               //p2_1.c
void  read_input(FILE *F, ROOT *M, FILE *G)     //p2_1.c

   You can also define new functions and structures here, but they will not be
        "seen" or used outside this file (e.g. you cannot use them in p2.c).
        For example, the following function is introduced to help implementing
        function read_input().
void insert_at_tail (ROOT *M, ENTRY *e)
                                                                Gang Qu
                                                                March 31, 2026

void show_list()        // position of the non-zero entries is added
                                                                April 13, 2026


void show_list()        // the do-while loop is replaced by a while loop

   The following three functions are added at the end. You need to implement them
        for Phase 1. The specification of these functions can be found in sparse.h.
void search (ROOT *M, int k, FILE *F)
void find_max(ROOT *M, FILE *F)
ROOT * addition (ROOT *M1, ROOT *M2, FILE *F)

                                                                Gang Qu
                                                                April 14, 2026

   One more function is defined to copy a matrix, return the ROOT pointer
ROOT * copy_matrix(ROOT *M);

   Sample implementations of the three functions are included. 
   Phase 1 is completely done. 
								April 18, 2026
*/

#include<stdio.h>
#include<stdlib.h>
#include "sparse.h"

ENTRY * make_node (int r, int c, int v)
{ ENTRY *temp;
  if (r<0 || c<0 || v==0)		// verify input values 
    return NULL;
  temp = NEW(ENTRY);
  if (temp != NULL)
  { temp->val = v;
    temp->row = r;
    temp->col = c;

    temp->left = NULL;
    temp->right = NULL;
    temp->up = NULL;
    temp->down = NULL;
    temp->info = NULL;
    temp->next = NULL;
  }
  return temp;
}

ROOT * make_root (void)
{ ROOT  *temp;
  temp = NEW(ROOT);
  if (temp != NULL)
  { temp->head = NULL;
    temp->num = 0;
    temp->info = NULL;
  }
  return temp; 
}

void insert_at_tail (ROOT *M, ENTRY *e)
{ ENTRY *tmp;

  if (M == NULL) return;
  if (M->head == NULL) 
  { M->head = e;
    M->num = 1;
    return;
  } 
  
  tmp = M->head;
  while (tmp->next != NULL) 
    tmp = tmp->next;
  tmp->next = e;
  e->next = NULL;
  M->num++;
}


void show_list (ROOT *M, FILE *F)
{ ENTRY *temp;
  int i=0;				// 5 values per line

  if (M != NULL)
  { 
    fprintf(F, "\nmatrix at %p ...\n", M);
    temp = M->head;
    while (temp != NULL)
    { fprintf(F, "%5d (%d,%d) ", temp->val, temp->row, temp->col);
       temp = temp->next;
      i++;
      if (i == 5)
      {	fprintf(F, "\n");
        i = 0;
      }
    } 
// the previous do-while loop seg fault when the list is empty
  }
  if (i!=0) 
    fprintf(F, "\n");
}


void  read_input(FILE *F, ROOT *M, FILE *G)
{ ENTRY *tmp;
  int r, c, v;
  
  if (M == NULL)
  { M = make_root();
    if (M == NULL)
    { printf("No space left. Fail to store data.\n");
      exit(0);
    }
  }

  fprintf(G, "\nReading entry from %p ... \n", F);
  while(fscanf(F, "%d %d %d", &r, &c, &v) != EOF)
  { tmp = make_node(r, c, v);
    if (tmp != NULL)			// check whether node is made or not
      insert_at_tail (M, tmp);
  }
  fprintf(G, "%d entries stored in matrix at %p.\n", M->num, M);
}


void search (ROOT *M, int k, FILE *F)
{ ENTRY *tmp;
  int r, c;

  if (M != NULL)
  { fprintf(F, "\nsearch %d in matrix at %p ...\n", k, M);
    tmp = M->head;
    while (tmp != NULL)
    { if (tmp->val == k)
        fprintf(F, "%d %d\n", tmp->row, tmp->col);
      tmp = tmp->next;
    }
  }
}


void find_max(ROOT *M, FILE *F)
{ int max, row, col;		// variables for max and its position
  ENTRY *tmp;

  if (M != NULL)
  { fprintf(F, "\nfind max in matrix at %p ...\n", M);
    tmp = M->head;
    if (tmp == NULL) 
    { fprintf(F, "maximum 0 at position (1, 1)\n");
      return;
    }
    max = tmp->val;
    row = tmp->row;
    col = tmp->col;
    while(tmp->next != NULL)
    { tmp = tmp->next;
      if (tmp->val > max)
      { row = tmp->row;
        col = tmp->col;
	max = tmp->val;
      }
    }   
    fprintf(F, "maximum %d at position (%d, %d)\n", max, row, col);
  }
}


ROOT * copy_matrix(ROOT *M)
{ ROOT *M2;
  ENTRY *tmp, *tmp2;

  M2 = make_root();
  if (M2 == NULL || M == NULL) return NULL;

  tmp = M->head;
  while (tmp!=NULL)
  { tmp2 = make_node(tmp->row, tmp->col, tmp->val);
    if (tmp2 != NULL)
      insert_at_tail(M2, tmp2);
    tmp = tmp->next;
  }
  
  return M2;
}


ROOT * addition (ROOT *M1, ROOT *M2, FILE *F)
{ ROOT *SUM;
  ENTRY *tmp, *tmp1, *tmp2;
  int r, c, v;

  SUM = make_root();
  if (SUM == NULL) return SUM;
  if (M1 == NULL || M1->head == NULL) return copy_matrix(M2);
  if (M2 == NULL || M2->head == NULL) return copy_matrix(M1);

// now both M1 and M2 are non-empty
//  fprintf(F, "\nAdding %p to %p ...\n", M2, M1);
  tmp1 = M1->head;
  while (tmp1 != NULL)
  { tmp2 = M2->head;                    // search for match in M2
    r = tmp1->row;
    c = tmp1->col;
    v = tmp1->val;
    while (tmp2 != NULL)
    { if (tmp2->row == r && tmp2->col == c)
      { v = tmp1->val+tmp2->val;
 	if (v != 0)			// only include non-zero ENTRY's
	{ tmp = make_node(r, c, v);
	  if (tmp != NULL)
	    insert_at_tail (SUM, tmp);
	}
	break;				// process next ENTRY in M1
      }
      else 
	tmp2 = tmp2->next;
    }
    if (tmp2 == NULL)			// match in M2 not found, add tmp1
    { tmp = make_node(r, c, v);
      if (tmp != NULL)
	insert_at_tail (SUM, tmp);
    }
    tmp1 = tmp1->next;
  }

// process non-zero ENTRY's in M2, but not in M1
  tmp2 = M2->head;
  while (tmp2 != NULL)
  { tmp1 = M1->head;
    while (tmp1 != NULL)
    { if (tmp2->row == tmp1->row && tmp2->col == tmp1->col)
        break;
      tmp1 = tmp1->next;
    }
    if (tmp1 == NULL)
    { tmp = make_node(tmp2->row, tmp2->col, tmp2->val);
      if (tmp != NULL)
        insert_at_tail (SUM, tmp);
    }
    tmp2 = tmp2->next;
  }

  fprintf(F, "\nmatrix at %p has %d non-zero entries.\n", SUM, SUM->num);

  return SUM;
}