Consider adding a Bidirectional Dictionary

[ianhays]

Last summer I looked into new collections to consider adding to .NET. I ultimately decided on adding the MultiValueDictionary, but a close contender was the bi-directional dictionary. Now that we have corefxlab and we're working in the open, I'd like to revisit the BiDictionary as a possible addition.

If I remember correctly, my basic implementation for a BiMap that I took to API review a year ago had two Dictionaries – one that maps from Key->Value and the other that maps Value->Key. Any time the BiMap is mutated, both internal dictionaries have to be updated. There was also a Property “Reverse” to get the Value->Key mapping such that you could do:

BiMap<int, string> map = new BiMap<int, string>();
Map[1] = “cat”;
BiMap<string, int> reverse = map.Reverse;
Assert.Equal(1, reverse[“cat”]);

Both “map” and “reverse” used the same internal store.

So moving forward we should look at the above as our “worst case” scenario. I think we can do something more clever.

The biggest design issue I'd like to get resolved is whether we should Implement IDictionary<TKey, Value> and IDictionary<TValue, TKey> or just the former.

@ReedKimble

[KrzysztofCwalina]

@ianhays, I don't think the compiler would let you implement IDictionary<TKey, Value> and IDictionary<TValue, TKey>. As there would be ambiguities when TKey and TValue were the same type.

[ReedKimble]

@KrzysztofCwalina we've already discussed using a small wrapper type around TKey/TValue to resolve the ambiguity problem. I am probably holding up this issue because Ian is waiting for me to post info about some of my previous attempts at this. I need to take the mock I have for an extended hashset and modify it to include the wrapper classes for the generic arguments. -EDIT- instead of editing the mockup I've gone ahead and posted a few different attempts which demonstrate some of the ideas.

[ReedKimble]

Here's some of what I've been experimenting with.

This first code block was the latest experiment, where I was using indexer collections into a single list of paired values. But after talking this over we determined that this wouldn't be more efficient than just having two internal dictionaries. But it does demonstrate the wrapper types for the generic arguments.

Public Class BijectiveSet(Of TLeft, TRight)
    'holds the hash value of left objects and the index of the pair in the core list
    Private leftHashIndexer As New Dictionary(Of Integer, Integer)
    'holds the hash value of right objects and the index of the pair in the core list
    Private rightHashIndexer As New Dictionary(Of Integer, Integer)
    'holds the pairs of left and right objects
    Private listCore As New List(Of Tuple(Of LeftValue, RightValue))
    'records empty indicies in the core list where items were removed from the set
    Private emptyIndicies As New Stack(Of Integer)

    'wraps the left type to prevent ambiguity when the left and right types are the same
    Public Class LeftValue
        Public Property Value As TLeft
        Public Sub New(left As TLeft)
            Value = left
        End Sub
    End Class

    'wraps the right type to prevent ambiguity when the left and right types are the same
    Public Class RightValue
        Public Property Value As TRight
        Public Sub New(right As TRight)
            Value = right
        End Sub
    End Class

    'provides a convienent empty tuple to use when releasing an entry in the core list due to removal
    'should this class be stubbed out and used to replace the tuple in the core list?
    Public Class BijectivePair
        Inherits Tuple(Of LeftValue, RightValue)
        Public Shared ReadOnly Empty As New BijectivePair
        Sub New()
            MyBase.New(Nothing, Nothing)
        End Sub
    End Class

    'records a bijective pair in the collection
    'since there is a distinct one-to-one relation on all items in the collection,
    '  we can blindly remove and replace items in the collection if they already exist
    Protected Sub UpdatePair(left As TLeft, right As TRight)
        Dim hashLeft = left.GetHashCode
        Dim hashRight = right.GetHashCode
        If leftHashIndexer.ContainsKey(hashLeft) Then
            SafeRemovePair(left)
        End If
        If rightHashIndexer.ContainsKey(hashRight) Then
            SafeRemovePair(right)
        End If
        Dim itemIndex As Integer
        If emptyIndicies.Count > 0 Then
            itemIndex = emptyIndicies.Pop
            listCore.Item(itemIndex) = New Tuple(Of LeftValue, RightValue)(New LeftValue(left), New RightValue(right))
        Else
            listCore.Add(New Tuple(Of LeftValue, RightValue)(New LeftValue(left), New RightValue(right)))
            itemIndex = listCore.Count - 1
        End If
        leftHashIndexer.Item(hashLeft) = itemIndex
        rightHashIndexer.Item(hashRight) = itemIndex
    End Sub

    'add overloads to access method with unwrapped type parameters
    'underlying method used by other overloads
    Public Function Remove(left As TLeft) As Boolean
        If leftHashIndexer.ContainsKey(left.GetHashCode) Then
            SafeRemovePair(left)
            Return True
        End If
        Return False
    End Function

    'add overloads to access method with unwrapped type parameters
    'underlying method used by other overloads
    Public Function Remove(right As TRight) As Boolean
        If rightHashIndexer.ContainsKey(right.GetHashCode) Then
            SafeRemovePair(right)
            Return True
        End If
        Return False
    End Function

    'removes a pair when the left item is known to exist
    Protected Sub SafeRemovePair(left As TLeft)
        Dim hashLeft = left.GetHashCode
        Dim itemIndex = leftHashIndexer(hashLeft)
        Dim hashRight = listCore(itemIndex).Item2.Value.GetHashCode
        listCore(itemIndex) = BijectivePair.Empty
        emptyIndicies.Push(itemIndex)
        leftHashIndexer.Remove(hashLeft)
        rightHashIndexer.Remove(hashRight)
    End Sub

    'removes a pair when the right item is known to exist
    Protected Sub SafeRemovePair(right As TRight)
        Dim hashRight = right.GetHashCode
        Dim itemIndex = rightHashIndexer(hashRight)
        Dim hashLeft = listCore(itemIndex).Item1.Value.GetHashCode
        listCore(itemIndex) = BijectivePair.Empty
        emptyIndicies.Push(itemIndex)
        leftHashIndexer.Remove(hashLeft)
        rightHashIndexer.Remove(hashRight)
    End Sub
