Java Method equals circular list

Question

Here is the code for my Element class:

public class Element<T> {
    Element<T> next;
    Element<T> previous;
    T info;
}

... and for CircularList:

public class CircularList<T> {
    Element<T> first=null;

    public void add(Element<T> e){
        if (first==null){
            first=e;
            e.next=e;
            e.previous=e;
        } 
        else { //add to the end;
            first.previous.next=e;
            e.previous = first.previous;
            first.previous=e;
            e.next=first;
        }
    }

    public boolean equals(Object o){
        // TODO
    }
}

I don't know how to make an equals method for a circular list...

Only check if o instanceof CircularList<T> ?? (if ! return false else true?) mmm.. dunno how to do it :(

I know (from school) that I have to check 3 conditions:

if this == o return true
if o == null return false
if !o instanceof CircularList<T> return false

...

I don't know now if I have to check element from list1 to o , with a while... help me :)

Is an university test and I cannot modify or add method to element class.. I only have to implement the equals method from the CircularList<T> class!

Answer 1

I think the key point is that the lists are circular. Thus, I assume that the lists

A, B, C, D, E 
   B, C, D, E, A

should be considered as equal. Because they are. When you rotate a circle, it's still a circle.

So I guess the trick is to check each element of the other list, and see whether the the list is equal when starting at this element. In the example above, one would test

• Is the list B, C, D, E, A equal to A, B, C, D, E? No
• Is the list C, D, E, A, B equal to A, B, C, D, E? No
• Is the list D, E, A, B, C equal to A, B, C, D, E? No
• Is the list E, A, B, C, D equal to A, B, C, D, E? No
• Is the list A, B, C, D, E equal to A, B, C, D, E? Yes. Finally.

A quick implementation with some test cases, I hope that the most important cases are covered:

public class CircularListEquality {
    public static void main(String[] args) {

        CircularList<String> c0 = createList("A", "B", "C", "D", "E");
        CircularList<String> c1 = createList("A", "B", "C", "D");
        CircularList<String> c2 = createList(     "B", "C", "D", "E");
        CircularList<String> c3 = createList(     "B", "C", "D", "E", "A");

        CircularList<String> c4 = createList("A", "B", "C", "A", "B", "C");
        CircularList<String> c5 = createList("A", "B", "C");

        CircularList<String> c6 = createList("A");
        CircularList<String> c7 = createList("A", "A", "B", "C");

        test(c0, c1, false);
        test(c0, c2, false);
        test(c1, c2, false);
        test(c0, c3, true);
        test(c3, c0, true);
        test(c4, c5, false);
        test(c5, c4, false);
        test(c6, c7, false);
    }

    private static <T> void test(
        CircularList<T> c0, CircularList<T> c1, boolean expected) {
        boolean actual = c0.equals(c1);
        if (actual == expected) {
            System.out.print("PASSED");
        } else {
            System.out.print("FAILED");
        }
        System.out.println(" for " + toString(c0) + " and " + toString(c1));
    }

    private static <T> String toString(CircularList<T> c) {
        StringBuilder sb = new StringBuilder();
        Element<T> current = c.first;
        while (true) {
            sb.append(String.valueOf(current.info));
            current = current.next;
            if (current == c.first) {
                break;
            } else {
                sb.append(", ");
            }
        }
        return sb.toString();
    }

    private static CircularList<String> createList(String... elements) {
        CircularList<String> c = new CircularList<String>();
        for (String e : elements) {
            c.add(createElement(e));
        }
        return c;
    }

    private static <T> Element<T> createElement(T t) {
        Element<T> e = new Element<T>();
        e.info = t;
        return e;
    }
}

class Element<T> {
    Element<T> next;
    Element<T> previous;
    T info;
}

class CircularList<T> {
    Element<T> first = null;

    public void add(Element<T> e) {
        if (first == null) {
            first = e;
            e.next = e;
            e.previous = e;
        } else { // add to the end;
            first.previous.next = e;
            e.previous = first.previous;
            first.previous = e;
            e.next = first;
        }
    }

    public boolean equals(Object object) {
        if (this == object)
        {
            return true;
        }
        if (object == null)
        {
            return false;
        }
        if (!(object instanceof CircularList<?>))
        {
            return false;
        }
        CircularList<?> that = (CircularList<?>) object;

        Element<?> first0 = first;
        Element<?> current0 = first0;
        Element<?> first1 = that.first;
        Element<?> current1 = first1;
        while (true) {
            if (equalSequence(current0, current0, current1, current1)) {
                return true;
            }
            current1 = current1.next;
            if (current1 == first1) {
                return false;
            }
        }
    }

    private static boolean equalSequence(
        Element<?> first0, Element<?> current0,
        Element<?> first1, Element<?> current1) {
        while (true) {
            if (!equalElements(current0, current1)) {
                return false;
            }
            current0 = current0.next;
            current1 = current1.next;
            if (current0 == first0 && current1 == first1) {
                return true;
            }
            if (current0 == first0) {
                return false;
            }
            if (current1 == first1) {
                return false;
            }
        }
    }

    private static boolean equalElements(Element<?> t0, Element<?> t1) {
        if (t0 == null) {
            return t1 == null;
        }
        return equal(t0.info, t1.info);
    }

    private static <T> boolean equal(T t0, T t1) {
        if (t0 == null) {
            return t1 == null;
        }
        return t0.equals(t1);
    }
}

(EDIT: Added another test case)

Answer 2

The solution is obtained by tweaking your CircularList class a little: let's add it a length field.

public class CircularList<T> {
    int length = 0;  // <- this field contains the number of elements that the list has.
    Element<T> first = null;

    public void add(Element<T> e){
        if (first == null){
            first = e;
            e.next = e;
            e.previous = e;
        } 
        else {
            first.previous.next = e;
            e.previous = first.previous;
            first.previous = e;
            e.next = first;
        }

        this.length++;  // <- increment each time you call add().
    }
}

Now, implementing equals becomes trivial:

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;

    @SuppressWarnings("unchecked")
    final CircularList<T> other = (CircularList<T>) obj;

    if(other.length != this.length) {
        return false;
    }

    Element<T> current = this.first;
    Element<T> otherCurrent = other.first;
    int offset = 0;
    boolean found = false;
    do {
        found = checkSequence(current, otherCurrent);
        if(!found) {
            offset++;
            otherCurrent = otherCurrent.next;
        }
    } while(!found && offset < length) ;

    return found;
}

private boolean checkSequence(Element<T> current, Element<T> otherCurrent) {
    int i = 0;
    while(i < length && current.info == otherCurrent.info) {
        current = current.next;
        otherCurrent = otherCurrent.next;
        i++;
    }

    return i == length;
}

What I'm doing here in the checkSequence method is simply iterating over each elements (there are length of them in both lists) and checking that they're all the same by pair.

Then, if I left my loop because i reached length, it means that I've been through all the elements and that they were all identical. If i, at this point, is smaller than length, it means that the ith elements of the lists weren't the same.

Thus, I simply return i == length.

---

On top of this, I want to handle the cases where we're considering lists like:

• A, B, C
• C, A, B

... which must be equal.

Thus, I'm simply calling checkSequence, at most length times, comparing the second list to the first one with all possibles offsets.