/*-
# X-BASED ABACUS
#
#  AbacusM.c
#
###
#
#  Copyright (c) 1994 - 2005	David Albert Bagley, bagleyd@tux.org
#
#                   All Rights Reserved
#
#  Permission to use, copy, modify, and distribute this software and
#  its documentation for any purpose and without fee is hereby granted,
#  provided that the above copyright notice appear in all copies and
#  that both that copyright notice and this permission notice appear in
#  supporting documentation, and that the name of the author not be
#  used in advertising or publicity pertaining to distribution of the
#  software without specific, written prior permission.
#
#  This program is distributed in the hope that it will be "useful",
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
#
*/

/* Methods string math file for Abacus */

/* What fancy mathematics could be here?
   Well, whenever possible math here is done with strings.
   (Roman math is limited by definition.)
   I use long long when I can't figure out how to do it by
   strings, as in Display Base.
 */

#include "AbacusP.h"

static char roman[] =
{
	'I', 'V', 'X', 'L', 'C', 'D', 'M',
	     'v', 'x', 'l', 'c', 'd', 'm'
/* pardon the non-standard notation (case historically was ignored)
_
V = v,
_
X = x, etc
SMALLEST_ROMAN I=1
BIGGEST_ROMAN mmmcmxcMxCMXCIX=3,999,999
LONGEST_ROMAN mmmdccclxxxvMMMDCCCLXXXVIII=3,888,888
It has been suggested to put more bars on top for bigger numbers but there
is no recorded usage of a larger Roman numeral in Roman times.
An older notation for Roman numerals was represented thus:
( = C, I) = D, (I) = M, I)) = v, ((I)) = x, I))) = l, (((I))) = c,
 _
|X| = m */
};

#ifdef HAVE_LONG_LONG
#define LONG unsigned long long
#else
#define LONG unsigned long
#endif

int
char2Int(char character)
{
	if (character >= '0' && character <= '9') {
		character += 0 - '0';
	/* ASCII or EBCDIC */
	} else if (character >= 'a' && character <= 'i') {
		character += 10 - 'a';
	} else if (character >= 'j' && character <= 'r') {
		character += 19 - 'j';
	} else if (character >= 's' && character <= 'z') {
		character += 28 - 's';
	} else if (character >= 'A' && character <= 'I') {
		character += 10 - 'A';
	} else if (character >= 'J' && character <= 'R') {
		character += 19 - 'J';
	} else if (character >= 'S' && character <= 'Z') {
		character += 28 - 'S';
	} else
		character = 36;
	return ((int) character);
}

char
int2Char(int digit)
{
	digit += '0';
	/* ASCII or EBCDIC */
	if (digit > '9' || digit < '0') {
		digit += ('A' - '9' - 1);
		if (digit > 'I')
			digit += ('J' - 'I' - 1);
		if (digit > 'R')
			digit += ('S' - 'R' - 1);
	}
	return ((char) digit);
}

static int
int2String(char *buf, LONG number, int base, Boolean negative)
{
	int digit, last, position = 0, i;
	LONG mult = 1;

	last = 1;
	while (number >= mult * base) {
		mult *= base;
		last++;
		if (mult > mult * base) {
			buf[0] = '\0';
			return 0;
		}
	}
	if (negative) {
		buf[position] = '-';
		position++;
	}
	for (i = 0; i < last; i++) {
		digit = (int) (number / mult);
		number -= mult * digit;
		buf[position] = int2Char(digit);
		mult /= base;
		if (mult == 0 && i != last - 1) {
			buf[0] = '\0';
			return 0;
		}
		position++;
	}
	buf[position] = '\0';
	return last;
}

static int
flt2String(char *buf, LONG number, int abacusBase, int base, int places, int decimalPosition)
{
	int position = 0, digit;
	double mult = 1.0 / base;
	double fraction = number;

	for (position = 0; position < places; position++) {
		fraction /= abacusBase;
	}
	for (position = 0; position < decimalPosition; position++) {
		digit = (int) (fraction / mult);
		fraction -= mult * ((double) digit);
		buf[position] = int2Char(digit);
		mult /= base;
		if (mult == 0 && position != places - 1) {
			buf[0] = '\0';
			return 0;
		}
	}
	buf[position] = '\0';
	for (digit = position - 1; digit > 0; digit--) {
		if (buf[digit] == '0')
			buf[digit] = '\0';
		else
			break;
	}
	return places;
}

#if 0
int
string2Int(char *buf, int base)
{
	int digit, position = 0, value = 0, last;

	if (buf[position] == '-') {
		return 0;
	}
	last = strlen(buf);
	for (; position < last; position++) {
		if (buf[position] == '.') {
			break;
		}
		digit = char2Int(buf[position]);
		value = value * base + digit;
		if (value >= ((base >= 8) ? base / 2 - 1 : base) *
				base * base * base * base * base * base)
			return 0;
	}
	return value;
}
#endif