End Class

'this partial class contains all of the method implementations for
'  IDictionary(Of LeftValue, RightValue) and IDictionary(Of RightValue, LeftValue)
'perhaps IDictionary is not the most appropriate interface to implement, but the
'  BijectiveSet does want to implement most of its functionality.
'the custom enumerator is not implemented in this example, but should be trival (if time consuming) to add
Partial Public Class BijectiveSet(Of TLeft, TRight)
    Implements IDictionary(Of LeftValue, RightValue)
    Implements IDictionary(Of RightValue, LeftValue)

    Public ReadOnly Property Count As Integer Implements ICollection(Of KeyValuePair(Of LeftValue, RightValue)).Count
        Get
            Return listCore.Count
        End Get
    End Property

    Public ReadOnly Property IsReadOnly As Boolean Implements ICollection(Of KeyValuePair(Of LeftValue, RightValue)).IsReadOnly
        Get
            Return False
        End Get
    End Property

    'add overloads to access Item property by unwrapped type
    Default Public Property Item(key As TRight) As TLeft
        Get
            Dim hash = key.GetHashCode
            If rightHashIndexer.ContainsKey(hash) Then
                Return listCore.Item(rightHashIndexer(hash)).Item1.Value
            End If
            Return Nothing
        End Get
        Set(value As TLeft)
            UpdatePair(value, key)
        End Set
    End Property
    Default Public Property Item(key As RightValue) As LeftValue Implements IDictionary(Of RightValue, LeftValue).Item
        Get
            Dim hash = key.Value.GetHashCode
            If rightHashIndexer.ContainsKey(hash) Then
                Return listCore.Item(rightHashIndexer(hash)).Item1
            End If
            Return Nothing
        End Get
        Set(value As LeftValue)
            UpdatePair(value.Value, key.Value)
        End Set
    End Property

    'add overloads to access Item property by unwrapped type
    Default Public Property Item(key As TLeft) As TRight
        Get
            Dim hash = key.GetHashCode
            If leftHashIndexer.ContainsKey(hash) Then
                Return listCore.Item(leftHashIndexer(hash)).Item2.Value
            End If
            Return Nothing
        End Get
        Set(value As TRight)
            UpdatePair(key, value)
        End Set
    End Property

    Default Public Property Item(key As LeftValue) As RightValue Implements IDictionary(Of LeftValue, RightValue).Item
        Get
            Dim hash = key.Value.GetHashCode
            If leftHashIndexer.ContainsKey(hash) Then
                Return listCore.Item(leftHashIndexer(hash)).Item2
            End If
            Return Nothing
        End Get
        Set(value As RightValue)
            UpdatePair(key.Value, value.Value)
        End Set
    End Property

    Public ReadOnly Property Keys As ICollection(Of LeftValue) Implements IDictionary(Of LeftValue, RightValue).Keys
        Get
            Return (From t In listCore Select t.Item1).ToArray
        End Get
    End Property

    Public ReadOnly Property Values As ICollection(Of RightValue) Implements IDictionary(Of LeftValue, RightValue).Values
        Get
            Return (From t In listCore Select t.Item2).ToArray
        End Get
    End Property

    Private ReadOnly Property ICollection_Count As Integer Implements ICollection(Of KeyValuePair(Of RightValue, LeftValue)).Count
        Get
            Return Count
        End Get
    End Property

    Private ReadOnly Property ICollection_IsReadOnly As Boolean Implements ICollection(Of KeyValuePair(Of RightValue, LeftValue)).IsReadOnly
        Get
            Return IsReadOnly
        End Get
    End Property

    Private ReadOnly Property IDictionary_Keys As ICollection(Of RightValue) Implements IDictionary(Of RightValue, LeftValue).Keys
        Get
            Return CType(Keys, ICollection(Of RightValue))
        End Get
    End Property

    Private ReadOnly Property IDictionary_Values As ICollection(Of LeftValue) Implements IDictionary(Of RightValue, LeftValue).Values
        Get
            Return CType(Values, ICollection(Of LeftValue))
        End Get
    End Property

    Public Sub Add(item As KeyValuePair(Of RightValue, LeftValue)) Implements ICollection(Of KeyValuePair(Of RightValue, LeftValue)).Add
        UpdatePair(item.Value.Value, item.Key.Value)
    End Sub

    Public Sub Add(item As KeyValuePair(Of LeftValue, RightValue)) Implements ICollection(Of KeyValuePair(Of LeftValue, RightValue)).Add
        UpdatePair(item.Key.Value, item.Value.Value)
    End Sub

    'add overloads to access method with unwrapped type parameters
    Public Sub Add(left As TLeft, right As TRight)
        UpdatePair(left, right)
    End Sub

    Public Sub Add(key As RightValue, value As LeftValue) Implements IDictionary(Of RightValue, LeftValue).Add
        UpdatePair(value.Value, key.Value)
    End Sub

    Public Sub Add(key As LeftValue, value As RightValue) Implements IDictionary(Of LeftValue, RightValue).Add
        UpdatePair(key.Value, value.Value)
    End Sub

    Public Sub Clear() Implements ICollection(Of KeyValuePair(Of LeftValue, RightValue)).Clear
        listCore.Clear()
        leftHashIndexer.Clear()
        rightHashIndexer.Clear()
    End Sub

    'could be implemented/lazy example
    Protected Sub CopyTo(array() As KeyValuePair(Of RightValue, LeftValue), arrayIndex As Integer) Implements ICollection(Of KeyValuePair(Of RightValue, LeftValue)).CopyTo
        Throw New NotImplementedException()
    End Sub

    Protected Sub CopyTo(array() As KeyValuePair(Of LeftValue, RightValue), arrayIndex As Integer) Implements ICollection(Of KeyValuePair(Of LeftValue, RightValue)).CopyTo
        Throw New NotImplementedException()
    End Sub

    Private Sub ICollection_Clear() Implements ICollection(Of KeyValuePair(Of RightValue, LeftValue)).Clear
        Clear()
    End Sub

    Public Function Contains(item As KeyValuePair(Of RightValue, LeftValue)) As Boolean Implements ICollection(Of KeyValuePair(Of RightValue, LeftValue)).Contains
        Return ContainsKey(item.Key) AndAlso ContainsKey(item.Value)
    End Function

    Public Function Contains(item As KeyValuePair(Of LeftValue, RightValue)) As Boolean Implements ICollection(Of KeyValuePair(Of LeftValue, RightValue)).Contains
        Return ContainsKey(item.Key) AndAlso ContainsKey(item.Value)
    End Function

    'add overloads to access method with unwrapped type parameter
    Public Function ContainsKey(key As TRight) As Boolean
        Return rightHashIndexer.ContainsKey(key.GetHashCode)
    End Function
    'add overloads to access method with unwrapped type parameter
    Public Function ContainsKey(key As TLeft) As Boolean
        Return leftHashIndexer.ContainsKey(key.GetHashCode)
    End Function

    Public Function ContainsKey(key As RightValue) As Boolean Implements IDictionary(Of RightValue, LeftValue).ContainsKey
        Return rightHashIndexer.ContainsKey(key.Value.GetHashCode)
    End Function

    Public Function ContainsKey(key As LeftValue) As Boolean Implements IDictionary(Of LeftValue, RightValue).ContainsKey
        Return leftHashIndexer.ContainsKey(key.Value.GetHashCode)
    End Function

    'could be implemented with custom enumerator/lazy example
    Public Function GetEnumerator() As IEnumerator(Of KeyValuePair(Of LeftValue, RightValue)) Implements IEnumerable(Of KeyValuePair(Of LeftValue, RightValue)).GetEnumerator
        Throw New NotImplementedException()
    End Function

    Public Function Remove(item As KeyValuePair(Of LeftValue, RightValue)) As Boolean Implements ICollection(Of KeyValuePair(Of LeftValue, RightValue)).Remove
        Return Remove(item.Key)
    End Function

    Public Function Remove(key As RightValue) As Boolean Implements IDictionary(Of RightValue, LeftValue).Remove
        Return Remove(key.Value)
    End Function

    Public Function Remove(item As KeyValuePair(Of RightValue, LeftValue)) As Boolean Implements ICollection(Of KeyValuePair(Of RightValue, LeftValue)).Remove
        Return Remove(item.Key)
    End Function

    Public Function Remove(key As LeftValue) As Boolean Implements IDictionary(Of LeftValue, RightValue).Remove
        Return Remove(key.Value)
    End Function

    Public Function TryGetValue(key As RightValue, ByRef value As LeftValue) As Boolean Implements IDictionary(Of RightValue, LeftValue).TryGetValue
        Dim hashRight = key.Value.GetHashCode
        If rightHashIndexer.ContainsKey(hashRight) Then
            value = listCore(rightHashIndexer(hashRight)).Item1
            Return True
        End If
        Return False
    End Function

    Public Function TryGetValue(key As LeftValue, ByRef value As RightValue) As Boolean Implements IDictionary(Of LeftValue, RightValue).TryGetValue
        Dim hashLeft = key.Value.GetHashCode
        If leftHashIndexer.ContainsKey(hashLeft) Then
            value = listCore(leftHashIndexer(hashLeft)).Item2
            Return True
        End If
        Return False
    End Function

    Private Function IEnumerable_GetEnumerator() As IEnumerator Implements IEnumerable.GetEnumerator
        Return GetEnumerator()
    End Function

    Private Function IEnumerable_GetEnumerator1() As IEnumerator(Of KeyValuePair(Of RightValue, LeftValue)) Implements IEnumerable(Of KeyValuePair(Of RightValue, LeftValue)).GetEnumerator
        Return CType(IEnumerable_GetEnumerator(), IEnumerator(Of KeyValuePair(Of RightValue, LeftValue)))
    End Function
