8
\$\begingroup\$

The management of bidirectional mappings is a reoccuring topic. I took the time to write an (hopefully) efficient implementation.

using System;
using System.Collections;
using System.Collections.Generic;

namespace buka_core.misc
{
    /// <summary>
    /// 
    /// File Bijection.cs
    /// 
    /// Provides an implementation of a discrete bijective mapping
    /// 
    /// The inverses are created using shallow copies of the underlying datastructures, which leads to
    /// the original object and all its derived inverses being modified if one object changes. For this
    /// reason the class implements the interface ICloneable which allows the user to create deep copies
    /// 
    /// The class also implements the interface IDictionary which provides easy access to the proto-
    /// type
    /// 
    /// </summary>
    /// <typeparam name="T_Proto">Datatype of keys for the prototype</typeparam>
    /// <typeparam name="T_Inv">Datatype of keys for its inverse</typeparam>
    public class Bijection<T_Proto, T_Inv> : ICloneable, IDictionary<T_Proto, T_Inv>
    {
        /// <summary>
        /// Creates an empty discrete bijective mapping
        /// </summary>
        public Bijection()
        {

        }

        /// <summary>
        /// Used internally to efficiently generate inverses
        /// </summary>
        /// <param name="proto">The prototype mapping</param>
        /// <param name="inverse">Its inverse mapping</param>
        private Bijection(IDictionary<T_Proto, T_Inv> proto, IDictionary<T_Inv, T_Proto> inverse)
        {
            _Proto = proto;
            _Inv = inverse;
        }

        /// <summary>
        /// Indexer to insert and modify records
        /// </summary>
        /// <param name="key">Object for which the corresponding dictionary entry should be returned</param>
        /// <returns>The value that key maps to</returns>
        public T_Inv this[T_Proto key]
        {
            get
            {
                if (!_Proto.ContainsKey(key))
                {
                    throw new KeyNotFoundException("[Bijection] The key " + key + " could not be found");
                }

                return _Proto[key];
            }
            set
            {
                this.Add(key, value);
            }
        }

        /// <summary>
        /// Returns a bijection for which keys and values are reversed
        /// </summary>
        public Bijection<T_Inv, T_Proto> Inverse
        {
            get
            {
                if (null == _inverse)
                {
                    _inverse = new Bijection<T_Inv, T_Proto>(_Inv, _Proto);
                }

                return _inverse;
            }
        }
        private Bijection<T_Inv, T_Proto> _inverse = null;                  // Backer for lazy initialisation of Inverse

        /// <summary>
        /// Prototype mapping
        /// </summary>
        private IDictionary<T_Proto, T_Inv> _Proto
        {
            get
            {
                if (null == _proto)
                {
                    _proto = new SortedDictionary<T_Proto, T_Inv>();
                }

                return _proto;
            }
            /* private */
            set
            {
                _proto = value;
            }
        }
        private IDictionary<T_Proto, T_Inv> _proto = null;                  // Backer for lazy initialisation of _Proto

        /// <summary>
        /// Inverse prototype mapping
        /// </summary>
        private IDictionary<T_Inv, T_Proto> _Inv
        {
            get
            {
                if (null == _inv)
                {
                    _inv = new SortedDictionary<T_Inv, T_Proto>();
                }

                return _inv;
            }
            /* private */
            set
            {
                _inv = value;
            }
        }
        private IDictionary<T_Inv, T_Proto> _inv = null;                    // Backer for lazy initialisation of _Inv

        #region Implementation of ICloneable
        /// <summary>
        /// Creates a deep copy
        /// </summary>
        public object Clone()
        {
            return new Bijection<T_Proto, T_Inv>(
                new SortedDictionary<T_Proto, T_Inv>(_Proto),
                new SortedDictionary<T_Inv, T_Proto>(_Inv)
                );
        }
        #endregion

        #region Implementation of IDictionary<T_Proto, T_Inv>
        public ICollection<T_Proto> Keys => _Proto.Keys;
        public ICollection<T_Inv> Values => _Proto.Values;
        public int Count => _Proto.Count;
        public bool IsReadOnly => _Proto.IsReadOnly;

        public bool Contains(KeyValuePair<T_Proto, T_Inv> item)
        {
            return _Proto.Contains(item);
        }

