I'm implementing a NavigableMap-implementing LinkedHashMap in Java. (There don't seem to be many (any?) reasons why LinkedHashMap doesn't implement NavigableMap already, but I digress...)

I've written lowerKey(), lowerEntry(), higherKey(), and higherEntry() by iterating the entrySet(). I don't see any way in these cases to avoid iterating the entire entrySet().

For floorKey(), floorEntry(), ceilingKey(), and ceilingEntry(), in the case that the key exists, I'd like to avoid the expense of iterating the entrySet(), considering that I can already get the value with plain-old get().

Is there a way to get the Map.Entry for a particular key, rather than just the value? Thanks.

CodePudding user response：

You have the key, and you can get the value associated with the key using get, now all you gotta do is to make a Map.Entry, and we can do that with the Map.entry factory method:

var value = theBackingLinkedHashMap.get(key);
if (value == null) {
    return null;
}
return Map.entry(key, value);

The entry returned by entry does have two caveats that you should be aware of:

• does not allow null keys, so your NavigableLinkedHashMap would need to not allow null keys either
• is immutable, so you cannot call setValue.

But other than that, it will work as if you got the Map.Entry from inside the backing LinkedHashMap, and it does fulfil the contract of ceilingEntry, floorEntry etc, since they just ask for a "a key-value mapping", and doesn't require that it has to have the mutability as the map itself or anything like that. For example, this is ceilingEntry:

Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

CodePudding user response：

You could do something like this.

Map<String,Integer> map = Map.of("Foo", 123, "Bar", 234);

Function<String, Entry<String,Integer>> getEntry = 
             getEntryFnc(map);
        
System.out.println(getEntry.apply("Foo"));
System.out.println(getEntry.apply("Bar"));
System.out.println(getEntry.apply("Baz"));

prints

Foo=123
Bar=234
Baz=null    

Returns a lambda which builds an entry using the supplied key and map.

public static <K,V> Function<K, Entry<K,V>> getEntryFnc(Map<K,V> map) {
    return key-> 
           new AbstractMap.SimpleEntry<>(key, map.get(key));
    };
}

CodePudding user response：

I would use TreeSet to keep the keys in the NavigableMap class. See example below:

import java.util.*;
public class Main{
    public static void main(String[] args) {
        NavMap<Integer, String> map = new NavMap<>();
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        map.put(4, "four");
        map.put(10, "ten");
        System.out.println(map.lowerKey(3));    //2
        System.out.println(map.higherKey(3));   //4
        System.out.println(map.ceilingKey(7));  //10
        System.out.println(map.floorKey(7));    //4
    }
}

class NavMap<K extends Comparable,V extends Comparable> extends LinkedHashMap<K,V>{
   private TreeSet<K> keys    = new TreeSet<>();
   
   public K lowerKey  (K key){ return keys.lower(key);  }
   public K higherKey (K key){ return keys.higher(key); }
   public K floorKey  (K key){ return keys.floor(key);  }
   public K ceilingKey(K key){ return keys.ceiling(key);}
   
   public V put(K key, V value){
      keys.add(key);
      return super.put(key, value);
   }
}