// This program is to my knowledge, the best low level scoreboad insertion scheme possible.
// ARRAY_SIZE must be equal to 2^n + 2 for this algorithm to work as optimally as it does.
// memmove() has replaced for() loops to shift array elements, because there is a claim that it is faster.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

#define ARRAY_SIZE 10
// This constant search depth is 1 less than LOG-base-2(ARRAY_SIZE - 2) because the final condition statement is conducted outside of the loop.
#define MAX_LOOP_SEARCH_DEPTH 2

// Returns the number of comparisons made to arrive at the insertion position.  Returns "1" if the "NewValue" is too small to make the list.
// When put into use, this function should only return a boolean flag to indicate if the "NewValue" made the cut.
unsigned int BinaryInsertionSortOne(unsigned int *ThisArray, unsigned int NewValue){
	unsigned int X;
	unsigned int Result = 1;
	unsigned int Left = 0;
	unsigned int Right = ARRAY_SIZE - 1;
	unsigned int NextElement;
	
	// "NewValue" does not make the cut; it is too small.
	if ( NewValue <= ThisArray[Right] ) return Result;

	// "NewValue" belongs at the end of the list.
	Right -= 1;
	Result += 1;
	if ( NewValue <= ThisArray[Right] ) {
		ThisArray[ARRAY_SIZE - 1] = NewValue;
		return Result;
	}
	
	// "NewValue" belongs at the first position in the list.
	Result += 1;
	if ( NewValue >=  ThisArray[Left] ) {
		memmove(ThisArray + 1, ThisArray, sizeof(unsigned int)*(ARRAY_SIZE - 1));
		ThisArray[Left] = NewValue;
		return Result;
	}
	
	// Set the initial midpoint.
	NextElement = Left + ((Right - Left)>>1);
	
	// This loop will be unwound by compiler optimization.
	for ( X = 0; X < MAX_LOOP_SEARCH_DEPTH; X++ ) {
		Result += 1;
		// "NextElement" is the new "Left".
		if ( ThisArray[NextElement] >  NewValue ) {
			Left = NextElement;
		}
		// "NextElement" will become the new "Right".
		else if ( ThisArray[NextElement] <  NewValue ) {
			Result += 1;
			Right = NextElement;
		}
		// "NextElement" holds a value equal to "NewValue", and is the insertion point.
		else {
			Result += 1;
			// memmove() is going to employ pointer arithmatic for pointers to internal array members.
			memmove(ThisArray + NextElement + 1, ThisArray + NextElement, sizeof(unsigned int)*(ARRAY_SIZE - 1 - NextElement));
			ThisArray[NextElement] = NewValue;
			printf("Out Early\n");
			return Result;
		}
		// Advance the "NextElement";
		NextElement = Left + ((Right - Left)>>1);
	}
	
	Result += 1;
	// "NextElement" is now flanked by "Left" and "Right", and this is known with absolute certainty.
	// Since two cases will result in the insertion position being equal to "Right", we only need to make one comparison on the final iteration.
	if ( ThisArray[NextElement] <  NewValue ) {
		memmove(ThisArray + NextElement + 1, ThisArray + NextElement, sizeof(unsigned int)*(ARRAY_SIZE - 1 - NextElement));
		ThisArray[NextElement] = NewValue;
		printf("Out First\n");
		return Result;
	}
	// The "NewValue" is smaller or equal to "ThisArray[NextElement]", so the insertion position will be "Right".
	else {
		memmove(ThisArray + Right + 1, ThisArray + Right, sizeof(unsigned int)*(ARRAY_SIZE - 1 - Right));
		ThisArray[Right] = NewValue;
		printf("Out Second\n");
		return Result;
	}
}

int main(){
	unsigned int X;
	unsigned int NumberOfComparisons;
	long int Input;
	unsigned int TheArray[ARRAY_SIZE];
	
	// Set the initial values on the scoreboard far enough apart, so we can test the insertion performance at every position in the array.
	for ( X = 0; X < ARRAY_SIZE; X++ ) TheArray[X] = 10*(ARRAY_SIZE - X);
	printf("We are going to be inserting values into this array if they are big enough:\n\n");
	for ( X = 0; X < ARRAY_SIZE; X++ ) printf("|%u", TheArray[X]);
	printf("|\n\n");
	
	while ( 1 ) {
		printf("Enter an unsigned, 32 bit integer that you want on the scoreboard(ctrl c - To Exit): ");
		if ( scanf("%ld", &Input) == 0 ) return 0;
		if ( Input < 0 ) return 0;
		if ( Input > UINT_MAX ) return 0;
		NumberOfComparisons = BinaryInsertionSortOne(TheArray, (unsigned int)Input);
		printf("\nThe Insertion of |%u| required |%d| comparisons.\n\n", (unsigned int)Input, NumberOfComparisons);
		for ( X = 0; X < ARRAY_SIZE; X++ ) printf("|%u", TheArray[X]);
		printf("|\n\n");
	}
	
	return 0;
}