在Java中重写deepEquals()方法，而不使用Java.util.*方法

Question

我的ArrayDeque文件中的deepEquals方法有问题，但我无法弄清楚。这对LinkedListArrayDeque也有意义。

如何使deepEquals工作不使用Java.util.* method?

---

下面的代码是关于一个双端数组队列的，其中第一项被添加到数组的中间。我删除了简要视图的几个方法。

package deque;
import java.util.Iterator;
public class ArrayDeque<T> implements Deque<T>, Iterable<T> {
private T[] ts;
private int size;
private int stposition;
private int firposition;
private int lastposition;
public ArrayDeque() {
ts = (T[]) new Object[8];
size = 0;
stposition = Math.round(ts.length / 2);
firposition = stposition;
lastposition = stposition;
}
public T get(int i) {
if (size < i | size == 0) {
return null;
}
int pos = (firposition + i) % ts.length;
return ts[pos];
}
public int size() {
return size;
}
@Override
public Iterator<T> iterator() {
return new ArrayDequeIterator();
}
private class ArrayDequeIterator implements Iterator<T> {
private int pos0 = firposition;
public boolean hasNext() {
if (size == 0) {
return false;
}
if (pos0 == lastposition) {
return true;
}
if (size > 1) {
if (firposition < lastposition) {
if (pos0 < lastposition) {
return true;
}
} else {
if (pos0 + 1 < ts.length) {
return true;
}
}
return false;
}
return false;
}
public T next() {
T x = ts[pos0];
pos0 = (pos0 + 1) % ts.length;
return x;
}
}
@Override
public boolean equals(Object o) { // the equal method passed the tests but deepequal fail
if (o == this) {
return true;
}
if (o == null || this == null) {
return false;
}
if (!(o instanceof Deque)) {
return false;
}
Deque oll = (Deque) o;
if (oll.size() != this.size()) {
return false;
}
for (int i = 0; i < this.size(); i++) {
Object a2 = oll.get(i);
Object a1 = this.get(i);
if (a1 == a2) {
continue;
}
if (a2 == null) {
return false;
}
if (a1.getClass() != a2.getClass()) {
return false;
}
return deepEquals(a1, a2);
}
return true;
}
private boolean deepEquals(Object a1, Object a2) {
boolean deq;
if (a1 instanceof Deque) { 
// maybe it's wrong here, I am not sure how to write this
deq = a1.equals(a2);
} else {
if (a1 == a2) {
return true;
}
return false;
}
return deq;
}
}

---

我终于想通了。谢谢你的帮助。

它确实不需要另一个deepEqual方法。
equals方法本身就足够了。

代码如下:
(1;在我的deque接口中没有iterator方法，所以我只使用了get(i)方法。但我可以用它为this。感谢@knittl的建议。
2。我认为(!a1.equals(a2))在我的代码中很重要。我终于弄明白了…)。

public boolean equals(Object o) {
if (o == this) {
return true;
}
if (o == null) {
return false;
}
if (!(o instanceof Deque)) {
return false;
}
Deque oll = (Deque) o;
if (oll.size() != this.size()) {
return false;
}
int i = 0;
for (final Object a1 : this) {
Object a2 = oll.get(i);
i += 1;
if (a1 == a2) {
continue;
}
if (a2 == null) {
return false;
}
if (a1.getClass() != a2.getClass()) {
return false;
}
if (!a1.equals(a2)) {
return false;
}
}
return true;
}

Answer 1

您将需要equals方法比较列表中的每个项是否相等。如果两项不相等，则返回false。注意，通过索引访问链表中的项是O(n)，这意味着equals方法的运行时复杂度是二次的。使用迭代器可以避免这种情况。

// ...
for (int i = 0; i < this.size(); i++) {
Object a2 = oll.get(i);
Object a1 = this.get(i);
if (!Objects.equals(a1, a2)) {
return false;
}
}
return true;
}

使用迭代器(这会给你线性运行时复杂度):

// ...
Iterator<Object> otherIterator = oll.iterator();
for (final Object a1 : this) {
// guaranteed to work, because both lists have the same size:
final Object a2 = otherIterator.next();
if (!Objects.equals(a1, a2)) {
return false;
}
}
return true;
}