Problems

1. (32 points) In this series of problems, you will design a class and several methods that act on arbitrarily large or small integers, resembling the BigInteger class. You cannot use any methods from BigInteger, or the BigInteger class itself.

   Warning: This problem is complicated and takes some time to think through. It shouldn't be completed in one sitting! Remember to ask us for help if you get stuck, and to break it down into smaller pieces. We have provided you with a lot of helper methods to make your life easier, so make sure to use them! Most important: follow the directions!

   1. Design the BigInt class, which has a constructor that receives a string. The BigInt class stores a List<Integer> as an instance variable, as well as a boolean for keeping track of whether it is negative. You will need to convert the given string into said list of digits. Store the digits in reverse order, i.e., the least-significant digit (the ones digit) of the number is the first element of the list. Leading zeroes should be omitted from the representation.

      The possible values for the parameter are an optional sign (either positive or negative), followed by one or more digits.

      Below are some example inputs.

      new BigInt("42")         => [2, 4], isNegative = false
      new BigInt("0420")       => [0, 2, 4], isNegative = false
      new BigInt("-42")        => [2, 4], isNegative = true
      new BigInt("0000420000") => [0, 0, 0, 0, 2, 4], isNegative = false
      new BigInt("+42")        => [2, 4], isNegative = false;

   Warning: One thing that a lot of students will do, showcasing a misunderstanding of the problem, is store the value as an integer after parsing it using Integer.parseInt. This will not work, and there is a very simple counterexample to show why.

   2. Override the equals method to return whether this instance represents the same integer as the parameter. If o is not an instance of BigInt, return false.

      new BigInt("42").equals(new BigInt("42"))      => true
      new BigInt("00042").equals(new BigInt("0042")) => true
      new BigInt("+42").equals(new BigInt("42"))     => true
      new BigInt("42").equals(new BigInt("-42"))     => false
      new BigInt("-42").equals(new BigInt("42"))     => false
      new BigInt("422").equals(new BigInt("420"))    => false

   3. Override the hashCode method to return the hash code of the number. The hash code is defined as the hash code, using Objects.hash of its list of digits and the sign (i.e., whether it is positive or negative).

   4. Override the toString method to return a stringified version of the number. Remember to include the negative sign where appropriate. If the number is positive, do not include a sign.

   5. Implement the Comparable<BigInt> interface and override the method it provides, namely public int compareTo(BigInt b2). Return the result of comparing this instance with the parameter. That is, if \(a < b\), return \(-1\), if \(a > b\), return \(1\), and otherwise return \(0\), where \(a\) is this and \(b\) is b2.

   6. Design the BigInt copy() method, which returns a (deep)-copy of this instance representing the same integer. Do not simply copy the reference to the list of digits over to the new BigInt (this violates the aliasing principle that we have repeatedly discussed and can be the cause of relentless debugging).

   7. Design the BigInt negate() method, which returns a copy of this instance of BigInt, but negated. Do not modify this instance.

   8. Design the private boolean areDifferentSigns(BigInt b) method, which returns whether this instance and b have different signs. That is, if one is positive and one is negative, areDifferentSigns returns true, and false otherwise.

   9. Design the private BigInt addPositive(BigInt b) method, which returns a BigInt instance that is the sum of this and b under the assumption that this and b are non-negative. We will use \(A \oplus B\) to symbolically represent this version of addition.

   10. Design the private BigInt subPositive(BigInt b) method, which returns a BigInt instance that is the difference of this and b under the assumption that this and b are non-negative, and the minuend (the left-hand operand) is greater than or equal to the subtrahend (the right-hand operand). We will use \(A ∸ B\) to symbolically represent this version of subtraction.

   11. Design the private BigInt mulPositive(BigInt b) method, which returns a BigInt instance that is the product of this and b under the assumption that this and b are non-negative.

   12. Design the BigInt add(BigInt b) and BigInt sub(BigInt b) methods that returns the sum/difference of this and b respectively. Note that these methods should be a case analysis of the signs of the operands. Use the following equivalences to guide your design. Do not over-complicate these methods. Importantly, sub can be written in exactly one line!

       \[ A - B = A + (-B) \]

       \[ (-A) + (-B) = -(A \oplus B). \]

       \[ A + (-B) = A ∸ B \text{ if } |A| \geq |B|. \text{ Otherwise, } -(B ∸ A). \]

       \[ (-A) + B = B + (-A). \]

   13. Design the BigInt mul(BigInt b) method, which returns the product of this and b. The product of two negative integers is a positive integer, and the product of exactly one positive and exactly one negative is a negative integer.

   Files to Submit: BigInt.java, BigIntTest.java

