[SOLVED] Sorted List (?)

[jonjava]

Hello!

What I want to do:

I have many object all with their own "depth" value. This value determines WHEN this object is drawn on the screen ( so that objects farther away don't overlap object that are supposed to be infront of them ).

I tried using an ArrayList at first. Inserting with arrayList.add(obj, obj.depth()); thinking it would sort the objects based on their depth. But it didn't sort them at all.

Then I tried using a Map, it worked except for one huge detail... I couldn't have multiple objects with the same depth. So lots of objects didn't get drawn on the screen at all.

Then I tried using this TreeMap class that implements a SortedMap interface - it sounded promising, however, the same problem occured as with the Map, I was unable to store multiple object with the same depth in the map.


the depth of these objects is an integer value. If that helps, I'm at a loss on how to accomplish this, any ideas?

Thanks,
Jon

[ra4king]

The simplest way is to just put them all in an ArrayList and then sort it using Collections.sort(List,Comparable).

A faster slower way is to search for the spot to put it in by using Collections.binarySearch(List<T>,T,Comparable). This either returns >= 0 if it has found a similar value or a negative number if it has not found it and has found the location to put it. Read the javadocs to understand how to use it.

[Riven]

It's actually much faster to call sort(...) after you filled a List by adding, than to insert every element at their proper location.

Games published by our own members! Check 'em out!

[jonjava]

I've been trying to figure out how to use the binarySearch method. I chose it since there will be lots of objects and whenever you add a new object it seems extremely wasteful to sort a list of a 1000+ objects that were already sorted.

This is how (in a nutshell) I've tried to implement the binarySearch:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28

ArrayList<ISOObject> arrayList = new ArrayList<ISOObject>(); // The Comparator        class DepthComparator implements Comparator<ISOObject> {                 // A Comparator class to compare objects depths                public int compare(ISOObject obj1, ISOObject obj2) {                         // compare depths                        if( obj1.getDepth() == obj2.getDepth() )                                 return 0;                         if( obj1.getDepth() < obj2.getDepth() )                                 return -1;                                 else                                 return 1;                 }         } /* The method to add an Object into our arrayList at the correct index position using binarySearch */ private void add(ArrayList<ISOObject> arrayList, ISOObject obj) {                 // adds an object to the array list at its correct position                // ( depends on getDepth() )                Comparator<ISOObject> c = new DepthComparator();                 int index;                 index =                         Collections.binarySearch(arrayList, obj.getDepth(), c); // Here I get a compiler error**********                 // Now that we get the correct index position with binarySearch, use the arrayList.add() method.                this.arrayList.add(index, obj);         }

*The error is the following:
"internal error; cannot instantiate <T>binarySearch(java.util.List<? extends T>, T, java.util.Comparator<? super T>> at java.util.Collections to ( java.util.ArrayList<ISOObject>, int, java.util.Comparator<ISOObject>>
      Collections.binarySearch(arrayList, obj.getDepth()m c);
                              ^     

Which, by staring at it for 10 minutes.. tells me nothing

If a quick glance by an experienced eye could be help me out I'd very much appreciate it!

Thanks,
jon

[Riven]

You can start by reading the javadoc of Collections.binarySearch to discover why the returned value cannot always be used to specify an index in a List.

[jonjava]

You mean if the list is undsorted it might return random indexes? But that won't be the case here since the list is sorted bottoms up.

Anyway, the problem with my code was that I had "obj.getDepth()" as the key-parameter in the binarySearch method when "obj" was correct.

The binarySearch returns the index in the list where the object fits in, and if it doesn't fit anywhere, it returns a negative value of what index it would have taken if it could have. So that's easy enough to convert back to its positive value.

Now it works fine as far as I can see:)

Thanks for your help,
jon

[EDIT] Here's a quick before and after glance for those interested

[Riven]

The binarySearch returns the index in the list where the object fits in, and if it doesn't fit anywhere, it returns a negative value of what index it would have taken if it could have. So that's easy enough to convert back to its positive value.

That's what I meant.

[jonjava]

A faster slower way is to search for the spot to put it in by using Collections.binarySearch(List<T>,T,Comparable).

How I sort the list is that whenever a new object is created it is added to the list in its sorted place. Is this still faster with binarySearch? Or should I add the object to the end of the ArrayList and then run the sort() method?

Basically my question is this: Is it faster to insert an object at its right place in an ArrayList containing 1000+ objects with binarySearch - or should I add the object at the end and run the sort() method?

Thanks,
jon

[Riven]

There are two situations we have to distinguish:

1. You have to add one or a handful of items to a list, which must be ordered.
In that case, use binarySearch(...) to insert the item(s)

2. You have to add more than a handful of items to a list, which must be ordered.
In that case, add the N items to the end of the list, and sort(...) the entire list

[ra4king]

Yeah only sort after ALL of the items have been added. Don't sort after each one.

Games published by our own members! Check 'em out!

[jonjava]

Thanks for clearing that up!

jon