Problems with Collections.sort in Java 8

Question

@Entity @NamedQueries({ @NamedQuery( name = "FolderNode.findByName", query = "SELECT f FROM FolderNode f WHERE f.name = :name AND f.parentNode = :parentNode"), @NamedQuery( name = "FolderNode.findRootNodeByName", query = "SELECT f FROM FolderNode f WHERE f.name = :name AND f.parentNode is null") }) public class FolderNode extends InstructorTreeNode { public FolderNode() { super(); } public FolderNode(String name) { this(); setName(name); } public FolderNode(int sortOrder, String name) { this(name); this.sortOrder = sortOrder; } public FolderNode(int sortOrder, String name, EmployeeState status) { this(sortOrder, name); this.status = status; } public static FolderNode addWaitingListNode(String name) { EntityManager em = getDao().getEntityManager(); em.getTransaction().begin(); FolderNode waitingListNode = getWaitingListFolder(); FolderNode folderNode = new FolderNode(0, name); waitingListNode.addChild(folderNode); em.merge(waitingListNode); em.getTransaction().commit(); em.close(); return folderNode; } public static void addWaitingListStudent(String waitingList, Student s) { EntityManager em = FolderNode.getDao().getEntityManager(); em.getTransaction().begin(); FolderNode waitingListsNode = getWaitingListFolder(); FolderNode waitingListNode = getDao().findFolderNodeByName(waitingListsNode, waitingList); waitingListNode.addChild(new EmployeeLeaf(s.getInmate())); em.merge(waitingListNode); em.getTransaction().commit(); em.close(); } public static FolderNode getAMClassFolder() { return getDao().findFolderNodeByName(getStudentsFolder(), "AM Class"); } public static FolderNode getAttendanceFolder() { return getDao().findFolderNodeByName(getRootFolder(), "Employee Attendance"); } public static FolderNode getFormerParaprosFolder() { return getDao().findFolderNodeByName(getParaprosFolder(), "Former"); } public static FolderNode getFormerStudentsFolder() { return getDao().findFolderNodeByName(getStudentsFolder(), "Former"); } public static FolderNode getPMClassFolder() { return getDao().findFolderNodeByName(getStudentsFolder(), "PM Class"); } public static FolderNode getParaprosFolder() { return getDao().findFolderNodeByName(getRootFolder(), "Parapros"); } public static FolderNode getPendingStudentsFolder() { return getDao().findFolderNodeByName(getRootFolder(), "Pending Students"); } public static FolderNode getRootFolder() { return getDao().findFolderNodeByName(null, EducationPreferences.getInstructor().getInstructorName()); } public static FolderNode getStudentsFolder() { return getDao().findFolderNodeByName(getRootFolder(), "Students"); } public static FolderNode getWaitingListFolder(String name) { FolderNode waitingListsNode = getWaitingListFolder(); return getDao().findFolderNodeByName(waitingListsNode, name); } public static FolderNode getWaitingListFolder() { return getDao().findFolderNodeByName(getRootFolder(), "Waiting List"); } public static void setClassFolder(Student aStudent, EntityManager entityManager) { EntityManager em = entityManager; if (entityManager == null) { em = FolderNode.getDao().getEntityManager(); em.getTransaction().begin(); } EmployeeLeaf leaf = EmployeeLeaf.findActiveStudentLeaf(aStudent); FolderNode node = aStudent.getShift() == Shift.AM ? getAMClassFolder() : getPMClassFolder(); leaf.setParentNode(node); em.merge(leaf); GlobalEntityMethods.updateHistory(leaf); if (entityManager == null) { em.getTransaction().commit(); em.close(); } } public static void transferWaitingListStudent(String currentFolder, String toFolder, Student student) { EntityManager em = FolderNode.getDao().getEntityManager(); em.getTransaction().begin(); FolderNode waitingListsNode = getWaitingListFolder(); FolderNode currentWaitingListNode = getDao().findFolderNodeByName(waitingListsNode, currentFolder); EmployeeLeaf employeeLeaf = EmployeeLeaf.getDao().findWaitingListLeafByInmate(student.getInmate()); currentWaitingListNode.removeChild(employeeLeaf); FolderNode toWaitingListNode = getDao().findFolderNodeByName(waitingListsNode, toFolder); toWaitingListNode.addChild(employeeLeaf); em.merge(currentWaitingListNode); em.merge(toWaitingListNode); em.getTransaction().commit(); em.close(); } public void addChild(InstructorTreeNode node) { childNodes.add(node); node.setParentNode(this); } public List<InstructorTreeNode> getChildNodes() { Collections.sort(childNodes); return childNodes; } @Override public Set<Inmate> getInmates() { Set<Inmate> inmateSet = new HashSet<> (50); for (InstructorTreeNode node: getChildNodes()) { inmateSet.addAll(node.getInmates()); } return inmateSet; } public int getSortOrder() { return sortOrder; } public EmployeeState getStatus() { return status; } @Override public List<InstructorTreeNode> getTree() { List <InstructorTreeNode> result = new ArrayList<> (25); for (InstructorTreeNode childNode: getChildNodes()) { if (childNode instanceof FolderNode) { result.add(childNode); } result.addAll(childNode.getTree()); } return result; } @Override public JPanel getView(EmployeeViewController controller) { if ("Employee Attendance".equals(getName())) { return new AttendanceView(); } else if ("Waiting List".equals(getName())) { return new AllWaitingListsPanel(controller); } else if (getParentNode().getName().equals("Waiting List")) { return new WaitingListPanel(controller); } else if ("Pending Students".equals(getName())) { return new PendingStudentsPanel(controller); } else if ("Students".equals(getName())) { return new AllStudentsPanel(controller); } else if ("AM Class".equals(getName())) { return new AllStudentsPanel(controller, Shift.AM); } else if ("PM Class".equals(getName())) { return new AllStudentsPanel(controller, Shift.PM); } else if (getParentNode().getName().equals("Students") && "Former".equals(getName())) { return new FormerStudentsPanel(controller); } else if ("Parapros".equals(getName())) { return new AllParaprosPanel(controller); } else if (getParentNode().getName().equals("Parapros") && "Former".equals(getName())) { return new FormerParaprosPanel(controller); } throw new UnsupportedOperationException("unknown folder"); } public void removeChild(InstructorTreeNode node) { childNodes.remove(node); node.setParentNode(null); } public void removeEmployeeLeaf(Inmate inmate) { for (InstructorTreeNode node: childNodes) { if (node instanceof EmployeeLeaf) { EmployeeLeaf employeeLeaf = (EmployeeLeaf) node; if (employeeLeaf.getInmate().equals(inmate)) { childNodes.remove(employeeLeaf); break; } } } } public void setChildNodes(List<InstructorTreeNode> childNodes) { this.childNodes = childNodes; } public void setSortOrder(int sortOrder) { this.sortOrder = sortOrder; } public void setStatus(EmployeeState status) { this.status = status; } @OneToMany(mappedBy = "parentNode", cascade = CascadeType.ALL, orphanRemoval = true) private List<InstructorTreeNode> childNodes; private int sortOrder; @Enumerated(EnumType.STRING) private EmployeeState status; } @Entity @Table(catalog = "education", name = "instructortreenode", uniqueConstraints = @UniqueConstraint(columnNames = { "PARENTNODE_ID", "NAME" })) @Inheritance(strategy = InheritanceType.SINGLE_TABLE) public abstract class InstructorTreeNode implements Comparable<InstructorTreeNode> { public InstructorTreeNode() { super(); } public static InstructorTreeNodeDAO getDao() { return dao; } @Override public int compareTo(InstructorTreeNode o) { if (o instanceof FolderNode && this instanceof FolderNode) { FolderNode thisFolder = (FolderNode) this; FolderNode otherFolder = (FolderNode) o; if (thisFolder.getSortOrder() != otherFolder.getSortOrder()) { return thisFolder.getSortOrder() - otherFolder.getSortOrder(); } else { return thisFolder.getName().compareToIgnoreCase(otherFolder.getName()); } } else if (o instanceof EmployeeLeaf && this instanceof EmployeeLeaf) { return getName().compareToIgnoreCase(((InstructorTreeNode) o).getName()); } return (o instanceof FolderNode) ? -1 : +1; } public int getCount() { return getTree().size(); } public abstract Set<Inmate> getInmates(); public String getName() { return name; } public FolderNode getParentNode() { return parentNode; } public abstract List<InstructorTreeNode> getTree(); public abstract JPanel getView(EmployeeViewController theController); public void setName(String name) { this.name = name; } public void setParentNode(FolderNode parentNode) { this.parentNode = parentNode; } @Override public String toString() { return name; } private static final InstructorTreeNodeDAO dao = new InstructorTreeNodeDAO(); private String name; @ManyToOne private FolderNode parentNode; } 

