[concurrency-interest] Deque and skip list integration

Luke Blanshard blanshlu@netscape.net
Thu, 30 Dec 2004 11:00:52 -0600


--------------030601060101040204060804
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

dl@cs.oswego.edu wrote:

>>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...
>
While that would be nice, it's not what I'm really looking for.  I would 
like to be able to make better use of the links that the LinkedHashMap 
maintains -- more than just for iteration.  I'd like to be able to jump 
into the map at a particular point and continue from there, in either 
direction.  The methods you've defined in NavigableMap do just this, and 
it would be no particular difficulty or extra overhead to provide this 
functionality in LinkedHashMap (AFAICT), so thus my complaint/proposal.

In fact, I'd be happy to have this functionality available on the 
LinkedHash classes regardless of whether you included the methods in 
separate interfaces.  But it seems to me so close to the intent of the 
Navigable interfaces that it looks like an oversight.  It is true that 
the methods would have slightly different semantics in the LinkedHash 
setting than in the Sorted setting because the order is not independent 
of the current contents of the collection.  But that could be finessed.

>...  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 :-)
>  
>
Thanks -- that's all I ask!

>>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;
>}
>  
>
Yeah, that's what I do now.  It works, and it keeps the garbage 
collector busy.

Luke

--------------030601060101040204060804
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
  <title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
<a class="moz-txt-link-abbreviated" href="mailto:dl@cs.oswego.edu">dl@cs.oswego.edu</a> wrote:<br>
<blockquote cite="mid16852.3840.858136.392373@altair.cs.oswego.edu"  type="cite">
  <blockquote type="cite">
    <pre wrap="">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.  
    </pre>
  </blockquote>
  <pre wrap=""><!---->I think what you want here is an IndexedList: a List (with associated
ListIterators and SubLists) with elements indexed by a hash
table...</pre>
</blockquote>
While that would be nice, it's not what I'm really looking for.&nbsp; I
would like to be able to make better use of the links that the
LinkedHashMap maintains -- more than just for iteration.&nbsp; I'd like to
be able to jump into the map at a particular point and continue from
there, in either direction.&nbsp; The methods you've defined in NavigableMap
do just this, and it would be no particular difficulty or extra
overhead to provide this functionality in LinkedHashMap (AFAICT), so
thus my complaint/proposal.<br>
<br>
In fact, I'd be happy to have this functionality available on the
LinkedHash classes regardless of whether you included the methods in
separate interfaces.&nbsp; But it seems to me so close to the intent of the
Navigable interfaces that it looks like an oversight.&nbsp; It is true that
the methods would have slightly different semantics in the LinkedHash
setting than in the Sorted setting because the order is not independent
of the current contents of the collection.&nbsp; But that could be finessed.<br>
<blockquote cite="mid16852.3840.858136.392373@altair.cs.oswego.edu"  type="cite">
  <pre wrap="">...  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 :-)
  </pre>
</blockquote>
Thanks -- that's all I ask!<br>
<blockquote cite="mid16852.3840.858136.392373@altair.cs.oswego.edu"  type="cite">
  <blockquote type="cite">
    <pre wrap="">I'd like to be able to look at or poll for the first entry. 
    </pre>
  </blockquote>
  <pre wrap=""><!---->While probably not as efficient as it might be if built-in, you can do:

&lt;T&gt; getFirst(LinkedHashSet&lt;T&gt; s) { return s.iterator().next(); }

&lt;T&gt; pollFirst(LinkedHashSet&lt;T&gt; s) { 
  Iterator&lt;T&gt; i = s.iterator();
  if (!i.hasNext() return null;
  T x = i.next();
  i.remove();
  return x;
}
  </pre>
</blockquote>
Yeah, that's what I do now.&nbsp; It works, and it keeps the garbage
collector busy.<br>
<br>
Luke<br>
</body>
</html>

--------------030601060101040204060804--