//=========================================================================
#define PROGRAMMER "SOLUTIONS, NoFrills"
#define PROG_CODE  "soln"
#define COURSE     "ECE-1021"
#define YEAR       (2003)
#define TERM       "Fall"
#define SECTION    (0)
#define ASSIGNMENT "HW #4A"
#define REVISION   (0)
#define TITLE      "Digitwise Math"
#define SUBTITLE   "Problem 6.12"
#define EMAIL      "wbahn@eas.uccs.edu"
#define FILENAME   "04a0soln.txt"
//=========================================================================

// PROBLEM:
//
// Write a program to take two five digit integers that are stored as
// individual digits in an integer array and add them together. The
// values can be positive or negative, with a negative value being
// indicated by having an additional digit be a one (zero if positive).

// SOLUTION:
//
// Representation:
//
// The number 12345 will be stored as:
//
// a[0] = 0  (the sign digit)
// a[1] = 1
// a[2] = 2
// a[3] = 3
// a[4] = 4
// a[5] = 5
//
// Dealing with strictly positive numbers first:
//
//     i :   0  1  2  3  4  5  6
//   a[i]:   0  a  b  c  d  e  -
//   b[i]:   0  f  g  h  i  j  -
//					  \  \  \  \  \
//                \  \  \  \  \
// sum[i]:   0  k  l  m  n  o  p
//
// The above assignments is clumsy (in my opinion) but it is what is
// required by the problem statement.
//------------------------------------------------------------------------
// The top level pseudocode is very straightforward:
//
// 1) TASK: Get the first value from the user.
// 1.1) CALL: Get5DigitSignedInt(a)
// 2) TASK: Get the second value from the user.
// 2.1) CALL: Get5DigitSignedInt(b)
// 3) TASK: Add the two values together.
// 3.1) CALL: Sum5DigitSignedInt(sum, a, b)
// 4) TASK: Output the results.
// 4.1) REM: Appropriate verbage added to below
// 4.2) CALL: Display5DigitSignedInt(a)
// 4.3) CALL: Display5DigitSignedInt(b)
// 4.4) CALL: Display6DigitSignedInt(sum)
//------------------------------------------------------------------------
// FUNCTION: Get5DigitInt(int d[])
//
// The user is required and expected to enter all of the digits, including
// the sign digit. So there is no need to initilize the elements of the
// array. We will assume that the user entered all six values as expected.
//
// 1) SET: i = 0;
// 2) WHILE (i < 6)
// 2.1) GET: d[i]
// 2.2) SET: i++
// 3) RETURN
//------------------------------------------------------------------------
// FUNCTION: Display5DigitSignedInt(int d[])
//
// Here we simply test the first digit to see what sign to print and then
// print out the elements in turn.
//
// 1) SET: i = 0;
// 2) IF: (d[0] = 1)
// 2.1) OUT: '-'
// 3) ELSE:
// 3.1) OUT: '+'
// 4) WHILE (i < 6)
// 4.1) OUT: d[i]
// 4.2) SET: i++
// 5) RETURN
//------------------------------------------------------------------------
// FUNCTION: Display6DigitSignedInt(int d[])
//
// Same as Display5DigitInt(int d[]) except loop extends one more digit.
//
// In fact, the functions can be combined into:
//
// FUNCTION: DisplayNDigitSignedInt(int d[], int n)
//
// 1) SET: i = 0;
// 2) IF: (d[0] = 1)
// 2.1) OUT: '-'
// 3) ELSE:
// 3.1) OUT: '+'
// 4) WHILE (i <= n)
// 4.1) OUT: d[i]
// 4.2) SET: i++
// 5) RETURN
//------------------------------------------------------------------------
// Similarly, the input function can be generalized in the same fashion.
//
// FUNCTION: GetNDigitSignedInt(int d[], int n)
//
// The user is required and expected to enter all of the digits, including
// the sign digit. So there is no need to initilize the elements of the
// array. We will assume that the user entered all six values as expected.
//
// 1) SET: i = 0;
// 2) WHILE (i <= n)
// 2.1) GET: d[i]
// 2.2) SET: i++
// 3) RETURN
//------------------------------------------------------------------------
// FUNCTION: SumNDigitUnsignedInt(int sum[], int a[], int b[], int n)
//
// To keep things incremental, we'll first write a function that
// can add two five digit unsigned arrays.
//
// The key is to note that we can simply do it the same way we would do
// it with pencil and paper - start with the rightmost digits, add them
// together, store the units digit as the result for that place and
// carry the one if needed, which merely means to add it to the two
// digits in the next column to the left. We can use the sum[] array
// to hold the carry digits.
//
// Keeping in mind that our sum[] array is one place longer:
//
// 1) SET: Carry = 0
// 2) WHILE: (n > 0)
// 1.1) sum[n] = ( carry + a[n-1] + b[n-1] )
// 1.2) IF: (sum[n] > 9)
// 1.2.1) SET: sum[n] -= 10
// 1.2.2) SET: carry = 1
// 1.3) ELSE:
// 1.3.1) SET: carry = 0
// 3) SET: sum[0] = carry
// 4) RETURN:
//------------------------------------------------------------------------
//
// The above work would allow us to add two unsigned 5-digit arrays
// without any problems (i.e., do Problem 6.11). To be able to add
// two signed five digit numbers, we can use one of several approaches.
// The most basic one is to do it the same way you would do it by hand:
//
// Given signed numbers a and b:
//
// sign of a: |            +             |         -
// -----------------------------------------------------------------
// sign of b: |                          | (|a|>|b|)? sum = |a|-|b|
//            |   sum = |a| + |b|        |            sign = -
//     +      |   sign = +               | (|b|>|a|)? sum = |b|-|a|
//            |                          |            sign = +
// -----------------------------------------------------------------
//            | (|a|>|b|)? sum = |a|-|b| |
//     -      |            sign = +      |   sum = |a| + |b|
//            | (|b|>|a|)? sum = |b|-|a| |   sign = -
//            |            sign = -      |
// -----------------------------------------------------------------
//
// Notice that if we add the two sign bits together, then
// we have grouped the two similar parts of the algorithm together.
//
// 1) IF: ( (a[0]+b[0]) = 1)  // one positive and the other negative
// 1.1) IF: ( |a| > |b| )
// 1.1.1) SET: AbsSum = |a| - |b|
// 1.1.2) SET: SignSum = SignOf(a)
// 1.2) ELSE:
// 1.2.1) SET: AbsSum = |b| - |a|
// 1.2.2) SET: SignSum = SignOf(b)
// 2) ELSE:                   // both positive or both negative
// 2.1) SET: AbsSum = |a| + |b|
// 2.2) SET: SignSum = SignOf(a)  // or SignOf(b)
//
// To implement the above algorithm, we need three things that we don't
// already have - a way to take the absolute value and a way to
// subtract two integers, at least given that we know they are both
// positive and that the result will be positive, and a way to check if
// one positive integer is larger than another positive integer.
//
// The first task is trivial given our data representation - we simply
// pass the address of a[1] instead of a[0]. That cuts off the sign bit.
//
// The second task requires only that we modify out function that
// adds two integers to carry out the same steps that we would do
// manually to subtract a smaller positive integer from a larger
// positive integer.
//
// Here we will still pass sum[] as being an array with an extra digit,
// but we know that this digit, under our constraints.
//
//------------------------------------------------------------------------
// FUNCTION: SubNDigitUnsignedInt(int sub[], int a[], int b[], int n)
//
// Keeping in mind that our sub[] array is one place longer:
//
// 1) SET: Borrow = 0
// 2) WHILE: (n > 0)
// 1.1) sub[n] = ( (a[n-1] - borrow)- b[n-1] )
// 1.2) IF: (sub[n] < 0)
// 1.2.1) SET: sub[n] += 10
// 1.2.2) SET: borrow = 1
// 1.3) ELSE:
// 1.3.1) SET: borrow = 0
// 3) SET: sub[0] = borrow
// 4) RETURN:
//------------------------------------------------------------------------
//
// FUNCTION: NDigitCompare(int a[], int b[], int n)
//
// a[] and b[] are two unsigned n-digit integers
// Return value: -1 if a[] < b[]
//                0 if equal
//               +1 if a[] > b[]
//
//
// 1) SET: i = 0
// 2) WHILE: (i < n) && (a[i] == b[i])
// 2.1) SET: i++
// 3) IF: (i == n) (exactly equal)
// 3.1) SET: result = 0
// 4) ELSE:
// 4.1) IF: a[i] < b[i]
// 4.1.1) result = -1
// 4.2) ELSE;
// 4.2.1) result = +1
// 5) RETURN result