End Class

Next, this was one of the attempts to take advantage of the internal workings of HastSet(Of T). In this attempt I used a custom interface instead of IDictionary, though I've tried a similar one with the wrappers and IDictionary implementations. The big drawback here is that using the internal IndexOf within HashSet makes the performance drop considerably as the collection gets larger.

Public Class BijectiveSet(Of TKeyLeft, TKeyRight)
    Implements IBijectiveSet(Of TKeyLeft, TKeyRight)

    Private leftHash As New HashSet(Of TKeyLeft)
    Private leftHashIndexAccessor As Func(Of TKeyLeft, Integer)
    Private rightHash As New HashSet(Of TKeyRight)
    Private rightHashIndexAccessor As Func(Of TKeyRight, Integer)

    Public Sub New()
        Dim info As System.Reflection.MethodInfo = leftHash.GetType.GetMethod("InternalIndexOf", Reflection.BindingFlags.Instance Or Reflection.BindingFlags.NonPublic)
        leftHashIndexAccessor = CType(info.CreateDelegate(GetType(Func(Of TKeyLeft, Integer)), leftHash), Func(Of TKeyLeft, Integer))
        info = rightHash.GetType.GetMethod("InternalIndexOf", Reflection.BindingFlags.Instance Or Reflection.BindingFlags.NonPublic)
        rightHashIndexAccessor = CType(info.CreateDelegate(GetType(Func(Of TKeyRight, Integer)), rightHash), Func(Of TKeyRight, Integer))
    End Sub

    Public Sub Add(left As TKeyLeft, right As TKeyRight) Implements IBijectiveSet(Of TKeyLeft, TKeyRight).Add
        leftHash.Add(left)
        rightHash.Add(right)
    End Sub

    Public Sub Clear() Implements IBijectiveSet(Of TKeyLeft, TKeyRight).Clear
        leftHash.Clear()
        rightHash.Clear()
    End Sub

    Public Function ContainsLeft(value As TKeyLeft) As Boolean Implements IBijectiveSet(Of TKeyLeft, TKeyRight).ContainsLeft
        Return leftHash.Contains(value)
    End Function

    Public Function ContainsRight(value As TKeyRight) As Boolean Implements IBijectiveSet(Of TKeyLeft, TKeyRight).ContainsRight
        Return rightHash.Contains(value)
    End Function

    Public ReadOnly Property Count As Integer Implements IBijectiveSet(Of TKeyLeft, TKeyRight).Count
        Get
            Return leftHash.Count
        End Get
    End Property

    Public Function GetEnumerator() As IEnumerator(Of Tuple(Of TKeyLeft, TKeyRight)) Implements IBijectiveSet(Of TKeyLeft, TKeyRight).GetEnumerator
        Return New Enumerator(Me)
    End Function

    Protected Function GetEnumeratorCore() As IEnumerator Implements IBijectiveSet(Of TKeyLeft, TKeyRight).GetEnumerator
        Return GetEnumerator()
    End Function

    Public Function GetEnumeratorLeft() As IEnumerator(Of TKeyLeft) Implements IBijectiveSet(Of TKeyLeft, TKeyRight).GetEnumeratorLeft
        Return leftHash.GetEnumerator
    End Function

    Public Function GetEnumeratorRight() As IEnumerator(Of TKeyRight) Implements IBijectiveSet(Of TKeyLeft, TKeyRight).GetEnumeratorRight
        Return rightHash.GetEnumerator
    End Function

    Public Function GetLeft(key As TKeyRight) As TKeyLeft Implements IBijectiveSet(Of TKeyLeft, TKeyRight).GetLeft
        If rightHash.Contains(key) Then
            Return ItemAtLeft(IndexOfRight(key))
        End If
        Throw New KeyNotFoundException
    End Function

    Public Function GetRight(key As TKeyLeft) As TKeyRight Implements IBijectiveSet(Of TKeyLeft, TKeyRight).GetRight
        If leftHash.Contains(key) Then
            Return ItemAtRight(IndexOfLeft(key))
        End If
        Throw New KeyNotFoundException
    End Function

    Public Function IndexOfLeft(value As TKeyLeft) As Integer Implements IBijectiveSet(Of TKeyLeft, TKeyRight).IndexOfLeft
        Return leftHashIndexAccessor(value)
    End Function

    Public Function IndexOfRight(value As TKeyRight) As Integer Implements IBijectiveSet(Of TKeyLeft, TKeyRight).IndexOfRight
        Return rightHashIndexAccessor(value)
    End Function

    Public Function ItemAtLeft(index As Integer) As TKeyLeft Implements IBijectiveSet(Of TKeyLeft, TKeyRight).ItemAtLeft
        Return leftHash(index)
    End Function

    Public Function ItemAtRight(index As Integer) As TKeyRight Implements IBijectiveSet(Of TKeyLeft, TKeyRight).ItemAtRight
        Return rightHash(index)
    End Function

    Public Function RemoveLeft(value As TKeyLeft) As Boolean Implements IBijectiveSet(Of TKeyLeft, TKeyRight).RemoveLeft
        If leftHash.Contains(value) Then
            rightHash.Remove(ItemAtRight(IndexOfLeft(value)))
            leftHash.Remove(value)
            leftHash.TrimExcess()
            rightHash.TrimExcess()
            Return True
        End If
        Return False
    End Function

    Public Function RemoveRight(value As TKeyRight) As Boolean Implements IBijectiveSet(Of TKeyLeft, TKeyRight).RemoveRight
        If rightHash.Contains(value) Then
            leftHash.Remove(ItemAtLeft(IndexOfRight(value)))
            rightHash.Remove(value)
            leftHash.TrimExcess()
            rightHash.TrimExcess()
            Return True
        End If
        Return False
    End Function

    Public Class Enumerator
        Implements IEnumerator(Of Tuple(Of TKeyLeft, TKeyRight))

        Protected core As BijectiveSet(Of TKeyLeft, TKeyRight)
        Protected keys As List(Of TKeyLeft)
        Protected index As Integer

        Protected Friend Sub New(bset As BijectiveSet(Of TKeyLeft, TKeyRight))
            core = bset
            keys = New List(Of TKeyLeft)(core.leftHash.ToArray)
            index = -1
        End Sub

        Public ReadOnly Property Current As Tuple(Of TKeyLeft, TKeyRight) Implements IEnumerator(Of Tuple(Of TKeyLeft, TKeyRight)).Current
            Get
                If index > -1 AndAlso index < core.leftHash.Count Then
                    Dim key As TKeyLeft = keys(index)
                    Return New Tuple(Of TKeyLeft, TKeyRight)(key, core.GetRight(key))
                End If
                Return Nothing
            End Get
        End Property

        Protected ReadOnly Property CurrentCore As Object Implements IEnumerator.Current
            Get
                Return Current
            End Get
        End Property

        Public Function MoveNext() As Boolean Implements IEnumerator.MoveNext
            index += 1
            Return index < core.leftHash.Count
        End Function

        Public Sub Reset() Implements IEnumerator.Reset
            index = -1
        End Sub

