main.c

/*
 * A simple implmentation of functions to manipulate an array in C.
 *
 * GistID: fe4b47db44173247be6f
 */
#include <stdio.h>
#include "UART.h"
#include "TExaS.h"

void EnableInterrupts(void);  // Enable interrupts
int FindIndexOfLargest(unsigned short*, int);
int RemoveEntry(unsigned short*, int, int);
unsigned short RemoveLargestEntry(unsigned short*, int);
unsigned short RemoveSecondLargestEntry(unsigned short*, int);

int main (void) {

	int max_index;
	unsigned short second_largest_value;

	// Define Given Array
	unsigned short data[100] = {
		58473, 33594, 38638, 26741, 13018, 29262, 16377, 12354, 46079,
		57240, 48949, 34054, 16212, 58485, 6198, 38678, 22525, 51012,
		43489, 8861, 54291, 21524, 7166, 22698, 39899, 27113, 30443,
		14888, 27935, 40035, 48710, 18067, 36008, 12644, 56319, 15852,
		54685, 61789, 57030, 4763, 10655, 24656, 60363, 23712, 28474,
		31274, 39647, 56166, 8219, 47413, 22201, 3129, 25630, 36027,
		4499, 56525, 32743, 9380, 22102, 51009, 16309, 16589, 26322,
		65279, 22780, 26002, 41101, 26082, 13389, 59504, 15784, 33416,
		57970, 8519, 57819, 34406, 40864, 31575, 52154, 60214, 39910,
		43107, 64825, 40284, 60148, 27287, 38245, 49930, 54062, 50668,
		30553, 27904, 38960, 49407, 10508, 62147, 33019, 3047, 33750, 18024};

	// Initialize board and UART
	TExaS_Init(UART_PIN_PA0,UART_PIN_PA1); // this initializes the TExaS grader lab 5
	UART_Init();    // initialize UART for printing
	EnableInterrupts();  // the grader needs interrupts


  
	// Demonstrate finding the maximum
	max_index = FindIndexOfLargest(data, 100);
	printf("The maximum value of the list is %d located at index %d\n", data[max_index], max_index);
	

	// Remove second largest value
	second_largest_value = RemoveSecondLargestEntry(data, 100);
	printf("The second largest value is %d\n", second_largest_value);

}

/*
 * Given a list and its length, the function traverses the list and finds the
 * first order statistic. It returns the index of the location of this value.
 */
int FindIndexOfLargest(unsigned short *list, int length)
{

	// Define
	int i, max_index;
	unsigned short max_value;

	// Declare
	max_value = 0;
	max_index = 0;

	// Iterate over given list and update max as nessecary
	for ( i = 0; i < length; i++ ) {
		if (list[i] > max_value) {
			max_value = list[i];
			max_index = i;
		}
	}

	return max_index;
}

/*
 * Shifts values right of index to the left one position and returns the value
 * removed. Takes an an array and lenght of the array as well as the index of
 * the item to remove.
 */
int RemoveEntry(unsigned short *list, int length, int index)
{

	int i;

	// Start iterating at index until given length
	for (i = index; i < length-1; i++) {
		// Update current value to be next value
		list[i] = list[i+1];
	}

	return length - 1;
}

/*
 * Finds maximum value in given list of length and removes it from the array.
 */
unsigned short RemoveLargestEntry(unsigned short* list, int length)
{

	unsigned short max_value;
	int max_index;

	// Find first order statistic and copy its value
	max_index = FindIndexOfLargest(list, length);
	max_value = list[max_index];

	// Remove the item at index
	RemoveEntry(list, length, max_index);

	return max_value;
}

/*
 * Effectively partions the given list by finding the first maximum value. Then
 * the the maximum of each of the sublists is found and compared to find and
 * remove from the given list of given length. Takes an array of given length.
 */
unsigned short RemoveSecondLargestEntry(unsigned short *list, int length)
{

	int max_index, lower_max_index, upper_max_index;
	unsigned short second_max_value;

	// First find the max value
	max_index = FindIndexOfLargest(list, length);
	
	// The second max is going to be in the partion created by the max value
	// index. The trick is to understand the nature of an array and use pointer arithmetic. The
	// first statement is easy to find the largest value up to max_index:
	lower_max_index = FindIndexOfLargest(list, max_index);
	
	// The second statement uses offsets within the array to establish new bounds to search through.
	// list is the 0 index of a contigous block of elements. Starting from the max
	// index + 1 we partion the original list on the right of the first order
	// statistic. The length of the partition is going to be the total length
	// minux the max_index offset.
	upper_max_index = FindIndexOfLargest(list + max_index+1 , length - max_index ) + max_index+1;

	// Determine which of the candidates is the true second maximum
	if (list[lower_max_index] > list[upper_max_index]) 
		second_max_value = RemoveLargestEntry(list, max_index);
	else 
		second_max_value = RemoveLargestEntry(list + max_index+1, length - max_index);
		

	return second_max_value;
}