2. (8 points) An infinite stream is one that, in theory, produces infinite results! We have illustrated this with Java's Stream API, but now we're going to design our own. Consider the IStream interface below:

   interface IStream<T> {
     T next();
   }

   When calling next on a stream, we update the contents of the stream and return the next result. We mark this as a generic interface to allow for any desired return type. For instance, below is a stream that produces factorial values:

   class FactorialStream implements IStream<Integer> {
   
     private int n;
     private int fact;
    
     FactorialStream() {
       this.n = 1;
       this.fact = 1;
     }
   
     @Override
     public Integer next() {
       this.fact *= this.n;
       this.n++;
       return this.fact;
     }
   }

   Testing it with ten calls to next yields predictable results.

   class FactorialStreamTest {
   
     @Test
     void testFactorialStream() {
       IStream<Integer> FS = new FactorialStream();
       assertEquals(1, FS.next());
       assertEquals(2, FS.next());
       assertEquals(6, FS.next());
       assertEquals(24, FS.next());
       assertEquals(120, FS.next());
     }
   }

   Design the FibonacciStream class, which implements IStream<Integer> and correctly overrides next to produce Fibonacci sequence values. You code should not use any loops or recursion. Recall that the Fibonacci sequence is defined as \(f(n) = f(n - 1) + f(n - 2)\) for all \(n \geq 2\). The base cases are \(f(0) = 0\) and \(f(1) = 1\).

   class FibonacciStreamTest {
   
     @Test
     void testFibonacciStream() {
       IStream<Integer> FS = new FibonacciStream();
       assertEquals(0, FS.next());
       assertEquals(1, FS.next());
       assertEquals(1, FS.next());
       assertEquals(2, FS.next());
       assertEquals(3, FS.next());
       assertEquals(5, FS.next());
     }
   }

   Files to Submit: IStream.java, FibonacciStream.java, FibonacciStreamTest.java

3. (8 points) Java's functional API allows us to pass lambda expressions as arguments to other methods, as well as method references (as we saw in Chapter 3). Design the generic FunctionalStream class to implement IStream, whose constructor receives a unary function Function<T, T> f and an initial value T t. Then, override the next method to invoke \(f\) on the current element of the stream and return the previous. For example, the following test case shows the expected results when creating a stream of infinite positive multiples of three.

   class FunctionalStreamTester {
   
     @Test
     void testMultiplesOfThreeStream() {
       IStream<Integer> mtll = new FunctionalStream<>(x -> x + 3, 0);
       assertEquals(0, mtll.next());
       assertEquals(3, mtll.next());
       assertEquals(6, mtll.next());
       assertEquals(9, mtll.next());
       assertEquals(12, mtll.next());
     }
   }

   What's awesome about this exercise is that it allows us to define the elements of the stream as any arbitrary lambda expression, meaning that we could redefine FactorialStream and FibonacciStream in terms of FunctionalStream. We can generate infinitely many ones, squares, triples, or whatever else we desire.

   Files to Submit: FunctionalStream.java, FunctionalStreamTest.java

4. (8 points) Design the StreamTake class. Its constructor should receive an IStream and an integer \(n\) denoting how many elements to take, as parameters. Then, write a List<T> getList() method, which returns a List<T> of \(n\) elements from the given stream.

   class StreamTakeTester {
   
    @Test
    void testStreamTake() {
     StreamTake llt1 = new StreamTake(new FactorialStream(), 8);
     StreamTake llt2 = new StreamTake(new FibonacciStream(), 10);
     assertEquals("[1, 2, 6, 24, 120, 720, 5040, 40320]",
                          llt1.getList().toString());
     assertEquals("[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]",
                          llt2.getList().toString());
    }
   }

   Files to Submit: StreamTake.java, StreamTakeTest.java