#Region "IDisposable Support"
        Private disposedValue As Boolean
        Protected Overridable Sub Dispose(disposing As Boolean)
            If Not Me.disposedValue Then
                If disposing Then
                    core = Nothing
                End If
            End If
            Me.disposedValue = True
        End Sub
        Public Sub Dispose() Implements IDisposable.Dispose
            Dispose(True)
            GC.SuppressFinalize(Me)
        End Sub
#End Region

    End Class
End Class

Public Interface IBijectiveSet(Of TKeyLeft, TKeyRight)
    Inherits IEnumerable(Of Tuple(Of TKeyLeft, TKeyRight))
    Sub Add(left As TKeyLeft, right As TKeyRight)
    Sub Clear()
    Function ContainsLeft(value As TKeyLeft) As Boolean
    Function ContainsRight(value As TKeyRight) As Boolean
    ReadOnly Property Count As Integer
    Function GetEnumeratorLeft() As IEnumerator(Of TKeyLeft)
    Function GetEnumeratorRight() As IEnumerator(Of TKeyRight)
    Function GetLeft(key As TKeyRight) As TKeyLeft
    Function GetRight(key As TKeyLeft) As TKeyRight
    Function IndexOfLeft(value As TKeyLeft) As Integer
    Function IndexOfRight(value As TKeyRight) As Integer
    Function ItemAtLeft(index As Integer) As TKeyLeft
    Function ItemAtRight(index As Integer) As TKeyRight
    Function RemoveLeft(value As TKeyLeft) As Boolean
    Function RemoveRight(value As TKeyRight) As Boolean
