LinkedHashMap containsKeyBetween(K target, K low, K high) method? (original) (raw)

Paulo Levi i30817 at gmail.com
Fri Aug 17 10:08:26 UTC 2012

I tried to make a LinkedHashMap.subMap(K low, K high) with a map implementation i had implemented inspired by linked list where the map keeps linked Nodes as values and unwraps them on get()

I failed of course, because i couldn't find a good way to deal with remove() on the original Map. The sublist implementation on the JDK depends on a modification counter to make sure no concurrent modifications from using the original list while the sublist is being used occur, which is fine for the linked list.

However a submap needs to limit their get() on a different way from linkedlist since it can't just check for range - though about adding a index to the nodes but that's obviously wrong since any remove from the map would ruin efficient size() if based on those indexes (even removes from before submap construction).

So i got less ambitious: public boolean containsKeyBetween(K target, K low, K high){ if(isEmpty()) return false;

    Node targetN = delegate.get(target);
    if(targetN == null)
        return false;

    Node highN, lowN;

    if(low == null) lowN = head.next; else lowN = delegate.get(low);
    if(high == null) highN = head.previous; else highN =

delegate.get(high);

    return lowN != null && highN != null && lowN.index <= targetN.index

&& targetN.index <= highN.index; } Node needs a monotonically increasing int index created when put(). I don't actually think it needs the forward and backwards links (i was just reusing code), but LinkedHashMap/Set (where it would be useful), use them already.

Is a method like this suitable for the JDK LinkedMap/Set?

More information about the core-libs-dev mailing list