5. (8 points) In this exercise, you will design an interface and classes that format numbers in different ways.

   1. Design the INumberFormat interface, which contains the String format(long n) method.

   2. Design the DollarFormat class, which implements INumberFormat, and returns a string where the number is prepended with a dollar sign "$".

   3. Design the CommaFormat class, which implements INumberFormat, and returns a string where the number contains commas where appropriate. For example, format(4412) should return "4,412".

   4. Finally, design the StandardFormat class, which implements INumberFormat, and returns a string where the number is simply returned as a string.

   Files to Submit: INumberFormat.java, DollarFormat.java, CommaFormat.java, StandardFormat.java, NumberFormatTest.java

6. (8 points) Design the abstract Ticket class, which represents a ticket that can be purchased. A ticket has a price and a unique ticket identifier. Each ticket has a method getPrice that returns the cost of the ticket, and a method getId that returns the ticket's unique identifier. The ticket identifier should be incremented via a static variable that is incremented and then assigned to the instance variable. The static variable should be initialized to 0, and the first ticket should have an identifier of 0. The Ticket class constructor should only receive a ticket cost (in USD). Override equals to return whether two tickets are the same, which is determined by whether they have the same ticket identifier. Override hashCode to return the hash code of the ticket identifier.

   Then, design the following concrete subclasses (note that none of these concrete classes should override hashCode or equals):

   • DiscountTicket, which receives both the price and the discount as parameters. The discount should be a value between 0.0 and 1.0. Apply the discount inside an overridden getPrice method.

   • VirtualTicket, which adds a convenience fee of $2.50 on top of whatever that ticket's price is.

   Files to Submit: Ticket.java, DiscountTicket.java, VirtualTicket.java, TicketTest.java

7. (28 points) This exercise is based on the ASPL interpreter that we wrote in the textbook. A copy of the starter code is listed in Canvas. In the autograder, you only need to submit the files we list below; not the starter code. Do not modify the starter code.

   1. First, design the ProgramNode class, which allows the user to define a program as a sequence of statements rather than a single expression. A ProgramNode evaluates all of the statements in order, and returns the result of the last expression.

   2. Design the DefNode class, which allows the user to create a global definition. Because we're now working with definitions that do not extend the environment, we need to directly mutate environments. To be clear, this means that when we create a global definition via DefNode, we're expressing the idea that, from that point forward, the (root) environment should contain a binding from the identifier to whatever value it binds.

      Note: If your Environment class does not have a set method, you will need to add one.

   3. Design the FuncNode node. We will consider a function definition as an abstract tree node that begins with FuncNode. Its constructor has two parameters: a list of formal parameters as strings and the function body as an abstract syntax tree. You should override eval by returning the FuncNode itself; do not evaluate the body!

      Warning: Don't forget to add an accessor for the formal parameters and the function body!

      Note 1: In this language, all functions resolve to values; we do not support void functions.

      Note 2: This language supports first-class functions, which means that functions can be passed as arguments to other functions and returned as values from functions, just like data!.

   4. Design the ApplyNode class, which applies a function to its arguments. You do not need to consider applications in which the first argument reduces to a non-function.

      Calling/Invoking a function is perhaps the hardest part of this exercise. Here's the idea, which is synonymous and shared with almost all programming languages:

      1. First, evaluate each argument of the function call, which produces a list of evaluated abstract syntax trees.

      2. We then want to create an environment in which the formal parameters are bound to their arguments. Overload the extend method in Environment to now receive a list of string identifiers and a list of (evaluated) AST arguments. Bind each formal to its corresponding AST, and return the extended environment.

      3. Evaluate the operator/function child of the abstract syntax tree. Cast the result to a FuncNode.

      4. Call eval on the function body and pass to it the new (extended) environment.

      This seems like a lot of work (because it is), but it means you can write really cool programs, including those that use recursion!

      new ProgramNode(
        new DefNode("!", 
          new FuncNode(
            List.of("n"),
            new IfNode(
              new PrimNode("eq?", 
                new VarNode("n"), 
                new NumNode(0)),
              new NumNode(1),
              new PrimNode("*", 
                new VarNode("n"), 
                new ApplyNode(new VarNode("!"), 
                  new PrimNode("-", 
                  new VarNode("n"), 
                  new NumNode(1))))))),
        new ApplyNode(new VarNode("!"), new NumNode(5)))

   Files to Submit: ProgramNode.java, DefNode.java, FuncNode, ApplyNode.java, Environment.java, AsplTest.java