End Interface

So all of this (and more) has brought me full circle back to implementing a customized hashset. I tried this route about a year ago and at that time didn't have access to the clr source to actually add a class (could only view it in ReferenceSource). So I had to try building a class which reimplements hashset but then I ran into issues of needing to recode a lot of internal functionality. Now though it might be possible to revist the idea. Here's just a little bit of how I thought to approach this:

Public Class BijectiveDictionary(Of TKeyLeft, TKeyRight)

    Private Structure Entry
        Public hashCode As Integer
        Public nextIndex As Integer
        Public leftKey As TKeyLeft
        Public rightKey As TKeyRight
    End Structure

    Private buckets() As Integer
    Private entries() As Entry
    Private _count As Integer
    Private version As Integer
    Private freeList As Integer
    Private freeCount As Integer
    Private comparerLeft As IEqualityComparer(Of TKeyLeft)
    Private comparerRight As IEqualityComparer(Of TKeyRight)
    Private keysLeft As KeyLeftCollection
    Private keysRight As KeyRightCollection
    Private _syncRoot As Object

So the general idea is to have the internal Entry object hold references to both TLeft and TRight and then to add overloads of all methods to handle both left and right cases (this snippet doesnt have the wrapper types but they might be necessary).

Sorry this is all in VB but hopefully it helps demonstrate some of the thinking.

