Key Order Agnostic, 2D Dictionary

Question

Note: I am using Unity3D game engine, which uses .Net 2.0 (.Net 2.0.50727.1433 to be precise) to compile code, so I don't have access to newest features of C# 6, or even C# 5. Please keep this in mind while writing your reviews.

---

What is this?

This (DataTable.cs) is a dictionary that takes two keys, and returns a value; along with a special implementation (SymmetricDataTable.cs) of this dictionary that is key-order agnostic.

---

What is this for?

This is for a diplomacy manager in a strategy game I am developing. I give it two nations, it gives me back the diplomatic relation between those nations.

---

What I want to be reviewed?

Everything.

---

Teminology I used in my code:

DataTable: Class name of my implementation of a 2D dictionary.

Symmetric DataTable: Key-order agnostic version of DataTable class.

Row: Alias for first key in DataTable.

Col: Short for Column, alias for second key in DataTable.

Cell: A value that corresponds to a specific Row and Col combination.

---

So here is my implementation that consists of two classes and one struct:

DataTable.cs

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

namespace UnityCSCommon.Expansions
{
    /// <summary>
    /// A fast collection that consists of rows and columns, and cells that corresponds to intersection of these.
    /// </summary>
    /// <typeparam name="TRow">The type of rows.</typeparam>
    /// <typeparam name="TCol">The type of columns.</typeparam>
    /// <typeparam name="TCell">The type of cells (values).</typeparam>
    ///
    /// <remarks>
    /// In this type, we treat all references as values and use integers as keys to access them.
    /// The way this is possible is:
    ///     1- We get hash codes of both row and column.
    ///     2- We use a pairing function to generate a unique number out of two hash codes.
    ///     3- We use the unique number as the key for the entry.
    ///
    /// So, if user didn't make something stupid like overriding the GetHashCode() method with a constant,
    /// we will get the same unique number for the same row and column every time. Thus, the same entry.
    ///
    /// I was using Cantor Pairing at first, but then I discovered Szudzik's Elegant Pairing,
    /// which has better coverage. So I switched to it, but I still keep Cantor Pairing in
    /// it's own method in case I need it.
    /// </remarks>
    public class DataTable<TRow, TCol, TCell> : IEnumerable<DataTableEntry<TRow, TCol, TCell>>
    {
        private static readonly TCell DefaultCellValue = default(TCell);
        private readonly Dictionary<long, DataTableEntry<TRow, TCol, TCell>> _entries = new Dictionary<long, DataTableEntry<TRow, TCol, TCell>>();

        /// <summary>
        /// Sets the intersection of <paramref name="row"/> and <paramref name="col"/> to <paramref name="newCell"/>.
        /// </summary>
        public void Set (TRow row, TCol col, TCell newCell)
        {
            long key = CalculateKey (row, col);
            var newEntry = CreateEntry (row, col, newCell);

            if (_entries.ContainsKey (key))
            {
                _entries[key] = newEntry;
            }
            else
            {
                _entries.Add (key, newEntry);
            }
        }

        /// <summary>
        /// Returns the intersection of <paramref name="row"/> and <paramref name="col"/>. <para/>
        /// Throws a <see cref="KeyNotFoundException"/> if no such cell exists (i.e. it has never set).
        /// </summary>
        public TCell Get (TRow row, TCol col)
        {
            long key = CalculateKey (row, col);
            DataTableEntry<TRow, TCol, TCell> value;

            if (_entries.TryGetValue (key, out value))
            {
                return value.Cell;
            }
            else
            {
                throw new KeyNotFoundException ("This cell is never set.");
            }
        }

