Java ArrayList Sort Exception: ArrayIndexOutOfBoundsException

Question

In my Java application, I have a class MyFileList that extends ArrayList and implements TableModel. The MyFile class

When I click to sort a column in the gui, I receive an exception and the list is left half sorted.

Exception in thread "AWT-EventQueue-2" java.lang.ArrayIndexOutOfBoundsException: -1
    at java.util.ArrayList.elementData(Unknown Source)
    at java.util.ArrayList.get(Unknown Source)
    at com.example.smdb.MyFileList.getValueAt(MyFileList.java:321)
    at com.example.util.MyObjectListComparator.compare(MyObjectListComparator.java:97)
    at java.util.TimSort.mergeHi(Unknown Source)
    at java.util.TimSort.mergeAt(Unknown Source)
    at java.util.TimSort.mergeForceCollapse(Unknown Source)
    at java.util.TimSort.sort(Unknown Source)
    at java.util.Arrays.sort(Unknown Source)
    at java.util.ArrayList.sort(Unknown Source)
    at java.util.Collections.sort(Unknown Source)
    at com.example.gui.MyTableSorter.sort(MyTableSorter.java:73)
    at com.example.gui.MyTableSorter.sortByColumn(MyTableSorter.java:93)
    at com.example.gui.PreservableColSizeJTable$PersistentJTableHeader.mouseClicked(PreservableColSizeJTable.java:935)

MyTableSorter sort method:

public void sort(int column) {
        if(model instanceof List){
           Collections.sort ((List)model, new MyObjectListComparator((List)model, column, ascending));
        }
    }

MyObjectListComparator compare method:

public int compare(Object obj, Object obj1) {
    int result = 0;
    int row = this.filelist.indexOf(obj);
    int row1 = this.filelist.indexOf(obj1);
    Object value = ((MyFileList) this.filelist).getValueAt(row, column);
    value = ((MyFile.FileAttr) value).getAttrValue();
    Object value1 = ((MyFileList) this.filelist).getValueAt(row1, column);
    value1 = ((MyFile.FileAttr) value1).getAttrValue();

    result = compareAttr(value, value1);

    return result;
}

MyFile equals method:

public boolean equals(Object obj) {
    if (obj instanceof MyFile) {
        if (this.getAttribute(FILE_ID) != null) {
            return this.getAttribute(FILE_ID).equals(((MyFile) obj).getAttribute(FILE_ID));
        } 
    }
    return false;
}

Upon debugging, I see that this.filelist.indexOf(obj) in the compare method is returning -1. If I catch this exception and let it keep sorting, I end up with some items duplicated in my list and some items missing.

I found some references to a bug in TimSort that sound very similar, so I tried the useLegacySortMerge option. That gives me the same behavior with a slightly different stack trace, so unfortunately that doesn't look like the issue.

Exception in thread "AWT-EventQueue-2" java.lang.ArrayIndexOutOfBoundsException: -1
    at java.util.ArrayList.elementData(Unknown Source)
    at java.util.ArrayList.get(Unknown Source)
    at com.example.smdb.MyFileList.getValueAt(MyFileList.java:321)
    at com.example.util.MyObjectListComparator.compare(MyObjectListComparator.java:97)
    at java.util.Arrays.mergeSort(Unknown Source)
    at java.util.Arrays.mergeSort(Unknown Source)
    at java.util.Arrays.mergeSort(Unknown Source)
    at java.util.Arrays.legacyMergeSort(Unknown Source)
    at java.util.Arrays.sort(Unknown Source)
    at java.util.ArrayList.sort(Unknown Source)
    at java.util.Collections.sort(Unknown Source)
    at com.example.gui.MyTableSorter.sort(MyTableSorter.java:73)
    at com.example.gui.MyTableSorter.sortByColumn(MyTableSorter.java:93)
    at com.example.gui.PreservableColSizeJTable$PersistentJTableHeader.mouseClicked(PreservableColSizeJTable.java:935)

This has been driving me crazy for a few days. Any insights?

I strongly suspect that your code is breaking an invariant. It is **highly** unlikely that there are bugs in `Collections.sort`. — Boris the Spider, Jan 13 '16 at 23:33
@Makoto I don't think this is duplicate - this is an error in `Collections.sort`, so it's an error in to OP's `Comparator` not in array logic. — Boris the Spider, Jan 13 '16 at 23:37
@BoristheSpider: That's fair. I'm not going to complain about that. — Makoto, Jan 13 '16 at 23:38
Well there was a bug in `Collections.sort` (see link), but as I show above it isn't the cause of my problem. I fully agree it is probably something in the code here, which is why I posted the relevant bits. Any ideas? — andreamc, Jan 13 '16 at 23:38
@andreamc 1) all the rawtypes worry my. 2) why on earth does the `Comparator` need a reference to the array it's comparing? One of those is likely the source of your woes. — Boris the Spider, Jan 13 '16 at 23:42
P.S. unless you are using OpenJDK then those bugs aren't likely relevant. — Boris the Spider, Jan 13 '16 at 23:43
@boris-the-spider This code is very old and not pretty, which is why detangling it has been a challenge. I think your skepticism on the Comparator reference to the list might be on the right track. I'll dig in there. — andreamc, Jan 13 '16 at 23:48
@andreamc my gut instinct is that `model` becomes `filelist` and that the comparing happens on the elements _as they are being sorted_. This obviously violates an invariant as comparing the same two items will produce different results. — Boris the Spider, Jan 13 '16 at 23:50
Incidentally `indexOf` returns `-1` if it cannot find the object - that is the root of your troubles. — Boris the Spider, Jan 13 '16 at 23:53
@boris-the-spider Getting the row index from the list was the issue, I reworked the code to not use that and it seems to be working now. If you want to add your comment as an answer I'll accept it. Thanks for taking a look! — andreamc, Jan 14 '16 at 00:30

score 0 · Answer 1 · answered Jan 13 '16 at 23:55

Just an idea: You can handle the cases where row and row1 are not found in the filelist assuming that both absence are equivalent and absence is "less" than any presence. Invert the 1 and -1 if this does not work.

public int compare(Object obj, Object obj1) {
    int result = 0;
    int row = this.filelist.indexOf(obj);
    int row1 = this.filelist.indexOf(obj1);

    if(row == -1){
        if(row1 == -1){
            return 0;
        }
        return -1;
    }else if(row1 == -1){
        return 1;
    }

    Object value = ((MyFileList) this.filelist).getValueAt(row, column);
    value = ((MyFile.FileAttr) value).getAttrValue();
    Object value1 = ((MyFileList) this.filelist).getValueAt(row1, column);
    value1 = ((MyFile.FileAttr) value1).getAttrValue();

    result = compareAttr(value, value1);

    return result;
}

Java ArrayList Sort Exception: ArrayIndexOutOfBoundsException

1 Answers1