/** @ title: Assignment #2
* @ course: COMP 352
* @ author: Loren Segal (5442680)
* @ date: October 14th 2005
*/
import java.util.*;
/** BigInt is a single linked list representration of large integers.
* The implementation of the 'free functions' are in the form of a class based
* implementation of a BigInt class. Creating a new BigInt object would equate
* to the free function 'read', which created a list of digits based on the
* String input value (Integer reading is also supported for small integers).
*
* In addition, the class supports three mathematical operations which are the
* free functions:
* add(BigInt b)
* subtract(BigInt b)
* multiply(BigInt b)
*
* Each of the above methods will return a new BigInt will the value of
* BigInt b added to, subtracted from, or multiplied by the current number,
* respectively.
*
* The class does not support mathematical operations for negative BigInt's since
* it is not required by the assignment specifications. However, the resulting value
* of a mathematical operation between two positive BigInt's _can_ yield a negative value.
*
* The Iterable interface has been implemented to loop through each digit of the
* number (or node of the list) with the foreach looping method. The Comparable
* interface has also been implemented to compare two numbers and so that the
* class can be used by Collection sorting methods (although not actually used
* in the assignment). Also, equals() has been overridden to compare the values
* of two numbers.
*
* Finally, the toString() method is implemented to print out the value of the
* number (the last free function) as per Java specification.
*
*/
public class BigInt implements Iterable<Node<Integer>>, Comparable<BigInt>
{
// Instance variables
private Node<Integer> top;
private boolean positive;
/** Creates a new BigInt object with a value and a sign (+/-) */
public BigInt(String value, boolean sign)
{
top = new Node<Integer>(0,null);
positive = sign;
Node<Integer> temp = getHead();
// Loop back through string, create list with LSD first
for (int i = value.length() - 1; i >= 0; i--)
{
int digit = value.charAt(i) - '0';
if (digit < 0 || digit > 9)
{
// The read digit was not a valid number
// Check if it's a - sign, or set the value to 0
if (value.charAt(i) == '-' && i == 0)
{
// Leftmost character is a negation sign
// Trim the 0 off the end that was added last iteration
positive = false;
this.trim();
}
else
{
// The character is not a digit or is a - sign that is
// illegally placed. The resulting value will be a null object
top = null;
}
break;
}
// Set the digit to the node
temp.setElement(digit);
if (i > 0)
{
// Set the next node
temp.setNext(new Node<Integer>(0,null));
temp = temp.getNext();
}
}
}
/** Creates a new BigInt object with a number represented in a String */
public BigInt(String value)
{
this(value, true);
}
/** Creates a new BigInt object with an Integer object */
public BigInt(Integer value)
{
this(String.valueOf(value), true);
}
/** Creates a copy of a BigInt object */
public BigInt(BigInt number)
{
positive = number.isPositive();
top = new Node<Integer>(0,null);
// Copy entire list from number
Node<Integer> t = getHead();
for (Node<Integer> n : number)
{
t.setElement(n.getElement());
if (n.getNext() != null)
{
t.setNext(new Node<Integer>(0,null));
t = t.getNext();
}
}
}
/** Creates a new BigInt object that is empty */
public BigInt()
{
top = null;
positive = true;
}
/** Iterable implementation, loops through each node from top to tail */
public Iterator<Node<Integer>> iterator()
{
return new DigitsIterator();
}
/** DigitsIterator class is the implementation of the Iterator.
* It is a child class of BigInt for simplicity purposes and direct
* access to parent methods.
**/
private class DigitsIterator implements Iterator<Node<Integer>>
{
Node<Integer> pointer;
public DigitsIterator()
{
pointer = getHead();
}
public boolean hasNext()
{
return (pointer != null ? true : false);
}
public Node<Integer> next()
{
Node<Integer> t = pointer;
pointer = pointer.getNext();
return t;
}
public void remove()
{
pointer = pointer.getNext();
}
}
/** Returns the visual representation of the large number */
public String toString()
{
String out = new String();
for (Node<Integer> t : this)
{
out = String.valueOf(t.getElement()) + out;
}
// show sign
return (!isPositive() ? "-" : "") + out;
}
/** Returns the top of the digit list, ie. the LSD */
private Node<Integer> getHead() { return top; }
/** Returns the number of digits in the number */
public int length()
{
int i = 0;
for (Node<Integer> n : this) i++;
return i;
}
/** Trims any extraneous 0's on the left of the number */
private void trim()
{
Node<Integer> t = null;
for (Node<Integer> n : this)
{
Node<Integer> next = n.getNext();
if (next != null && next.getElement() == 0)
{
// Keep track of last found 0, unless there was one already found
if (t == null) t = n;
}
// If next is not 0 then forget the last found 0
else if (next != null) t = null;
}
// If there was a found ending 0, remove the digits from that point
if (t != null) t.setNext(null);
}
/** Checks that each digit is in the range 0-9, and carries any
* extra values over, if not.
*/
private void normalize()
{
// Loop through digits of new number carry over any extra values
for (Node<Integer> n : this)
{
int digit = n.getElement();
if (digit >= 10)
{
// Set digit to n mod 10
n.setElement(digit % 10);
// Take carry value to next digit (create one if null)
digit /= 10;
if (n.getNext() != null)
{
int nextDigit = n.getNext().getElement();
n.getNext().setElement(nextDigit + digit);
}
else
{
// If there is no next digit, we can break out of the loop
// since we can guarantee that this new next digit will be
// smaller than 10.
n.setNext(new Node<Integer>(digit, null));
break;
}
}
}
}
/** Negates the sign of the number */
public void negate()
{
positive = !positive;
}
/** Returns true if the number has a value (including 0) or false if
* it has no digits (an empty list).
*/
public boolean hasValue()
{
return (top == null ? false : true);
}
/** Checks if the value of the number is 0 and returns true or false */
public boolean isZero()
{
for (Node<Integer> node : this)
{
// If a digit is not zero, number is not zero.
if (node.getElement() != 0) return false;
}
return true;
}
/** Returns the sign value of the number */
public boolean isPositive() { return positive; }
/** Comparable implementation.
* Returns -1 if number is smaller than b
* Returns 0 if number is equal to b
* Returns 1 if number is greater than b
*/
public int compareTo(BigInt b)
{
// Trim both numbers so length() is valid
b.trim();
this.trim();
// check positive/negative cases, checking value only is not good enough
if (this.isPositive() && !b.isPositive()) return 1;
if (!this.isPositive() && b.isPositive()) return -1;
// Check each digit and fill an array with comparisons of each digit from
// MSD to LSD where 0, 1, 2 values denote smaller, equal, greater respectively
Node<Integer> p = b.getHead();
int i = length() - 1;
int[] tempArray = new int[i+1];
for (Node<Integer> t : this)
{
// this number has more digits and is greater if p is null
if (p == null) return 1;
// fill array elements with digit comparison values
if (p.getElement() > t.getElement()) tempArray[i] = 0;
else if (p.getElement() < t.getElement()) tempArray[i] = 2;
else tempArray[i] = 1;
i--;
// get next digit of b
p = p.getNext();
}
// if number b still has digits left, it is greater in length
// and therefore in magnitude as well
if (p != null) return -1;
// Check array from MSD to LSD
for (i = 0; i < tempArray.length; i++)
{
if (tempArray[i] == 0) return -1; // smaller digit, smaller value
if (tempArray[i] == 2) return 1; // larger digit, larger value
// otherwise digits are equal, continue checking
}
// All digits are equal
return 0;
}
/** Returns true is this number equals b in magnitude and sign */
public boolean equals(BigInt b)
{
if (this.compareTo(b) == 0) return true;
return false;
}
/** Returns a new BigInt object that is the sum of this object plus another BigInt */
public BigInt add(BigInt number)
{
BigInt newInt = new BigInt(0);
Node<Integer> p = newInt.getHead();
// Find smaller number
Node<Integer> smaller = (this.compareTo(number) < 0 ?
this.getHead() : number.getHead());
// Loop through digits of larger number
for (Node<Integer> larger : (smaller == this.getHead() ? number : this))
{
// Set digit of new number, the value can be >= 10, this will be fixed in a second loop
p.setElement(larger.getElement() +
(smaller != null ? smaller.getElement() : 0));
// Create next node in new number and move to next digit
if (larger.getNext() != null) p.setNext(new Node<Integer>(0,null));
if (smaller != null) smaller = smaller.getNext();
p = p.getNext();
}
// Fix carry values
newInt.normalize();
// return new BigInt
return newInt;
}
/** Returns a new BigInt object that equals the current value minus another BigInt */
public BigInt subtract(BigInt number)
{
BigInt newInt = new BigInt(0);
Node<Integer> p = newInt.getHead();
if (this.compareTo(number) < 0)
{
// Instead of subtracting a larger value from a smaller value
// Subtract the larger from the smaller and negate the result
newInt = number.subtract(this);
newInt.negate();
return newInt;
}
Node<Integer> smaller = number.getHead();
for (Node<Integer> larger : new BigInt(this)) // make a copy of this so we can do scratchwork on it
{
int largerDigit = larger.getElement();
int smallerDigit = (smaller != null ? smaller.getElement() : 0);
if (largerDigit - smallerDigit < 0)
{
// current subtraction will need a carry from next digit
Node<Integer> nextDigit = larger.getNext();
if (nextDigit == null) return null; // this should never happen
// carry over a 10 from next digit
largerDigit += 10;
// take off the 1 from next digit
nextDigit.setElement(nextDigit.getElement() - 1);
}
// Set value in new number
p.setElement(largerDigit - smallerDigit);
// Move to next digit
if (larger.getNext() != null) p.setNext(new Node<Integer>(0,null));
else if (p.getElement() == 0) newInt.trim(); // trim if there will be a 0 on the end
if (smaller != null) smaller = smaller.getNext();
p = p.getNext();
}
return newInt;
}
/** Returns a new BigInt object of the current value times another BigInt value */
public BigInt multiply(BigInt number)
{
BigInt newInt = new BigInt(0);
// If either numbers are zero, stop here.
if (number.isZero() || this.isZero()) return newInt;
Node<Integer> p;
int compared = this.compareTo(number);
int power = 0;
for (Node<Integer> smaller : (compared < 0 ? this : number))
{
p = newInt.getHead();
// Start multiplying from node `power`
for (int i = 0; i < power; i++)
{
if (p.getNext() == null) p.setNext(new Node<Integer>(0,null));
p = p.getNext();
}
// For each value in number A, multiply by number B and set to a digit of
// the new BigInt starting from the `power`th node.
for (Node<Integer> larger : (compared >= 0 ? this : number))
{
p.setElement(p.getElement() + larger.getElement() * smaller.getElement());
// Move to the next digit on the new BigInt
if (larger.getNext() != null && p.getNext() == null)
{
p.setNext(new Node<Integer>(0,null));
}
p = p.getNext();
}
power++; // next time start from the next node
}
// Fix carry values
newInt.normalize();
// return new BigInt
return newInt;
}
/** main method: does the test runs for 2 input values */
public static void main(String[] args)
{
BigInt i = null, j = null;
Scanner scan = new Scanner(System.in);
while (true)
{
// Read input values
System.out.print("i = ");
i = new BigInt(scan.nextLine());
System.out.print("j = ");
j = new BigInt(scan.nextLine());
// Valid input, break
if (i.hasValue() && j.hasValue()) break;
// Invalid input, loop
System.out.println("One of the values is not a valid large integer, try again.");
}
// Perform test operations on i and j
int comparison = i.compareTo(j);
String equality = "";
switch(comparison)
{
case -1: equality = "i is smaller than j"; break;
case 0: equality = "i is equal to j"; break;
case 1: equality = "i is greater than j"; break;
}
System.out.println(equality);
System.out.println("i + i = \t" + i.add(i));
System.out.println("i - j = \t" + i.subtract(j));
System.out.println("i + j = \t" + i.add(j));
System.out.println("j + i = \t" + j.add(i));
System.out.println("i + j + i + j = " + i.add(j).add(i).add(j));
System.out.println("i * i = \t" + i.multiply(i));
System.out.println("i * j = \t" + i.multiply(j));
System.out.println("i * j * i = \t" + i.multiply(j).multiply(i));
BigInt temp = new BigInt(i), faci = new BigInt(1);
while (!temp.isZero())
{
faci = faci.multiply(temp);
temp = temp.subtract(new BigInt(1));
}
System.out.println("Factorial of i:\n" + faci);
}
} Powered by
GeSHi Syntax Highlighting software.
Author of all (other) material unless otherwise specified:
Loren Segal. Copyright 2005.