        /// <summary>
        /// Tries to get the intersection of <paramref name="row"/> and <paramref name="col"/> and assigns it to <paramref name="cell"/>. <para/>
        /// Returns true if a cell is found, false otherwise (i.e. it has never set). <para/>
        /// Note: If return is false, the value of <paramref name="cell"/> will be the default value of <typeparamref name="TCell"/>.
        /// </summary>
        public bool TryGet (TRow row, TCol col, out TCell cell)
        {
            long key = CalculateKey(row, col);
            DataTableEntry<TRow, TCol, TCell> value;

            if (_entries.TryGetValue (key, out value))
            {
                cell = value.Cell;
                return true;
            }
            else
            {
                cell = DefaultCellValue;
                return false;
            }
        }

        public TCell this [TRow row, TCol col]
        {
            get { return Get (row, col); }
            set { Set (row, col, value); }  // Note for CodeReview SE: *value* is a keyword here, but snippet highlighter doesn't think so.
        }

        protected virtual long CalculateKey (TRow row, TCol col)
        {
            int rowHash = row.GetHashCode();
            int colHash = col.GetHashCode();

            return Pair (rowHash, colHash);
        }

        protected static long Pair (int x, int y)
        {
            return SzudzikPairing (x, y);
        }

        private static long SzudzikPairing (int x, int y)
        {
            // Szudzik's Elegant Pairing Function
            return x >= y ? x*x + x + y : y*y + x;
        }

        // Cantor Pairing is no longer in use since Szudzik's Pairing gives better coverage.
        // But I am still keeping it in case we need it later.
        private static long CantorPairing (int x, int y)
        {
            // Cantor Pairing Function
            return (x + y)*(x + y + 1)/2 + y;
        }

        private static DataTableEntry<TRow, TCol, TCell> CreateEntry (TRow row, TCol col, TCell cell)
        {
            return new DataTableEntry<TRow, TCol, TCell> (row, col, cell);
        }

        #region Implementation of IEnumerable
        public IEnumerator<DataTableEntry<TRow, TCol, TCell>> GetEnumerator()
        {
            return _entries.Values.GetEnumerator();
        }

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

DataTableEntry.cs

namespace UnityCSCommon.Expansions
{
    /// <summary>
    /// The value type of the internal dictionary of a <see cref="DataTable{TRow,TCol,TCell}"/> class.
    /// </summary>
    public struct DataTableEntry<TRow, TCol, TCell>
    {
        private readonly TRow _row;
        private readonly TCol _col;
        private readonly TCell _cell;

        public TRow Row
        {
            get { return _row; }
        }

        public TCol Col
        {
            get { return _col; }
        }

        public TCell Cell
        {
            get { return _cell; }
        }

