Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Glitch in Java Collections (No descendingMap in LinkedHashMap)

Reply
Thread Tools

Glitch in Java Collections (No descendingMap in LinkedHashMap)

 
 
Jan Burse
Guest
Posts: n/a
 
      10-05-2012
Jan Burse schrieb:
> 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.


Corr.:
keySet or entrySet.
 
Reply With Quote
 
 
 
 
Jan Burse
Guest
Posts: n/a
 
      10-05-2012
Jan Burse schrieb:
> But I was not aspiring in detecting this glitch.


My post implies that I would fix this glitch by
introducing a new interface such as:

public interface ImplicitlySortedMap<K,V> {
}

But its not clear where to squeeze in this interface.
Basically I think the main glitch is to locate the
following method in NavigableMap:

public interface NavigableMap<K,V> {
NavigableMap<K,V> descendingMap();
}

So I would place it in the new interface,
instead of in NavigableMap:

public interface ImplicitlySortedMap<K,V> {
ImplicitlySortedMap<K,V> descendingMap();
}

And then squeezethe the new interface into the interface
hierarchie after Map and before SortedMap:

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

Bye



 
Reply With Quote
 
 
 
 
Daniel Pitts
Guest
Posts: n/a
 
      10-05-2012
On 10/5/12 1:04 PM, Lew wrote:
> On Friday, October 5, 2012 12:06:18 PM UTC-7, Daniel Pitts wrote:
>> Iteration is how you reveal the order.

>
> Iteration of what?

Anything that is a view into this map.
>
> 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.

The intent is pretty clear to me. It is predictable if the Set (or
Collection for the values() method) comes from a LinkedHashSet.
>
> So I ask one more time - in what way is that guaranteed iteration order revealed?

By definition of this class, both in documentation and implementation.

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

Perhaps they do, but the intent is more than clear, as is the
implementation. Perhaps the JavaDoc could have been more explicit, but
that isn't the point.

Any iteration over the contents of LinkedHashMap has a guaranteed order.
 
Reply With Quote
 
glen herrmannsfeldt
Guest
Posts: n/a
 
      10-05-2012
Jan Burse <(E-Mail Removed)> wrote:
> 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.


(snip)

> 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?


There are some problems in PracticeIt that require one to reverse
the order of something. Especially in the section on stacks.
Write a loop that takes objects and pushes them onto a stack.
Then remove them from the stack in the appropriate order.

Usually two lines instead of one.

http://webster.cs.washington.edu:8080/practiceit/

-- glen
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      10-06-2012
glen herrmannsfeldt schrieb:
>> 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?

> Write a loop that takes objects and pushes them onto a stack.
> Then remove them from the stack in the appropriate order.


The idea would of course be to have an iterator and not
do a copy of the LinkedHashMap. Copying the LinkedHashMap
could be a last resort, but for larger LinkedHashMaps and
frequent iteration this is not an option.

Bye

 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      10-06-2012
Jan Burse schrieb:
> glen herrmannsfeldt schrieb:
>>> 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?

>> Write a loop that takes objects and pushes them onto a stack.
>> Then remove them from the stack in the appropriate order.

>
> The idea would of course be to have an iterator and not
> do a copy of the LinkedHashMap. Copying the LinkedHashMap
> could be a last resort, but for larger LinkedHashMaps and
> frequent iteration this is not an option.
>
> Bye
>


On the other hand.

One could hold a parallel structure to the LinkedHashMap,
and already fill this parallel structure during put(). And
then use this parallel structure for the reverse iteration.

For example instead:

put(key, value);

One could do:

if (put(key, value)==null)
list.add(key);

And then use the list in reverse order to get a
keySet reverse iterator.

Bye
 
Reply With Quote
 
Robert Klemme
Guest
Posts: n/a
 
      10-06-2012
On 05.10.2012 20:05, Lew wrote:
> Robert Klemme wrote:
>> Lew wrote:
>>> Robert Klemme wrote:


>>> 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.


Lew, I'm sorry, but I think you're overly picky here.

>>> 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)."


Well, the entrySet() obtained for LHM does provide this guarantee. Even
though it's not explicitly stated in comments for methods entrySet(),
keySet() and values() because they are inherited the class level comment
makes it clear that the ordering observed during iteration will usually
be insertion order. I would conceded that the fact that you can also
have access order if invoking one specific constructor is a not made
explicit enough in the class JavaDoc.

> 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.


I think that clearly derives from the class comment because there is no
other way to iterate a Map than through the three dependent collections
(which usually include this comment in their accessor methods: "The
collection is backed by the map, so changes to the map are reflected in
the collection, and vice-versa.").

>>> 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.


And?

Regards

robert

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/
 
Reply With Quote
 
Jim Janney
Guest
Posts: n/a
 
      10-09-2012
Jan Burse <(E-Mail Removed)> writes:

> 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


You haven't overlooked anything. The ability is not there and I don't
see any simple way to add it without package access to java.util.
LinkedHashMap is a bit of an oddity in the collections framework, but
it's useful enough that I don't mind.

If I really needed that functionality I'd probably try maintaining my
own access-order list in parallel to the map.

--
Jim Janney
 
Reply With Quote
 
Jim Janney
Guest
Posts: n/a
 
      10-10-2012
Jim Janney <(E-Mail Removed)> writes:

> Jan Burse <(E-Mail Removed)> writes:
>
>> 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

>
> You haven't overlooked anything. The ability is not there and I don't
> see any simple way to add it without package access to java.util.
> LinkedHashMap is a bit of an oddity in the collections framework, but
> it's useful enough that I don't mind.
>
> If I really needed that functionality I'd probably try maintaining my
> own access-order list in parallel to the map.


Oops, stupid me. The other way is to define a comparator based on
insertion order, and then use a SortedMap.

--
Jim Janney
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      10-10-2012
On 10/10/2012 11:00 AM, Jim Janney wrote:
> Jim Janney <(E-Mail Removed)> writes:
>
>> Jan Burse <(E-Mail Removed)> writes:
>> [...]
>> If I really needed that functionality I'd probably try maintaining my
>> own access-order list in parallel to the map.

>
> Oops, stupid me. The other way is to define a comparator based on
> insertion order, and then use a SortedMap.


Defining the comparator might be something of a struggle,
especially if the same object instance could be referred to by
two different LinkedHashMaps.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: CLI Java Glitch Martin Gregorie Java 54 07-25-2011 11:25 AM
Re: CLI Java Glitch Stefan Ram Java 2 06-21-2011 07:43 AM
strange netbeans glitch not finding java classes gwlucas@sonalysts.com Java 4 06-11-2008 11:12 PM
Sorting collections based on nested collections Doug Poland Java 9 09-27-2003 10:46 PM
InnerProperty Persistance for Collections containing other Collections mutex ASP .Net Building Controls 0 07-27-2003 02:45 PM



Advertisments