Description
An immutable keyed set is a readonly collection of elements without duplicates or null values having each of the elements linked to exactly one key.
Example
This simple example of an Exact Cover solution has a constraint set \$\{ 1,2,3,4,5,6,7 \}\$ covered by candidates \$\{ B,D,F \}\$.
- \$B: \{ 1,4 \}\$
- \$D: \{ 3,5,6 \}\$
- \$F: \{ 2,7 \}\$
This could be presented as an immutable keyed set. What's imperative is that each of the constraints \$X\$ only has 1 matching candidate \$S\$.
Usage
[TestMethod]
public void Usage()
{
IReadOnlyKeyedSet<char, int> set = new ImmutableKeyedSet<char, int>(Data());
var sb = new StringBuilder();
foreach (var entry in set)
{
sb.AppendLine($"{entry.Key}: {string.Join(",", entry)}");
}
var rendered = sb.ToString();
// B: 1,4
// D: 3,5,6
// F: 2,7
}
private static IEnumerable<KeyValuePair<char, IEnumerable<int>>> Data()
{
yield return new KeyValuePair<char, IEnumerable<int>>('B', new[] { 1, 4 });
yield return new KeyValuePair<char, IEnumerable<int>>('D', new[] { 3, 5, 6 });
yield return new KeyValuePair<char, IEnumerable<int>>('F', new[] { 2, 7 });
}
The purpose is to guard against an invalid set.
private static IEnumerable<KeyValuePair<char, IEnumerable<int>>> Data()
{
yield return new KeyValuePair<char, IEnumerable<int>>('B', new[] { 1, 2, 4 });
yield return new KeyValuePair<char, IEnumerable<int>>('D', new[] { 3, 5, 6 });
yield return new KeyValuePair<char, IEnumerable<int>>('F', new[] { 2, 7 });
}
The above should throw:
"Duplicate value 2 on key F and B"
Code
Interface IReadOnlyKeyedSet<TKey, TElement>
public interface IReadOnlyKeyedSet<TKey, TElement> : ILookup<TKey, TElement>
{
IEqualityComparer<TKey> KeyComparer { get; }
IEqualityComparer<TElement> ElementComparer { get; }
bool ContainsValue(TElement value);
bool TryGetValues(TKey key, out IEnumerable<TElement> values);
bool TryGetKey(TElement value, out TKey key);
}
Implementation ImmutableKeyedSet<TKey, TElement>
public class ImmutableKeyedSet<TKey, TElement> : IReadOnlyKeyedSet<TKey, TElement>
{
private readonly Dictionary<TKey, Bucket> buckets;
private readonly Dictionary<TElement, TKey> elements;
public ImmutableKeyedSet(
IEnumerable<KeyValuePair<TKey, IEnumerable<TElement>>> keyedSet,
IEqualityComparer<TKey> keyComparer = null,
IEqualityComparer<TElement> elementComparer = null)
{
KeyComparer = keyComparer ?? EqualityComparer<TKey>.Default;
ElementComparer = elementComparer ?? EqualityComparer<TElement>.Default;
buckets = new Dictionary<TKey, Bucket>(KeyComparer);
elements = new Dictionary<TElement, TKey>(ElementComparer);
Set(keyedSet ?? throw new ArgumentNullException(nameof(keyedSet)));
}
public IEqualityComparer<TKey> KeyComparer { get; }
public IEqualityComparer<TElement> ElementComparer { get; }
public IEnumerable<TElement> this[TKey key] => buckets[key];
public int Count => buckets.Count;
public bool Contains(TKey key) => buckets.ContainsKey(key);
public bool ContainsValue(TElement value) => elements.ContainsKey(value);
public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator()
=> buckets.Values.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
public bool TryGetValues(TKey key, out IEnumerable<TElement> values)
{
var bucket = FindBucketByKey(key);
values = bucket == null ? default : bucket.Values;
return bucket != null;
}
public bool TryGetKey(TElement value, out TKey key)
{
var bucket = FindBucketByValue(value);
key = bucket == null ? default : bucket.Key;
return bucket != null;
}
private Bucket FindBucketByValue(TElement value)
{
if (elements.TryGetValue(value, out var key))
{
return buckets[key];
}
return null;
}
private Bucket FindBucketByKey(TKey key)
{
if (buckets.TryGetValue(key, out var bucket))
{
return bucket;
}
return null;
}
private void Set(IEnumerable<KeyValuePair<TKey, IEnumerable<TElement>>> keyedSet)
{
foreach (var entry in keyedSet)
{
var key = entry.Key;
if (key == null) throw new ArgumentException("Key must be set");
var bucket = FindBucketByKey(key);
if (bucket != null)
{
throw new InvalidOperationException($"Duplicate key {key}");
}
bucket = new Bucket(key);
if (entry.Value == null) throw new ArgumentException("Value must be set");
var values = new HashSet<TElement>(entry.Value);
foreach (var value in values)
{
if (value == null) throw new ArgumentException(
"Value must not contain null");
var valueBucket = FindBucketByValue(value);
if (valueBucket != null)
{
throw new InvalidOperationException(
$"Duplicate value {value} on key {key} and {valueBucket.Key}");
}
bucket.Values.Add(value);
}
buckets.Add(key, bucket);
foreach (var value in values)
{
elements.Add(value, key);
}
}
}
class Bucket : IGrouping<TKey, TElement>
{
public TKey Key { get; }
public IEnumerator<TElement> GetEnumerator() => Values.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
internal ICollection<TElement> Values { get; }
internal Bucket(TKey key)
{
Key = key;
Values = new List<TElement>();
}
}
}
Questions
- Is this a useful type of collection?
- Is this collection implementing immutability correctly?
Contains
method should be renamedContainsKey
since (1) it callsbuckets.ContainsKey
and (2) there is also aContainsValue
method so the rename adds clarity. \$\endgroup\$