        public DataTableEntry (TRow row, TCol col, TCell cell)
        {
            _row = row;
            _col = col;
            _cell = cell;
        }
    }
}

SymmetricDataTable.cs

namespace UnityCSCommon.Expansions
{
    /// <summary>
    /// A special <see cref="DataTable{TRow,TCol,TCell}"/> type where you get the same cell when you swap the row and column. <para/>
    /// For example: When you assign value A to [1-2], you will get value A for both [1-2] and [2-1]. ([1-2] means row 1 and column 2) <para/>
    /// To be able to swap row and column, they have to be the same type. So this class takes a single type for both rows and columns.
    /// </summary>
    ///
    /// <remarks>
    /// Implementing this class is really easy. While getting the key before pairing function, we sort the hash values, so it doesn't matter which hash is which object's.
    /// For example, say we have object A and object B. Let hash code of A be 1 and B be 2.
    ///     - CalculateKey (A, B) --> Pair (Max (A,B), NotMax (A,B)) = Pair (2,1).
    ///     - CalculateKey (B, A) --> Pair (Max (B,A), NotMax (B,A)) = Pair (2,1).
    /// As you see, the pair remains same no matter the order of objects.
    /// </remarks>
    public class SymmetricDataTable<TRowAndCol, TCell> : DataTable<TRowAndCol, TRowAndCol, TCell>
    {
        #region Overrides of DataTable<TRow,TCol,TCell>
        protected override long CalculateKey (TRowAndCol row, TRowAndCol col)
        {
            int rowHash = row.GetHashCode();
            int colHash = col.GetHashCode();

            // This is a sorting operation. If colHash is bigger, we swap them. So first parameter is always the bigger one.
            return rowHash >= colHash ? Pair (rowHash, colHash) : Pair (colHash, rowHash);
        }
        #endregion
    }
}

Answer 1

As @JanDotNet explains in their answer, your DataTable<TRow, TCol, TCell> does not handle hash collisions at all. If a two two-item keys happen to have the same hash, your dictionary will overwrite the value for the first with the value for the second in random, hard-to-reproduce situations.

Since Dictionary<TKey, TValue> is already designed to handle hash collisions, I would recommend that, before implementing your own replacement from scratch, you ask: is there any way I can use the existing Dictionary<TKey, TValue> type with two symmetric keys? And, in fact, this can be done, because a .Net dictionary can be constructed with a custom IEqualityComparer. Given that, your problem now simplifies to: how can I create an equality comparer between pairs of keys that is symmetric?

Assuming you have access to the Tuple or ValueTuple types, you can an IEqualityComparer that returns true if two 2-tuples have items that are identical or identical when swapped. Note that the comparer must be a proper equivalence relation by being reflexive, symmetric and transitive. Thus the implementation of IEqualityComparer.GetHashCode(x, y) must therefore return the same value for flipped tuples, i.e. comparer.GetHashCode(Tuple.Create(a, b)) == comparer.GetHashCode(Tuple.Create(b, a)) for all a and b.

The following comparers and dictionary extension methods can be used for this purpose:

public abstract class SymmetricTupleComparerBase<T> : IEqualityComparer<Tuple<T, T>>
{
    protected readonly IEqualityComparer<T> comparer = EqualityComparer<T>.Default;

    public bool Equals(Tuple<T, T> x, Tuple<T, T> y)
    {
        if (object.ReferenceEquals(x, y))
            return true;
        else if (object.ReferenceEquals(x, null) || object.ReferenceEquals(y, null))
            return false;

        if (comparer.Equals(x.Item1, y.Item1) && comparer.Equals(x.Item2, y.Item2))
            return true;
        if (comparer.Equals(x.Item1, y.Item2) && comparer.Equals(x.Item2, y.Item1))
            return true;
        return false;
    }

    public abstract int GetHashCode(Tuple<T, T> obj);
}

public class SymmetricTupleComparer<T> : SymmetricTupleComparerBase<T>
{
    public override int GetHashCode(Tuple<T, T> obj)
    {
        if (obj == null)
            return 0;
        return HashHelper.SymmetricCombineHash(comparer.GetHashCode(obj.Item1), comparer.GetHashCode(obj.Item2));
    }
}

public class SymmetricTupleComparerComplex<T> : SymmetricTupleComparerBase<T>
{
    public override int GetHashCode(Tuple<T, T> obj)
    {
        if (obj == null)
            return 0;
        return HashHelper.SymmetricCombineHashComplex(comparer.GetHashCode(obj.Item1), comparer.GetHashCode(obj.Item2));
    }
}

public static partial class HashHelper
{
    public static int SymmetricCombineHash(int code1, int code2)
    {
        // in case Item1 and Item2 are identical, code1 == code2 so code1 ^ code2 will always be zero.
        if (code1 == code2)
        {
            // As implemented in practice, hash codes seem to be biased towards small numbers, 
            // so reverse the bytes of the single-item hash to bias it towards a larger number.
            return ReverseBytes(code1);
        }
        // Note that the XOR operator is symmetric
        return code1 ^ code2;
    }

    public static int SymmetricCombineHashComplex(int code1, int code2)
    {
        // This can be useful when input hash codes are biased towards small integers by
        // expanding the input values to larger numbers.

        if (code1 == code2)
        {
            // in case Item1 and Item2 are identical, code1 == code2 so code1 ^ code2 will always be zero.
            return ReverseBytes(code1);
        }
        // Note that the multiplation operator is symmetric
        return unchecked(((ulong)~(uint)code1) * ((ulong)~(uint)code2)).GetHashCode();
    }