        public bool ContainsKey(T_Proto key)
        {
            return _Proto.ContainsKey(key);
        }

        public void Clear()
        {
            _Proto.Clear();
            _Inv.Clear();
        }

        public void Add(T_Proto key, T_Inv value)
        {
            if (_Proto.ContainsKey(key))
            {
                _Inv.Remove(_Proto[key]);
            }

            if (_Inv.ContainsKey(value))
            {
                throw new ArgumentException("[Bijection] The inverse already maps " + value + " to " + _Inv[value]);
            }

            _Proto.Add(key, value);
            _Inv.Add(value, key);
        }
        public void Add(KeyValuePair<T_Proto, T_Inv> item)
        {
            this.Add(item.Key, item.Value);
        }

        public bool Remove(T_Proto key)
        {
            if (_Proto.ContainsKey(key))
            {
                bool removed_inv = _Inv.Remove(_Proto[key]);
                bool removed_proto = _Proto.Remove(key);

                return (removed_proto && removed_inv);              // == true
            }
            else
            {
                return false;
            }
        }
        public bool Remove(KeyValuePair<T_Proto, T_Inv> item)
        {
            return this.Remove(item.Key);
        }

        public bool TryGetValue(T_Proto key, out T_Inv value)
        {
            return _Proto.TryGetValue(key, out value);
        }

        public void CopyTo(KeyValuePair<T_Proto, T_Inv>[] array, int arrayIndex)
        {
            _Proto.CopyTo(array, arrayIndex);
        }

        public IEnumerator<KeyValuePair<T_Proto, T_Inv>> GetEnumerator()
        {
            return _Proto.GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return _Proto.GetEnumerator();
        }
        #endregion

        #region Overrides
        public override bool Equals(object obj)
        {
            Bijection<T_Proto, T_Inv> obj_bijection = (obj as Bijection<T_Proto, T_Inv>); if (null == obj) return false;

            if (this.Count != obj_bijection.Count) return false;
            if (!_Proto.Equals(obj_bijection._Proto)) return false;
            if (!_Inv.Equals(obj_bijection._Inv)) return false;

            return true;
        }

        public override int GetHashCode()
        {
            return _Proto.GetHashCode();
        }

        public override string ToString()
        {
            return _Proto.ToString();
        }
        #endregion
    }
}

Instances would be used as follows

Bijection<int, string> b = new Bijection<int, string>();

b[1] = "frog";
b[2] = "fish";
b[3] = "dog";
b[5] = "cat";
b[8] = "snake";
b[13] = "crocodile";

Console.WriteLine(b.Inverse["crocodile"]);
Console.WriteLine(b[13]);

Any feedback/ suggestions are welcome. Is it reasonable to keep the object and its inverse tied like this or would it be unexpected behavior that changing the inverse also changes the original object

\$\endgroup\$
  • 1
    \$\begingroup\$ Why are you waiting to document the code until a someone posts a review? If it's because you want reviews that are specific to a certain aspect of your code, it's better to include that in your question. As a general rule, the more information you can include, the better reviews will be. \$\endgroup\$ – Alex F Sep 4 at 5:14
  • \$\begingroup\$ @AlexF because honestly I was worried that maybe I just did not find the official implementation of this class and somebody points to it with a oneliner \$\endgroup\$ – Benj Sep 4 at 5:17
  • \$\begingroup\$ I would include that in your question with something like "if an official implementation of a bidirectional dictionary exists, please link to it." I don't see how withholding the documentation would change the kind of answers you get, and even if an implementation already exists, you could still benefit from someone else reviewing your code more easily. \$\endgroup\$ – Alex F Sep 4 at 5:22
  • \$\begingroup\$ @AlexF Alright, will add it \$\endgroup\$ – Benj Sep 4 at 5:34
  • \$\begingroup\$ @AlexF added documentation and an example on how to use it \$\endgroup\$ – Benj Sep 4 at 5:59