Here is my problem: The Collections.sort line works fine in Java 8u5 before, but in Java 8u20 they seem to have changed the code for Collections.sort and it no longer uses anything other than the natural order, even if you specify Comparator.

Should I use a different method to sort my list, or is there an error in Collections.sort.

Any help would be greatly appreciated as it drives me crazy.

I forgot to say that this code does not use the specified comparator, but according to the documentation, it is supposed to use CompareTo if your class implements Comparable, and this is what I use. I also tried to specify a comparator, but it did not work either.

Answer 1

Since Collections.sort now delegated to List.sort , the actual implementation of List has an impact. Implementations such as ArrayList and Vector take advantage of the more efficient use of List.sort than the default implementation, as they pass their internal array directly to Arrays.sort , omitting the steps of copying the default implementation.

This works without problems if programmers do not use an anti-subclass pattern to implement (instead of using delegation) method overrides to implement inconsistent behavior. Lazily populated lists like these from EclipseLink / JPA are known to have problems with this , as they try to intercept each reading method to populate the list before continuing, but skip the new sort method. If the list is not populated yet when sort called, sort will see the status of the empty list.

There is no indication in your code where this list comes from or what actual implementation class it has, but since I see a lot of familiar annotations, I think you use this structure ...

Answer 2

If you use the Collections#sort(List<T> list) method, it deviates to the List#sort(Comparator comparator) method with the comparator specified as null . The source code from java.util.Collections as follows:

 public static <T extends Comparable<? super T>> void sort(List<T> list) { list.sort(null); } 

