/*
 * 整数。
 *
 * Date: 2014-04-11
 * Author: Leonardone
 */

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

#define DEBUG_FLAG 1

#if DEBUG_FLAG
#  define DebugDo(d) d
#else
#  define DebugDo(d)
#endif

struct _digit;
struct _decimal;
typedef struct _digit Digit, *LPDigit;
typedef struct _decimal Decimal, *LPDecimal;

struct _digit {
	int value;
	LPDigit upper;
	LPDigit under;
};

struct _decimal {
	int point;
	int sign;
	LPDigit head;
	LPDigit tail;
};

LPDigit newDigit(void);
LPDigit newDigitByInt(int value);
int countDigits(const LPDecimal dec);
LPDecimal newDecimal(void);
LPDecimal newDecimalByInt(int value);
void printDecimal(const LPDecimal dec);
LPDecimal addDecimal(LPDecimal val1, LPDecimal val2);
LPDecimal mulDecimal(LPDecimal val1, LPDecimal val2);
void releaseDecimal(LPDecimal dec);
void releaseDigit(LPDigit dig);

int main(void) {
	
	LPDecimal d1 = newDecimalByInt(111);
	LPDecimal d2 = newDecimalByInt(2222);
	LPDecimal d3 = newDecimalByInt(999);
	LPDecimal d4 = addDecimal(d1, d2);
	LPDecimal d5 = addDecimal(d1, d3);
	LPDecimal d6 = addDecimal(d2, d3);
	
	printDecimal(d1);
	printDecimal(d2);
	printDecimal(d3);
	printDecimal(d4);
	printDecimal(d5);
	printDecimal(d6);
	
	releaseDecimal(d1);
	releaseDecimal(d2);
	releaseDecimal(d3);
	releaseDecimal(d4);
	releaseDecimal(d5);
	releaseDecimal(d6);
	
	return 0;
}

LPDigit newDigit(void) {
	return (LPDigit)calloc(1, sizeof(Digit));
}

LPDigit newDigitByInt(int value) {
	LPDigit dig = newDigit();
	if (value > 9) {
		dig->upper = newDigitByInt(value / 10);
		dig->upper->under = dig;
	}
	dig->value = value % 10;
	return dig;
}

int countDigits(const LPDecimal dec) {
	LPDigit dig = dec->head;
	int i = 0;
	while (dig != NULL) {
		i++;
		dig = dig->under;
	}
	return i;
}

LPDecimal newDecimal(void) {
	return newDecimalByInt(0);
}

LPDecimal newDecimalByInt(int value) {
	LPDecimal dec = (LPDecimal)calloc(1, sizeof(Decimal));
	LPDigit dig;
	if (value < 0) {
		dec->sign = 1;
		value *= -1;
	}
	dec->tail = dig = newDigitByInt(value);
	while (dig->upper != NULL) {
		dig = dig->upper;
	}
	dec->head = dig;
	dec->point = countDigits(dec);
	return dec;
}

void releaseDigit(LPDigit dig) {
	if (dig->under != NULL) {
		dig->under->upper = NULL;
		releaseDigit(dig->under);
		dig->under = NULL;
	}
	if (dig->upper != NULL) {
		dig->upper->under = NULL;
		releaseDigit(dig->upper);
		dig->upper = NULL;
	}
	DebugDo(printf("release Digit: %d\n", dig->value));
	free(dig);
}

void releaseDecimal(LPDecimal dec) {
	DebugDo(printf("release Decimal: "));
	DebugDo(printDecimal(dec));
	releaseDigit(dec->head);
	dec->head = NULL;
	dec->tail = NULL;
	free(dec);
}

void printDecimal(const LPDecimal dec) {
	int p = dec->point;
	LPDigit dig = dec->head;
	if (dec->sign) {
		putchar('-');
	}
	while (p > 1 && dig != NULL && dig->value == 0) {
		dig = dig->under;
		p--;
	}
	while (p > 0 && dig != NULL) {
		putchar('0' + (char)dig->value);
		dig = dig->under;
		p--;
	}
	if (p > 0) {
		printf("error\n");
		exit(1);
	}
	if (dig != NULL) {
		putchar('.');
		while (dig != NULL) {
			putchar('0' + (char)dig->value);
			dig = dig->under;
		}
	}	
	putchar('\n');
}

LPDecimal addDecimal(LPDecimal val1, LPDecimal val2) {
	LPDecimal val3 = newDecimal();
	LPDigit dig1 = val1->tail;
	LPDigit dig2 = val2->tail;
	LPDigit dig3 = val3->tail;
	int p1 = val1->point;
	int p2 = val2->point;
	int c1 = countDigits(val1) - p1;
	int c2 = countDigits(val2) - p2;
	int c3 = c1 > c2 ? c1 : c2;
	int t1, t2, t3, ca;
	
	if (val1->sign != val2->sign) {
		return val3; /* difDecimal() */
	}
	val3->sign = val1->sign;
	
	while (c1 < c2) {
		dig3->value = dig2->value;
		dig3->upper = newDigit();
		dig3->upper->under = dig3;
		dig2 = dig2->upper;
		dig3 = dig3->upper;
		c2--;
	}
	while (c1 > c2) {
		dig3->value = dig1->value;
		dig3->upper = newDigit();
		dig3->upper->under = dig3;
		dig1 = dig1->upper;
		dig3 = dig3->upper;
	}
	ca = 0;
	while (dig1 != NULL || dig2 != NULL) {
		if (dig1 != NULL) {
			t1 = dig1->value;
			dig1 = dig1->upper;
		} else {
			t1 = 0;
		}
		if (dig2 != NULL) {
			t2 = dig2->value;
			dig2 = dig2->upper;
		} else {
			t2 = 0;
		}
		t3 = t1 + t2 + ca;
		ca = t3 / 10;
		dig3->value = t3 % 10;
		dig3->upper = newDigit();
		dig3->upper->under = dig3;
		dig3 = dig3->upper;
	}
	if (ca > 0) {
		dig3->value = ca;
		val3->head = dig3;
	} else {
		val3->head = dig3->under;
		val3->head->upper = NULL;
		dig3->under = NULL;
		releaseDigit(dig3);
	}
	val3->point = countDigits(val3) - c3;
	
	return val3;
}

LPDecimal mulDecimal(LPDecimal val1, LPDecimal val2) {
	return NULL;
}