/* Try not to use since this restricts the size of abacus. */
static LONG power(int x, int n)
{				/* raise x to the nth power n >= 0 */
	int i;
	LONG p = 1;

	for (i = 1; i <= n; ++i)
		p *= ((LONG) x);
	return p;
}

/* This is fast for small i, a -1 is returned for negative i. */
static int
squareroot(int i)
{
	int j = 0;

	while (j * j <= i)
		j++;
	return (j - 1);
}

void
dividePieces(char * buf, int base, int pieces, int mult, int places)
{
	int position, digit, inter;

	digit = mult / pieces;
	inter = mult % pieces;
	/* This works because digit should never be greater than base here */
	(void) sprintf(buf, "%1d.", digit);
	for (position = 2; position < places;) {
		digit = (inter * base) / pieces;
		inter = (inter * base) % pieces;
		buf[position] = int2Char(digit);
		position++;
		if (inter == 0)
			break;
	}
	buf[position] = '\0';
}

/* 2nd grade math is hard */
/* May disregard sign if different */
void
addStrings(char *finalBuf, char *aBuf, char *bBuf, int base)
{
	int aEnd = strlen(aBuf), bEnd = strlen(bBuf); /* zeros included */
	int aDecimal = aEnd, bDecimal = bEnd;
	int aSign = ((aBuf[0] == '-') ? 1 : 0);
	int bSign = ((bBuf[0] == '-') ? 1 : 0);
	int i, carry = 0, digit;

	for (i = 0; i < aEnd; i++) {
		if (aBuf[i] == '.' && aDecimal == aEnd) {
			aDecimal = i;
			break;
		}
	}
	for (i = 0; i < bEnd; i++) {
		if (bBuf[i] == '.' && bDecimal == bEnd) {
			bDecimal = i;
			break;
		}
	}
	if (bEnd - bDecimal < aEnd - aDecimal) {
		for (i = 0; i < aEnd - bEnd - aDecimal + bDecimal; i++)
			bBuf[bEnd + i] = '0';
		bEnd += i;
		bBuf[bEnd] = '\0';
	}
	if (bEnd - bDecimal > aEnd - aDecimal) {
		for (i = 0; i < bEnd - aEnd - bDecimal + aDecimal; i++)
			aBuf[aEnd + i] = '0';
		aEnd += i;
		aBuf[aEnd] = '\0';
	}
	if (aDecimal - aSign >= bDecimal - bSign) {
		for (i = aEnd - 1; i > aDecimal; i--) {
			digit = char2Int(aBuf[i]) +
				char2Int(bBuf[i - aEnd + bEnd]) + carry;
			aBuf[i] = int2Char(digit % base);
			carry = digit / base;
		}
		for (i = aDecimal - 1; i >= aSign ; i--) {
			digit = char2Int(aBuf[i]) + ((i - aEnd + bEnd >= bSign) ?
				char2Int(bBuf[i - aEnd + bEnd]) : 0) + carry;
			aBuf[i] = int2Char(digit % base);
			carry = digit / base;
		}
		if (aSign == 1) {
			finalBuf[0] = '-';
			finalBuf[1] = '\0';
		}
		if (carry > 0) {
			finalBuf[aSign] = (char) (carry + '0');
			(void) strcpy(&finalBuf[aSign + 1], &aBuf[aSign]);
		} else
			(void) strcpy(finalBuf, aBuf);
	} else {
		for (i = bEnd - 1; i > bDecimal; i--) {
			digit = char2Int(bBuf[i]) +
				char2Int(aBuf[i - bEnd + aEnd]) + carry;
			bBuf[i] = int2Char(digit % base);
			carry = digit / base;
		}
		for (i = bDecimal - 1; i >= bSign ; i--) {
			digit = char2Int(bBuf[i]) +
				((i - bEnd + aEnd >= aSign) ?
			char2Int(aBuf[i - bEnd + aEnd]) : 0) + carry;
			bBuf[i] = int2Char(digit % base);
			carry = digit / base;
		}
		if (bSign == 1)
			finalBuf[0] = '-';
		if (carry > 0) {
			finalBuf[aSign] = (char) (carry + '0');
			(void) strcpy(&finalBuf[aSign + 1], &bBuf[bSign]);
		} else
			(void) strcpy(finalBuf, bBuf);
	}
}

