Homework 1: Packages, Interfaces, Generics, Exceptions, Iteration

CS61B

Review: What is an Interface? Why would you want one?

As discussed in class, an interface is a formal contract between a class and the outside world. If your class claims to implement an interface, then all methods defined by that interface must appear in your class (or somewhere in your superclass) before the class will successfully compile. This is a way of enforcing promised behavior. All methods that you declare or define are automatically public and abstract (even if you omit the public keyword).

Review: What is an Abstract Class? Why would you want one?

Methods and classes can be declared as abstract using the abstract keyword. Abstract classes cannot be instantiated, but they can be subclassed using the extends keyword. Unlike interfaces, abstract classes can provide implementation inheritance for features other than public methods, including instance variables.

Classes that implement interfaces will inherit all of the methods and variables from that interface. If an implementing class fails to implement any abstract methods inherited from an interface, then that class must be declared abstract, as in:

public abstract class AbstractBoundedQueue

As an aside, it is also possible to declare additional abstract methods. To do so, the method must be defined with the abstract keyword and without an implementation (without braces, and followed by a semicolon), like this:

abstract void moveTo(double deltaX, double deltaY);

We won't explicitly define any non-inherited methods as abstract in HW1, but it's a thing you might find useful someday (perhaps in the HugLife lab during week 6).

If you're having trouble compiling your AbstractBoundedQueue.java file from the command line, because the compiler can't find BoundedQueue.class, try compiling with:

javac BoundedQueue.java AbstractBoundedQueue.java

or if you want to compile ALL java files in a folder, you can just do:

javac *.java

This is a minor quirk in the way the javac compiler behaves when compiling from inside package directories.

Side note: When to Use a Interface versus Abstract Class

In practice, in can be a little unclear when to use an interface and when to use an abstract class. One mostly accurate metaphor that might help is that you can think of an interface as defining a "can-do" or an "is-a" relationship, whereas an abstract class should be a stricter "is-a" relationship. The difference can be subtle, and you can often use one instead of the other.

In practice, large Java libraries often have a hierarchy of interfaces, which are extended by abstract classes that provided default implementations for some methods, and which are in turn ultimately implemented by concrete classes. A good example is the Collection interface: It extends Iterable (which is its superinterface), and is implemented by many subinterfaces (i.e. List, Set, Map), which in turn have their own abstract implementations (AbstractList, AbstractSet AbstractMap). However, for smaller programs, the hierarchy is often stubbier, sometimes starting with an abstract class. For example, we could have just started with AbstractBoundedQueue at the top of the hierarchy and skipped having a BoundedQueue interface altogether.

做Task 3: ArrayRingBuffer的时候，写好后想要测试TestArrayRingBuffer.java, 但遇到ClassNotFoundException报错：

Exception in thread "main" java.lang.ClassNotFoundException: synthesizer.TestArrayRingBuffer
    at java.net.URLClassLoader.findClass(URLClassLoader.java:381)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:424)
    at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:331)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:357)
    at java.lang.Class.forName0(Native Method)
    at java.lang.Class.forName(Class.java:264)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:123)

我用命令行编译TestArrayRingBuffer.java,报下列错：

结果是因为16psring做hw的前提是设置一个环境变量,这点因为我之前全是跟的17pring完全不知道。
资料：Lab 3b: Installing the 61B Libraries

设置好以后编译没问题，但IntelliJ继续报错，命令行却可以顺利通过测试。

在写ArrayRingBuffer.java时候，发现泛型是不能初始化对象的，比如下面：

public ArrayRingBuffer(int capacity) {
        // TODO: Create new array with capacity elements.
        //       first, last, and fillCount should all be set to 0.
        //       this.capacity should be set appropriately. Note that the local variable
        //       here shadows the field we inherit from AbstractBoundedQueue, so
        //       you'll need to use this.capacity to set the capacity.
        first = 0;
        last = 0;
        this.fillCount = 0;
        this.capacity = capacity;
        rb = new T [this.capacity];
    }

会报错：

Type parameter 'T' cannot be instantiated directly

所以我按照后面的要求，把T改成了这里需要用到的类型double.

写到产生一个不重复的随机的-0.5 -0.5的double这里，用到了Math.random用法，如何才能产生一个范围内不重复的随机数呢？

参考:JAVA随机数之多种方法从给定范围内随机N个不重复数

写完之后run那个TestArrayRingBuffer.java, 结果IntelliJ继续报错No class found, 想要解决这个问题，结果找到了：
Class Not Found: Empty Test Suite in IntelliJ

一个没有vote的投票帮到了我：

打开Project Structure > Modules

Output path 和 Test output path一定要写完整路径!!

and then everything works fine.

Task 5: Iteration and Exceptions

As an exercise in making your data structures more industrial strength, we'll add the ability to iterate through a BoundedQueue and also ensure that it throws exceptions when given invalid inputs.

BoundedQueue

First, modify your BoundedQueue<T> interface so that it extends Iterable<T> and add the required abstract method to the interface. You'll need to import java.util.Iterator.

abstractBoundedQueue

Consider your AbstractBoundedQueue. You don't need to change anything in this class to support iteration. Make sure you understand why.
这个为什么？

ArrayRingBuffer

Now finally add the required iterator() method to ArrayRingBuffer. You'll need to define a private class that implements the Iterator interface. See lecture 14 for an example: github slides.

这里留意一下iterator的惯用写法：

public class MapWizard implements Iterator<K> {
        private int notionOfWhereHeIs;
        public MapWizard() {
            notionOfWhereHeIs = 0;
        }
        public boolean hasNext() {
            return (notionOfWhereHeIs < size);
        }
        public K next() {
            K currentThing = keys[notionOfWhereHeIs];
            notionOfWhereHeIs += 1;
            return currentThing;
        }
    }
    public Iterator<K> iterator() {
        return new MapWizard();
    }

Exceptions
Now modify ArrayRingBuffer so that it throws a RuntimeException with the String "Ring Buffer Overflow" when a user attempts to enqueue into a full ArrayRingBuffer, and "Ring Buffer Underflow" when a user attempts to deque an empty ArrayRingBuffer.