Java自定义Deque的equals方法深度比较与性能优化实践

public boolean equals(Object o) { // 原始equals方法
    if (o == this) {
        return true;
    }
    if (o == null || this == 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) { // 引用相等或都为null
            continue;
        }
        if (a2 == null) { // a1不为null但a2为null
            return false;
        }
        if (a1.getClass() != a2.getClass()) { // 类型检查过于严格
            return false;
        }
        return deepEquals(a1, a2); // 问题所在：提前返回且deepEquals实现不当
    }
    return true;
}

private boolean deepEquals(Object a1, Object a2) { // 原始deepEquals方法
    boolean deq;
    if (a1 instanceof Deque) { 
        deq = a1.equals(a2); // 委托给Deque的equals
    } else {
        if (a1 == a2) { // 再次检查引用相等
            return true;
        }
        return false; // 如果不是Deque，且引用不相等，则直接返回false
    }
    return deq;
}

public boolean equals(Object o) {
    // 1. 自反性：检查是否是同一个对象的引用
    if (o == this) {
        return true;
    }
    // 2. 非空性：检查传入对象是否为null
    if (o == null) {
        return false;
    }
    // 3. 类型检查：检查传入对象是否是Deque的实例
    // 使用 instanceof 优于 getClass() == other.getClass()，因为它允许子类与父类对象进行比较
    if (!(o instanceof Deque)) {
        return false;
    }

    // 将Object转换为Deque类型，以便访问其特定方法
    Deque<?> otherDeque = (Deque<?>) o; // 使用<?>泛型以兼容不同类型的Deque

    // 4. 大小检查：如果大小不同，则不可能相等
    if (otherDeque.size() != this.size()) {
        return false;
    }

    // 5. 元素级比较：遍历所有元素进行深度比较
    // 注意：这里的实现是基于get(i)的，后续会讨论迭代器优化
    for (int i = 0; i < this.size(); i++) {
        Object elementOfThis = this.get(i);
        Object elementOfOther = otherDeque.get(i);

        // 处理元素为null的情况和引用相等的情况
        // 如果两个元素引用相同（包括都为null），则认为它们相等，继续下一个元素
        if (elementOfThis == elementOfOther) {
            continue;
        }
        // 如果elementOfThis不为null但elementOfOther为null，则不相等
        if (elementOfOther == null) {
            return false;
        }
        // 至此，elementOfThis和elementOfOther都保证不为null
        // 委托给元素的equals方法进行值比较
        if (!elementOfThis.equals(elementOfOther)) {
            return false; // 只要有一个元素不相等，整个Deque就不相等
        }
    }
    // 如果所有元素都相等，则两个Deque相等
    return true;
}

import java.util.Iterator; // 虽然原问题要求不使用java.util.*，但Iterator接口是集合框架的基础，通常被允许使用

public class ArrayDeque<T> implements Deque<T>, Iterable<T> {
    // ... 其他成员和方法 ...

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

    private class ArrayDequeIterator implements Iterator<T> {
        private int currentPosition = firposition; // 迭代器当前位置
        private int elementsTraversed = 0; // 已遍历元素计数

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

        @Override
        public T next() {
            if (!hasNext()) {
                throw new java.util.NoSuchElementException();
            }
            T item = ts[currentPosition];
            currentPosition = (currentPosition + 1) % ts.length;
            elementsTraversed++;
            return item;
        }
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) {
            return true;
        }
        if (o == null) {
            return false;
        }
        if (!(o instanceof Deque)) {
            return false;
        }

        Deque<?> otherDeque = (Deque<?>) o;
        if (otherDeque.size() != this.size()) {
            return false;
        }

        // 使用迭代器进行元素遍历和比较，提高效率
        Iterator<T> thisIterator = this.iterator(); // 获取当前Deque的迭代器
        // 假设 otherDeque 也是 Iterable 的，或者其 get(i) 性能可接受
        // 如果 otherDeque 也是自定义的，且我们知道它有高效的迭代器，可以这样：
        // Iterator<?> otherIterator = otherDeque.iterator();
        // 但根据原问题，oll.get(i) 是一个通用接口方法，我们先沿用它。
        // 如果 Deque 接口本身没有 iterator() 方法，但 ArrayDeque 实现了 Iterable，
        // 那么对于 otherDeque，我们可能只能依赖 get(i) 或假设它也是 Iterable。
        // 为了通用性，我们这里继续使用get(i)作为otherDeque的访问方式，
        // 但强调如果otherDeque也提供迭代器，应优先使用。

        int i = 0;
        while (thisIterator.hasNext()) { // 遍历当前Deque的元素
            Object elementOfThis = thisIterator.next();
            Object elementOfOther = otherDeque.get(i); // 访问另一个Deque的对应元素
            i++;

            if (elementOfThis == elementOfOther) {
                continue;
            }
            if (elementOfOther == null) {
                return false;
            }
            if (!elementOfThis.equals(elementOfOther)) {
                return false;
            }
        }
        return true;
    }
}

// 假设 Deque 接口定义了 iterator() 方法
// public interface Deque<T> extends Iterable<T> { ... }

@Override
public boolean equals(Object o) {
    if (o == this) {
        return true;
    }
    if (o == null) {
        return false;
    }
    if (!(o instanceof Deque)) {
        return false;
    }

    Deque<?> otherDeque = (Deque<?>) o;
    if (otherDeque.size() != this.size()) {
        return false;
    }

    // 同时使用两个迭代器进行元素遍历
    Iterator<T> thisIterator = this.iterator();
    Iterator<?> otherIterator = otherDeque.iterator(); // 获取另一个Deque的迭代器

    while (thisIterator.hasNext()) {
        Object elementOfThis = thisIterator.next();
        Object elementOfOther = otherIterator.next(); // 两个迭代器同步前进

        if (elementOfThis == elementOfOther) {
            continue;
        }
        if (elementOfOther == null) { // 此时 elementOfThis 必不为 null
            return false;
        }
        if (!elementOfThis.equals(elementOfOther)) {
            return false;
        }
    }
    // 因为之前已经检查了size相等，且迭代器同步前进，
    // 如果一个迭代器hasNext()为false，另一个也应如此。
    // 如果循环结束，则所有元素都相等。
    return true;
}