0

Is there a datatype or class which will allow me to accomplish this or what would be an efficient way to produce a similar effect.

1) Add items to an array with an associated float key (will have a few duplicate float keys)

2) Sort the array from least to greatest based on the float key OR grab the lowest float key and return those objects.

I need this to be relatively efficient because I will be repeating this many times per second.

CodeCamper
  • 6,609
  • 6
  • 44
  • 94
  • HashMap for a data structure and TreeMap for sorting should accomplish this – ryekayo Apr 06 '15 at 21:44
  • @ryekayo HashMap doesn't allow duplicate values per key does it? Post an answer with a simple working example so I can mark you as the answer. – CodeCamper Apr 06 '15 at 21:47
  • Float keys are a recipe for trouble, because they will frequently be a tiny bit off. – SLaks Apr 06 '15 at 21:47
  • You aren't going to want to have to sort several times per second, so you're going to want something that "self sorts". Take a look at the answers to [this question](http://stackoverflow.com/questions/8725387/why-is-there-no-sortedlist-in-java) for some ideas. – azurefrog Apr 06 '15 at 21:47
  • @SLaks in libGDX pretty much all the libraries use float so I am using float. I need this because I want to keep a record of the objects that are closest to my object and order them from furthest to closest. – CodeCamper Apr 06 '15 at 21:48
  • @azurefrog checking it out now. If you post a simple example of doing step 1 and 2 I will mark you as the answer. – CodeCamper Apr 06 '15 at 21:51
  • @CodeCamper, unfortunately, HashMaps do not allow duplicate keys so that will not work. – ryekayo Apr 06 '15 at 21:58
  • @ryekayo what is an easy alternative to allow duplicates without an external library? – CodeCamper Apr 06 '15 at 21:59
  • @CodeCamper, it seems that someone has already provided an answer. I would take a look at the links Sunil provided – ryekayo Apr 06 '15 at 22:00
  • @ryekayo I am looking at it, but I don't know if I need all the features at the moment, I just need to be able to quickly pull a key with duplicate items. I can handle the sorting myself by keeping track of the lowest key I entered pretty easily. – CodeCamper Apr 06 '15 at 22:01
  • "will have a few duplicate float keys" This is possible, but not recommended. Float comparisons don't always work like you expect them to. – David Ehrmann Apr 06 '15 at 23:32
  • @DavidEhrmann I am using libGDX and the default coordinate system is all in float. I want to measure the closest object. What other option do I really have? – CodeCamper Apr 07 '15 at 00:58

1 Answers1

1

What you need for your purpose is a Multimap as there will be duplicate keys. While C++ provides the multimap interface, Java SE does not have one built in. But you can use the TreeMultimap from the Google Guava library (it used to be available under Google Collections but as Louis Wassernman noted in the comments, it's been dead for a long time and you should avoid using it). The documentation for the class is at http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/TreeMultimap.html

Please keep in mind that the TreeMultimap sorts both the keys and values based on the comparator provided (or natural ordering if no comparators are provided). The natural ordering is to sort the map from the smallest to the biggest entry. If you do not want your values sorted as well, you will want to play around with the supplied comparator a bit.

Here is code that has some unit tests for the TreeMultimap itself. You can very easily use this as an example for what you want http://google-collections.googlecode.com/svn-history/r76/trunk/test/com/google/common/collect/TreeMultimapNaturalTest.java.

ucsunil
  • 7,378
  • 1
  • 27
  • 32
  • 1
    Please don't use Google Collections; it has been dead for years and years. Use Guava. (And also feel free to use `MultimapBuilder.treeKeys().arrayListValues().build()` if you don't want to sort values.) – Louis Wasserman Apr 06 '15 at 22:58