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

/**
 * Prints a linked-list "head" into the output fie "out"
 *
 * NOTE: we have given the code for this function
 */
void List_print(FILE * out, Node * head)
{
 while(head != NULL)
	{
	    fprintf(out, "%5d: %6d\n", head -> index, head -> value);
	    head = head -> next;
	}
    printf("\n");
}


/**
 * Please fill in the code below
 */

/**
 * Destroys a linked list.
 * Arguments:
 * head    A pointer pointing to the first element of the linked list.
 *
 * Returns:
 * void
 *
 * Destroys (frees memory for) the whole linked list. 
 * You can either use recursion or a while loop.
 */
void List_destroy(Node * head)
{
  Node *temp = head;
  while(head != NULL)
  {
		temp = temp->next;
		free(head);
		head = temp;
  }
}

/**
 * Create and initialize a linked list. 
 *
 * Arguments:
 * value     The "value" of the new node
 * index     The "index" of the new node
 *
 * Returns:
 * Returns a newly constructed node. The node can be the head of a
 * linked list.
 * 
 * You should allocate memory in this function. 
 */
Node * List_create(int value, int index)
{
	if(value == 0 || index < 0)
		return NULL;
		
	Node *temp;
	temp = malloc(sizeof(Node));
	
	temp->value = value;
	temp->index = index;
	temp->next = NULL;

  return temp;
}

/**
 * Build a sparse array from the given indices and values with 
 * specific length.
 *
 * Arguments:
 * value    Array of values
 * index    Array of indices
 * length   Length of the above arrays
 *
 * Returns:
 * A sparse array.
 *
 * If a sparse array node has { value = 1000, index = 2 }, then that means that
 * the index "2" caries the value "1000". This is meant to convey an array of 1000 
 * "2s", but instead of creating 1000 nodes in your linked list, you only create
 * 1 node, and that note conceptually has 1000 "copies" of it. Hence 
 * each node in a sparse array has a "value" in addition to its "index".
 *
 * Note that an index can never carry the value of "0", because this would not make
 * any sense; however, negative values are fine. A negative value may seem odd
 * at first blush; however, this is like substraction, and makes sense for certain
 * cases.
 *
 * You need to insert nodes in ascending order by index.
 * See the notes to "List_insert_ascend"
 */

void q_sort(int *arr0, int *arr1, int start, int end) // helper function for sort
{	
	if(end - start < 1) // condition to end recursion
		return;

	int pivot = start; // set initial pivot index
	int val0; // create temporary variable used to swap values
	int val1;
	int i = start; // incrementor variable
	int j = end; // decrementor variable

	while(i < j) // prevent i and j from over-lapping
	{
		while(arr0[i] < arr0[pivot] && i <= end)
		{	
			i++; // find index of value less than pivot value
		}
		while (arr0[j] > arr0[pivot] && j >= start)
		{
			j--; // find index of value greater than pivot value
		}
		val0 = arr0[i]; // swap value at i with value at j
		arr0[i] = arr0[j];
		arr0[j] = val0;
		
		val1 = arr1[i];
		arr1[i] = arr1[j];
		arr1[j] = val1;
	} // repeat for all values i < j, i.e. one pass

  q_sort(arr0, arr1, start, j-1); // repeat for sub array of smaller indices
  q_sort(arr0, arr1, j+1, end);  // repeat for sub array of larger indices
}


Node * List_build(int * value, int * index, int length)
{
	if(length < 1)
		return NULL;
		
	q_sort(index, value, 0, length - 1);
	Node *head = NULL;
	Node *temp = NULL;

	int i;
	for(i = length - 1; i >= 0; i--)
	{
		if(value[i] != 0)
		{
			temp = List_create(value[i], index[i]);
			temp->next = head;
			head = temp;
		}
	}
	
  return head;
}

 
/**
 * Inserting "value" and "index" into the correct location in the 
 * sparse array "head"
 * 
 * Arguments: 
 * head      A pointer pointing to the first element of the linked list.
 * value     The "value" of the value
 * index     The "value" of the index
 *
 * Returns:
 * A sparse array
 *
 * This function inserts the node ["value", "index"] into the sparse
 * array "head", and ensures that the nodes remain in ascending order
 * by their "index".
 *
 * Before and after the call to this function, "head" must be in
 * ASCENDING order by the "index" of each node.
 */
