Project 1: Data Structures

前言

Project1 文档：https://sp21.datastructur.es/materials/proj/proj1/proj1
Project1 EC 文档：https://sp21.datastructur.es/materials/proj/proj1/proj1ec

Project 1 将用到继承的相关知识，所以在完成之前最好先将继承章节学完。当然如果只是查看数据结构的实现请自便。

Introduction

在 Project 1 中，我们将同时使用链表和数组来实现一个双端队列（Double Ended Queue）。这个 Project 将分为两个部分：数据结构部分与应用部分。

对于数据结构部分，我们将在包中创建两个 Java 文件：LinkedListDeque.java 和 ArrayDeque.java，实现下面的 public 方法，并使用从 Lab 3 中学到的随机测试与计时测试技能来验证数据结构的正确性。

对于应用部分，我们将创建一个 Java 文件 MaxArrayDeque.java 并用我们的包实现一个能够利用 Guitar Hero 演奏音乐的声音合成器。我们必须测试 MaxArrayDeque，但声音合成器的测试已经给定。

包

这个项目中我们使用包来实现逻辑和功能的分离。本项目中我们将有两个包：deque 包提供数据结构的实现，gh2 实现能够演奏 guitar hero 的合成器。但具体什么是“包”？

包（package）是一组 Java 类的集合，这些类共同协作以实现某些共同的目标。我们在了解包之前就已经见过了一些包，例如 org.junit 是一个包含了各种用于测试的类的包，如包含了 assertEquals 方法的 Assert 类。换句话说，当我们看见了 org.junit.Assert.assertEquals，org.junit 是包名，Assert 是类名，而 assertEquals 便是方法名。我们称 org.junit.Assert.assertEquals 为方法的规范名称（canonical name）而 assertEquals 是方法的简单名称（simple name）。

当创建一个包时，我们要通过在文件顶部使用 package 关键字指定包名来表明代码是包的一部分。

package deque;

当需要调用我们 deque 包中的类或方法时，需要使用规范名称如：deque.ArrayDeque ;或使用 import deque.ArrayDeque，这样在编码过程中只要使用简称 ArrayDeque 就好了。

通常，包的命名规则是采用代码实体的互联网域名的反序形式。例如，JUnit 库的官网地址是 junit.org，因此其包名就被命名为 org.junit。

那为什么要使用包？归根结底是为了“规范”。只要包名不同，即使是相同的类名也可以在各自的包中自由使用。

而我们可以将包看作是电脑中不同的文件夹。当我们构建一个大项目时，用不同的包来管理是一个很好的主意。

Deque

deque 的实现必须包含下列方法：

• public void addFirst(T item)：添加一个 T 型变量到 deque 头部。可以假设 item 永不为空。
• public void addLast(T item)：添加一个 T 型变量到 deque 尾部。可以假设 item 永不为空。
• public boolean isEmpty()：判断 deque 是否为空。为空返回 true，非空返回 false。
• public int size()：返回 deque 中元素个数。
• public void printDeque()：从头至尾打印 deque 中的元素，用空格分隔，打印完毕后换行。
• public T removeFirst()：删除并返回 deque 第一个元素。如果不存在则返回 null。
• public T removeLast()：删除并返回 deque 最后一个元素。如果不存在则返回 null。
• public T get(int index)：返回下标为 index 的元素（从 0 开始），不存在则返回 null。

除此之外，还需要实现两个特殊的方法：

• public Iterator<T> iterator()：我们将使 deque Iterable，所以我们需要通过该方法返回迭代器。
• public boolean equals(Object o)：判断参数 o 是否与 deque 相等（当 o 为一个包含相同元素及顺序的 deque 时我们认为 o 与 deque 相等）。

注意：并非 Deque 接口实现 Iterable 而是 LinkedListDeque 和 ArrayDeque，否则 autograder 将出现 API error。

deque 应当能够接受泛型。

Linked List Deque

任务

在 proj1/deque 目录下创建一个 LinkedListDeque.java 文件并确保声明是包的一部分。

我们在实现中需要确保：

• add 和 remove 操作不能包含任何循环或迭代。单次操作必须花费常数时间，即执行时间不依赖于 deque 的大小。这意味着你无法使用循环遍历整个 deque。
• get 必须使用迭代。
• size 必须花费常数时间。
• 不要保留对 deque 中不存在元素的引用。

除此之外还需要实现：

