• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 193
  • Last Modified:

Java - sorting a list of objects where the properties of the objects can change during the sort

Hi all,

I am getting an exception in Java 8

java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.util.TimSort.mergeLo(TimSort.java:777)
	at java.util.TimSort.mergeAt(TimSort.java:514)
	at java.util.TimSort.mergeCollapse(TimSort.java:441)
	at java.util.TimSort.sort(TimSort.java:245)
	at java.util.Arrays.sort(Arrays.java:1512)
	at java.util.ArrayList.sort(ArrayList.java:1454)
	at java.util.Collections.sort(Collections.java:175)

Open in new window


when running Sort on a list of Objects of "AreaInfo":

List<AreaInfo> mArrayList = new ArrayList<>(getAreaInfoList());
Collections.sort(mArrayList, getComparator());

Open in new window


where AreaInfo is the class:

class AreaInfo {
     public int nameID;
     public boolean hasViolation;

     public void setViolation(boolean n) {
             this.hasViolation = n;
     }
}

Open in new window


and the comparator is

    protected Comparator<AreaInfo> getComparator() {
    	return new Comparator<AreaInfo>() {
		    public int compare(AreaInfo c1, AreaInfo c2) {
				if (c1.hasViolation() && !c2.hasViolation()) {
	    			return 1;
				} else if (!c1.hasViolation() && c2.hasViolation()) {
					return -1;
				} else if (c1.hasViolation() && c2.hasViolation()) {
		    		if (c1.getName() > c2.getName()) {
		    			return 1;
		    		} else if (c1.getName() < c2.getName()) {
		    			return -1;
		    		} else {
		    			return 0;
		    		}
		    	}
		    }
		};
    }

Open in new window


due to the "hasViolation" property of "AreaInfo" changing (from false to true and vice versa) during the sort.

To avoid the exception, I've tried something like

List<AreaInfo> mArrayList = Collections.unmodifiableList(new ArrayList<>(getAreaInfoList()));

Open in new window


but this does not work, as even though the list itself isn't modifiable, the list objects still are.

Is there a way I can "freeze" the state of the list objects for the duration of the sort?

FYI, the sort is run from a worker thread (SwingWorker.doInBackground() )
0
jksung
Asked:
jksung
1 Solution
 
gurpsbassiCommented:
what do you mean by
due to the "hasViolation" property of "AreaInfo" changing

why is it changing? if it is, why are you changing it inflight when you're sorting?
0
 
micropc1Commented:
You don't have a hasViolation method in your AreaInfo class, but you are referencing hasViolation() in your comparator. Maybe create a getter method for hasViolation or access the boolean directly (although that's poor encapsulation)
0
 
jksungAuthor Commented:
The AreaInfo objects are changing because we want to show a realtime map using the AreaInfo object's info, which must always have the most up to date information.  We want to sort, because we want to also show the information in a table above the map, which we want sorted based on certain criterias.
0
Cloud Class® Course: MCSA MCSE Windows Server 2012

This course teaches how to install and configure Windows Server 2012 R2.  It is the first step on your path to becoming a Microsoft Certified Solutions Expert (MCSE).

 
dpearsonCommented:
I would consider using a TreeSet (https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html) to maintain the sorted list.

A TreeSet updates the sort order as objects are added/removed so the algorithm would become - which means you'd need to explicitly add/remove them from the map

TreeSet<AreaInfo> mySortedMap ;

public void updateAreaEntry(AreaInfo old, AreaInfo new) {
   mySortedMap.remove(old) ;
   mySortedMap.add(new) ;
}

where before you would have just modified the contents of an AreaInfo object rather than making a new one.

Doug
0
 
jksungAuthor Commented:
Hi Doug,

Thanks, but I can't do this since the functions and events changing the hasViolated property has no visibility of this particular arraylist, plus the AreaInfo objects are used in many places throughout the program, that may also need to be sorted.

Is there a way I can freeze the objects so that their properties don't change for the duration of the sort?  I tried using a countdown latch right after the call to sort, but the object properties are still changing, something else other than these threads are changing the properties of the objects.
0
 
dpearsonCommented:
Yeah there's no way to say "please ignore changes to my object while I am sorting them".

I think you have 2 options:
a) Create a complete copy of the list (including a copy of all the AreaInfo objects), sort that and then use that sorted list to re-order the list you are actually showing.

Complicated and slow.

b) Write your own sort function.

This might sound hard, but really isn't that bad.  What I'd suggest is implementing the world's simplest sort - bubble sort.
Bubble sort is just this at it's core (psuedo code):

while (!done) {
   done = true ;
   for (int i = 0 ; i < list.length()-1 ; i++) {
      a = list.get(i) ;
      b = list.get(i+1) ;
      if (a.biggerThan(b)) {
        swap(a,b) ;
        done = false ;
      }
  }
}

Open in new window


The key for this is you can keep running this over and over.  If the elements in the list are changing position, the sorting doesn't break - the elements that are out of order will slow bubble up/down to the correct positions.  Bubble sort is relatively slow but it's simple and works.

A normal sort assumes that once it puts something into order, it will stay there.
But bubble sort (at least implemented like I suggested) doesn't have that problem.

Doug
1
 
jksungAuthor Commented:
Thank you!  Your bubble sort works for my purposes.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now