1

Given the following TreeMap:

Map<Double, Integer> treeMap = new TreeMap<Double, Integer>() {{. 
        put("52.1", 1);
        put("53.4", 2); 
        put("57.1", 3); 
        put("59.4", 7); 
        put("60.2", 11); 
        put("71.6", 16)}};

What would be the best way to return the closest n matches (in both directions) for a given double? For instance, n=2 and "58.0" would return 53.4, 57.1, 59.4, 60.2

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
ShaneK
  • 193
  • 9
  • 3
    Have a look at `lowerEntry()` and `higherEntry()` and simple for-loops – Lino Jul 15 '20 at 16:56
  • 2
    Or `headMap()` and `tailMap()`. Look over the [NavigableMap API](https://docs.oracle.com/javase/8/docs/api/java/util/NavigableMap.html), there are lots of options. – John Kugelman Jul 15 '20 at 17:11
  • 2
    A key part to make the extended methods of `NavigableMap` work is conversion of the `String` data (e.g., "53.4") to a `Double` instance. Your code doesn't illustrate that. Can you please include your actual, compilable code, so that we can help address any issues there? As an aside, you are using [double-brace initialization](https://stackoverflow.com/a/27521360/3474) here, which I would strongly discourage. – erickson Jul 15 '20 at 17:20
  • 2
    Pun not intended. – erickson Jul 15 '20 at 17:26

1 Answers1

3

tl;dr

new TreeMap <>(
        Map.of(
                52.1d , 1 ,
                53.4d , 2 ,
                57.1d , 3 ,
                59.4d , 7 ,
                60.2d , 11 ,
                71.6d , 16
        )
)
.floorKey( 58.0d )     // Or call `.ceilingKey( 58.0d )`

See this code run live at IdeOne.com.

57.1

NavigableMap::lowerKey/higherKey

TreeMap is a NavigableMap.

The NavigableMap interface provides methods for retrieving adjacent keys (and entries).

Repeat the commands to fetch as many adjacent keys as you desire, until receiving a null.

Comparing keys

On second reading, it seems you do not have a key. You have a value you want to compare to keys in a map.

In this case, fetch a Set of all the keys in the map. NavigableMap extends SortedMap. So we can call SortedMap::keySet. The returned set iterates in sorted order.

Set< Double > set = map.keySet() ;

Make a List of that, to access individual elements by index.

List< Double > doublesListSorted = List.of( set.toArray() ) ;  // Get un-modifiable list.

Now you can loop the sorted list to compare values.

NavigableMap::floorKey/ceilingKey

Or, as dnault commented, we can ask the NavigableMap to compare key values for a nearest-match.

  • floorKey
    Returns the greatest key less than or equal to the given key, or null if there is no such key.
  • ceilingKey
    Returns the least key greater than or equal to the given key, or null if there is no such key.

Example code

Make an input map. We use Map.of initially for its convenient literal syntax. Then we feed that un-modifiable map to the constructor of TreeMap. Our literal input seen here happens to be sorted, but that is irrelevant, as the TreeMap constructor will sort the entries by key.

NavigableMap < Double, Integer > map =
        new TreeMap <>(
                Map.of(
                        52.1d , 1 ,
                        53.4d , 2 ,
                        57.1d , 3 ,
                        59.4d , 7 ,
                        60.2d , 11 ,
                        71.6d , 16
                )
        );

map.toString(): {52.1=1, 53.4=2, 57.1=3, 59.4=7, 60.2=11, 71.6=16}

Set our target to which we want the closest matches.

Double target = 58.0d;

Get the adjacent keys, next lower, and next higher.

Double nextLower = map.floorKey( target );
Double nextHigher = map.ceilingKey( target );

nextLower = 57.1 nextHigher = 59.4

See this code run live at IdeOne.com.

Notes:

Table of map implementations in Java 11, comparing their features

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
  • I appreciate (and yes up-voted) the help. I was using lowerkey and higherkey but it seemed a little kludgy. I like the SortedMap solution. – ShaneK Jul 15 '20 at 17:37
  • 2
    Instead of looping over the keyset to compare keys, you can call [ceilingKey(K key)](https://docs.oracle.com/javase/8/docs/api/java/util/NavigableMap.html#ceilingKey-K-) or [floorKey(K key)](https://docs.oracle.com/javase/8/docs/api/java/util/NavigableMap.html#floorKey-K-) to get the keys nearest any given starting point. – dnault Jul 15 '20 at 17:39
  • @dnault Thank you for the tip. That makes for slick simple coding. – Basil Bourque Jul 15 '20 at 19:47
  • I ended up using a variation of this in loop form. I was attempting to find n values below and above a given value for interpolation. – ShaneK Jul 17 '20 at 15:37