Why does TreeSet not implement SCG.ISet?

[NightOwl888]

Seems reasonable to expect a "Set" to implement System.Collections.Generic.ISet, especially since the TreeSet in Java does just that. Is there any particular reason why that was left out?

[sestoft]

On 6Nov16 10:23, "Shad Storhaug" <notifications@github.commailto:notifications@github.com> wrote:

Seems reasonable to expect a "Set" to implement System.Collections.Generic.ISet, especially since the TreeSet in Java does just that. Is there any particular reason why that was left out?

First, most of the ISet operations can be found on ICollection, which is implemented by the C5 TreeSet and HashSet operations. The C5 tech report http://www.itu.dk/research/c5/latest/ITU-TR-2006-76.pdf explains how both destructive and functional set implementations can be based on TreeSet and HashSet. Second, the ISet operation names (eg UnionWith) are more appropriate for immutable set operations than the destructive ones (eg AddAll) implemented by the C5 sets. Third, the ISet interface was added to .NET long after C5 was designed.

But, agreed, it would make complete sense to redesign the C5 interfaces and classes in the light of the last decade of .NET developments (such as extension methods). Mikkel Riise Lund's MSc thesis (https://www.itu.dk/research/c5/MikkelRiiseLund-C6-20160601.pdf) is a step in that direction.

However, scalable support for concurrency is even more interesting, and presents many challenges both from a research and interface design perspective.

Peter

[NightOwl888]

This was never about functionality, as the collections function and perform well enough for our requirements. The problem is API compatibility. If I specify an API should accept ISet<T>, the end user should be able to use either System.Collections.Generic.HashSet<T> or C5.TreeSet<T>. But without the interface implementation, users have to resort to creating a facade just to get it to work with C5.

I started putting together a PR for this, and the implementation of ISet<T> on TreeSet<T> went off without a hitch.

But we also need IDictionary<TKey, TValue> on all of C5's dictionaries as well (namely TreeDictionary<K, V> and HashDictionary<K, V>), see LUCENENET-612. This is where there is a problem: IDictionary<TKey, TValue> inherits IEnumerable<SCG.KeyValuePair<TKey, TValue>>, meaning if it is put onto the existing dictionaries we effectively get:

TreeDictionary<K, V> : IEnumerable<C5.KeyValuePair<K, V>>, IEnumerable<SCG.KeyValuePair<K, V>>

And that makes extension methods (such as LINQ) break down since it doesn't know which one it should iterate by default. According to Eric Lippert, this should be avoided at all cost.

I took a look at the C5.KeyValuePair<K, V> and it seems the only reasons for its existence are:

1. Custom GetHashCode() implementation
2. Custom ToString(string, IFormatProvider) implementation

Since the ToString() overload doesn't exist on SCG.IDictionary<TKey, TValue>, there is no reason why an extension method cannot be used for this. So, unless there is some semantic meaning to the GetHashCode() values it seems like we should be able to switch the implementation to use SCG.IDictionary<TKey, TValue>, which solves the above issue. What are your thoughts on this?

Failing that, the options are:

1. Create facade collections to implement SCG.IDictionary<TKey, TValue> in C5
2. Create a collection library with facade collections that implement SCG.IDictionary<TKey, TValue> and depends on C5
3. Create a collection library with real dictionaries by cannibalizing C5 with no dependencies

We are seriously considering option 2 because we have additional collections that aren't in C5 and want to try (as much as possible) to create a "one stop shop" for people to select them. There are a small number of collections and some extension methods and collection utilities that we would like to move to a more general collection library (such as implementations of Equals(), GetHashCode(), and ToString() that work on all collection types the same way they do in Java). What are your thoughts on making C5 into that collection library?

We really want to take a dependency on C5 rather than maintain copies of or facade wrappers for your collections. But given the fact that the SCG interfaces aren't implemented, and your recent beta has dropped support for .NET Framework 4.5.0 and .NET Standard 1.6 we are at an impasse. You have gone from not having any support for .NET Standard, to fully supporting the frameworks (but not the interfaces) we need, to dropping them in less time than it has taken us to get out of beta. But lack of API compatibility with C5 is one of the reasons why we are still in beta.

[ondfisk]

Given your input, we have chosen to get rid of the custom KeyValuePair implementation.
The latest master should reflect that.
We will happily accept a PR with an ISet implementation for HashSet and TreeSet.