indexOf with nested ArrayList

Hi there,

I’ve got some menu structure where I’m nesting ArrayLists like this class Menu extends ArrayList<Menu>. It gives me some really interesting results when I’m using indexOf. Somehow it looks like it’s doing a recursive indexOf (traversing down the tree). Is this normal? What do you think?
When I override the indexOf function with my own code it works as I would expect.

Menu root = new Menu();

void setup() {  
  Menu a = root.addItem("a");
  Menu b = root.addItem("b");
  Menu c = root.addItem("c");
  Menu d = root.addItem("d");
  
  Menu b1 = b.addItem("b1");
  Menu b2 = b.addItem("b2");
  Menu b3 = b.addItem("b3");
  
  Menu b2x = b2.addItem("b2x");
  Menu b2y = b2.addItem("b2y");
  Menu b2z = b2.addItem("b2z");
  
  println(root.indexOf(b2z)); //returns 0 instead of -1
  println(b.indexOf(b2z));    //returns 0 instead of -1
  println(b2.indexOf(b2z));   //returns 0 instead of 2
}

class Menu extends ArrayList<Menu> {
  String title;

  Menu addItem(String title) {
    Menu m = new Menu();
    m.title = title;
    add(m);
    return m;
  }

  //when overriding indexOf it works like I would expect. 
  //int indexOf(Menu findMe) {
  //  for (int i=0; i<size(); i++) {
  //    if (get(i)==findMe) return i;
  //  }
  //  return -1;
  //}
}
1 Like

Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/util/AbstractList.html#equals(java.lang.Object)

Thanks. I read the documentation about the equals and indexOf function. But I still don’t understand why indexOf would return 0 instead of -1…

B/c an Object’s equals() method can have its own arbitrary rules to “determine” that another Object is “equal to” it:
Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Object.html#equals(java.lang.Object)

While your @Override indexOf() relies instead on the equality == operator:
Processing.org/reference/equality.html

A very peculiar behavior of Java’s == operator is that it always compare values, regardless whether they’re numbers or references (a.K.a. pointers or memory addresses).

So at your statement if (get(i) == findMe) return i;, it matches only when 1 of the stored Menu objects has the same memory address value stored in the findMe parameter.

That is, when the loop finds out they’re exactly the very same object.

That only matches at println(b2.indexOf(b2z));, b/c b2z
is indeed the 3rd (index 2) Menu object created by Menu b2: Menu b2z = b2.addItem("b2z");

Now back to the original indexOf(), why does it seem like that it always finds a match at index 0?

Well, not always! Try out replacing b2z in println(root.indexOf(b2z)); w/ b2: println(root.indexOf(b2));

You’ll see it’s finally gonna log -1 this time!

As stated before, the original indexOf() relies on the implementation of equals() from AbstractList:
Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/util/AbstractList.html#equals(java.lang.Object)

Actually you’d get the same behavior as your @Override indexOf() if you simply @Override equals(), comparing the passed Object to this using the == operator:

@Override boolean equals(final Object o) {
  return o == this;
}

According to original AbstractList::equals():

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal .

W/ the rules above in mind, let’s get into why println(root.indexOf(b2z)); logs 0 rather than -1.

  • Variable root is a Menu list w/ size() = 4, w/ elements a, b, c & d.
  • Variable b2z is a Menu list w/ size() = 0. It’s empty, so no elements.
  • The 1st root element at index 0 is a.
  • Like b2z, a is also a Menu list w/ size() = 0.
  • Given both are empty lists, comparing each of their elements at their corresponding index position using their own equals() is completely skipped.
  • Thus the Menu a list is considered “equal to” Menu b2z list at index 0 according to AbstractList::equals()'s condition rules.
4 Likes

Wow, thank you so much @GoToLoop for explaining this in so much detail. I now fully understand it.

1 Like