void
convertString(char * buf, char * inbuf, int base, int displayBase, int decimalPosition)
{
	char fltbuf[256];
	int i, last, place = -1, decimalPlace, decimalPointPlace;
	Boolean negative, gotDecimal = False;
	LONG intPart = 0, floatPart = 0;

	last = strlen(inbuf);
	negative = (inbuf[0] == '-');
	for (i = (negative) ? 1 : 0; i < last; i++) {
		if (inbuf[i] == '.') {
			place = i - 1 - ((negative) ? 1 : 0);
			break;
		}
	}
	if (place == -1)
		place = last - 1 - ((negative) ? 1 : 0);
	decimalPlace = place;
	decimalPointPlace = last - 2 - ((negative) ? 1 : 0) - place;
	for (i = (negative) ? 1 : 0; i < last; i++) {
		if (inbuf[i] == '.') {
			gotDecimal = True;
			place = last - decimalPlace - 2 - ((negative) ? 1 : 0);
			floatPart = 0;
			place--;
		} else if (gotDecimal) {
			floatPart += (((LONG) power(base, place)) *
				char2Int(inbuf[i]));
			place--;
		} else {
			intPart += (((LONG) power(base, place)) *
				char2Int(inbuf[i]));
			place--;
		}
	}
	(void) int2String(buf, intPart, displayBase, negative);
	(void) flt2String(fltbuf, floatPart, base, displayBase,
		decimalPointPlace, decimalPosition);
	(void) sprintf(buf, "%s.%s", buf, fltbuf);
}

int
sizeofRoman(int base, Boolean romanNumerals)
{
	int romanWidth = ((base < 8) ? base : base / 2 - 1);

	return ((romanNumerals) ? ((sizeof(roman) + 1) / 2) *
		romanWidth + 12 : 0);
}

int
string2Roman(char *buf, char *inbuf, int base)
{
	int i = 0, position = 0, digit, last, j;
	int loga = (sizeof(roman) + 1) / 2;

	buf[position] = '[';
	position++;
	if (inbuf[i] == '-') {
		buf[position] = ']';
		position++;
		buf[position] = '\0';
		return 0;
	}
	last = strlen(inbuf);
	for (i = 0; i < last; i++) {
		if (inbuf[i] == '.') {
			break;
		}
	}
	last = i;
	i = 0;
	digit = char2Int(inbuf[i]);
	if (last > loga || (last == loga &&
			digit >= ((base >= 8) ? base / 2 - 1 : base))) {
		buf[position] = ']';
		position++;
		buf[position] = '\0';
		return 0;
	}
	for (i = 0; i < last; i++) {
		digit = char2Int(inbuf[i]);
		/* IX */
		if (digit >= base + 1 - base / 4 && base >= 8) {
			for (j = 0; j < base - digit; j++) {
				buf[position] = roman[2 * (last - i - 1)];
				position++;
			}
			buf[position] = roman[2 * (last - i)];
			position++;
		/* VI */
		} else if (digit >= (base + 1) / 2 && base >= 4) {
			buf[position] = roman[2 * (last - i) - 1];
			position++;
			digit = digit - (base + 1) / 2;
			while (digit > 0) {
				buf[position] = roman[2 * (last - i - 1)];
				position++;
				digit--;
			}
		/* IV */
		} else if (digit >= (base + 1) / 2 + 1 - base / 4 &&
				base >= 8) {
			for (j = 0; j < (base + 1) / 2 - digit; j++) {
				buf[position] = roman[2 * (last - i - 1)];
				position++;
			}
			buf[position] = roman[2 * (last - i) - 1];
			position++;
		/* I */
		} else {
			while (digit > 0) {
				buf[position] = roman[2 * (last - i - 1)];
				position++;
				digit--;
			}
		}
	}
	buf[position] = ']';
	position++;
	buf[position] = '\0';
	return 0;
}

#if 0
#define MAX_ROMAN 3999999
#define MAX_ROMANDIGIT 1000000
int
int2Roman(char *buf, int arabic)
{
	int i = 0, position = 0, digit;
	int loga = (sizeof(roman) + 1) / 2;
	int place = MAX_ROMANDIGIT;
	int base = DEFAULTBASE;

	buf[position] = '[';
	position++;
	if (arabic < 0 || arabic > MAX_ROMAN) {
		buf[position] = ']';
		position++;
		buf[position] = '\0';
		return 0;
	}
	for (i = 0; i < loga; i++) {
		digit = arabic / place;
		arabic = arabic - digit * place;
		if (digit >= base - 1) {
			buf[position] = roman[2 * (loga - i - 1)];
			position++;
			buf[position] = roman[2 * (loga - i)];
			position++;
		} else if (digit >= (base + 1) / 2) {
			buf[position] = roman[2 * (loga - i) - 1];
			position++;
			digit = digit - (base + 1) / 2;
			while (digit > 0) {
				buf[position] = roman[2 * (loga - i - 1)];
				position++;
				digit--;
			}
		} else if (digit >= (base + 1) / 2 - 1) {
			buf[position] = roman[2 * (loga - i - 1)];
			position++;
			buf[position] = roman[2 * (loga - i) - 1];
			position++;
		} else {
			while (digit > 0) {
				buf[position] = roman[2 * (loga - i - 1)];
				position++;
				digit--;
			}
		}
		place /= base;
	}
	buf[position] = ']';
	position++;
	buf[position] = '\0';
	return 0;
}
#endif

int
baseToBottom(int base)
{
	int j;

	for (j = squareroot(base); j > 1; j--) {
		if (base % j == 0) {
			return (base / j);
		}
	}
	return base;
}