10
\$\begingroup\$
public T_Inv this[T_Proto key]
{
  get
  {
    if (!_Proto.ContainsKey(key))
    {
      throw new KeyNotFoundException("[Bijection] The key " + key + " could not be found");
    }

    return _Proto[key];
  }
  set
  {
    this.Add(key, value);
  }

For get: I would just rely on the behavior of _Proto[TKey] - because you're not adding any new or extended behavior with your code.

For set: I would just do:

_Proto[key] = value;
_Inv[value] = key;

because you're not adding to the dictionary, you're setting.

Update : As JAD points out in his comment this isn't consistent either, because it could lead to orphans in _Inv. So be careful.


public void Add(T_Proto key, T_Inv value)
{
  if (_Proto.ContainsKey(key))
  {
    _Inv.Remove(_Proto[key]);
  }

  _Proto.Add(key, value);
  _Inv.Add(value, key);
}

There is something wrong with the workflow or logic here:

Let's say _Proto.ContainsKey(key) returns true, then you remove the value from the inverse. But if _Proto.ContainsKey(key) is true, _Proto.Add(key, value) will throw an exception, and you then have an inconsistent Bijection object - because the existing inverse was removed while the proto was not.

Further: doing this:

  Bijection<string, int> b = new Bijection<string, int>();
  b["a"] = 1;
  b.Add("b", 1);

b.Add("b", 1); will throw an exception because _Inv already has a key of 1 - but now b.Proto contains both an entry for "a" and "b" with the value of 1, while b.Inv only have the entry 1 = "a".

You'll have to ensure that there always is a one-one correspondence between key and value, and ensure that the Bijection object is consistent even if a invalid operation is performed on it.

Update

I can see, that you've updated the Add() method after I've copied the code to my IDE, so the above relates to the first version.

The new version:

    public void Add(T_Proto key, T_Inv value)
    {
        if (_Proto.ContainsKey(key))
        {
            _Inv.Remove(_Proto[key]);
        }

        if (_Inv.ContainsKey(value))
        {
            throw new ArgumentException("[Bijection] The inverse already maps " + value + " to " + _Inv[value]);
        }

        _Proto.Add(key, value);
        _Inv.Add(value, key);
    }

however, doesn't do the trick either, because it will still throw and exception if _Proto contains key leaving the dictionaries out of sync.


public bool Remove(T_Proto key)
{
  if (_Proto.ContainsKey(key))
  {
    bool removed_inv = _Inv.Remove(_Proto[key]);
    bool removed_proto = _Proto.Remove(key);

    return (removed_proto && removed_inv);              // == true
  }
  else
  {
    return false;
  }
}

You can simplify this by using TryGetValue():

public bool Remove(T_Proto key)
{
  if (_Proto.TryGetValue(key, out T_Inv value))
  {
    _Proto.Remove(key);
    _Inv.Remove(value);
    return true;
  }

  return false;
}
\$\endgroup\$
  • \$\begingroup\$ For Dictionary d I did not expect the behavior of d.Add(key,val) to differ from d[key]=val \$\endgroup\$ – Benj Sep 4 at 7:51
  • 1
    \$\begingroup\$ @Benj but users expect that as this is unfortuantelly how dictionaries work. \$\endgroup\$ – t3chb0t Sep 4 at 7:53
  • 1
    \$\begingroup\$ Your suggestion for this[] doesn't necessarily work. Take the example code in the OP. If you run that, and afterwards run b[13] = "frog";, the OP's implementation throws an exception due to value already being a key in the inverse. If you do it your way, I think you lose that behaviour, and end up with two dictionaries that are not mirrors of eachother anymore. \$\endgroup\$ – JAD Sep 4 at 7:57
  • 2
    \$\begingroup\$ @Benj keep in mind that it's not allowed to update the code anymore. I'd invalidate the answers. Any edits will be rolledback. \$\endgroup\$ – t3chb0t Sep 4 at 7:59
  • 1
    \$\begingroup\$ @HenrikHansen I'd advocate making the elements read-only. You can add and remove them, but not replace them in place. In other words, remove the this[] getter. This is actually what OP is doing in a roundabout way: if the setter is used, the existing item is removed and re-added. \$\endgroup\$ – JAD Sep 4 at 8:07
9
\$\begingroup\$

In general I find this implementation is OK. It uses internally two dictionaries as it should or rather must so there is not much to get wrong.


What I do not like is the underscore naming convention for the generic parameters and their abbrevaited names.


I wouldn't let this class implement the IDictionary interface as technically it needs two of them: TKey --> TValue and TValue --> TKey. This however will lead to problems with the default indexer when TKey and TValue are of the same type you would have two identical indexers and it would be ambiguous which one should be used.

At this point I also have to say that your API is incomplete because even though it uses two dictionaries, it doesn't allow me to get TKey by TValue as there is only one TryGetValue method. So your claim that it's bi-directional is false.


Instead, I would just call it Mapping and implement only APIs that you need. If you need dictionaries then I think it'd be cleaner if you added such methods as ToXYDictionary and ToYXDictionary. With your custom class you can implement whatever behavior you desire. As long as you use the IDictionary interface you should be consistent with its behaviour (see your comment Add vs this[]).


Remove doesn't have to check whether any of the keys exists. Just remove them both and return the result. It's guaranteed that there are always two keys.

\$\endgroup\$
  • \$\begingroup\$ I did not mean to say it was bidirectional. I meant to say it is a bijection saying that each value element is addressable and it is addressable by exactly one key only which is why I thought it makes sense to implement IDictionary . A corollary is that it is invertible so for convenience I supply the user the Inverse element \$\endgroup\$ – Benj Sep 4 at 8:09
  • 1
    \$\begingroup\$ @Benj you titled the question with Bidirectional dictionary but implemented something else :-P this is a little bit confusing, don't you think? \$\endgroup\$ – t3chb0t Sep 4 at 8:11
  • 1
    \$\begingroup\$ You are correct the title is a mistake. I will suggest to add a method to fit it :) \$\endgroup\$ – Benj Sep 4 at 8:12