    public static Int32 ReverseBytes(Int32 value)
    {
        return unchecked((Int32)ReverseBytes((UInt32)value));
    }

    public static UInt32 ReverseBytes(UInt32 value)
    {
        // https://stackoverflow.com/questions/18145667/how-can-i-reverse-the-byte-order-of-an-int
        return (value & 0x000000FFU) << 24 | (value & 0x0000FF00U) << 8 |
            (value & 0x00FF0000U) >> 8 | (value & 0xFF000000U) >> 24;
    }
}

public static partial class DictionaryExtensions
{
    // Extension methods for dictionaries of symmetric pairs.
    // https://unity3d.com/learn/tutorials/topics/scripting/extension-methods

    public static void Add<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary.Add(Tuple.Create(item1, item2), value);
    }

    public static void Set<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary[Tuple.Create(item1, item2)] = value;
    }

    public static bool Remove<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.Remove(Tuple.Create(item1, item2));
    }

    public static TValue Get<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary[Tuple.Create(item1, item2)];
    }

    public static bool TryGetValue<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2, out TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.TryGetValue(Tuple.Create(item1, item2), out value);
    }
}

Notice that:

• SymmetricTupleComparerBase<T>.GetHashCode() checks whether the items are identical or identical when flipped.

• SymmetricTupleComparer<T>.GetHashCode() XOR's the hash codes of the items when not equal, or uses a hash of one of them when equal. Since XOR is symmetric, two tuples with flipped items will have the same hash code.

  This works well when the input hash codes are fairly randomly distributed among possible int values, such as with string hash codes.

• SymmetricTupleComparerComplex<T>.GetHashCode() uses a hash of the product of the two values as longs when not equal, or uses a hash of one of the values when equal. Since multiplication is symmetric, two tuples with flipped items will have the same hash code.

  This works better when the input hash codes are biased towards small numbers. E.g. Int32.GetHashCode() returns the integer value itself.

Now you can use the comparer and extension methods as follows:

var dictionary = new Dictionary<Tuple<int, int>, string>(new SymmetricTupleComparerComplex<int>());
dictionary.Set(1, 0, "hello");
Console.WriteLine(dictionary.Get(0, 1));

Sample fiddle with basic tests working.

If you don't have access to Tuple or ValueTuple you can create your own generic symmetric pair quite easily:

public struct SymmetricPair<TKey> : IEquatable<SymmetricPair<TKey>>
{
    readonly TKey item1;
    readonly TKey item2;

    public SymmetricPair(TKey item1, TKey item2)
    {
        this.item1 = item1;
        this.item2 = item2;
    }

    public TKey Item1 { get { return item1; } }
    public TKey Item2 { get { return item2; } }

    #region IEquatable<SymmetricPair<TKey>> Members

    public bool Equals(SymmetricPair<TKey> other)
    {
        var comparer = EqualityComparer<TKey>.Default;
        if (comparer.Equals(Item1, other.Item1) && comparer.Equals(Item2, other.Item2))
            return true;
        if (comparer.Equals(Item2, other.Item1) && comparer.Equals(Item1, other.Item2))
            return true;
        return false;
    }

    #endregion

    public override bool Equals(object obj)
    {
        if (!(obj is SymmetricPair<TKey>))
            return false;
        return Equals((SymmetricPair<TKey>)obj);
    }

    public override int GetHashCode()
    {
        var comparer = EqualityComparer<TKey>.Default;
        var code1 = comparer.GetHashCode(Item1);
        var code2 = comparer.GetHashCode(Item2);

        // Here we use the fact that the XOR operator is symmetric
        return HashHelper.SymmetricCombineHash(code1, code2);
    }

    public override string ToString()
    {
        return string.Format("SymmetricPair: ({0} {1})", Item1, Item2);
    }
}

