[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

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

Posted on 2016-11-16
7
Medium Priority
?
102 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 28

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 28

Accepted Solution

by:
dpearson earned 2000 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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
Suggested Courses
Course of the Month18 days, 23 hours left to enroll

834 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