7
\$\begingroup\$

Much of what I wanted to say has already been said, but there's a few points I haven't seen being addressed yet:

  • Why are the internal dictionaries lazily created? When someone creates a Bijection instance then they probably intend to actually use it, so you might as well create them up-front. It'll simplify the code.
  • When creating an inverse Bijection, why not link it to the current instance? That means that b.Inverse.Inverse will give you b again, instead of a new instance. As with the internal dictionaries, creating the inverse instance up-front would simplify things. It's cheap, anyway - Bijection contains no state of its own other than the shared dictionaries.
  • What's the reason for using SortedDictionary instead of Dictionary?
  • Equals contains a bug: you're performing the null-check against obj instead of obj_bijection. Note that instead of var t = obj as T;, followed by a null-check, you can also use if (!(obj is T t)).
  • What's the idea behind those overridden methods? The way your implementation works is that two Bijection instances are seen as equal when they refer to the same shared dictionaries (which is only true for b.Equals(b.Inverse.Inverse)). It won't treat different dictionaries with the same content as equal. That's (unfortunately?) the expected behavior for Equals, so you might as well just not override it (the same goes for GetHashCode).
  • ToString's behavior is nonsensical - its result suggests that a Bijection really is a sorted dictionary.
\$\endgroup\$
  • \$\begingroup\$ Great eye spotting the bug in Equals. And regarding Equals / GetHashcode I just blindly assumed it was properly overriden by the Dictionaries. \$\endgroup\$ – Benj Sep 4 at 11:22
3
\$\begingroup\$

KISS

I find this class too complex. It stores 2 dictionaries, but only allows manipulations from the perspective of one the types. And it requires a second instance with the dictionaries swapped to manipulate data from the other perspective.

Furthermore, a bijection should be seen as a function amongst two sets, rather than a dictionary from either perspective.

How about picking no perspective at all. From the public view, it's just a collection (actually a set) of tuples of an element of set x and one of set y. Ideal usage of a bijection, in my opinion, is as follows:

var bijection = new Bijection<int, string>();

bijection.Add((1, "USA"));
bijection.Add((2, "UK"));

// X and Y chosen from set theory: https://en.wikipedia.org/wiki/Bijection
var country = bijection.X[1];
var id = bijection.Y["UK"];

You no longer have a perspective on the bijection from either the proto or inv types. Instead, you work with an atomic type (X, Y). Readonly dictionaries X and Y are provided to give you the perspective of either of the types.

public class Bijection<TX, TY> : ICollection<(TX, TY)>
{
    private readonly IDictionary<TX, TY> _x = new Dictionary<TX, TY>();
    private readonly IDictionary<TY, TX> _y = new Dictionary<TY, TX>();

