API Proposal: Add ImmutableHashSet<T>.Builder.TryGetValue

[GeorgeAlexandria]

Hi,

what's about adding to the System.Collections.Immutable.ImmutableHashSet<T>.Builder and System.Collections.Immutable.ImmutableSortedSet<T>.Builder a method bool TryGetValue(T equalValue, out T actualValue);?

Rationale and Usage

A main goals for it is that you may avoid redundant object allocations and performance issues in the cases when you have a custom IEqualityComparer<T> and, for example, try to remove a actual value if it equals existing value or something else:

// It doesn't matter how EqualityComparer will compares items
private class CustomEqualityComparer : IEqualityComparer<int>
{
    private CustomEqualityComparer()
    {
    }

    public static CustomEqualityComparer Instance = new CustomEqualityComparer();

    public bool Equals(int x, int y) => x >> 1 == y >> 1;

    public int GetHashCode(int obj) => (obj >> 1).GetHashCode();
}

...

var hashSet = ImmutableHashSet.CreateRange(CustomEqualityComparer.Instance, new[] { 1, 2, 3, 4, 5, 6 });
foreach (var item in new[] { 1, 3, 6 })
{
    if (hashSet.TryGetValue(item, out var existingItem))
    {
        // Here we now that items are equal by our equality comparer 
        // but we want to determine if are equals by other criteria, and if so, remove them
        if (item == existingItem)
        {
            // Remove will allocates a new ImmutableHashSet each time
            hashSet = hashSet.Remove(existingItem); 
        }
        else
        {
            // do something else
        }
    }
}

To avoid redundant object allocations in the example above, we can use a relevant builder, but we will search an items in the full set, when we have a less actual set. It may have a performance issues when th set is large and GetHashCode with Equals for items are expensive:

...

var builder = hashSet.ToBuilder();
foreach (var item in new[] { 1, 3, 6 })
{
    // Here we always try to find an item in the original set
    if (hashSet.TryGetValue(item, out var existingItem))
    {
        if (item == existingItem)
        {
            // avoid allocation a new ImmutableHashSet
            builder.Remove(existingItem); 
        }
        else
        {
            // do something else
        }
    }
}
hashSet = builder.ToImmutable();

With proposed changes we can get items from the actual state of set:

var builder = hashSet.ToBuilder();
foreach (var item in new[] { 1, 3, 6 })
{
    // Try to find item in a actual state of set
    if (builder.TryGetValue(item, out var existingItem))
    {
        if (item == existingItem)
        {
            // avoid allocation a new ImmutableHashSet
            builder.Remove(existingItem); 
        }
        else
        {
            // do something else
        }
    }
}
hashSet = builder.ToImmutable();

Proposed API

public sealed class ImmutableHashSet<T> ...
{
    ...
    public sealed class Builder ...
    {
+      public bool TryGetValue(T equalValue, out T actualValue);
    }
}

public sealed class ImmutableSortedSet<T> ...
{
    ...
    public sealed class Builder ...
    {
+      public bool TryGetValue(T equalValue, out T actualValue);
    }
}

Implementation

I guess that implementation of Builder.TryGetValue must be the same as the TryGetValue from the corresponding immutable set

Any suggestion would be grateful.

[safern]

Hello @GeorgeAlexandria thanks for your detailed proposal. This makes sense to me, would you mind structuring the issue description so that it is easier for our API Review folks to do the review? Here are the guidelines for API proposals: https://github.com/dotnet/corefx/blob/master/Documentation/project-docs/api-review-process.md

Also here is an example on the format it should follow: https://github.com/dotnet/corefx/issues/35938

Thanks 😄

[GeorgeAlexandria]

Hello @safern and thanks for you suggestions. Issue was updated and I'm hope that now it's more structured and easy to reviewed.

[safern]

Thanks @GeorgeAlexandria, I marked it as api-ready-for-review so that the API Review crew reviews this.

[terrajobst]

Video

Looks good as proposed.

However, we should review the API surface of all immutable types and make sure that the API surface of the builder is logically equivalent.

@GeorgeAlexandria / @safern would one of you be willing to do that?

namespace System.Collections.Immutable
{
    public partial class ImmutableHashSet<T>
    {
        public partial class Builder
        {
            public bool TryGetValue(T equalValue, out T actualValue);
        }
    }

    public partial class ImmutableSortedSet<T>
    {
        public partial class Builder
        {
            public bool TryGetValue(T equalValue, out T actualValue);
        }
    }
}

[GeorgeAlexandria]

@GeorgeAlexandria / @safern would one of you be willing to do that?

Did you mean to append proposed api or to review all immutable types and their builders api?

[reflectronic]

I ran a diff between the API of each immutable collection and its builder & proposed some mostly appropriate fixes #822