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

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