#include <iostream>
#include "MatrixLinkedList.h"
using namespace std;

int main () {
  cout << sizeof(MatrixElement) << endl;
  MatrixElement* list = insert(NULL, 0,0,2);
  
  printMatrix(list);
  list = insert(list,1,1,3);
  
  print(list);
  
  list = insert(list,0,3,2);
  list = insert(list,1,1,6);
  cout << "in list form: " << endl;
  print(list);
  cout << "in matrix form: " << endl;
  printMatrix(list);
  MatrixElement* doubled = add(list,list);
  printMatrix(doubled);
  
  return 0;
}

void printElement(const MatrixElement& m)
{
  cout << m.row << " " << m.column << " " << m.value << endl;
}

void print(MatrixElement* root)
{
  for (MatrixElement* current = root; current != NULL; current = current->next)
  {
    printElement(*current);
  } 
}

MatrixElement* add(MatrixElement* m1, MatrixElement* m2) {
  //to add 2 matrices now we will create a new matrix and just add each element.
  MatrixElement* sum = NULL;
  
  //iterate through first linked list and insert.
  //Potentially auxilliary method would be good here:
  //insertAll(MatrixElement* source, MatrixElement* destination)
  while (m1 != NULL) {
    sum = insert(sum, m1->row, m1->column, m1->value);
    m1 = m1->next;
  }
  
  //iterate through second linked list and insert elements.
  while (m2 != NULL) {
    sum = insert(sum, m2->row, m2->column, m2->value);
    m2 = m2->next;
  }
  
  return sum;
}

void printMatrix(MatrixElement* m1) {
  if (m1 == NULL) {
    return;
  }
  
  int max = getMaxColumns(m1);
  int lastRow = 0;
  int lastColumn = -1;
  
  while (m1 != NULL) {
    //first print an appropriate number of 0s.
    if (lastRow != m1->row) {
      //finish the line off
      printZeros(max - lastColumn);
      cout << endl;
      
      //print complete rows of zeros
      for (int i=0; i < m1->row - lastRow - 1; i++) {
	printZeros(max);
	cout << endl;
      }
      
      printZeros(m1->column);
      cout << m1->value << " ";
    }
    else {
      printZeros(m1->column - lastColumn - 1);
      cout << m1->value << " ";
    }
    
    lastRow = m1->row;
    lastColumn = m1->column;
    m1 = m1->next;
  }
  
  //now just finish printing the column
  for (int i= lastColumn; i < max; i++) {
    cout << "0 ";
  }
  
  cout << endl;
}

//iterate over all values of the matrixelement linked list
int getMaxColumns(MatrixElement* m1) {
  int max = -1; //we can assume all values are >= 0
  while (m1 != NULL) {
    if (m1->column > max) {
      max = m1->column;
    }
    
    m1 = m1->next;
  }
  
  return max;
}

void printZeros(int numberZeros) {
	for (int i=0; i < numberZeros; i++) {
		cout << "0 ";
	}
}

//should insert in order
MatrixElement* insert(MatrixElement* root, int row, int column, int data) {
  cout << "At the start of the insert method" << endl;
  MatrixElement* newNode = new MatrixElement;
  newNode->row = row;
  newNode->column = column;
  newNode->value = data;
  if (root == NULL) {
    newNode->next = NULL;
    return newNode;
  }
  
  //check if node comes before the first one
  if (compareTo(*newNode, *root) < 0) {
    cout << "compare to was negative " << endl;
    newNode->next = root;
    return newNode;
  }
  
  if (compareTo(*newNode, *root) == 0) {
    root->value = root->value + newNode->value;
    return root;
  }
  
  //else find the correct place to insert it.
  MatrixElement* current = root;
  while (current->next != NULL) {
    if (compareTo(*newNode, *(current->next)) == 0) {
      current->next->value = current->next->value + newNode->value;
      return root;
    }
    
    if (compareTo(*newNode, *(current->next)) < 0) {
      MatrixElement* next = current->next;
      current->next = newNode;
      newNode->next = next;
      return root;
    }
    
    current = current->next;
  }
  
  //add to the end of the list
  return append(root, row, column, data);
}

int compareTo(const MatrixElement &me1, const MatrixElement &me2) {
  if (me1.row < me2.row) {
    return -1;
  }
  
  if (me1.row > me2.row) {
    return 1;
  }
  
  if (me1.column < me2.column) {
    return -1;
  }
  
  if (me1.column > me2.column) {
    return 1;
  }
  
  return 0;
}

MatrixElement* append(MatrixElement* root, int row, int column, int data) {
  MatrixElement* newNode = new MatrixElement;
  newNode->row = row;
  newNode->column = column;
  newNode->value = data;
  newNode->next = NULL;
  
  MatrixElement* last = getLast(root);
  
  if (last == NULL) {
    return newNode;
  }
  
  last->next = newNode;
  return root;
}

MatrixElement* getLast(MatrixElement* root) {
  if (root == NULL) {
    return NULL;
  }
  
  while (root->next != NULL) {
    root = root->next;
  }
  
  return root;
}

MatrixElement* deleteFirst(MatrixElement* root)
{
  if (root == NULL)
  {
    return NULL;
  }

  MatrixElement* second = root->next;
  delete root;
  return second;
}

void deleteList(MatrixElement* root)
{
  if (root == NULL)
  {
    return;
  }

  while (root != NULL)
  {
    root = deleteFirst(root);
  }
}