    public IReadOnlyDictionary<TX, TY> X => new ReadOnlyDictionary<TX, TY>(_x);
    public IReadOnlyDictionary<TY, TX> Y => new ReadOnlyDictionary<TY, TX>(_y);

    // ICollection members ..
}
\$\endgroup\$
2
\$\begingroup\$

Since this question got over 1000 views within 24 hours I decided to completely rework the class addressing as many comments as possible

Further remarks for improvement are appreciated

Since editing the question would result in a rollback as mentioned by t3chb0t I decided to post the changes in a separate answer

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Text;

namespace com.stackexchange.codereview.datastruc
{
    /// <summary>
    /// File Bijection.cs
    /// 
    /// This class implements a Bijection (which can be thought of a bidirectional Dictionary)
    /// 
    /// Link to Discussion 
    /// https://codereview.stackexchange.com/questions/227445/bidirectional-dictionary
    ///
    /// Link to Source 
    /// https://github.com/pillepalle1/stackexchange-codereview/blob/master/datastruc/Bijection.cs
    ///
    /// </summary>

    /*
     * Thanks to (see below) for their valuable input
     * ---------------+---------------------------------------------------------------------------
     * Henrik Hansen  | https://codereview.stackexchange.com/users/73941/henrik-hansen
     * dfhwze         | https://codereview.stackexchange.com/users/200620/dfhwze
     * t3chb0t        | https://codereview.stackexchange.com/users/59161/t3chb0t
     * Pieter Witvoet | https://codereview.stackexchange.com/users/51173/pieter-witvoet
     * JAD            | https://codereview.stackexchange.com/users/140805/jad
     * 
     * Remarks
     * -------------------------------------------------------------------------------------------
     * 
     * IDictionary has been removed as suggested by dfhwze . This does not cause a loss of functionality
     * due to the introduced properties .MappingXtoY and .MappingYtoX which provide read only access to
     * the internal Dictionaries
     * 
     * JAD and Pieter Witvoet seemed to be irritated by using a SortedDictionary rather than a Dictionary.
     * In the end it is a question of optimizing space or access time. Given that the structure maintains
     * two dictionaries, I first considered it reasonable to rather optimize space but it seems like that
     * the expected default behaviour is to optimize speed
     * 
     * Implementation of .Equals .GetHashcode .ToString has been changed given the remarks of Pieter Witvoet
     *
     */

    public class Bijection<T_SetX, T_SetY> : ICollection<(T_SetX, T_SetY)>
    {
        #region Exceptions the Structure might throw
        private static ArgumentException _xCollisionEx = new ArgumentException(String.Empty
            + "A collision occured in subset X when attempting to add the current element"
            + "You might want to: "
            + "- have a look at the property .CollisionHandlingProperty"
            + "- consider changing the implementation of x.Equals"
        );

        private static ArgumentException _yCollisionEx = new ArgumentException(String.Empty
            + "A collision occured in subset Y when attempting to add the current element"
            + "You might want to: "
            + "- have a look at the property .CollisionHandlingProperty"
            + "- consider changing the implementation of y.Equals"
        );

        private static Exception _internalError = new Exception(String.Empty
            + "[Bijection] Internal error / Inconsistent state"
        );
        #endregion

        private IDictionary<T_SetX, T_SetY> _x_to_y = null;                             // Mapping x to y (Get y given x)
        private IDictionary<T_SetY, T_SetX> _y_to_x = null;                             // Mapping y to x (Get x given y)

        public Bijection() :
        this(new Dictionary<T_SetX, T_SetY>(), new Dictionary<T_SetY, T_SetX>())
        {
        }

        public Bijection(IDictionary<T_SetX, T_SetY> dict)
        {
            _x_to_y = new Dictionary<T_SetX, T_SetY>();
            _y_to_x = new Dictionary<T_SetY, T_SetX>();

            foreach (T_SetX x in dict.Keys)
            {
                this.Add((x, dict[x]));
            }
        }

        private Bijection(IDictionary<T_SetX, T_SetY> x_to_y, IDictionary<T_SetY, T_SetX> y_to_x)
        {
            _x_to_y = x_to_y;
            _y_to_x = y_to_x;
        }

        /// <summary>
        /// Elements of set X
        /// </summary>
        public IList<T_SetX> X => new List<T_SetX>(_x_to_y.Keys);

