Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (512)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (576)
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 1639 times)
0 Members and 1 Guest are viewing this topic.
Offline jonjava
« Posted 2011-10-09 11: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: 350
Projects: 3
Exp: 5 years


I'm the King!


« Reply #1 - Posted 2011-10-09 12: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.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2011-10-09 12: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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline jonjava
« Reply #3 - Posted 2011-10-09 13: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

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2011-10-09 13: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
Offline jonjava
« Reply #5 - Posted 2011-10-09 14: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

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2011-10-09 14: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
Offline jonjava
« Reply #7 - Posted 2011-10-10 21: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

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2011-10-10 21: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
Offline ra4king

JGO Kernel


Medals: 350
Projects: 3
Exp: 5 years


I'm the King!


« Reply #9 - Posted 2011-10-10 21: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
« Reply #10 - Posted 2011-10-11 04:40:37 »

Thanks for clearing that up!

jon

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

 

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

The first screenshot will be displayed as a thumbnail.

Longarmx (50 views)
2014-10-17 03:59:02

Norakomi (39 views)
2014-10-16 15:22:06

Norakomi (31 views)
2014-10-16 15:20:20

lcass (35 views)
2014-10-15 16:18:58

TehJavaDev (66 views)
2014-10-14 00:39:48

TehJavaDev (65 views)
2014-10-14 00:35:47

TehJavaDev (55 views)
2014-10-14 00:32:37

BurntPizza (72 views)
2014-10-11 23:24:42

BurntPizza (43 views)
2014-10-11 23:10:45

BurntPizza (84 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
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!