# Part 1 Short Answers

20 Points

## Q1.1 - 5 Points

In Java, methods on a class can be marked static. Briefly explain the difference between static methods and methods which lack that marking. Give an example of when you would use one and when you would the other.

```
Static methods are associated with a class, instance methods with an instance.  The first argument of an instance method is a pointer to the instance (aka `this`), static methods are more like plain C functions and do not pass `this`.
```

## Q1.2 - 5 Points

Briefly explain why Java has primitive types and list three of those types.

```
Performance.  primitive types map directly onto the hardware instruction set.  int, long, float, double, boolean, byte, short, char
```

## Q1.3 - 5 Points

List three attributes that a well-engineered software system might be expected to have and briefly describe why each would be desirable.

Any of the things we've been talking about all semester.

- Modularity - allows the system to grow and change because of low-coupling
- Reliability - provides users what they need without errors
- Availability - makes sure that users can access what they need when they need it.
- Securability - ensures that the system does only what it is intended
- Scalability - allows many users simultaneously without degrading the other features

## Q1.4 - 5 Points

Suppose you have a need to frequently insert items at the head of a list. You can choose between representing your list as an ArrayList or a LinkedList. State which you would chose and your reasons for choosing it.

```
LinkedList.  It has O(1) performance on insertions
```

# Part 2 Lists

20 Points

In this problem, you will write part of DLL, a class that the implements a DoublyLinkedList similarly to class LL from lecture. Here is the beginning of the class, to get you started.

```
class DLL<E>  {
  private class Cell {
    public E element; public Cell next; public Cell prev;
        public Cell(E element, Cell prev, Cell next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }
    }
    private Cell head; private Cell tail;
  ...
```

## Q2.1 - 4 Points

Write a method void append(E x) { ... } that appends the value x, to the tail of the list. Properly update both head and tail as necessary.

You may type your answer here:

```
public void append(E x) {
        Cell newCell = new Cell(x, null, null);
        if (head == null) {
            head = newCell;
            tail = newCell;
        } else {
            tail.next = newCell;
            newCell.prev = tail;
            tail = newCell;
        }
    }
```

## Q2.2 - 5 Points

Write a method void prepend(E x) { ... } that inserts a value x at the head of the list. Properly update both head and tail as necessary.

```
public void prepend(E x) {
        Cell newCell = new Cell(x, null, null);
        if (head == null) {
            head = newCell;
            tail = newCell;
        } else {
            head.prev = newCell;
            newCell.next = head;
            head = newCell;
        }
    }
```

## Q2.3 - 5 Points

Write a method void insertAheadOf(int index, E newElement) { ... } that inserts an element at the indicated position in the list, throws IndexOutOfBoundsException if index is negative or larger than the number of values in the list and leaves the list the correct state.

```
public void insertAheadOf(int index, E newElement) {
        Cell currentCell = head;
        Cell newCell = new Cell(newElement, null, null);
        for (int i = 1; i == index; i++) {
            currentCell = currentCell.next;
            if (currentCell == null || index < 0) {
                throw new IndexOutOfBoundsException();
            }
        }
        Cell prev = currentCell.prev;
        currentCell.prev = newCell;
        newCell.next = currentCell;
        if (prev != null) prev.next = newCell;
    }
```

## Q2.4 - 6 Points

Write a method E removeAt(int index) { ... } that removes the element at the indicated position in the list, throws IndexOutOfBoundsException if index is negative or larger than the number of values in the list and leaves the list the correct state.

```
 public E removeAt(int index) {
        Cell currentCell = head;
        for (int i = 1; i == index; i++) {
            currentCell = currentCell.next;
            if (currentCell == null || index < 0) {
                throw new IndexOutOfBoundsException();
            }
        }
        Cell prev = currentCell.prev;
        Cell next = currentCell.next;
        prev.next = next;
        next.prev = prev;
        return currentCell.element;
    }
```

# Part 3 - The Observer Pattern

30 Points

In this problem, we will consider the Observer Pattern, in which we transmit state changes in one object (the Subject) to zero or more other objects (the Observers). In particular, we will notify multiple objects of updates to stock prices, which we will represent as a class with ticker symbols (Strings) and prices (Doubles). Because in the future, we might want to process ticks for several different types of securities in addition to stocks, the type of security will be generic.

To get you started here are the interfaces for the pattern:

```
import java.util.*;
interface Ticker<T> {
    void tick(T newPrice);
}

interface TickerObserver<T> {
    void update(T newPrice);
}

interface TickerSubject<T> extends Ticker<T> {
    void attach(TickerObserver<T> observer);
    void detach(TickerObserver<T> observer);
    void notifyObservers();
}

class StockPrice {
    String symbol;
    double price;
}
```

You will be asked to provide classes which implement the pattern correctly below.

## Q3.1 The Stock class

6 Points

Provide a class Stock (which is not generic) with 4 member variables:

```
    Set<TickerObserver<StockPrice>> observers;
    StockPrice current;
    Ticker<StockPrice> ticker;
    TickerSubject<StockPrice> subject;
```

