[concurrency-interest] Deque and skip list integration

Doug Lea dl@cs.oswego.edu
Thu, 30 Dec 2004 09:21:52 -0500


> I'd like to be able to look at or poll for the first entry.  I'd like to 
> be able to construct views that begin, end, or are bounded by particular 
> keys.  Or that yield the same collection in reverse order.  

I think what you want here is an IndexedList: a List (with associated
ListIterators and SubLists) with elements indexed by a hash
table. This is more than LinkedHashMap can do without adding a lot of
overhead.  It would make nearly all users of LinkedhashMap unhappy to
have slower performance if this functionality wer added anyway, so it
would need to be a new java.util class and interface.  This is not
officially in scope of JSR166 unless we also added
ConcurrentIndexedList, for which there is probably not enough
demand/need.  But the expert group just so happens to include the
people who wrote most of java.util collections, who will discuss it as
an unrelated RFE :-)

> I'd like to be able to look at or poll for the first entry. 

While probably not as efficient as it might be if built-in, you can do:

<T> getFirst(LinkedHashSet<T> s) { return s.iterator().next(); }

<T> pollFirst(LinkedHashSet<T> s) { 
  Iterator<T> i = s.iterator();
  if (!i.hasNext() return null;
  T x = i.next();
  i.remove();
  return x;
}


-Doug