Java method is equal to circular list
Here is the code for my class Element
:
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 the equals method for a circular list ...
Check only o instanceof CircularList<T>
? (if! return false else true?) mmm .. dunno how to do it: (
I know (from school) that I need to check 3 conditions:
if this == o return true
if o == null return false
if !o instanceof CircularList<T> return false
...
Now I don't know if I need to check an element from list1
to o
, with while
... help me :)
Is it a university test and I cannot change or add a method to the element class. I need to implement a method equals
from a class CircularList<T>
!
source to share
The solution is obtained by tweaking your class a little CircularList
: add it to the field length
.
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 the implementation 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 am doing here in the method checkSequence
is just iterating over each item (both lists have length
) and checking that they are all the same in pairs.
Then, if I left my loop because I i
reached length
, it means that I went through all the elements and they were all identical. If i
, at this point, less than length
, it means that the i
th elements of the lists were not the same.
Thus, I just return i == length
.
Also, I want to handle cases where we consider lists like:
- A, B, C
- C, A, B
... which should be equal
.
So I just call checkSequence
, at most length
times, comparing the second list to the first with all possible offsets.
source to share
I think the key point is that the lists are circular . Thus, I am assuming that the lists
A, B, C, D, E B, C, D, E, A
should be considered equal. Because they. When you turn the circle, it is still a circle.
So, I think the trick is to check each element of another list and see if the list is equal when run on that element. In the example above, one could check
- Is the list
B, C, D, E, A
equalA, B, C, D, E
? Not - Is the list
C, D, E, A, B
equalA, B, C, D, E
? Not - Is the list
D, E, A, B, C
equalA, B, C, D, E
? Not - Is the list
E, A, B, C, D
equalA, B, C, D, E
? Not - Is the list
A, B, C, D, E
equalA, B, C, D, E
? Yes. At last.
A quick implementation with some test cases, I hope 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)
source to share
The operator !
inverts true to false and vice versa.
So your code is that one thing would mean the opposite of the actual
if !o instanceof CircularList<T>
will return false if the object o
is an instance CircularList<T>
. Otherwise it will fallback to true if o
not an instance CirculatList<T>
. You are just trying to invert the actual result o instanceof CircularList<T>
.
source to share
How about this equal implementation? We can avoid customizing your class.
public boolean equals(CircularList<T> other)
{
**Standard checks will go here (ref equals, class type etc)**
boolean result = false;
result = first.equals(other.first);
Element<T> next = first.next;
Element<T> nextOfOther = other.first.next;
while (null != next && null != nextOfOther)
{
// break cyclic loop
if (next.equals(first))
break;
result = next.equals(nextOfOther);
if (!result)
// We know they aren't equal so break
break;
next = next.next;
nextOfOther = nextOfOther.next;
}
return result;
}
source to share
Instruction: this == o;
Returns true only when they have the same address (when it is the same object), I think you need something that will return true if both lists contain the same elements, try this:
public boolean equals(CircularList<T> other){
Element<T> e1 = first;
Element<T> e2 = other.first;
while(e1.next != first && e2.next != other.first){
if(e1.info == e2.info){
e1 = e1.next;
e2 = e2.next;
}
else return false;
}
if (e1.next == first && e2.next == other.first)
return true;
else return false;
}
I think it will work !!
source to share
How about this, here I will first find and check the length, then check the elements.
public boolean equals(CircularList<T> other)
{
boolean result = false;
result = first.equals(other.first);
if (!result)
return result;
Element<T> next = first.next;
Element<T> nextOfOther = other.first.next;
int firstCount = 1;
while (null != next)
{
if (next.equals(first))
break;
firstCount++;
next = next.next;
}
int secondCount = 1;
while (null != nextOfOther)
{
if (nextOfOther.equals(other.first))
break;
secondCount++;
nextOfOther = nextOfOther.next;
}
if (firstCount != secondCount)
{
result = false;
}
next = first.next;
nextOfOther = other.first.next;
while (firstCount > 1)
{
result = next.equals(nextOfOther);
if (!result)
// We know they aren't equal so break
break;
next = next.next;
nextOfOther = nextOfOther.next;
firstCount--;
}
return result;
}
source to share