/***************************** factoriser.c ***************************** 

 Factoriser (C) 2004 - Brendan Arnold

 This was meant to be an exercise in linked lists but  whilst I
 struggled with the, (remarkably easy) concept, stray fingers started to
 add lots of noddy features. I did, however, discover lots of new stuff
 including...

 	o #ifdef for debugging
	o strtol() is now preferred to atoi() (see man page)
	o How to return pointers from functions
	o A solid way to check user input (as a number)
	o A loop which iterates the correct number of time in a linked list
	o That I don't want to program for a living

 Its not that fast but its pretty versatile and robust.
 
 Does anyone know if factoriser should be spelt with an 'e' or an 'o'?

************************************************************************/ 

/* Include some other files */
#include<stdio.h>
#include<math.h> 
#include<stdlib.h>
#include<ctype.h>
#include<string.h>

/* Define some constants */
#define VERSION "0.9"
#define GETINT_PROMPT "Please enter your number to be factorised: "
/* #define DEBUG */
#define MAXINPUT 100000000
#define MININPUT -100000000

/* Create data structure for nodes in linked list */
struct int_ll_node_tmp {
	int num;
	struct int_ll_node_tmp *next; 
}; 
typedef struct int_ll_node_tmp int_ll_node; /* Give shorter alias */

/* Create data structure for the switches */
struct cmd_options_tmp {
	/* Every time a 'priority' option is set, this should be set as
	 * well, current priority options are, badOption, showVersion
	 * showHelp, the priorityOptions flag bypasses the main algorythm
	 * cutting to the output of text */
	int priorityOption; 
	/* badOption is set to aid with error handling */
	int badOption;
	int showVersion;
	int printNegative;
	int showHelp;
	int formatSimple;
};
typedef struct cmd_options_tmp cmd_options; /* Give shorter alias */

/* Prototype some fns. Ripped a couple of ideas off data ;-) */
void printHelp(int full);
void printVersion();
int getInt();
int validateInt(char array[], int max, int min);
int_ll_node *appendLinkList(int_ll_node *curNode, int factor);
int printResults(int_ll_node *startNode, int number, int isNegative, int printNegative);
int printSimpleResults(int_ll_node *startNode, int number, int isNegative, int printNegative);
int isCommandSwitch(char cmdArg[]);
int numDigits(int number);
cmd_options *setOptions(char cmd_string[], cmd_options *tmp_options);

/***************************** main() *********************************	
                        Lets Go! Start main()
**********************************************************************/ 
int main (int argc, char **argv) {

	/* VARIABLES FOR main() */
	int number, i, isNegative;
	int_ll_node *listRoot, *currentNode;
	cmd_options *options; 

	/* Initialise options */
	options = (cmd_options *)malloc(sizeof(cmd_options));
	options->priorityOption = 0;
	options->badOption = 0;
	options->showVersion = 0;
	options->printNegative = 0;
	options->showHelp = 0;
	options->formatSimple = 0;

	/* Initialise some vars to 0 */
	number = 0;

	/* PARSING OF THE COMMAND LINE ARGUMENTS */
	if (argc == 1) {
		/* factoriser called on its own need to get number */
		number = getInt(MAXINPUT,MININPUT);
	} else {

		/* We have arguments to attend to! */

		/* Iterate over all arguments */
		for (i=1; argv[i] != NULL && !options->priorityOption ; i++) {
			if (isCommandSwitch(argv[i])) {
				options = setOptions(argv[i], options);
			/* If its not an argument, assume it is number input */
			} else {
				/* Test to see if number is last argument */
				if (argv[i+1]) {
					printf("Number input should be last argument\n");
					options->badOption = 1;
					options->priorityOption = 1;
					break;
				/* Test to see if it is a valid number */
				} else if (validateInt(argv[i], MAXINPUT, MININPUT)) {
					number = (int)strtol(argv[i], (char **)NULL, 10);
					break;
				/* If not, quit. (validateInt gives user feedback) */	
				} else {
					options->badOption = 1;
					options->priorityOption = 1;
					break;
				}
			}
		}
		/* If still don't have number, get one! */
		if (!options->priorityOption && !number) {
			number = getInt(MAXINPUT,MININPUT);
		}
	}

	/* If the options->priorityOption is set, it means that a switch is
	 * specified which does not need to factorise a number, examples are
	 * the output of help info, version info and when a bad option has
	 * been specified */
	if (!options->priorityOption) {

		/* Checks if number is negative, if so makes it positive and sets
		 * the isNegative flag */
		if (number < 0) {
			number = fabs(number);
			isNegative = 1;
		} else {
			isNegative = 0;
		}		
		
		/* Initialise the linked list with 1 */
		listRoot = (int_ll_node *)malloc(sizeof(int_ll_node));
		listRoot->num = 1;
		listRoot->next = NULL;
		currentNode = listRoot;

		/* ACTUAL ROUTINE (Pathetic isn't it?) */
		for (i = 2; i <= sqrt(number); i++) {
			if ((number % i) == 0) {
				/* Append the factor */
				currentNode = appendLinkList(currentNode, i);
				currentNode->next = NULL;
			}
		}
	}

	/* Output the results. These are set in order of importance since in
	 * theory all options can be set without error. */
	if (options->badOption) {
		printHelp(0);
		return(1);
	} else if (options->showHelp) {
		printHelp(1);
		return(0);
	} else if (options->showVersion) {
		printVersion();
		return(0);
	} else if (options->formatSimple) {
		if (!printSimpleResults(listRoot, number, isNegative, options->printNegative)) {
			return(1);
		}
	} else {
		if (!printResults(listRoot, number, isNegative, options->printNegative)) {
			return(1);
		}
	}

	return(0);
	/* END OF MAIN */
}

