Override deepEquals() method in Java without using Java.util.* method

Question

There is something wrong with the deepEquals method in my ArrayDeque file, but I can not figure it out. It should also make sense for LinkedListArrayDeque.

How to make the deepEquals work without using Java.util.* method?

---

The code below is about a double-ended array queue where the first item was added in the middle of the array. I deleted several methods for brief view.

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;
    }
}

---

I finally figured it out. Thank for all the help.

It indeed doesn't not need another deepEqual method.
The equals method itself is enough.

The code is as follows:
(1. There is no iterator method in my deque interface, so I just used the get(i) method. But I can use it for this. Thanks for the advice from @knittl.
2. I think (!a1.equals(a2)) is important in my code.. I finally figured it out !...).

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

You will want your equals method to compare each item in the list for equality. If two items are not equal, return false. Note that accessing an item in a linked list by index is O(n), meaning your equals method has quadratic runtime complexity. Use iterators to avoid that.

        // ...
        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;
    }

With iterators (which gives you linear runtime complexity):

        // ...
        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;
    }