Upon initialization, observers should be a HashSet (which has an zero-arg construct), current should be null, ticker should be an instance of StockTicker which we will define below (which also has a zero-arg constructor) and subject should be an instance of StockSubject (with again a zero-arg constructor).

```
class Stock {
    Set<TickerObserver<StockPrice>> observers = new HashSet<>();
    StockPrice current = null;
    Ticker<StockPrice> ticker = new StockTicker();
    TickerSubject<StockPrice> subject = new StockSubject();
}
```

## Q3.2 The StockTicker class

9 Points

Provide the code for an inner class on Stock called: StockTicker which implements the Ticker interface using StockPrice as its generic type. Your implementation should set current to a new value and cause the subject to notify its observers of the change, if the value of current is NOT null.

```
   class StockTicker implements Ticker<StockPrice> {
        public void tick(StockPrice newPrice) {
            current = newPrice;
            if (current != null)
                subject.notifyObservers();
        }
    }
```

## Q3.3 The StockSubject class

15 Points

Provide the code for an inner class on Stock called: StockSubject which implements the TickerSubject interface using StockPrice as its generic type.

This method should:

In attach, use Set's add(Object) method to add a new observer to observers and update the new observer with the current value of the stock price. In detach, use Set's remove(Object) method to remove a new observer from observers In notifyObservers, loop over the observers and invoke each observer's update method. You may type your answer here:

```
   class StockSubject implements TickerSubject<StockPrice> {
        @Override
        public void attach(TickerObserver<StockPrice> observer) {
            observers.add(observer);
            if (current != null) {
                observer.update(current);
            }
        }

        @Override
        public void detach(TickerObserver<StockPrice> observer) {
            observers.remove(observer);
        }

        @Override
        public void notifyObservers() {
            for (TickerObserver<StockPrice> observer : observers) {
                observer.update(current);
            }
        }
    }
}
```

## Part 4 - Iterators and Processors

30 Points Recall the DLL class from Question 2:

```
public class DLL<E>  {
    private class Cell {
        public E element; public Cell next; public Cell prev;
        public Cell(E element, Cell prev, Cell next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }
    }
    private Cell head; private Cell tail;
    ...
```

## Q4.1 10 Points

Implement a class DLLReverseIterator which implements the Iterator interface for DLL

<e> iterating over the elements of DLL<e> in reverse order.
Below is the Iterator interface, for reference. </e></e>

```
interface Iterator<E> {
  boolean hasNext();
  E next();
}
```

```
   class DLLReverseIterator implements Iterator<E> {
        Cell current;

        DLLReverseIterator() {
            current = tail;
        }

        public boolean hasNext() {
            return current != null;
        }

        public E next() {
            E tmp = current.element;
            current = current.prev;
            return tmp;
        }
    }
```

## Q4.2 Map

10 Points

Recall the Processor interface from class:

```
public interface Processor<E> {
    public void process(E x);
}
```

and the iterate method:

```
    public void iterate(Processor<E> p) {
        for (Cell current = head;
             current != null;
             current = current.next) {
            p.process(current.element);
        }
    }
```

also recall that this method could be used to implement the map method from other languages. Map converts a the generic from one type to another. e.g. it can convert a `DLL<Integer>` to a `DLL<String>`. Let's implement that method.

Provide an implementation of map which

1. processes the list in forward order.

2. Uses the following form of Processor:

  ```
  public interface MapProcessor<E, F> {
  public F process(E x);
  }
  ```

(N.B. This form returns a value rather than returning void.)

1. and finally, returns a DLL

  <f>
  </f>

To get you started here is the declaration of a Mapper inner class on DLL:

```
    public class Mapper<F> {
        public DLL<F> map(MapProcessor<E, F> p) {
         ...
        }
    }
```

You are to implement the function in the location shown as ... using the MapProcessor type above.

Hint: what you are doing here is converting a DLL

<e> into a DLL<f> such that for every E in the first DLL, there is a corresponding F in the returned DLL which is produced by the MapProcessor.  You do this by calling the process method on MapProcessor</f></e>

```
public class Mapper<F> {
   public DLL<F> map(MapProcessor<E, F> p) {
        DLL<F> mapped = new DLL<>();
        for (Cell current = head; current != null; current = current.next) {
            mapped.append(p.process(current.element));
        }
        return mapped;
    }
}
```

## Q4.3 Using Map

10 Points

Recall from class that java allows us to make "anonymous inner classes". Assume that you have instance of type `DLL<int>` named dll. Using the map method from the previous problem to create a `DLL<String>`.

Hints:

1. Your statement should look like:

```
DLL<String> newdll = dll.map(
    ...
);
```

It should create a new `MapProcessor<int, String>`

You may use the static method `valueOf(int)` on String to do the conversion.<br>
You may type your answer here:

```
DLL<String> newdll = dll.map(
    new MapProcessor<Integer, String>() {
        public String process(Integer x) { return String.valueOf(x); }
    }
);
```