/************************* setOptions() *******************************
  Takes a command switch string and parses it into binary switch 
  options
**********************************************************************/ 
cmd_options *setOptions(char cmd_string[], cmd_options *tmp_options) {

	/* Declare some vars */
	int i;
	
	#ifdef DEBUG
		printf("Got to setOptions\n");
	#endif

	/* Starts at 1 because 0th char should be a minus sign. Iterates
	 * over all the rest of the chars in the string */ 
	for (i=1; cmd_string[i] != NULL && !tmp_options->badOption; i++) {
		switch (cmd_string[i]) {
			case 'h':
				/* User wants help */
				if (tmp_options->showHelp) {
					tmp_options->badOption = 1;
					tmp_options->priorityOption = 1;
					printf("Command '-h' specified twice!\n");
				} else {
					tmp_options->showHelp = 1;
					tmp_options->priorityOption = 1;
				}
				break;
			case 'v':
				/* User wants to see version info */
				if (tmp_options->showVersion) {
					tmp_options->badOption = 1;
					tmp_options->priorityOption = 1;
					printf("Command '-v' specified twice!\n");
				} else {
					tmp_options->showVersion = 1;
					tmp_options->priorityOption = 1;
				}
				break;
			case 'n':
				/* User isn't up to imagining negative signs infront of
				 * all the factors */
				if (tmp_options->printNegative) {
					tmp_options->badOption = 1;
					tmp_options->priorityOption = 1;
					printf("Command '-n' specified twice!\n");
				} else {
					tmp_options->printNegative = 1;
				}
				break;
			case 's':
				/* User wants to use the program for sthg useful (i.e.
				 * piping to another prog) */
				if (tmp_options->formatSimple) {
					tmp_options->badOption = 1;
					tmp_options->priorityOption = 1;
					printf("Command '-s' specified twice!\n");
				} else {
					tmp_options->formatSimple = 1;
				}
				break;
			default:
				/* User is obviously bonkers */
				printf("Command '-%c' not recognised\n",cmd_string[i]);
				tmp_options->badOption = 1;
				tmp_options->priorityOption = 1;
				break;
		}
	}
	return(tmp_options);
}
/************************* isCommandSwitch() **************************
  	Returns 1 if string param is a -X style switch, 0 otherwise
**********************************************************************/	
int isCommandSwitch(char cmdArg[]) {

	#ifdef DEBUG
		printf("Got to isCommandSwitch\n");
	#endif

	/* Just check that first char is a minus sign and second is an alpha
	 * character */
	if (cmdArg[0] == '-' && isalpha(cmdArg[1])) {
		return(1);
	} else {
		return(0);
	}
}

/************************** printHelp() ******************************** 
               			Outputs help text.
**********************************************************************/ 
void printHelp(int full) {

	if (full) {
		puts(
		" Factoriser overview:\n\n"
		" Factoriser factors an integer returning the output in a neatly\n"
	    " formatted table. Other information such as the number of factors and\n"
	    " whether or not the number is a prime is also included at no extra\n"
	    " charge.\n");
	}
	puts(
		" Usage:\n"
		"\tfactoriser -[hvsn] [integer]\n"
		" Options:\n" 
		"\t-h Prints full help text\n"
		"\t-v Prints version information\n"
		"\t-s Outputs just the factors seperated by newline characters\n"
		"\t-n Outputs negative factors as well\n"
		" Notes:"
	);
	/* Need to use printf here because puts doesn't allow non strings to
	 * be printed */
	printf("\t[integer] can be positive or negative between %d and %d\n", MININPUT, MAXINPUT);
}

/************************* printVersion() *****************************	
						Outputs version text
**********************************************************************/	
void printVersion() {
	puts(
		" Factoriser Version " VERSION 
		"\n Copyright(C) 2004 Brendan Arnold" 
	);
}