[ReedKimble]

Sorry, the Entry structure in that last example may need a second hashCode field; I forgot that I was also playing around (unsuccessfully) with an idea of trying to get custom equality comparers to return the same hash code for both the left and right object instances.

[ianhays]

I'm not sure that I understand the concept of the wrapper type. Could you explain it in more detail? Thinking again on the first example, I don't see how the compiler can distinguish between Remove(TLeft) and Remove(TRight) when typeof(TLeft) == typeof(TRight). When they are the same type, both removes should have the same signature.

In your partial implementation that fulfills the IDictionary interface you use explicit definitions for all functions which makes sense and is fine, but I don't see how the public Removes above work without ambiguity. The code I'm talking about:

    'add overloads to access method with unwrapped type parameters
    'underlying method used by other overloads
    Public Function Remove(left As TLeft) As Boolean
        If leftHashIndexer.ContainsKey(left.GetHashCode) Then
            SafeRemovePair(left)
            Return True
        End If
        Return False
    End Function

    'add overloads to access method with unwrapped type parameters
    'underlying method used by other overloads
    Public Function Remove(right As TRight) As Boolean
        If rightHashIndexer.ContainsKey(right.GetHashCode) Then
            SafeRemovePair(right)
            Return True
        End If
        Return False
    End Function

From an API perspective, for the second example I think a system where we can get the inverse dictionary would be more user-friendly than GetLeft, GetRight, AddLeft, AddRight, etc. That way we could keep the API as simple as possible while adding all of the necessary functionality (albeit through the inverse redirect).

If we did that, our API for the BiDictionary would be essentially one function on top of IDictionary:

    public class BiDictionary<TLeft, TRight> : IDictionary<TLeft, TRight>
    {
        #region new API surface area

        public BiDictionary<TRight, TLeft> Inverse { get; } // Changes to the inverse dictionary are reflected in the original BiDictionary.

        #endregion

        #region Implemented from IDictionary
        // For these functions the BiDictionary of TLeft, TRight is functionally equivalent to a Dictionary of TLeft, TRight with a few exceptions e.g. TRight values must be unique.
        #endregion
    }

The question of API is somewhat parallel to the question of implementation structure, but once we determine the best route for the former our options for the latter will likely narrow down. I'd be interested to see some perf results and memory usage stats for the methods above, particularly the hashset of Pair<TLeft, TRight>. I'd be worried that the extra layer of indirection would be bad for perf for Reference objects when compared to the double-dictionary approach particularly if wrapper objects were required.

Thanks for starting the conversation on this, Reed. The BiDictionary/BiMap is a fun structure :)

[ReedKimble]

You are correct; in the case where TLeft = TRight you cannot use the overloads which take the generic type parameters. In that case you must use the overloads which take the LeftValue/RightValue (wrapper type) parameters. Maybe the overloads which take the generic type parameter should be removed. The wrapper type can be extended to perform implicit conversions to/from the generic type so consumers could still pass the generic type parameter to an overload which takes the wrapper type when TLeft <> TRight. When TLeft = TRight then the explicit wrapper types would have to be used.

I expect the common usage scenario to have different types for TLeft and TRight, so maybe it is not a big deal if the usage is a little more cumbersome when the two types are the same.

I posted everything just to show the various ideas I've experimented with, but I think you are right that the hashset of pair would only offer potential savings with large value types. In most cases with small value types or reference types it would be disadvantageous.

I also don't like the Left/Right-specific members and would prefer to keep the API simple. While it does deal with the ambiguity problem it doesn't make for a clean class layout.

I understand the ease of implementation offered by BiDictionary<TRight, TLeft> Inverse, however, I'm not sure about ease of use... in a situation where you are constantly accessing both sides of the collection you would probably end up holding a reference to the inverse dictionary so you'd still have two collections to work with. From a look-up standpoint this isn't really any better than just having two dictionaries, though from an update standpoint you would still have the advantage of only needing to update one collection and the changes would be reflected in the other.

