//=========================================================================
#define PROGRAMMER "SOLUTIONS, NoFrills"
#define PROG_CODE  "soln"
#define COURSE     "ECE-1021"
#define YEAR       (2003)
#define TERM       "Fall"
#define SECTION    (0)
#define ASSIGNMENT "HW #5A Supplemental"
#define REVISION   (0)
#define TITLE      "Stack Example"
#define SUBTITLE   "Demo Program"
#define EMAIL      "wbahn@eas.uccs.edu"
#define FILENAME   "stacks.c"
//=========================================================================

// PROBLEM:
//
// Write a program that takes a 20 element integer array and initializes
// the values to random three digit numbers.
//
// Using four stacks, sort the array so that the first element ends with a
// a number divisible by 2, the second element is divisible by 3, and the
// third element is divisible by 5, and the fourth element is not divisble
// by any of these. This then repeats (the fifth element is divisible by 2
// and so on).
//
// At some point, there will not be any values left that can be put at a
// given location - perhaps you need to place a number that is divisble by
// 3 and no such numbers remain. At this point, dump all of the remaining
// values into the rest of the array grouping all the values divisible by
// 2 first, then by 3, then by 5, then all the rest.
//
// Print the result out to the screen is some logical way.
//
// SOLUTION:
//
// After creating the data, go through and sift the data onto one of four
// stacks. After the data is on the stacks, go through and pull one item
// from each stack in turn until one of the stacks goes empty. After that
// dump the entire contents of each stack into the array in order.
//
//
// Stack Functions:
//

// The data associated with each stack is a pointer to the stack itself,
// a pointer to the stack pointer, and the size of the stack. Not all of
// the functions use all of the information and so some warnings about
// variables that are declared by never used will be issued. We'll accept
// this as the penalty for having a consistent User Interface to these
// functions.

#include <stdio.h> // printf()
#include <conio.h> // gotoxy(), clrscr()
#include <stdlib.h> // rand(), srand()

// Prototypes for Support Functions
int rand3digit(void);

// Prototypes for Stack Functions
void Flush(int *stack, int *pointer, int size);
int IsEmpty(int *stack, int *pointer, int size);
int IsFull(int *stack, int *pointer, int size);
int Pop(int *stack, int *pointer, int size);
void Push(int *stack, int *pointer, int size, int value);

#define SIZE (20)
#define FALSE (0)
#define TRUE  (!FALSE)

int main(void)
{
	int array[SIZE];
	int i;
	int Phase1;
	unsigned int seed;

	// software stacks
	int divby2[SIZE], sp_2;
	int divby3[SIZE], sp_3;
	int divby5[SIZE], sp_5;
	int divbyX[SIZE], sp_X;

	// Initialize Array to random numbers between 0 and 100
	printf("Random Number Seed: ");
	scanf("%u", &seed);
	srand(seed);
		for(i = 0; i < SIZE; i++)
		array[i] = rand3digit();

	// Print out the array in a column on the left hand side of the screen.
	clrscr();
	gotoxy(8,1);
	printf("Original");
	for(i = 0; i < SIZE; i++)
	{
		gotoxy(10, i+2);
		printf("%3i", array[i]);
	}

	// Because each stack is big enough to hold the entire contents
	// of array[], we can avoid the overhead of checking to see if the
	// stack is full prior to pushing something onto it. In general, this
	// issue needs to be considered since pushing an object onto a full
	// stack (or popping an item off an empty stack) can lead to serious
	// problems (generally referred to as "corrupting the stack").

	// Put the contents of the array onto the appropriate stacks:
	// First, flush all of the stacks
	Flush(divby2, &sp_2, SIZE);
	Flush(divby3, &sp_3, SIZE);
	Flush(divby5, &sp_5, SIZE);
	Flush(divbyX, &sp_X, SIZE);

	gotoxy(20,1);
	printf("Div By");
	for(i = 0; i < SIZE; i++)
	{
		gotoxy(22, i+2);
		if(0==(array[i]%2))
		{
			Push(divby2, &sp_2, SIZE, array[i]);
			putchar('2');
		}
		else if(0==(array[i]%3))
		{
			Push(divby3, &sp_3, SIZE, array[i]);
			putchar('3');
		}
		else if(0==(array[i]%5))
		{
			Push(divby5, &sp_5, SIZE, array[i]);
			putchar('5');
		}
		else
		{
			Push(divbyX, &sp_X, SIZE, array[i]);
			putchar('X');
		}
	}

	// Phase 1 is pulling values from the stacks in sequence until one of
	// the stacks goes empty.
	Phase1 = TRUE;
	for(i = 0; (Phase1) && (i < SIZE); i++)
	{
		switch(i%4)
		{
			case 0: // Pull from divby2
				if(IsEmpty(divby2, &sp_2, SIZE))
					Phase1 = FALSE;
				else
					array[i] = Pop(divby2, &sp_2, SIZE);
				break;
			case 1: // Pull from divby3
				if(IsEmpty(divby3, &sp_3, SIZE))
					Phase1 = FALSE;
				else
					array[i] = Pop(divby3, &sp_3, SIZE);
				break;
			case 2: // Pull from divby5
				if(IsEmpty(divby5, &sp_5, SIZE))
					Phase1 = FALSE;
				else
					array[i] = Pop(divby5, &sp_5, SIZE);
				break;
			case 3: // Pull from divbyX
				if(IsEmpty(divbyX, &sp_X, SIZE))
					Phase1 = FALSE;
				else
					array[i] = Pop(divbyX, &sp_X, SIZE);
				break;
		}
	}

	// If the above loop ended because one of the stacks ran out, then
	// the counter i was incremented even though no value was loaded
	// into the array. If it ran out because we filled up the array,
	// then this is not the case. The value of Phase1 tells us which
	// occurred - if Phase1 is still TRUE, then there were exactly
	// SIZE/4 elements on each stack and we are finished. If Phase1
	// is false, then we need to proceed with Phase2 and the first
	// thing we need to do is decrement the counter so that it again
	// points to the first element of the array that has not been
	// reloaded.

	if(!Phase1)
	{
		i--;
		while(!IsEmpty(divby2, &sp_2, SIZE))
			array[i++] = Pop(divby2, &sp_2, SIZE);
		while(!IsEmpty(divby3, &sp_3, SIZE))
			array[i++] = Pop(divby3, &sp_3, SIZE);
		while(!IsEmpty(divby5, &sp_5, SIZE))
			array[i++] = Pop(divby5, &sp_5, SIZE);
		while(!IsEmpty(divby2, &sp_2, SIZE))
			array[i++] = Pop(divbyX, &sp_X, SIZE);
	}

	// Print out new array to the right of the previoius output.
	gotoxy(28, 1);
	printf("Ordered");
	for(i = 0; i < SIZE; i++)
	{
		gotoxy(30, i+2);
		printf("%3i", array[i]);
	}

	return;
}


// SUPPORT FUNCTIONS

int rand3digit(void)
{
	return( (rand()%900)+100 );
}

// STACK FUNCTIONS
void Flush(int *stack, int *pointer, int size)
{
	*pointer = 0;
	return;
}

int IsEmpty(int *stack, int *pointer, int size)
{
	return(0 == *pointer);
}

int IsFull(int *stack, int *pointer, int size)
{
	return(size == *pointer);
}

int Pop(int *stack, int *pointer, int size)
{
	(*pointer)--;
	return(stack[*pointer]);
}

void Push(int *stack, int *pointer, int size, int value)
{
	stack[(*pointer)++] = value;
	return;
}