/************************** getInt() V 0.2 **************************
 Retrieves an integer from STDIN. Actually 'validateInt' does most of
 the hard work, getInt just adds a nice prompt and includes a loop. 
 Notes:
	o Vets characters
	o Vets floats
	o Allows negative numbers
	o Gets prompt from #define GETINT_PROMPT statement
********************************************************************/

int getInt(int max, int min) {

	#ifdef DEBUG
		printf("Got to getInt\n");
	#endif

	/* Declare local vars */
	char usrInput[10];

	/* Start loop that wont stop until we have a valid integer! */
	do {
		/* Print #define'd prompt */
		printf("%s",GETINT_PROMPT);
		/* Get user input into string initially */
		scanf("%s",usrInput);
	/* Continue until it is valid */
	} while (!validateInt(usrInput, max, min));
	/* Return the converted integer */
	return((int)strtol(usrInput, (char **)NULL, 10));
}

/********************** validateInt() *********************************	
  Checks an array to see if it contains only an integer and whether it
           is in range, returns 1 if true, 0 if false
**********************************************************************/	
int validateInt(char array[], int max, int min) {

	#ifdef DEBUG
		printf("Got to validateInt 1\n");
	#endif

	/* Declare some vars. */
	int i;
	long num;

	for (i=0; array[i] != NULL; i++) {
		/* Skip if first element is a negative sign */
		if ((i==0) && (array[i] == '-')) {
			#ifdef DEBUG
				printf("Skipped due to negative sign\n");
			#endif
			continue;
		/* Check each element is a digit */
		} else if (isdigit(array[i]) == 0) {
			printf("Not an integer, try again.\n");
			return(0);
		}
		#ifdef DEBUG
			printf("In loop: %d\n",i);
		#endif
	}

	#ifdef DEBUG
		printf("Got to validateInt 2\n");
	#endif
	
	/* now convert to number to check if in range */
	num = strtol(array, (char **)NULL, 10); 
	if ((num < min) || (num > max)) {
		printf("Valid range is between %d and %d\n",min,max);
		return(0);
	} else if (num == 0) {
		printf("Zero has an infinte number of factors, I'll tell you that for free...\n");
		return(0);
	}

	#ifdef DEBUG
		printf("Got to validateInt 3\n");
	#endif

	/* No reason why should reject, return 1 */
	return(1);
}
/************************* appendLinkList() ***************************	
                    Adds a value to the linked list
**********************************************************************/ 
int_ll_node *appendLinkList(int_ll_node *curNode, int factor) {

	/* Create a pointer to a new node */
	int_ll_node *newNode;

	#ifdef DEBUG
		printf("Got to appendLinkList: %d\n", factor);
	#endif

	/* Create a new node somewhere randomly in memory */
	newNode = (int_ll_node *)malloc(sizeof(int_ll_node));
	/* Set the last node's ->next value to point to the new node */
	curNode->next = newNode;
	/* Assign values to the new node */
	newNode->num = factor;
	newNode->next = NULL;

	/* Return latest node pointers address */
	return(newNode);
}

/*********************** numDigits() **********************************
		Returns numbers of chars needed to print out this number
		ONLY ACCEPTS POSITIVE NUMBERS
**********************************************************************/	
int numDigits(int number) {

	/* Declare variables */
	int i, isNegative;

	/* Has own check to see if negative due to maths type stuff that
	 * goes on in printResults function */
	if (number < 0) {
		number = fabs(number);
		isNegative = 1;
	} else {
		isNegative = 0;
	}

	/* Iterates i to number of digits */
	i = 1;
	while (number/(pow(10,i)) >= 1) {
		i++;
	}

	/* Add one to accomodate minus sign */
	if (isNegative) {
		i++;
	}

	#ifdef DEBUG
		printf("Got to numDigits: %d\n",i);
	#endif

	return(i);
}
		