What do you think about the last idea, where we recreate HashSet with extended functionality to hold two objects?

[ianhays]

in a situation where you are constantly accessing both sides of the collection you would probably end up holding a reference to the inverse dictionary so you'd still have two collections to work with.

Yeah, this would likely be the case. Having to do biDictionary.Inverse every time would get old fast, but having to do biDictionary.AddLeft etc. would be equally annoying. For cases when TLeft != TRight, having the compiler determine which side to use would definitely be the most friendly.

I suppose we could always special case the situation where TLeft == TRight.... not sure if there's precedent for that anywhere else in the framework. That's sort of what you mentioned in the first part of your comment, though I think exposing the wrapper types would be more hassle than just forcing use of AddRight, AddLeft, etc. when TLeft == TRight. But then the API gets very large very fast...

From a look-up standpoint this isn't really any better than just having two dictionaries, though from an update standpoint you would still have the advantage of only needing to update one collection and the changes would be reflected in the other.

This is what the MultiValueDictionary ended up being: a wrapper around an existing collection that simplifies special-case usage. While I do think that has value for the MVD, I'm not sure that it has enough value - particularly for the BiDictionary.

What do you think about the last idea, where we recreate HashSet with extended functionality to hold two objects?

I'm probably being pedantic here, but I don't think looking at HashSet as a starting point would be as productive as looking at Dictionary as a starting point. Dictionary is already a HashSet with extended functionality to hold two objects: we just need to add some extra methods and another Buckets array to make it capable for bidirectional access.

HashSet{T}:

        internal struct Slot
        {
            internal int hashCode;      // Lower 31 bits of hash code, -1 if unused
            internal int next;          // Index of next entry, -1 if last
            internal T value;
        }

        private int[] _buckets;
        private Slot[] _slots;
        private int _count;
        private int _lastIndex;
        private int _freeList;
        private IEqualityComparer<T> _comparer;
        private int _version;

Dictionary{TKey, TValue}:

    private struct Entry {
            public int hashCode;    // Lower 31 bits of hash code, -1 if unused
            public int next;        // Index of next entry, -1 if last
            public TKey key;           // Key of entry
            public TValue value;         // Value of entry
        }

        private int[] buckets;
        private Entry[] entries;
        private int count;
        private int version;
        private int freeList;
        private int freeCount;
        private IEqualityComparer<TKey> comparer;
        private KeyCollection keys;
        private ValueCollection values;

BiDictionary{Tleft, TRight}:

    private struct Entry {
            public int hashCode;    // Lower 31 bits of hash code, -1 if unused
            public int next;        // Index of next entry, -1 if last
            public Tleft key;           // left entry
            public TRight value;         // Right entry
        }

        private int[] leftbuckets;
        private int[] rightBuckets;
        private Entry[] entries;
        private int count;
        private int version;
        private int freeList;
        private int freeCount;
        private IEqualityComparer<TLeft> leftcomparer;
        private IEqualityComparer<TRight> rightcomparer;
        private KeyLeftCollection leftkeys;
        private KeyRightCollection rightkeys;

I think that's probably what you meant anyways, but better to be sure :)

So anyways, back to the recreation. What does is give us? How is it better than two Inverse Dictionaries? Off the top of my head:

Pros:

• Only one Entries array instead of two
• Only one copy of _count, _version, _freelist, and _freecount
• One less layer of indirection to the underlying Entries list since we don't have to go through a private Dictionary reference to get to it.

Cons:

• More complicated of an implementation
• Lots of copied code from Dictionary. Any future Dictionary modifications will need to manually copied to the BiDictionary. This probably isn't a big deal.

I can't think of any other major cons. Do you have anything else to add to this list? For very large BiDictionaries, only having one Entries array could be a worthwhile memory savings.

[ReedKimble]

I suppose we could always special case the situation where TLeft == TRight.... not sure if there's precedent for that anywhere else in the framework

I wondered about precedent as well and couldn't really think of any; that's why I'm not sure if those overloads should exist or not.

...I think exposing the wrapper types would be more hassle than just forcing use of AddRight, AddLeft, etc. when TLeft == TRight.

That's the argument I've been having with myself all along lol. The Left/Right-specific members are less hassle in the long run if the wrapper types have to be explicitly created... its definitely best when the wrappers can be abstracted away from the consumer.

Though I suppose we could make it easier to use the wrappers by offering simple methods like MakeLeft(value As TLeft) As LeftValue so that consumers can just call instance.MakeLeft(x) when they need a wrapped value. Just talking about it, I think I like that idea better than AddRight/AddLeft/etc.

I think that's probably what you meant anyways, but better to be sure :)

Yup, that's what I meant. :) I used HashSet as the lowest common denominator but you're right that it's really more of a modification of Dictionary.

