I'm trying to create a Dictionary is C# that takes an Unordered Pair of Indices as its Key.
For example:
exampleDictionary[new UnorderedPair(x,y)] and exampleDictionary[new UnorderedPair(y,x)] should both return the same value.
Is there a way to create a custom unordered collection other than using a HashSet? Or some way to create an unordered Tuple?
This question is similar to what I'm trying to accomplish, except in C# rather than python.
CodePudding user response：
If the type is not your own or you can't or don't want to modify refer to Theodor Zoulias's answer
Otherwise, assuming that UnorderedPair is your own class you can modify what you could do is e.g.
public class UnorderedPair<T> : IEquatable<UnorderedPair<T>>
{
public T x;
public T y;
public UnorderedPair(T x, T y)
{
this.x = x;
this.y = y;
}
public bool Equals(UnorderedPair<T>? other)
{
if (ReferenceEquals(null, other))
{
return false;
}
if (ReferenceEquals(this, other))
{
return true;
}
// For equality simply include the swapped check
return x.Equals(other.x) && y.Equals(other.y) || x.Equals(other.y) && y.Equals(other.x);
}
public override bool Equals(object? obj)
{
if (ReferenceEquals(null, obj))
{
return false;
}
if (ReferenceEquals(this, obj))
{
return true;
}
if (obj.GetType() != this.GetType())
{
return false;
}
return Equals((UnorderedPair<T>)obj);
}
public override int GetHashCode()
{
// and for the HashCode (used as key in HashSet and Dictionary) simply order them by size an hash them again ^^
var hashX = x is null ? 0 : x.GetHashCode();
var hashY = y is null ? 0 : y.GetHashCode();
return HashCode.Combine(Math.Min(hashX,hashY), Math.Max(hashX,hashY));
}
public static bool operator ==(UnorderedPair<T>? left, UnorderedPair<T>? right)
{
return Equals(left, right);
}
public static bool operator !=(UnorderedPair<T>? left, UnorderedPair<T>? right)
{
return !Equals(left, right);
}
}
and then e.g.
var testDict = new Dictionary<UnorderedPair<int>, string>();
testDict.Add(new UnorderedPair<int>(1,2), "Hello World!");
Console.WriteLine(testDict[new UnorderedPair<int>(2,1)]);
As per suggestion by Jodrell in the comments you could even make the types swappable - not sure this would be ever needed - but this way you could even have a pair of different types:
public class UnorderedPair<TX, TY> : IEquatable<UnorderedPair<TX, TY>>
{
public TX X;
public TY Y;
public UnorderedPair(TX x, TY y)
{
this.X = x;
this.Y = y;
}
public UnorderedPair(TY y, TX x)
{
this.X = x;
this.Y = y;
}
public override int GetHashCode()
{
// and for the HashCode (used as key in HashSet and Dictionary) simply order them by size an hash them again ^^
var hashX = x is null ? 0 : x.GetHashCode();
var hashY = y is null ? 0 : y.GetHashCode();
return HashCode.Combine(Math.Min(hashX, hashY), Math.Max(hashX, hashY));
}
public bool Equals(UnorderedPair<TX, TY>? other)
{
if (ReferenceEquals(null, other))
{
return false;
}
if (ReferenceEquals(this, other))
{
return true;
}
return EqualityComparer<TX>.Default.Equals(X, other.X) && EqualityComparer<TY>.Default.Equals(Y, other.Y);
}
public override bool Equals(object? obj)
{
if (ReferenceEquals(null, obj))
{
return false;
}
if (ReferenceEquals(this, obj))
{
return true;
}
return obj switch
{
UnorderedPair<TX, TY> other => Equals(other),
UnorderedPair<TY, TX> otherSwapped => Equals(otherSwapped),
_ => false
};
}
public static bool operator ==(UnorderedPair<TX, TY>? left, UnorderedPair<TX, TY>? right)
{
return Equals(left, right);
}
public static bool operator !=(UnorderedPair<TX, TY>? left, UnorderedPair<TX, TY>? right)
{
return !Equals(left, right);
}
public static bool operator ==(UnorderedPair<TX, TY>? left, UnorderedPair<TY, TX>? right)
{
return Equals(left, right);
}
public static bool operator !=(UnorderedPair<TX, TY>? left, UnorderedPair<TY, TX>? right)
{
return !Equals(left, right);
}
public static implicit operator UnorderedPair<TX, TY>(UnorderedPair<TY, TX> pair)
{
return new UnorderedPair<TX, TY>(pair.Y, pair.X);
}
}
and
var testDict = new Dictionary<UnorderedPair<int, double>, string>();
testDict.Add(new UnorderedPair<int, double>(1,2.5), "Hello World!");
Console.WriteLine(testDict[new UnorderedPair<double,int>(2.5,1)]);
CodePudding user response：
You could write a custom IEqualityComparer<UnorderedPair<T>> implementation, and pass it as argument to the constructor of your Dictionary<UnorderedPair<TKey>, TValue>. This way you won't have to modify your UnorderedPair<T> type, by overriding its Equals and GetHashCode methods. Below is an example of such a comparer for the ValueTuple<T1, T2> struct, with both T1 and T2 being the same type:
class UnorderedValueTupleEqualityComparer<T> : IEqualityComparer<(T, T)>
{
private readonly IEqualityComparer<T> _comparer;
public UnorderedValueTupleEqualityComparer(IEqualityComparer<T> comparer = default)
{
_comparer = comparer ?? EqualityComparer<T>.Default;
}
public bool Equals((T, T) x, (T, T) y)
{
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 int GetHashCode((T, T) obj)
{
int h1 = _comparer.GetHashCode(obj.Item1);
int h2 = _comparer.GetHashCode(obj.Item2);
if (h1 > h2) (h1, h2) = (h2, h1);
return HashCode.Combine(h1, h2);
}
}
Usage example:
Dictionary<(int, int), string> dictionary = new(
new UnorderedValueTupleEqualityComparer<int>());
CodePudding user response：
Inspired by @derHugo's answer and my comments on it,
A generic implementation,
#nullable enable
public class UnorderedPair<T> : IEquatable<UnorderedPair<T>>
{
private static IEqualityComparer<T> comparer = EqualityComparer<T>.Default;
public T X { get; }
public T Y { get; }
public UnorderedPair(T x, T y)
{
X = x;
Y = y;
}
public bool Equals(UnorderedPair<T>? other)
{
if(other is null)
{
return false;
}
if (ReferenceEquals(this, other))
{
return true;
}
// For equality simply include the swapped check
return
comparer.Equals(X, other.X) && comparer.Equals(Y, other.Y)
||
comparer.Equals(X, other.Y) && comparer.Equals(Y, other.X);
}
public override bool Equals(object? obj)
{
return Equals(obj as UnorderedPair<T>);
}
public override int GetHashCode()
{
unchecked
{
return
(X is null ? 0 : comparer.GetHashCode(X))
(Y is null ? 0 : comparer.GetHashCode(Y));
}
}
public static bool operator ==(UnorderedPair<T>? left, UnorderedPair<T>? right)
{
return Equals(left, right);
}
public static bool operator !=(UnorderedPair<T>? left, UnorderedPair<T>? right)
{
return !Equals(left, right);
}
}
#nullable disable