Solved

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

Posted on 2016-11-16
7
60 Views
Last Modified: 2016-11-17
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
Comment
Question by:jksung
7 Comments
 
LVL 16

Expert Comment

by:gurpsbassi
ID: 41890269
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
 
LVL 7

Expert Comment

by:micropc1
ID: 41890304
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
 

Author Comment

by:jksung
ID: 41890307
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
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 27

Expert Comment

by:dpearson
ID: 41890406
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
 

Author Comment

by:jksung
ID: 41890433
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
 
LVL 27

Accepted Solution

by:
dpearson earned 500 total points
ID: 41890661
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
 

Author Closing Comment

by:jksung
ID: 41891888
Thank you!  Your bubble sort works for my purposes.
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
eclipse shortcuts 9 63
oracle 11g 23 107
Way to decrease size of apk file 9 87
swing controls 2 16
By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.

831 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question