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