        /// <summary>
        /// Elements of set Y
        /// </summary>
        public IList<T_SetY> Y => new List<T_SetY>(_y_to_x.Keys);


        public IReadOnlyDictionary<T_SetX, T_SetY> MappingXtoY => new ReadOnlyDictionary<T_SetX, T_SetY>(_x_to_y);
        public IReadOnlyDictionary<T_SetY, T_SetX> MappingYtoX => new ReadOnlyDictionary<T_SetY, T_SetX>(_y_to_x);


        #region Indexer and Inverse

        /*
         * The indexer remained because some users (including me) prefer to manage the object through indices
         * rather than calling the method .Add((x,y)) even though it is conceptually not entirely appropriate
         * 
         * The .Inverse has however been removed because it introduces the question on how to handle the prop
         * CollisionHandlingPolicy (is it supposed to be kept synchronous with its Inverse?) which then com-
         * plicates the code to an inappropriate extent.
         * 
         * This also removed the question of how to manage the inverse as mentioned by Pieter Witvoet
         * 
         * This introduces an asymmetrie and bias in favor of elements in X since elements cannot be added to
         * Y by using an indexer. This should however not cause a problem in practise, since both elements x
         * and y must be known when added to the collection as a tuple
         */

        public T_SetY this[T_SetX x]
        {
            get
            {
                return GetY(x);
            }
            set
            {
                Add((x, value));
            }
        }
        #endregion

        public T_SetX GetX(T_SetY y)
        {
            return _y_to_x[y];
        }

        public T_SetY GetY(T_SetX x)
        {
            return _x_to_y[x];
        }

        public void RemoveX(T_SetX x)
        {
            this.Remove((x, _x_to_y[x]));
        }

        public void RemoveY(T_SetY y)
        {
            this.Remove((_y_to_x[y], y));
        }

        /// <summary>
        /// Indicates the policy to be applied if an element cannot be added because it would break the bijection
        /// </summary>
        public ECollisionHandlingPolicy CollisionHandlingPolicy
        {
            get
            {
                return _collisionHandlingPolicy ?? ECollisionHandlingPolicy.ThrowX_ThrowY;
            }
            set
            {
                _collisionHandlingPolicy = value;
            }
        }
        protected ECollisionHandlingPolicy? _collisionHandlingPolicy = null;

        #region Implementation of Interface System.ICloneable

        /*
         *
         * Attempting to implement this ICloneable led to a conflict that suggested to discard it
         * alltogether
         *
         * The problem is that creating a deep copy would require T_SetX and T_SetY to implement
         * System.ICloneable which would severly limit the flexibility. It could however be reason-
         * able for immutable types but then the issue of having to properly inform the user before-
         * hand
         *
         */

        #endregion

        #region Implementation of Interface ICollection<T_SetX, T_SetY>
        public int Count => X.Count;

        public bool IsReadOnly => false;

        public void Add((T_SetX, T_SetY) item)
        {
            if (this.Contains(item)) return;

            if (X.Contains(item.Item1))
            {
                switch (CollisionHandlingPolicy)
                {
                    case (ECollisionHandlingPolicy.ThrowX_ThrowY):
                    case (ECollisionHandlingPolicy.ThrowX_ResolveY): throw _xCollisionEx;

                    case (ECollisionHandlingPolicy.ResolveX_ThrowY):
                    case (ECollisionHandlingPolicy.ResolveX_ResolveY): _x_to_y.Remove(item.Item1); break;

                    default: throw _internalError;
                }
            }

            if (Y.Contains(item.Item2))
            {
                switch (CollisionHandlingPolicy)
                {
                    case (ECollisionHandlingPolicy.ThrowX_ResolveY):
                    case (ECollisionHandlingPolicy.ResolveX_ResolveY): _y_to_x.Remove(item.Item2); break;

                    case (ECollisionHandlingPolicy.ThrowX_ThrowY):
                    case (ECollisionHandlingPolicy.ResolveX_ThrowY): throw _yCollisionEx;

                    default: throw _internalError;
                }
            }

            _x_to_y[item.Item1] = item.Item2;
            _y_to_x[item.Item2] = item.Item1;
        }

        public void Clear()
        {
            _x_to_y.Clear();
            _y_to_x.Clear();
        }

