Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Java (http://www.velocityreviews.com/forums/f30-java.html)
-   -   Glitch in Java Collections (No descendingMap in LinkedHashMap) (http://www.velocityreviews.com/forums/t953028-glitch-in-java-collections-no-descendingmap-in-linkedhashmap.html)

Jan Burse 10-04-2012 12:09 PM

Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
Dear All,

I just wonder whether I have overlooked something.
But could it be that LinkedHashMap is lacking the
following API:

Map<K,V> descendingMap();

So I can only iterate from oldest to youngest, and
not the other direction?

Although under the hood it uses a double linked list,
and a reverse iterator would be simple.

Also the whole matter seems to be complicated, since
the other collections have descendingMap() in an
Interface NavigableMap, which extends SortedMap.

But SortedMap map assumes a compartor, whereby the
sorting in LinkedHashMap is implicit.

Is there some shortcut to arrive at a reverse iterator
of LinkedHashMap?

(Troll disclaimer: No I have no SSCCE (Short, Self
Contained, Correct (Compilable), Example). This is
a conceptual question.)

Bye

Robert Klemme 10-04-2012 09:01 PM

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
On 04.10.2012 14:09, Jan Burse wrote:
> Dear All,
>
> I just wonder whether I have overlooked something.
> But could it be that LinkedHashMap is lacking the
> following API:
>
> Map<K,V> descendingMap();
>
> So I can only iterate from oldest to youngest, and
> not the other direction?


I guess they omitted it because the purpose is to provide a Map which
always returns elements in insertion order (and not reverse insertion
order).

> Although under the hood it uses a double linked list,
> and a reverse iterator would be simple.
>
> Also the whole matter seems to be complicated, since
> the other collections have descendingMap() in an
> Interface NavigableMap, which extends SortedMap.


There you see why it's not in LinkedHashMap: it's neither a NavigableMap
nor a SortedMap.

> But SortedMap map assumes a compartor, whereby the
> sorting in LinkedHashMap is implicit.


There is no sorting going on - you just get insertion order.

Cheers

robert

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

Lew 10-04-2012 09:43 PM

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
Robert Klemme wrote:
> Jan Burse wrote:
>> I just wonder whether I have overlooked something.
>> But could it be that LinkedHashMap is lacking the
>> following API:

>
>> Map<K,V> descendingMap();


It's also lacking 'ascendingMap()'

>> So I can only iterate from oldest to youngest, and
>> not the other direction?

>
> I guess they omitted it because the purpose is to provide a Map which
> always returns elements in insertion order (and not reverse insertion
> order).
>
>> Although under the hood it uses a double linked list,
>> and a reverse iterator would be simple.
>>
>> Also the whole matter seems to be complicated, since
>> the other collections have descendingMap() in an
>> Interface NavigableMap, which extends SortedMap.

>
> There you see why it's not in LinkedHashMap: it's neither a NavigableMap
> nor a SortedMap.
>
>> But SortedMap map assumes a compartor, whereby the
>> sorting in LinkedHashMap is implicit.

>
> There is no sorting going on - you just get insertion order.


You get insertion order how?

The interesting thing about this class is that it has no public methods that reveal
the order.

So what difference does the order make?

I can guess, but the docs don't confirm, that iterators off the keyset or entryset would
respect the order, but the documentation for the 'keySet()' and 'entrySet()' methods doesn't
promise this.

It's useful for subclasses, from what the documentation hints, but to the public?

--
Lew

Jan Burse 10-04-2012 10:17 PM

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
Lew schrieb:
> You get insertion order how?


The class LinkedHashMap provides two orders. It has a constructor:

/**
...
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
...
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)

I am only interested in the case accessOrder = false. As you see
the doc mentions itself the term "insertion-order".

I would refine it to "first-insert-order". Since the implementation
is such that only the first put() counts concerning the order.

put 2, 1, 1, 2
Gives you the order 2, 1

Bye


Robert Klemme 10-05-2012 05:11 PM

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
On 04.10.2012 23:43, Lew wrote:
> Robert Klemme wrote:
>> Jan Burse wrote:


>>> But SortedMap map assumes a compartor, whereby the
>>> sorting in LinkedHashMap is implicit.

>>
>> There is no sorting going on - you just get insertion order.

>
> You get insertion order how?


First paragraph of JavaDoc:

Hash table and linked list implementation of the Map interface, with
predictable iteration order. This implementation differs from HashMap in
that it maintains a doubly-linked list running through all of its
entries. This linked list defines the iteration ordering, which is
normally the order in which keys were inserted into the map
(insertion-order). Note that insertion order is not affected if a key is
re-inserted into the map.

> The interesting thing about this class is that it has no public methods that reveal
> the order.


Why would they need to?

> So what difference does the order make?


There are some use cases described in the class JavaDoc.

> I can guess, but the docs don't confirm, that iterators off the keyset or entryset would
> respect the order, but the documentation for the 'keySet()' and 'entrySet()' methods doesn't
> promise this.


You do not have to guess - logical reasoning is enough. The only way to
iterate through a Map is via entrySet(), keySet() and values(). What
other methods could make use of the order if not these?

> It's useful for subclasses, from what the documentation hints, but to the public?


It seems you could create a LRU Map with this, right. Other uses are
described in the class doc as mentioned above.

Kind regards

robert



--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

Lew 10-05-2012 06:05 PM

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
Robert Klemme wrote:
> Lew wrote:
>> Robert Klemme wrote:
>>> Jan Burse wrote:

> > You get insertion order how?

>
> First paragraph of JavaDoc:
>
> Hash table and linked list implementation of the Map interface, with
> predictable iteration order. This implementation differs from HashMap in
> that it maintains a doubly-linked list running through all of its
> entries. This linked list defines the iteration ordering, which is
> normally the order in which keys were inserted into the map
> (insertion-order). Note that insertion order is not affected if a key is
> re-inserted into the map.


That says how you put the order, not how you get the order.

>> The interesting thing about this class is that it has no public methods that reveal
>> the order.

>
> Why would they need to?


If the ordered state is not observable, what difference does it make?

>> So what difference does the order make?

>
> There are some use cases described in the class JavaDoc.


It doesn't explain how you reveal the order, only how you put it into another structure.

>> I can guess, but the docs don't confirm, that iterators off the keyset or entryset would
>> respect the order, but the documentation for the 'keySet()' and 'entrySet()' methods doesn't
>> promise this.

>
>
> You do not have to guess - logical reasoning is enough. The only way to
> iterate through a Map is via entrySet(), keySet() and values(). What
> other methods could make use of the order if not these?


But these methods do not promise to return the data in any particular order, particularly
they do not promise to return the data in the order stored. In fact, they promise not to,
necessarily. From Set#iterator(): "The elements are returned in no particular order
(unless this set is an instance of some class that provides a guarantee)."

The Map makes the guarantee, and one has to infer the underlying Set will therefore
make that guarantee, but when one copies the Map into another Map implementation,
even that implicit promise is removed. Furthermore, why do they not state that the Set
implementation iterator's order is guaranteed? It seems there's a hole in the docs.

>> It's useful for subclasses, from what the documentation hints, but to the public?

>
> It seems you could create a LRU Map with this, right. Other uses are
> described in the class doc as mentioned above.


Right, that LRU Map would be a subclass, as I said.

--
Lew

Jan Burse 10-05-2012 06:18 PM

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
Lew schrieb:
>> There are some use cases described in the class JavaDoc.

> It doesn't explain how you reveal the order,


Java doc that only shows public entries does indeed not
help, since the magic happens in a package local method.

From HashMap:

// Subclass overrides these to alter behavior of views' iterator()
method
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}

From LinkedHashMap:

// These Overrides alter the behavior of superclass view iterator()
methods
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator() { return new
EntryIterator(); }




Daniel Pitts 10-05-2012 07:06 PM

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
On 10/5/12 11:05 AM, Lew wrote:
> Robert Klemme wrote:
>> Lew wrote:
>>> Robert Klemme wrote:
>>>> Jan Burse wrote:
>>> You get insertion order how?

>>
>> First paragraph of JavaDoc:
>>
>> Hash table and linked list implementation of the Map interface, with
>> predictable iteration order. This implementation differs from HashMap in
>> that it maintains a doubly-linked list running through all of its
>> entries. This linked list defines the iteration ordering, which is
>> normally the order in which keys were inserted into the map
>> (insertion-order). Note that insertion order is not affected if a key is
>> re-inserted into the map.

>
> That says how you put the order, not how you get the order.


What are you talking about Lew?
The JavaDoc says specifically "with predictable iteration order.".

This indicates that the iteration order is the same as the order in
which items are "put", baring key collisions.
>
>>> The interesting thing about this class is that it has no public methods that reveal
>>> the order.

>>
>> Why would they need to?

>
> If the ordered state is not observable, what difference does it make?

The ordered state is observable through iteration. The OP was only
asking for reverse iterator, which isn't part of what he can get. I
wouldn't call that a glitch, just a feature request.
>
>>> So what difference does the order make?

>>
>> There are some use cases described in the class JavaDoc.

>
> It doesn't explain how you reveal the order, only how you put it into another structure.


Iteration is how you reveal the order.

Lew 10-05-2012 08:04 PM

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
On Friday, October 5, 2012 12:06:18 PM UTC-7, Daniel Pitts wrote:
> Iteration is how you reveal the order.


Iteration of what?

Again, my concern is that 'Set' doesn't promise predictable iteration order, in fact,
exactly the opposite. The only iterators available for a 'Map' are through its 'Set'-
returning methods, which result in a collection that promises not to have a predictable
iteration order.

So I ask one more time - in what way is that guaranteed iteration order revealed?

I understand that the only way is through those iterators, but the Javadocs have a hole
in them about that.

--
Lew

Jan Burse 10-05-2012 09:44 PM

Re: Glitch in Java Collections (No descendingMap in LinkedHashMap)
 
Lew schrieb:
> Again, my concern is that 'Set' doesn't promise predictable iteration order, in fact,
> exactly the opposite. The only iterators available for a 'Map' are through its 'Set'-
> returning methods, which result in a collection that promises not to have a predictable
> iteration order.


Well that is not fully correct. When you get a keySet, entrySet or
valueSet, you indeed get an object that is derived from the class
Set. And this class in itself has indeed no guarantee.

The key for understanding what guarantees are around, is looking at
the interface which provides the keySet, entrySet or valueSet. For
example when the entrySet comes from SortedMap, then we have the
following javadoc:

public interface SortedMap<K,V> extends Map<K,V> {

/**
* Returns a {@link Set} view of the mappings contained in this map.
* The set's iterator returns the entries in ascending key order.
...
*/
Set<Map.Entry<K, V>> entrySet();

Do you see the mention of ascending key order above?

But LinkedHashMap does not implement this interface as I mentioned
in my initial post. And HashMap, the super class, has no guarantee.
So this is probably a Java glitch.

But I was not aspiring in detecting this glitch. I am more interested
in the reverse iterator. Any route to get at a reverse iterator?

Bye






All times are GMT. The time now is 10:15 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.