If you want to specify your own comparator, you need to use the Collections#sort(List<T> list, Comparator<T> comparator) method, which passes your comparator to the list sorting method. The source code from java.util.Collections as follows:

 public static <T> void sort(List<T> list, Comparator<? super T> c) { list.sort(c); } 

So far so good. Now, as you correctly pointed out, if you did not specify a comparator, the natural order of the class is used, that is, the compareTo method that you defined.

However, the documentation for the Comparable class states the following:

It is strongly recommended (though not necessary) that natural orders correspond to equalities. This is because sorted sets (and sorted cards) without explicit comparators behave “weirdly” when they are used with elements (or keys) whose natural ordering is incompatible with equal ones. In particular, such a sorted set (or sorted map) violates the general contract for the set (or map), which is defined in terms of the equals method.

Since the InstructorTreeNode class does not override Object#equals , your compareTo method can return 0, even if == returns false. I believe this leads to documentation being "weird."

Answer 3

You may not like this answer because it does not give you a quick fix for your situation, but it will help you in the long run.

This is a bug with which you may find yourself with a little debugging. I don’t know which IDE you are using, but with Eclipse you can even enter code that is in the JDK!

So, what would I do is set a breakpoint on the line where you call sort () on childNodes. Then I would enter the JDK code and just go through it myself. It will be very clear what is happening and why it is not calling your comparison function.

Answer 4

You can try to create a custom comparator. Here is an example of how it should look. This is for comparing BigDecimals.

 class YourComparator implements Comparator<InstructorTreeNode> { @Override public int compare(final InstructorTreeNode 01, final InstructorTreeNode o2) { return o2.getYourCompVal().compareTo(o1.getYourCompVal()); } 

}

  public List<InstructorTreeNode> getChildNodes() { Collections.sort(childNodes, new YourComparator()); return childNodes;}