        public bool Contains((T_SetX, T_SetY) item)
        {
            if (!X.Contains(item.Item1)) return false;
            if (!Y.Contains(item.Item2)) return false;
            if (!_x_to_y[item.Item1].Equals(item.Item2)) return false;

            return true;
        }

        public void CopyTo((T_SetX, T_SetY)[] array, int arrayIndex)
        {
            foreach (T_SetX x in X)
            {
                array[arrayIndex++] = (x, _x_to_y[x]);
            }
        }

        public bool Remove((T_SetX, T_SetY) item)
        {
            if (!this.Contains(item)) return false;

            _x_to_y.Remove(item.Item1);
            _y_to_x.Remove(item.Item2);
            return true;
        }

        public IEnumerator<(T_SetX, T_SetY)> GetEnumerator()
        {
            return new BijectionEnumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new BijectionEnumerator(this);
        }
        #endregion

        #region Bijection Specific Nested Data Structures
        /// <summary>
        /// Enumerator for element-wise access to a bijection
        /// </summary>
        public class BijectionEnumerator : IEnumerator<(T_SetX, T_SetY)>
        {
            private Bijection<T_SetX, T_SetY> _bijection = null;
            private List<T_SetX> _keys = null;
            private int _keyIndex;

            public BijectionEnumerator(Bijection<T_SetX, T_SetY> bijection)
            {
                _bijection = bijection;
                _keys = new List<T_SetX>(bijection.X);
                _keyIndex = 0;
            }
            public (T_SetX, T_SetY) Current
            {
                get
                {
                    return (_keys[_keyIndex], _bijection.GetY(_keys[_keyIndex]));
                }
            }

            object IEnumerator.Current
            {
                get
                {
                    return (_keys[_keyIndex], _bijection.GetY(_keys[_keyIndex]));
                }
            }

            public bool MoveNext()
            {
                return (_keyIndex < (_keys.Count - 1));
            }

            public void Reset()
            {
                _keyIndex = 0;
            }

            public void Dispose()
            {
                // This enumerator does not occupy any ressources that need to be released
            }

        }
        #endregion

        #region Overrides
        public override string ToString()
        {
            StringBuilder b = new StringBuilder();

            b.Append("Count=" + this.Count);
            b.Append(' ');
            b.Append("[" + typeof(T_SetX).ToString() + " <-> " + typeof(T_SetY).ToString() + "]");

            return b.ToString();
        }
        public override int GetHashCode()
        {
            return Count;
        }
        public override bool Equals(object obj)
        {
            Bijection<T_SetX, T_SetY> obj_bijection = (obj as Bijection<T_SetX, T_SetY>);
            if (null == obj_bijection) return false;

            if (Count != obj_bijection.Count) return false;

            foreach (var t in this)
            {
                if (!obj_bijection.Contains(t)) return false;
            }

            return true;
        }
        #endregion
    }

    #region Bijection Specific External Data Structures
    /// <summary>
    /// Available policies on resolving a conflict caused by attempting to map an element a to b which already maps to c
    /// - Throw will cause an ArgumentException to be thrown
    /// - Resolve will remove the existing mapping and replace it by the one provided
    /// </summary>
    public enum ECollisionHandlingPolicy
    {
        ThrowX_ThrowY,
        ThrowX_ResolveY,
        ResolveX_ThrowY,
        ResolveX_ResolveY
    }
    #endregion
}

I also added a property that allows the user to decide the behavior in case of a collision

Example on how to use the structure

public static void Main(string[] args)
{
    Bijection<int, string> bijection = new Bijection<int, string>();

    bijection[1] = "frog";
    bijection.Add((2, "camel"));
    bijection.[3] = "horse";

    if(bijection.Y.Contains("frog"))
    {
        bijection.RemoveY("frog");
        EatFrog();
    }

    foreach(int i in bijection.X)
    {
        Console.WriteLine(bijection[i]);
    }

    foreach(var t in bijection)
    {
        Console.WriteLine(t.item2);
    }
}

That should cover most of the cases

\$\endgroup\$
  • 1
    \$\begingroup\$ Writing a self-answer is exactly the right way to post the updated code ;-) \$\endgroup\$ – t3chb0t Sep 6 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.