I think you hit the Pros/Cons list quite well. I can't really think of anything to add. The single Entries array is the critical performance piece and the complicated implementation is the only real con (I also doubt that potential future changes to Dictionary would cause difficulty).

So I think we have a direction from a code-implementation point of view, now we just have to hammer down the actual API structure.

[ianhays]

So I think we have a direction from a code-implementation point of view, now we just have to hammer down the actual API structure.

Agreed. That's the fun part :)

I wondered about precedent as well and couldn't really think of any; that's why I'm not sure if those overloads should exist or not.

Though I suppose we could make it easier to use the wrappers by offering simple methods like MakeLeft(value As TLeft) As LeftValue so that consumers can just call instance.MakeLeft(x) when they need a wrapped value. Just talking about it, I think I like that idea better than AddRight/AddLeft/etc.

So to Add you would do

biDictionary<T, T>;
T leftThingToAdd, rightRightToAdd
biDictionary.Add(biDictionary.MakeLeft(leftThingToAdd), biDictionary.MakeRight(rightThingToAdd));

Or I suppose you could circumvent the necessity for the wrapper on one side by making the internal structure akin to a Dictionary<TLeft, TRightWrapper>, but that could get potentially very confusing. That would then look like:

biDictionary<T, T>;
T leftThingToAdd, rightRightToAdd
biDictionary.Add(leftThingToAdd, biDictionary.MakeRight(rightThingToAdd));

Personally I don't like either of the above. I would rather just be able to do:

biDictionary<T, T>;
T leftThingToAdd, rightRightToAdd
biDictionary.AddByLeft(leftThingToAdd, rightThingToAdd);

or

biDictionary<T, T>;
T leftThingToAdd, rightRightToAdd
biDictionary.Add(leftThingToAdd, rightThingToAdd); //OR: biDictionary.Inverse.Add(rightThingToAdd, leftThingToAdd);

[ReedKimble]

So to Add you would do
biDictionary<T, T>;
T leftThingToAdd, rightRightToAdd
biDictionary.Add(biDictionary.MakeLeft(leftThingToAdd), biDictionary.MakeRight(rightThingToAdd

Yes, that is what I was getting at. However, you wouldn't have to explicitly provide both parameters that way; as soon as you do the first one the signature is narrowed down and the second parameter type can be implied/auto-cast. Assuming of course that there are no overloads which take TLeft/TRight directly (that is, only the wrapper types are used in parameters).

I guess it really comes down to whether or not we are going to implement the IDictionary interface(s). If we do, then the wrapper types are necessary, if we don't then AddByLeft/AddByRight would be fine (if we agree that the extra members on the class are better than having to create the wrapper instances).

I think the reason I favor the wrappers is because they only have to be manually used in the situation where TLeft == TRight. Whenever that is not the case, the wrappers can be completely abstracted through type conversion defined on LeftValue and RightValue.

I kind of like the implication of providing the Inverse wrapper just to house the members that deal with inverted parameters (there'd still just be the one core BiDictionary underneath) but that would preclude implementing IDictionary<TRight, TLeft> as all of the "Right" members would be in the Inverse wrapper.

[ianhays]

Sorry for the delay in response, I just got back from vacation.

I guess it really comes down to whether or not we are going to implement the IDictionary interface(s). If we do, then the wrapper types are necessary

My issue with this is that we would have to implement the IDictionary interfaces for the wrapper types, not the actual types. And I don't imagine this has much value since you can't pass it around as a Dictionary< type, type> which is the whole point of implementating the IDictionary< type, type> interface.

(if we agree that the extra members on the class are better than having to create the wrapper instances).

I think so, yes.

[ianhays]

I kind of like the implication of providing the Inverse wrapper just to house the members that deal with inverted parameters (there'd still just be the one core BiDictionary underneath) but that would preclude implementing IDictionary as all of the "Right" members would be in the Inverse wrapper.

Well the inverse wrapper would implement IDictionary< TRight>, but the primary BiDictionary would only implement IDictionary< TLeft>. I envisioned them both being full Dictionaries but with the same underlying information.

[ReedKimble]

Hi Ian, sorry I dropped on the face on the Earth on this. But I think we reached a consensus on the design. What should be our next step?

[ianhays]

I'm not sure exactly what the API review process is like for corefxlab. In CoreFX the process is strictly documented, but corefxlab may be less restrictive since it is more of a work-in-progress repo.

This is what I imagine it will look like:

1. It would probably be the most helpful to start with an initial implementation submitted as a PR to CoreFXLab. That way we can get some more feedback on the real result and refine our best-case API and implementation.
2. Next up we'll want to make a formal API proposal and submit it to CoreFX as an issue. The System.Buffers issue is a perfect example of what we'll want this to look like since that also came from Corefxlab and was merged into the main CoreFX repo. We'll no doubt get significantly more feedback in this stage.
3. Go through API reviews and further refine the prototype
4. Submit the implementation to CoreFX as a Pull Request.
5. After more feedback, merge in the BiDictionary.