Java Collections – Why Set Implements Iterable but SortedMap Does Not

collectionsiteratorjava

There are two aspects to this question that I felt were too closely related to ask as separate questions.

Why doesn't SortedMap implement Iterable<Map.Entry<K,V>>?

If you need to perform an action on every key-value pair in a map, iterating over the entrySet() seems like the way to go. So why not provide a direct iterator() method on SortedMap? Unless you are worried about iteration order being inconsistent in a HashMap. Which leads me to:

Does implementing Iterable imply a stable ordering?

Iterating over an ordered collection (List, SortedMap, SortedSet) is a great way to reliably implement equals() (see Note 1) and do other things that have to produce the same result every time. Iterating over an unsorted set or map could yield different ordering if you call it multiple times, so is unsuitable for these purposes. Especially if you are comparing HashSets or HashMaps – two of them could contain the same objects, but the order of their iterators would be different.

I guess there are 2 aspects to those questions:

What are the historical reasons for these design decisions?
If doing it again today, are there correct answers to these questions? Maybe OrderedIterable should extend Iterable to guarantee order?

Notes:

I had originally suggested that you needed a reliable ordering to implement hashCode(), but if you sum all the hashcodes, it turns out that you don't need a reliable ordering if your hashing algorithm is commutative. Addition is commonly used for hashCodes and it is commutative: a + b = b + a and B. even with overflow, addition is still commutative so that a + Integer.MAX_VALUE = Integer.MAX_VALUE + a. You do still need a reliable ordering to implement equals() so that you can compare the first item of one to the first item of the other, etc.

P.S.

This question is about the interfaces Iterable, Set, SortedSet, Map, and SortedMap. It's fine to bring up other interfaces as examples, but
I do not think the Collection interface is relevant to this question. It's quirky and has the potential to be a distraction.

Best Answer

Although it is correct from a narrowly technical point of view to say that Set implements Iterable, but SortedMap does not, it is not a very useful question to ask. A more useful question to ask is whether both classes offer the Iterable interface, and they certainly both do.

As you know, there are three ways to offer an interface:

By explicitly implementing it using the implements keyword.
By implementing an interface which extends the interface in question.
By exposing a function which returns the interface in question.

Set is declared as follows: public interface Set<E> extends Collection<E> {... so, as you can see, Set does not directly implement Iterable, it only implements it indirectly, by virtue of implementing Collection, which extends Iterable.

Now, SortedMap would also be implementing Iterable indirectly, just as Set does, if it was implementing Collection, but it does not even do that. Instead, it exposes an entrySet() function, which returns a Collection, which extends Iterable.

So, you can have your much desired Iterable in both cases.

If you would like to insist on the narrowly technical question of why Set (indirectly) implements Iterable, but SortedMap offers it via a function instead, the answer is that the designers of the java language runtime made the decision a long time ago to refrain from making extensive use of interfaces extending other interfaces. That's why Map<K,V> does not extend Collection<Map.Entry<K,V>>, offering an entrySet() method instead.

They could have done the opposite, and as a matter of fact the designers of the C# language runtime did choose to go the other way, so IDictionary<K,V> extends ICollection<KeyValuePair<K,V>>.

I have experimented with both ways, and I still have not arrived at a conclusive decision as to which one is better. They simply appear to be two different ways of accomplishing the same thing.

The implementation of Iterator does not imply a stable ordering, as you seem to understand (and therefore it is not clear to me where your question is in that respect.) You may iterate over an unsorted map, in which case nobody can tell what the order of the items will be, and you may insert an element to the map and re-iterate, in which case the order of the items may be completely different from the previous time. (Not just different by one item: all items may appear to be re-arranged.)

There is no need for an OrderedIterable interface because its signature would be identical to Iterable. (And don't get me started on the choice of the java people to introduce a Set besides Collection.) You can just invoke OrderedMap.entrySet(), which the documentation promises will return an ordered set, which means that the Iterator of that set will always yield items in order.

Related Solutions

Java – A design decision in composition or aggregation

There's a lot to say here.

Inventory's api looks like a value object (since it has no identity, on its own, I suppose that it belongs to a Player). If so, it should be immutable, returning a new instance each time you add or remove an Item.
Your Item class looks like a shared identifier, thus it should override equals and hashcode and (strictly speaking, in DDD term) it should not hold any reference to the icon since it's not useful for its own invariants. You should use a domain service that take the Item and provide the proper icon instead (probably wrapping a statically defined Hashtable). However, be pragmatic with this: if you measure actual performance issues with such (formally correct) approach, keep the field there.
The Slot, as it stands, cannot be considered a domain object, because it does not implement equality in a domain relevant way (it ignores the quantity). This is perfecly correct for a private class internally used by the Inventory, but should not be exposed to clients (as in the second Inventory's implementation of the first solution you proposed). This because the clients could compare for equality two Slots from two different players, obtaining unreliable results.
To get rid of most boilerplate code, I would code
- a supporting functor interface like ItemQuantityChanger (below)
- a "functional" immutable collection, say ItemsSet, with a metod of signature ItemsSet set(Item item, ItemQuantityChanger transformation) that iterates over a simple array for the item to change. Such method would always create a new ItemsSet to return, without the Item (if the trasformation returns zero), with a new Item if the item is not found (with the quantity returned by applying the transformation to zero) or simply with the previous item coupled with the result of the trasformation.

However, concretely, I would just use an ImmutableList.Builder, since the functional design described in 4 adds few value in this case. A single if, in a method, is not that huge smell.

public interface ItemQuantityChanger {
   /**
    * Accept the current quantity of an Item and return the new one.
    */
   int applyTo(int currentQuantity);
}

Design .NET – Why SortedDictionary Does Not Implement IReadOnlyDictionary

Looking at MSDN today, one can see that the MSDN documentation page for SortedDictionary<TKey, TValue>, SortedDictionary<TKey, TValue> does implement IReadOnlyDictionary<TKey, TValue>.

According to the internet archive, that was not the case on November 14th, 2013.

Given that information, it is likely that it was simply an oversight from Microsoft, fixed in a recent .NET point update.

Best Answer

Related Solutions

Java – A design decision in composition or aggregation

Design .NET – Why SortedDictionary Does Not Implement IReadOnlyDictionary

Related Topic