双向词典

Question

双向映射的管理是一个重新出现的话题。我花时间写了一个(希望是)高效的实现。

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
    }
}

实例将按以下方式使用

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]);

欢迎任何反馈/建议。保持对象及其逆序像这样绑定是合理的吗?还是更改逆对象也会改变原始对象是意外的行为？

Answer 1

KISS

我觉得这门课太复杂了。它存储两个字典，但只允许从一个类型的角度进行操作。它需要第二个实例，从另一个角度交换字典来操作数据。

此外，双射应该被看作是两个集合之间的函数，而不是从任何一个角度来看都是字典。

干脆不选一个视角怎么样。从公众的角度来看，它只是一个集合(实际上是一个集合)，集合x的元素和集合y的元组。在我看来，双射的理想用法如下：

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"];

您不再从proto或inv类型透视双射。相反，您可以使用原子类型(X, Y)。只提供阅读词典X和Y，让您了解这两种类型的透视图。

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 ..
}

Answer 2

由于这个问题在24小时内就有超过1000次浏览，所以我决定尽可能多地回复这个课程。

如有进一步改进意见，敬请谅解。

因为编辑这个问题会导致t3chb0t提到的回滚，所以我决定将更改放在一个单独的答案中。

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
}

我还添加了一个属性，允许用户在发生冲突时决定行为。

关于如何使用结构的示例

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);
    }
}

这应该涵盖了大部分案件