public static partial class HashHelper
{
    public static int SymmetricCombineHash(int code1, int code2)
    {
        // in case Item1 and Item2 are identical, code1 == code2 so code1 ^ code2 will always be zero.
        if (code1 == code2)
        {
            // As implemented hash codes seem to be biased towards small numbers, 
            // so reverse the bytes of the single-item hash to bias it towards a larger number.
            return ReverseBytes(code1);
        }
        // Note that the XOR operator is symmetric
        return code1 ^ code2;
    }

    public static int SymmetricCombineHashComplex(int code1, int code2)
    {
        // in case Item1 and Item2 are identical, code1 == code2 so code1 ^ code2 will always be zero.
        if (code1 == code2)
            return ReverseBytes(code1);
        // Note that the multiplation operator is symmetric
        return unchecked(((ulong)~(uint)code1) * ((ulong)~(uint)code2)).GetHashCode();
    }


    public static Int32 ReverseBytes(Int32 value)
    {
        return unchecked((Int32)ReverseBytes((UInt32)value));
    }

    public static UInt32 ReverseBytes(UInt32 value)
    {
        // https://stackoverflow.com/questions/18145667/how-can-i-reverse-the-byte-order-of-an-int
        return (value & 0x000000FFU) << 24 | (value & 0x0000FF00U) << 8 |
            (value & 0x00FF0000U) >> 8 | (value & 0xFF000000U) >> 24;
    }
}

public static partial class DictionaryExtensions
{
    // Extension methods for dictionaries of symmetric pairs.
    // https://unity3d.com/learn/tutorials/topics/scripting/extension-methods

    public static void Add<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary.Add(new SymmetricPair<TKey>(item1, item2), value);
    }

    public static void Set<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary[new SymmetricPair<TKey>(item1, item2)] = value;
    }

    public static bool Remove<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.Remove(new SymmetricPair<TKey>(item1, item2));
    }

    public static TValue Get<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary[new SymmetricPair<TKey>(item1, item2)];
    }

    public static bool TryGetValue<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2, out TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.TryGetValue(new SymmetricPair<TKey>(item1, item2), out value);
    }
}

And do:

var dictionary = new Dictionary<SymmetricPair<int>, string>();
dictionary.Set(1, 0, "hello");
Console.WriteLine(dictionary.Get(0, 1));

Sample fiddle #2.

In both cases your testing is now much simpler: you no longer need to validate your own dictionary implementation, you only need to validate your implementations of GetHashCode() and Equals().

Answer 2

Your implementation does not work. It is not enough to generate a key based on the hash codes of column and the row. The key must be an identifier that is unique for each combination of column and row. That is not the case for hash codes because different combinations of column and row may result in the same hash codes.

---

A simple solution for generating combined keys could be to use a tuple:

var key = Tuple.Create(row, col);

If the Tuple data type is not available in your version of the .Net framework, it is open source ;):

https://referencesource.microsoft.com/#mscorlib/system/tuple.cs

Answer 3

Here are a few minor changes.

DataTable's Set method can be simplified. Dictionary's indexer will replace the value if the key exists or add the key and value if it doesn't. This version only computes the hash value once in both cases.

    /// <summary>
    /// Sets the intersection of <paramref name="row"/> and <paramref name="col"/> to <paramref name="newCell"/>.
    /// </summary>
    public void Set (TRow row, TCol col, TCell newCell)
    {
        long key = CalculateKey (row, col);
        var newEntry = CreateEntry (row, col, newCell);

        _entries[key] = newEntry;
    } 

The initializer for _elements constructs a dictionary with a default size. If you add a DataTable(int capacity) constructor then client code that knows the number of elements does not have to pay for resizing the dictionary.

    private readonly Dictionary<long, DataTableEntry<TRow, TCol, TCell>> _entries;

    public DataTable() : this(0)
    {
    }

    public DataTable(int capacity)
    {
        if (capacity < 0)
        {
            throw new ArgumentOutOfRangeException("capacity");
        }
        _entries = new Dictionary<long, DataTableEntry<TRow, TCol, TCell>>(capacity);
    }