Solved

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

Posted on 2016-11-16
7
30 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 15

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
Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

 
LVL 26

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 26

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

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Suggested Solutions

For customizing the look of your lightweight component and making it look lucid like it was made of glass. Or: how to make your component more Apple-ish ;) This tip assumes your component to be of rectangular shape and completely opaque. (COD…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:

705 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now