/********************** printResults() *******************************	
 All singing/dancing output function that frames text MySQL stylee.
**********************************************************************/ 
int printResults(int_ll_node *startNode, int number, int isNegative, int printNegative) {

	/* Declare some vars. */
	int i, counter, numWidth;
	/* Create a pointer to iterate over all in list */
	int_ll_node *nodeIterator;

	#ifdef DEBUG
		printf("Got to printResults\n");
	#endif

	/* Quit prematurely if there is no value in first node for some
	 * crazy reason */
	if (!startNode || !startNode->num) {
		return(0);
	}

	/* Restore the numbers negative status if needed  for the purpose of
	 * creating factor pairs */
	if (isNegative) {
		number *= -1;
	}

	/* Set nodeIterator at start of linked list */
	nodeIterator = startNode;

	/* START OUTPUT */

	/* 
	   Going to output a table like below...

       +---------------+---------------+---------------+---------------+
	   | Factor        | Factor pair   | - Factor      | - Factor Pair |
	   +---------------+---------------+---------------+---------------+
	   | 1             | 23456         | -1            | -23456        |
       | 2             | 11728         | -2            | -11728        |

	   etc. etc. or

       +---------------+---------------+
	   | Factor        | Factor pair   |
	   +---------------+---------------+
	   | 1             | 23456         |
       | 2             | 11728         |

	   ...and so on, depending on whether or not negative factors are 
	   wanted. (Rather cool formatting robbed from MySQL client ;-).
	*/

	/* Print Table Header */

	/* Longest ordinary 'int' on 32bit system is 11 (-2147483648)
	 * Longestheader is '- Factor Pair' at 13 chars. So can set table
	 * width to 15 (2 spaces of padding) without bother, just hope
	 * no-one uses SDFs full potential ;-) */
	if (printNegative) {
		puts("\n +---------------+---------------+---------------+---------------+\n"
			   " | Factor        | Factor Pair   | - Factor      | - Factor Pair |\n"
			   " +---------------+---------------+---------------+---------------+");
	} else {
		puts("\n +---------------+---------------+\n"
			   " | Factor        | Factor Pair   |\n"
			   " +---------------+---------------+");
	}

	/* Print Table Body */

	/* Finally got a loop that works for all the list, the && operator
	 * allows you to assign _after_ the test has been done so we get the
	 * last iteration. */
	counter = 0;
	do  {
		/* Print the factor */
		printf(" | ");
		printf("%d", nodeIterator->num);
		numWidth = numDigits(nodeIterator->num);
		for (i=0; i < (14 - numWidth); i++) {
			printf(" ");
		}
		printf("| ");
		/* ...and its pair */
		printf("%d", number/nodeIterator->num);
		numWidth = numDigits((number/nodeIterator->num));
		for (i=0; i < (14 - numWidth); i++) {
			printf(" ");
		}
		/* Now to see if we want the negative factors */
		if (printNegative) {
			printf("| ");
			/* Print the negative factor */
			printf("%d", nodeIterator->num * -1);
			numWidth = numDigits(nodeIterator->num * -1);
			for (i=0; i < (14 - numWidth); i++) {
				printf(" ");
			}
			printf("| ");
			/* ...and its negative pair */
			printf("%d", (number/nodeIterator->num) * -1);
			numWidth = numDigits(number/nodeIterator->num * -1);
			/* Note 16 because of space infront */
			for (i=0; i < (14 - numWidth); i++) {
				printf(" ");
			}
		}
		printf("|\n");
		counter++;
	} while (nodeIterator->next && (nodeIterator = nodeIterator->next));

	/* Print Table Footer */
	if (printNegative) {
		puts(" +---------------+---------------+---------------+---------------+\n");
	} else {
		puts(" +---------------+---------------+\n");
	}

	/* Add some interesting stats */
	printf(" Number factored: %d", number);
	if (number == 1 || number == -1) {
		printf(" (not a prime despite no factors other than itself)\n");
	} else if (counter == 1) {
		printf(" (prime)\n");
	} else {
		printf(" (not a prime)\n");
	}
	printf(" Number of factors, not including one and itself: %d\n\n", (counter * 2) - 2);
	

	return(1);	
	
	
}

/*********************** printSimpleResults()**************************
  Prints out the factors just seperated by newlines. Designed for 
  piping through external programs
**********************************************************************/	
int printSimpleResults(int_ll_node *startNode, int number, int isNegative, int printNegative) {

	/* Create a pointer to iterate over all in list */
	int_ll_node *nodeIterator;

	#ifdef DEBUG
		printf("Got to printSimpleResults\n");
	#endif

	/* Quit prematurely if there is no value in first node for some
	 * crazy reason */
	if (!startNode || !startNode->num) {
		return(0);
	}

	/* Restore the numbers negative status if needed  for the purpose of
	 * creating factor pairs */
	if (isNegative) {
		number *= -1;
	}

	/* Set nodeIterator at start of linked list */
	nodeIterator = startNode;

	/* Finally got a loop that works for all the list, the && operator
	 * allows you to assign _after_ the test has been done so we get the
	 * last iteration. */
	do  {
		/* Print the factor */
		printf("%d\n", nodeIterator->num);
		/* ...and its pair */
		printf("%d\n", number/nodeIterator->num);
		/* Now to see if we want the negative factors */
		if (printNegative) {
			/* Print the negative factor */
			printf("%d\n", nodeIterator->num * -1);
			/* ...and its negative pair */
			printf("%d\n", (number/nodeIterator->num) * -1);
		}
	} while (nodeIterator->next && (nodeIterator = nodeIterator->next));

	return(1);

}