Java-Gaming.org
Play Revenge of the Titans! The situation is critical. We need fancy commanders to defend Earth, the moon, Mars!
Featured games (78)
games approved by the League of Dukes
Games in Showcase (408)
games submitted by our members
Games in WIP (293)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  [SOLVED] Sorted List (?)  (Read 1063 times)
0 Members and 1 Guest are viewing this topic.
Offline jonjava

JGO Knight


Medals: 33



« Posted 2011-10-09 13:46:12 »

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

Offline ra4king

JGO Kernel


Medals: 264
Projects: 2


I'm the King!


« Reply #1 - Posted 2011-10-09 14:13:41 »

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.

Online Riven
« League of Dukes »

JGO Overlord


Medals: 439
Projects: 4


Hand over your head.


« Reply #2 - Posted 2011-10-09 14:18:16 »

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Projects: Revenge of the Titans, Titan Attacks, Droid Assault, and Ultratron
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline jonjava

JGO Knight


Medals: 33



« Reply #3 - Posted 2011-10-09 15:49:53 »

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 Sad

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

Thanks,
jon

Online Riven
« League of Dukes »

JGO Overlord


Medals: 439
Projects: 4


Hand over your head.


« Reply #4 - Posted 2011-10-09 15:58:10 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Projects: Revenge of the Titans, Titan Attacks, Droid Assault, and Ultratron
Offline jonjava

JGO Knight


Medals: 33



« Reply #5 - Posted 2011-10-09 16:53:43 »

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

Online Riven
« League of Dukes »

JGO Overlord


Medals: 439
Projects: 4


Hand over your head.


« Reply #6 - Posted 2011-10-09 16:56:44 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Projects: Revenge of the Titans, Titan Attacks, Droid Assault, and Ultratron
Offline jonjava

JGO Knight


Medals: 33



« Reply #7 - Posted 2011-10-10 23:12:27 »

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

Huh

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

Online Riven
« League of Dukes »

JGO Overlord


Medals: 439
Projects: 4


Hand over your head.


« Reply #8 - Posted 2011-10-10 23:19:28 »

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Projects: Revenge of the Titans, Titan Attacks, Droid Assault, and Ultratron
Offline ra4king

JGO Kernel


Medals: 264
Projects: 2


I'm the King!


« Reply #9 - Posted 2011-10-10 23:41:04 »

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!
Legends of Yore - The Casual Retro Roguelike
Offline jonjava

JGO Knight


Medals: 33



« Reply #10 - Posted 2011-10-11 06:40:37 »

Thanks for clearing that up!

jon

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

Play Revenge of the Titans! The situation is critical. We need fancy commanders to defend Earth, the moon, Mars!
 
Play Revenge of the Titans! The situation is critical. We need fancy commanders to defend Earth, the moon, Mars and Titan!

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

The invasion has landed! On Mars! And you're there to beat 'em!
cubemaster21 (133 views)
2013-05-17 21:29:12

alaslipknot (142 views)
2013-05-16 21:24:48

gouessej (171 views)
2013-05-16 00:53:38

gouessej (166 views)
2013-05-16 00:17:58

theagentd (175 views)
2013-05-15 15:01:13

theagentd (160 views)
2013-05-15 15:00:54

StreetDoggy (204 views)
2013-05-14 15:56:26

kutucuk (228 views)
2013-05-12 17:10:36

kutucuk (228 views)
2013-05-12 15:36:09

UnluckyDevil (231 views)
2013-05-12 05:09:57
Complex number cookbook
by Roquen
2013-04-24 12:47:31

2D Dynamic Lighting
by Oskuro
2013-04-17 16:46:12

2D Dynamic Lighting
by Oskuro
2013-04-17 16:45:57

2D Dynamic Lighting
by Oskuro
2013-04-17 16:23:20

Noise (bandpassed white)
by Roquen
2013-04-05 17:36:01

Noise (bandpassed white)
by Roquen
2013-04-03 16:17:38

Java Data structures
by Roquen
2013-03-29 13:21:12

Topic Request
by kutucuk
2013-03-22 21:42:01
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!
Page created in 0.156 seconds with 21 queries.