• public LinkedListDeque()：构造一个空 deque。
• public T getRecursive(int index)：与 get 功能相同，但用递归实现。

必要时，可以在 LinkedListDeque.java 中添加任何 private 辅助类或方法。

如 Lists 中最终提到的两种解法：我们可以尝试设置首尾两个哨兵节点，或采用循环链表的形式。我将用循环链表的方式实现。

代码实现（并非最终版本，需要按照 Deque 接口修改）

package deque;

import java.util.Iterator;

public class LinkedListDeque<T> implements Iterable<T> {
    private class Node {
        private Node prev, next;
        private T item;

        private Node(Node p, T i, Node n) {
            prev = p;
            item = i;
            next = n;
        }
    }

    private int size;
    private Node sentinel;

    public LinkedListDeque() {
        size = 0;
        sentinel = new Node(null, null, null);
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    public void addFirst(T item) {
        Node newNode = new Node(sentinel, item, sentinel.next);
        newNode.next.prev = newNode;
        sentinel.next = newNode;
        size += 1;
    }

    public void addLast(T item) {
        Node newNode = new Node(sentinel.prev, item, sentinel);
        newNode.prev.next = newNode;
        sentinel.prev = newNode;
        size += 1;
    }

    public T removeFirst() {
        if (sentinel.next == sentinel) {
            return null;
        }
        Node removedNode = sentinel.next;
        removedNode.prev.next = removedNode.next;
        removedNode.next.prev = removedNode.prev;
        removedNode.prev = null;
        removedNode.next = null;
        size -= 1;
        return removedNode.item;
    }

    public T removeLast() {
        if (sentinel.prev == sentinel) {
            return null;
        }
        Node removedNode = sentinel.prev;
        removedNode.prev.next = removedNode.next;
        removedNode.next.prev = removedNode.prev;
        removedNode.prev = null;
        removedNode.next = null;
        size -= 1;
        return removedNode.item;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void printDeque() {
        for (Node i = sentinel.next; i != sentinel; i = i.next) {
            System.out.print(i.item);
            if (i.next != sentinel) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }

    public T get(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        Node p = sentinel.next;
        for (int i = 0; i < index; ++i) {
            p = p.next;
        }
        return p.item;
    }

    private T recursionHelper(int index, Node p) {
        if (index == 0) {
            return p.item;
        }
        return recursionHelper(index - 1, p.next);
    }

    public T getRecursive(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        return recursionHelper(index, sentinel.next);
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedListDequeIterator();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o instanceof LinkedListDeque) {
            LinkedListDeque<T> otherLLD = (LinkedListDeque<T>) o;
            if (size != otherLLD.size) {
                return false;
            }
            for (int i = 0; i < size; ++i) {
                T a = get(i);
                T b = otherLLD.get(i);
                if (a == null) {        // 确保处理 null 值
                    if (b != null) {
                        return false;
                    }
                } else if (!a.equals(b)) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

    private class LinkedListDequeIterator implements Iterator<T> {
        private Node p;

        LinkedListDequeIterator() {
            p = sentinel.next;
        }

        @Override
        public boolean hasNext() {
            return p != sentinel;
        }

        @Override
        public T next() {
            T returnVal = p.item;
            p = p.next;
            return returnVal;
        }
    }
}

Array Deque

任务

在 proj1/deque 目录下创建一个 ArrayDeque.java 文件并确保声明是包的一部分。

我们在实现中需要确保：

• 除去 resize 操作，add 和 remove 操作必须花费常数时间。
• get 和 size 必须花费常数时间。
• 数组的起始长度为 8。
• 无论何时我们的数组占用的内存都应与数组中元素的数量匹配。例如：如果向数组中添加 10000 个元素后删除 9999 个，数组占用的内存则不应再是 10000 个元素的大小了。对于长度为 16 及以上的数组，使用率应至少为 25%。这意味着如果我们删除数组中的一个元素时，剩余的元素数量少于数组总长度的 25%，我们需要对数组进行缩容

除此之外还需要实现：

• public ArrayDeque()：构造一个空 deque。

必要时，可以在 ArrayDeque.java 中添加任何 private 辅助类或方法。

为了便于对数组头部和尾部的操作，你需要以某种方式追踪数组中哪些索引位置存放着双端队列（Deque）的头部和尾部元素。我们强烈建议你在本练习中将数组视为循环的。换句话说，如果你的队首元素在数组的第 0 个位置，而你调用了 addFirst，那么新的队首应该回绕到数组的末尾（也就是说，新的队首元素将放在底层数组的最后一个位置）。

采用循环数组的方法会比非循环的方法少很多麻烦。

写点测试。

代码实现（并非最终版本，需要按照 Deque 接口修改）

package deque;

import java.util.Iterator;

public class ArrayDeque<T> implements Iterable<T> {
    private T[] items;
    private int size;
    private int nextFirst;
    private int nextLast;

    public ArrayDeque() {
        items = (T[]) new Object[8];
        size = 0;
        nextFirst = 7;
        nextLast = 0;
    }

    private int mod(int index) {
        int m = items.length;
        return (index % m + m) % m; // 利用求模保证下标在[0, items.length)区间内且非负
    }

    private void resize(int capacity) {
        T[] a = (T[]) new Object[capacity];
        for (int i = 0; i < size; ++i) {
            a[i] = get(i);
        }
        items = a;
        nextFirst = items.length - 1;
        nextLast = size;
    }

    public void addFirst(T item) {
        if (size == items.length) {
            resize(items.length * 2);
        }
        items[nextFirst] = item;
        nextFirst = mod(nextFirst - 1); // nextFirst 向后移动
        size += 1;
    }

    public void addLast(T item) {
        if (size == items.length) {
            resize(items.length * 2);
        }
        items[nextLast] = item;
        nextLast = mod(nextLast + 1); // nextLast 向前移动
        size += 1;
    }

    public T removeFirst() {
        if (isEmpty()) {
            return null;
        }
        if (size < items.length / 4 && items.length >= 16) {
            resize(items.length / 2);
        }
        nextFirst = mod(nextFirst + 1); // nextFirst 向前移动
        T removedItem = items[nextFirst];
        items[nextFirst] = null;
        size -= 1;
        return removedItem;
    }

    public T removeLast() {
        if (isEmpty()) {
            return null;
        }
        if (size < items.length / 4 && items.length >= 16) {
            resize(items.length / 2);
        }
        nextLast = mod(nextLast - 1);   // nextLast 向后移动
        T removedItem = items[nextLast];
        items[nextLast] = null;
        size -= 1;
        return removedItem;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void printDeque() {
        for (int i = 0; i < size; ++i) {
            System.out.print(get(i));
            if (i != size - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }

    // 处理逻辑下标与物理下标的对应
    public T get(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        return items[mod(nextFirst + 1 + index)];
    }

    @Override
    public Iterator<T> iterator() {
        return new ArrayDequeIterator();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o instanceof ArrayDeque) {
            ArrayDeque<T> otherAD = (ArrayDeque<T>) o;
            if (size != otherAD.size) {
                return false;
            }
            for (int i = 0; i < size; ++i) {
                T a = get(i);
                T b = otherAD.get(i);
                if (a == null) {        // 确保处理 null 值
                    if (b != null) {
                        return false;
                    }
                } else if (!a.equals(b)) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

    private class ArrayDequeIterator implements Iterator<T> {
        private int index;

        ArrayDequeIterator() {
            index = 0;
        }

        @Override
        public boolean hasNext() {
            return index < size;
        }

        @Override
        public T next() {
            T returnVal = get(index);
            index += 1;
            return returnVal;
        }
    }
}

Project 1: Checkpoint

完成了上面两个数据结构就可以提交 gradescope 的 Project 1: Checkpoint 了。Checkpoint 只是为了确保你跟得上脚步，所以它只会测试一些基本功能如：所有 add、所有 remove、size、isEmpty、get方法，即我们不会测试 equals(Object o) 和 iterator()。

值得一提的是，我们不会向 ArrayDeque 添加超过 8 个元素，所以也暂时不需要担心 resize 的问题。

MaxArrayDeque

任务

现在我们已经实现了 ArrayDeque，现在我们将创建一个 MaxArrayDeque。MaxArrayDeque 除了拥有 ArrayDeque 的所有方法，还要两个额外的方法和一个新的构造器：

• public MaxArrayDeque(Comparator<T> c)：利用给定的 Comparator 创建 MaxArrayDeque。
• public T max()：返回由先前给定的 Comparator 比较获得的 deque 中的最大值。如果 MaxArrayDeque 为空，应当返回 null。
• public T max(Comparator<T> c)：返回由参数 Comparator c 比较获得的 deque 中的最大值。如果 MaxArrayDeque 为空，应当返回 null。

MaxArrayDeque 不仅可以通过构造器传入的 Comparator<T>，还可以通过传入的其它任意的 Comparator<T> 比较出自身最大的元素。

这一节我们并不关心 equals(Object o) 方法，所以只要合适，可以自由定义。

如果你尝试从 ArrayDeque 中拷贝代码，那你尝试的方向恐怕错了，因为冗余是我们对抗复杂性最棘手的敌人之一。

记得写点测试。

代码实现

// File: MaxArrayDeque.java
package deque;

import java.util.Comparator;

public class MaxArrayDeque<T> extends ArrayDeque<T> {
    private Comparator<T> comparator;

    public MaxArrayDeque(Comparator<T> c) {
        comparator = c;
    }

    public T max() {
        return max(comparator);
    }

    public T max(Comparator<T> c) {
        if (isEmpty()) {
            return null;
        }
        int maxDex = 0;
        for (int i = 0; i < size(); ++i) {
            if (c.compare(get(maxDex), get(i)) < 0) {
                maxDex = i;
            }
        }
        return get(maxDex);
    }
}

// File: MaxArrayDequeTest.java
package deque;

import org.junit.Test;

import java.util.Comparator;

import static org.junit.Assert.*;

public class MaxArrayDequeTest {
    @Test
    public void testIntegerDeque() {
        MaxArrayDeque<Integer> ad1 = new MaxArrayDeque<>(new IntegerComparator());
        for (int i = 0; i < 100000; ++i) {
            ad1.addFirst(i);
        }
        for (int i = 100001; i < 200000; ++i) {
            ad1.addLast(i);
        }
        assertEquals(199999, (int) ad1.max());
    }

    @Test
    public void testStringDeque() {
        MaxArrayDeque<String> ad1 = new MaxArrayDeque<>(new StringComparator());
        ad1.addFirst("Elyse");
        ad1.addLast("Sture");
        ad1.addFirst("Benjamin");
        ad1.addLast("Oski");
        ad1.addFirst("Cerebus");
        assertEquals("Sture", ad1.max());
    }

    @Test
    public void testNullDeque() {
        MaxArrayDeque<Integer> ad1 = new MaxArrayDeque<>(new IntegerComparator());
        MaxArrayDeque<String> ad2 = new MaxArrayDeque<>(new StringComparator());
        assertEquals(null, ad1.max());
        assertEquals(null, ad2.max());
    }

    private static class IntegerComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer a, Integer b) {
            return a.compareTo(b);
        }
    }

    private static class StringComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            return a.compareTo(b);
        }
    }
}

Deque 接口

任务

这是 Deque 部分的最后一个任务。目前我们的 deque 已经实现了以下 API，或者说行为：

public void addFirst(T item)
public void addLast(T item)
public boolean isEmpty()
public int size()
public void printDeque()
public T removeFirst()
public T removeLast()
public T get(int index) 

之后我们的程序将依赖于这些方法，底层是通过 ArrayDeque 还是 LinkedListDeque 实现并不重要。所以为了将这些方法归档，我们将借用 interface 的力量。

• 在 proj1/deque 目录下创建一个 Deque.java 文件包含上面的所有方法，并确保声明是包的一部分。确保使用 interface 关键字来代替 class。
• 添加 implements Deque<T> 来修改你的 ArrayDeque 和 LinkedListDeque 以确保它们实现接口。
• 为所有重写的方法添加 @Override 标签。
• 在 Deque 接口中给出 isEmpty() 的默认实现，接着就可以将之前在 ArrayDeque 和 LinkedListDeque 中实现的 isEmpty() 删掉了。
• 最后需要将 equals 方法中的 LinkedListDeque 类型或是 ArrayDeque 类型换成 Deque 接口以保证统一性。

现在你的代码就可以在完整版的 autograder 上正常编译了。

代码实现

package deque;

public interface Deque<T> {
    void addFirst(T item);

    void addLast(T item);

    int size();

    void printDeque();

    T removeFirst();

    T removeLast();

    T get(int index);

    default boolean isEmpty() {
        return this.size() == 0;
    }
}

除了 Deque 接口，你还需要按照要求对 LinkedListDeque 和 ArrayDeque 进行修改。

Guitar Hero

在这一部分我们将创建另一个包，利用我们刚刚构建好的 deque 包来生成合成的乐器。我们将利用我们的数据结构来实现允许我们模拟吉他拨弦的算法。

gh2 包中只有一个需要我们编辑的内容：

• GuitarString：类 GuitarString 利用 Deque<Double> 来实现 Karplus–Strong 算法，进而合成出吉他的音色。

GuitarString

完成 GuitarString 文件，需要利用 deque 包来模拟出拨弦的剩余。我们将使用 Karplus–Strong 算法，该算法很容易使用 Deque 实现。

实现 Karplus-Strong 有以下三个步骤：

1. 用随机噪声（-0.5 和 0.5 之间的 double 型）代替 Deque 中的每个元素。
2. 移除 Deque 的头部元素，并与下个元素求平均数（提示：使用 removeFirst() 和 get()），接着乘能量衰减系数 0.996（我们称为总数 newDouble）。然后将 newDouble 添加到 Deque 尾部。
3. 播放在步骤 2 中出队的 double 值（newDouble），返回步骤 2（并永远重复）。

解释一下 GuitarString 中各方法的作用：

• 构造器：用 0 填充缓冲区，相当于初始化一根静止的琴弦。
• pluck()：向缓冲区内填充 -0.5 和 0.5 之间的随机数，以模拟琴弦被波动时产生的白噪音。
• tic()：用算法计算出一个新值填充到缓冲区尾部，以模拟声音的衰减。
• sample()：返回缓冲区头部的值以模拟对声音的采样。
• StdAudio.play()：该方法虽然并不在 GuitarString 中，但它会根据传入的浮点数模拟出扬声器振膜的运动以模拟出声音的产生。

请完善 GuitarString.java，使其实现 Karplus-Strong 算法的第一步和第二步。注意：你需要在构造器中用零值初始化 Deque 缓冲区。第三步将由 GuitarString 类的调用方完成。

例如，提供的测试类 TestGuitarString 中包含一个示例测试 testPluckTheAString，该测试尝试在吉他弦上演奏 A 音。运行测试时，你应该能听到 A 音。如果未能听到，建议先运行 testTic 方法并逐步调试。可以考虑在 GuitarString.java 中添加打印语句或 toString 方法，以便观察每次 tic 操作后的状态变化。

注意：我们在此提到的是 Deque，但并未指定具体实现类型。这是因为我们只需要使用 addLast、removeFirst 和 get 这些操作，而所有实现 Deque 接口的类都包含这些方法。因此你可以自由选择 LinkedListDeque 或 ArrayDeque 作为具体实现。作为选做（但强烈推荐）的练习，建议思考这两种实现的优缺点，并与同伴讨论哪种选择更优，或者它们是否同样适用。

代码实现

// File: GuitarString.java
package gh2;

import deque.ArrayDeque;
import deque.Deque;

//Note: This file will not compile until you complete the Deque implementations
public class GuitarString {
    /** Constants. Do not change. In case you're curious, the keyword final
     * means the values cannot be changed at runtime. We'll discuss this and
     * other topics in lecture on Friday. */
    private static final int SR = 44100;      // Sampling Rate
    private static final double DECAY = .996; // energy decay factor

    /* Buffer for storing sound data. */
    private Deque<Double> buffer;

    /* Create a guitar string of the given frequency.  */
    public GuitarString(double frequency) {
        buffer = new ArrayDeque<>();
        for (int i = 0; i < (int) Math.round(SR / frequency); ++i) {
            buffer.addLast(0.0);
        }
    }


    /* Pluck the guitar string by replacing the buffer with white noise. */
    public void pluck() {
        for (int i = 0; i < buffer.size(); ++i) {
            buffer.removeFirst();
            buffer.addLast(Math.random() - 0.5);
        }
    }

    /* Advance the simulation one time step by performing one iteration of
     * the Karplus-Strong algorithm.
     */
    public void tic() {
        double num1 = buffer.removeFirst();
        double num2 = buffer.get(0);
        double newDouble = (num1 + num2) / 2 * DECAY;

        buffer.addLast(newDouble);
    }

    /* Return the double at the front of the buffer. */
    public double sample() {
        return buffer.get(0);
    }
}

GuitarHeroLite

下面的内容不参与 gradescope 评分。

搞清楚了 Karplus–Strong 算法发声的原理，也完善了 GuitarString，我们现在可以着手 GuitarHeroLite 类了。运行它，它能够根据你从键盘上输入的 a 和 c 分别播出 A 音和 C 音。尝试搞清楚它的原理，并自己实现一个 GuitarHero，使其支持从 110Hz 到 880Hz 半音阶的共 37 个音符。使用以下 37 个按键来对应键盘布局（从最低音到最高音排列）：

String keyboard = "q2we4r5ty7u8i9op-[=zxdcfvgbnjmk,.;/' ";

这种键盘布局模拟了钢琴键盘：

• "白键"对应 qwerty 和 zxcv 行
• "黑键"对应 12345 和 asdf 行

字符串 keyboard 中第 i 个字符对应的频率计算公式为：$440 \times 2^{(i - 24)/12}$

因此：

• 字符’q’对应 110Hz（低八度A音）
• 'i’对应 220Hz（标准A音）
• 'v’对应 440Hz（高八度A音）
• 空格键对应 880Hz

重要实现提示：

绝对不要声明 37 个独立的 GuitarString 变量或编写 37 个条件分支！正确的做法是：

• 创建包含 37 个 GuitarString 对象的数组
• 使用 keyboard.indexOf(key) 来定位按下的键
• 确保程序在接收到非映射按键时不会崩溃

代码实现

// File: GuitarHero.java
package gh2;

import edu.princeton.cs.algs4.StdAudio;
import edu.princeton.cs.algs4.StdDraw;

public class GuitarHero {
    private static final String KEYBOARD = "q2we4r5ty7u8i9op-[=zxdcfvgbnjmk,.;/' ";

    public static void main(String[] args) {
        GuitarString[] guitarStrings = new GuitarString[KEYBOARD.length()];
        for (int i = 0; i < KEYBOARD.length(); ++i) {
            guitarStrings[i] = new GuitarString(440.0 * Math.pow(2, (i - 24) / 12.0));
        }

        while (true) {
            if (StdDraw.hasNextKeyTyped()) {
                char key = StdDraw.nextKeyTyped();
                if (KEYBOARD.contains(String.valueOf(key))) {   // 如何确保程序在接收到非映射按键时不会崩溃？
                    int index = KEYBOARD.indexOf(key);          // 加个判断就行了
                    guitarStrings[index].pluck();
                } else {
                    continue;
                }
            }

            double sample = 0.0;
            for (int i = 0; i < KEYBOARD.length(); ++i) {
                sample += guitarStrings[i].sample();
            }

            StdAudio.play(sample);

            for (int i = 0; i < KEYBOARD.length(); ++i) {
                guitarStrings[i].tic();
            }
        }
    }
}

整点乐子：TTFAF

只要你对 GuitarString 的实现感到自信，尝试运行 TTFAF 吧！确保你的声音打开了！

提交与评分

完成上面的任务，你就可以提交到 Project 1: Data Structures 了。

整个项目有 640 分：

• deque/LinkedListDeque: 230 分
• deque/ArrayDeque: 230 分
• deque/MaxArrayDeque: 80 分
• gh2/GuitarString: 80 分

额外学分：Autograder

除了上面的内容，还有一个 32 学分的额外内容。这个项目中你将为 project1 的数据结构部分搭建一个基础的自动评分器。这个项目具有一定的挑战性并被认作是额外的学分，所以比起前面的工作具有最低的优先级。

项目文件中已经提供了：

• student/StudentArrayDeque.java：有 bug 的 ArrayDeque
• tester/ArrayDequeSolution.java：正确的 ArrayDeque
• tester/AssertEqualsStringDemo.java：如何使用 assertEquals 的演示
• tester/StudentArrayDequeLauncher.java：如何使用 StudentArrayDeque 的演示

随机测试

说一个有趣的秘密：project1 的自动评分器极大依赖于随机测试。举个例子，我们 gradescope 上的 JUnit 测试只是随机调用你的 LinkedListDeque 类与我们正确实现的 LinkedListDequeSolution 类中的方法，结果一旦不匹配测试就会失败，并输出造成这个失败的操作序列。在这个项目环节中，你需要模拟编写课程的自动评分程序，运用相同的思路。

我们将在此介绍如何生成清晰的 JUnit 错误信息——这实际上是一项非常重要的技能。如果你能编写出简洁易懂且实用的测试错误提示，你未来的上司一定会对你青睐有加。

开始本项目前，请先确保你的 IntelliJ 已正确导入工程。你可以尝试运行 StudentArrayDequeLauncher.java 文件进行验证。如果运行成功，你将看到 0 到 9 之间的数字被打印出来（顺序可能不固定）。若遇到任何问题，请参照 lab2 的指导说明进行处理。

任务一

接下来，在你的 tester 包中创建一个名为 TestArrayDequeEC.java 的 JUnit 测试文件。文件开头需要添加包声明：

package tester;

然后确保导入必要的依赖：

import static org.junit.Assert.*;
import org.junit.Test;
import student.StudentArrayDeque;

在该文件中，编写一个带有 @Test 注解的 JUnit 测试方法，方法名称可以任意。你的测试应该随机调用 StudentArrayDeque 和 ArrayDequeSolution 的方法，直到两者的输出不一致为止。你可以使用 StdRandom 库生成随机数（文档参考此处）。可以参考 StudentArrayDequeLauncher 的实现，如果直接复制了其中的代码，请使用 @source 标签注明来源。你在项目 1 中编写的测试代码可能也会派上用场。

注意：本次附加任务不测试 equals(Object o) 和 iterator() 方法，因此只需针对其他方法编写测试。

要求：

• 必须使用 Integer 作为双端队列（Deque）的泛型类型，即 StudentArrayDeque<Integer>。
• 仅使用 addFirst、addLast、removeFirst 和 removeLast 方法就能触发错误，当然你也可以尝试其他方法。
• 测试不应引发 NullPointerException。确保不会从空的双端队列中移除元素，因为 Integer x = ad.removeFirst() 会导致 NullPointerException。从双端队列中获取值时，请始终使用 Integer 而非 int，即不要写成 int x = ad.removeFirst()。

任务二

当你成功让测试稳定复现错误后，真正的挑战才刚开始。如果只是告诉学生“代码有错”，只会带来眼泪、沮丧、困惑和深夜的讨论区提问。因此，你需要改进自动评分系统，让它提供真正有用的反馈。

为此，我们将利用 assertEquals(message, expected, actual) 方法，它能向用户输出更有帮助的错误信息。可以参考 AssertEqualsStringDemo.java 来理解这个方法的使用方式。

请按以下要求修改你的 TestArrayDequeEC.java：

传递给 assertEquals 的 message 参数需要包含导致 StudentArrayDeque 输出错误结果的操作序列。这个字符串消息必须是一系列方法调用的完整记录，其中最后一个操作产生了错误的返回值。例如：

如果依次执行了 addFirst(5) → addFirst(3) → removeFirst() 这三个操作后得到错误结果，那么传递给 assertEquals 的字符串消息应该是（注意每个命令之间用换行分隔）：

addFirst(5)
addFirst(3)
removeFirst()

重要说明：

消息字符串不需要包含预期值和实际值，因为这些会作为单独的 expected/actual 参数传递给 assertEquals。或者说不要这样做：

addFirst(5)
addFirst(3)
removeFirst(), student was 3, correct was 7

或：

addFirst(5)
addFirst(3)
removeFirst(): 3
removeLast(): 4

代码实现

// File: TestArrayDequeEC.java
package tester;

import static org.junit.Assert.*;

import edu.princeton.cs.algs4.StdRandom;
import org.junit.Test;
import student.StudentArrayDeque;

public class TestArrayDequeEC {
    @Test
    public void randomizedTest() {
        ArrayDequeSolution<Integer> correct = new ArrayDequeSolution<>();
        StudentArrayDeque<Integer> broken = new StudentArrayDeque<>();
        StringBuilder msg = new StringBuilder();
        int N = 50000;
        for (int i = 0; i < N; ++i) {
            int opNum = StdRandom.uniform(0, 4);
            if (opNum == 0) {
                Integer randNum = StdRandom.uniform(0, 100);
                correct.addFirst(randNum);
                broken.addFirst(randNum);
                msg.append("addFirst(");
                msg.append(randNum);
                msg.append(")\n");
            } else if (opNum == 1) {
                Integer randNum = StdRandom.uniform(0, 100);
                correct.addLast(randNum);
                broken.addLast(randNum);
                msg.append("addLast(");
                msg.append(randNum);
                msg.append(")\n");
            } else if (opNum == 2) {
                if (correct.size() == 0) {
                    continue;
                }
                msg.append("removeFirst()\n");
                assertEquals(msg.toString(), correct.removeFirst(), broken.removeFirst());
            } else {
                if (correct.size() == 0) {
                    continue;
                }
                msg.append("removeLast()\n");
                assertEquals(msg.toString(), correct.removeLast(), broken.removeLast());
            }
        }
    }
}