Node * List_insert_ascend(Node * head, int value, int index)
{
	if(head == NULL)
		return NULL;
	Node *temp = NULL;
	Node *temp1 = head;
	
	while(temp1 != NULL)
	{
		if(index < temp1->index)
		{
			temp = List_create(value, index);
			temp->next = temp1;
			return temp;
		}
		if(index == temp1->index)
		{
			temp1->value = temp1->value + value;
			return head;
		}
		if(temp1->next == NULL)
		{
			temp = List_create(value, index);
			temp->next = temp1->next;
			temp1->next = temp;
			return head;
		}
		if(index > temp1->index && index < temp1->next->index)
		{
			temp = List_create(value, index);
			temp->next = temp1->next;
			temp1->next = temp;
			return head;
		}
		temp1 = temp1->next;
	}
	return head;
}


/**
 * This function deletes the node with the passed "index"
 * 
 * Arguments: 
 * head      A pointer pointing to the first element of the sparse array.
 * index     The index to be deleted
 *
 * Returns: 
 * A sparse array with the node removed (the one with index)
 */
Node * List_delete(Node * head, int index)
{		
	if(head == NULL)
		return NULL;
	
	Node *temp;
	temp = head;
	
	Node *temp1;
	temp1 = head;

	if (temp == NULL)
		return temp;

	if (head->index == index)
	{
		if(head->next == NULL)
		{
			free(head);
			return NULL;
		}
		else
		{
			head->index = head->next->index;
			head->value = head->next->value;
			temp = head->next;
			head->next = head->next->next;
			free(temp);
			temp1 = head->next;
		}
	}
	while(temp1->next != NULL)
	{
		if(temp1->next->index == index)
		{
			temp = temp1->next;
			temp1->next = temp1->next->next;
			free(temp);
			return head;
		}
	}
	return head;
}

/**
 * Copy a list
 *
 * Arguments:
 * head      A pointer pointing to the first element of the sparse array
 *
 * Returns:
 * A copy sparse array
 *
 * This function will copy the sparse array that is passed to it. The
 * copy will be made into new memory. 
 *
 * This is useful, for example, when we want to merge
 * two linked lists together. We can make a copy of one of the linked
 * lists, and then merge the second into the copy. In this way the
 * original copy of the list is not "mutated".
 */
Node * List_copy(Node * head)
{
	if(head == NULL)
		return NULL;
	Node *temp = head;
	Node *copy = malloc(sizeof(Node));
	copy->value = temp->value;
	copy->index = temp->index;
	copy->next = NULL;

	Node *const head1 = copy;

	temp = temp->next;

	while (temp != NULL) 
	{
		copy = copy->next = malloc(sizeof(Node));
		copy->value = temp->value;
		copy->index = temp->index;
	  copy->next = NULL;
		temp = temp->next;
	}
	return head1;
}


/**
 * Merged two linked list together
 * 
 * Arguments:
 * head1      A pointer pointing to linked list 1
 * head2      A pointer pointing to linked list 2
 *
 * Returns:
 * A merged sparse array
 *
 * This function will merge two linked lists. Before merging, you 
 * should make a copy of "head1" so that you will still have the 
 * original array while modifying (merging) the second linked list. 
 *
 * Please refer to the README file for detailed instructions on how to
 * merge two lists.
 *
 * This function should not modify either "head1" or "head2". You only
 * need to make a clone of "head1".
 */
Node * List_merge(Node * head1, Node * head2)
{
	if(head1 == NULL)
		return List_copy(head2);
	if(head2 == NULL)
		return List_copy(head1);
	
	Node *temp;
	temp = List_copy(head1);
	
	Node *temp1;
	temp1 = head2;
	
	
	while(temp1 != NULL)
	{
		temp = List_insert_ascend(temp, temp1->value, temp1->index);
		temp1 = temp1->next;
	}
	temp1 = temp;
	while(temp != NULL)
	{
		if(temp->value == 0)
			temp = List_delete(temp, temp->index);
		temp = temp->next;
	}
	return temp1;
}