Solved

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

Posted on 2016-11-16
7
63 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
Creating Instructional Tutorials  

For Any Use & On Any Platform

Contextual Guidance at the moment of need helps your employees/users adopt software o& achieve even the most complex tasks instantly. Boost knowledge retention, software adoption & employee engagement with easy solution.

 
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

Secure Your Active Directory - April 20, 2017

Active Directory plays a critical role in your company’s IT infrastructure and keeping it secure in today’s hacker-infested world is a must.
Microsoft published 300+ pages of guidance, but who has the time, money, and resources to implement? Register now to find an easier way.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
servlet filter example 37 85
by zero exception 10 70
Detect Closed Loops (circles, figure-8s, etc) in PNG Images 6 79
mysql jsp example issue 32 75
After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
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…

696 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